Closure of subpowers versus local interpolation
OpenFunctionAlgebras.closure_iff_interpolationis a set; operations are maps (). is a clone: it contains all projections and is closed under composition . 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 . Let and let be a partial -ary function with domain . For an matrix (rows in , columns in ), applies to each column. The following are equivalent: (a) every is closed under (for every with rows in and columns in , ); (b) for every with columns in , lies in the row space of (the intersection of all containing the rows of ); (c) for every with at most elements some agrees with on .
import Definitions.Def_FunctionAlgebras_defs universe u
namespace FunctionAlgebras
variable {A : Type u}
/-- Baker–Pixley (1975), Lemma 3.1, for the clone `C` of term operations ("polynomials") of an
algebra on `A` (Lau, proof of Theorem 8.3.1, step I). Let `n, k > 0` and let `f` be a partial
`n`-ary function with domain `D`. An `n × k` matrix `M` has rows `M j ∈ A^k` and columns
`(fun j => M j i) ∈ A^n`. The following are equivalent:
(a) every `k`-ary invariant relation of `C` (subuniverse of `A^k`) is closed under `f` where `f`
is defined;
(b) for every `n × k` matrix `M` whose columns lie in `D`, the row vector `f(M)` lies in the row
space of `M` (the subuniverse of `A^k` generated by the rows of `M`);
(c) the restriction of `f` to any `k` or fewer points of its domain is interpolated by a member
of `C n`. -/
theorem closure_iff_interpolation (C : ∀ n : ℕ, Set ((Fin n → A) → A)) (hC : IsClone C)
{n k : ℕ} (hn : 0 < n) (hk : 0 < k) (f : (Fin n → A) → A) (D : Set (Fin n → A)) :
List.TFAE
[∀ R ∈ Inv C k, ∀ M : Fin n → Fin k → A, (∀ j, M j ∈ R) →
(∀ i, (fun j => M j i) ∈ D) → (fun i => f (fun j => M j i)) ∈ R,
∀ M : Fin n → Fin k → A, (∀ i, (fun j => M j i) ∈ D) →
(fun i => f (fun j => M j i)) ∈ ⋂₀ {R | R ∈ Inv C k ∧ ∀ j, M j ∈ R},
∀ E : Finset (Fin n → A), (↑E : Set (Fin n → A)) ⊆ D → E.card ≤ k →
Interpolates C f ↑E] := by sorry
end FunctionAlgebrasRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be a family of operations on ( arbitrary, not assumed finite) containing all projections and closed under composition, let , let be any total -ary function and any set of points. For an matrix over write for its rows () and for its columns (); let . The following three statements are claimed equivalent:
- for every and every with all rows and all columns , we have ;
- for every with all columns in , lies in the intersection of all that contain all rows ;
- for every finite with at most elements there is with for all .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.