Constraint satisfaction problems, compactness and non-measurable sets

2025/08/20 by Claude Tardif, Tardif, Claude
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Algebra homomorphism #Axiom #Axiom of choice #Compact space #Constraint (computer-aided design) #Constraint Satisfaction and Optimization #Homomorphism #Set theory #Type (biology)

paper · pdf · doi:10.46298/lmcs-22(3:1)2026

published in Logical Methods in Computer Science Volume 22, Issue 3 (Logical Methods in Computer Science e.V.)

openalex created_date 2025/10/10 · openalex publication_date 2026/07/14 · openalex updated_date 2026/08/05

Abstract

A finite relational structure A is called compact if for any infinite relational structure B of the same type, the existence of a homomorphism from B to A is equivalent to the existence of homomorphisms from all finite substructures of B to A. We show that if A has width one, then the compactness of A can be proved in the axiom system of Zermelo and Fraenkel, but otherwise, the compactness of A implies the existence of non-measurable sets in 3-space.

Related

• A note on noncompact logics
• Combinatorial and model-theoretical principles related to regularity of ultrafilters and compactness of topological spaces. I
• Abstract Model Structures and Compactness Theorems
• Combinatorial and model-theoretical principles related to regularity of ultrafilters and compactness of topological spaces. II
• Characterizations of ℕ-compactness and realcompactness via ultrafilters in the absence of the axiom of choice