Lemma 16 (compactness for structures), p. 15 — if every finite induced substructure of F maps to a finite B, so does F
ProvedPCSPBLPAff.Characterization.lemma_16Let and be relational structures with the same signature, on domains and , with finite. Suppose that for every finite subset , the substructure of induced on admits a homomorphism to . Then admits a homomorphism to :
This generalization of the de Bruijn–Erdős theorem turns the instance-wise condition of Observation 15 into the single homomorphism .
Formalization Note A homomorphism from is encoded as a map that is required to preserve only the tuples of with all entries in ; its values off are irrelevant. The page's hypothesis that is infinite is dropped: for finite the statement is immediate (take ), and the generalization lets the lemma apply to every free structure, including the empty one.
import Mathlib import Definitions.Def_PCSPBLPAff_Characterization_Setting
namespace PCSPBLPAff.Characterization
/-- Lemma 16 (compactness for structures), p. 15: if `𝔹` is finite and every finite induced
substructure of `𝔽` admits a homomorphism to `𝔹`, then so does `𝔽`. A homomorphism from the
substructure induced on a finite set `S` is encoded as a map `D → B` that is checked only on
the tuples with all entries in `S`. -/
theorem lemma_16 {τ : Type} {ar : τ → ℕ} {D B : Type} [Finite B]
(𝔽 : PCSPBLPAff.Symmetric.RelStruct τ ar D) (𝔹 : PCSPBLPAff.Symmetric.RelStruct τ ar B)
(h : ∀ S : Finset D, ∃ σ : D → B,
∀ R : τ, ∀ t ∈ 𝔽.rel R, (∀ k, t k ∈ S) → σ ∘ t ∈ 𝔹.rel R) :
∃ σ : D → B, PCSPBLPAff.Symmetric.IsHom 𝔽 𝔹 σ := by sorry
end PCSPBLPAff.Characterization
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.