Baker-Pixley theorem: C = Pol Inv_d C
ProvedFunctionAlgebras.baker_pixleyis a set; operations are maps (). is a clone: it contains all projections and is closed under composition . contains a -ary near-unanimity operation , i.e. for every position of , where . An -ary preserves if applying coordinatewise to any tuples of gives a tuple of ; is the set of -ary relations preserved by all members of . If is finite, then for every and every -ary operation : if and only if preserves every relation in . That is, .
import Definitions.Def_FunctionAlgebras_defs universe u
namespace FunctionAlgebras
variable {A : Type u}
/-- Lau, *Function Algebras on Finite Sets*, Part II, Theorem 8.3.1 (Baker–Pixley theorem;
Baker–Pixley 1975, Corollary 5.1). Let `C` be a clone on a finite set containing a `(d+1)`-ary
near-unanimity operation, `d ≥ 2`. Then `C = Pol Inv_d C`: an operation belongs to `C` if and
only if it preserves every `d`-ary invariant relation of `C`. -/
theorem baker_pixley [Finite A] (C : ∀ n : ℕ, Set ((Fin n → A) → A)) (hC : IsClone C) {d : ℕ}
(hd : 2 ≤ d) (m : (Fin (d + 1) → A) → A) (hm : m ∈ C (d + 1)) (hnu : IsNearUnanimity m)
(n : ℕ) (f : (Fin n → A) → A) :
f ∈ C n ↔ ∀ R ∈ Inv C d, Preserves f R := by sorry
end FunctionAlgebrasRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be a finite set, a family of operations on that contains all projections and is closed under composition, and . Assume satisfies for every position of and all . Then for every (including ) and every -ary operation : if and only if preserves every -ary relation that is preserved by all operations of all arities in (i.e. every ).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.