Remark 7.13 — compactness: a countable structure whose finite substructures map to a finite B maps to B
ProvedAlgebraicPCSP.BLP.remark_7_13compactnesshomomorphismsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1promise-csp
Let be a relational structure with a countable (possibly infinite) universe , and let be a similar structure with a finite universe. Suppose that for every finite set , the substructure of on maps homomorphically to . Then
In the proof of Theorem 7.9 this turns homomorphisms from the finite pieces of the countable structure into a single homomorphism .
Formalization Note A homomorphism from the substructure on is encoded as a map required to preserve only the tuples of whose entries all lie in ; its values off are irrelevant. The platform theorem PCSPBLPAff.Characterization.lemma_16 states the same conclusion without the countability hypothesis.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting
Formal statement
namespace AlgebraicPCSP.BLP
open PCSPBLPAff.Symmetric
/-- Remark 7.13 (arXiv:1811.00970v3, pp. 47–48), compactness for countable structures: let `𝕀`
be a structure with a countable (possibly infinite) universe and `𝔹` a similar finite structure.
If every finite substructure of `𝕀` maps homomorphically to `𝔹`, then `𝕀` maps homomorphically
to `𝔹`. A homomorphism from the substructure on a finite set `S` is encoded as a map `I → B`
that is required to preserve only the tuples of `𝕀` with all entries in `S`. -/
theorem remark_7_13 {τ : Type} {ar : τ → ℕ} {I B : Type} [Countable I] [Finite B]
(𝕀 : RelStruct τ ar I) (𝔹 : RelStruct τ ar B)
(hfin : ∀ S : Finset I, ∃ σ : I → B,
∀ R : τ, ∀ t ∈ 𝕀.rel R, (∀ k, t k ∈ S) → σ ∘ t ∈ 𝔹.rel R) :
∃ σ : I → B, IsHom 𝕀 𝔹 σ := by sorry
end AlgebraicPCSP.BLP
Source
L. Barto, J. Bulín, A. Krokhin, J. Opršal, Algebraic approach to promise constraint satisfaction, arXiv:1811.00970v3, pp. 47–48, Remark 7.13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.