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.

@article{paperbot3971,
  title = {Constraint satisfaction problems, compactness and non-measurable sets},
  author = {Claude Tardif},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 22, Issue 3},
  year = {2026},
  doi = {10.46298/lmcs-22(3:1)2026}
}