Constraint satisfaction problems, compactness and non-measurable sets
arXiv:2508.14838 · doi:10.46298/lmcs-22(3:1)2026
The paper investigates compactness of finite relational structures, proving that compactness is provable in ZF for structures of width one, while for other structures compactness would entail the existence of non‑measurable sets in three‑dimensional space.
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.