Constraint satisfaction problems, compactness and non-measurable sets
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.
Fields of Study & Subjects
Advanced Topology and Set Theory
Advanced Graph Theory Research
Constraint Satisfaction and Optimization
Publication details
- Journal / source
- Logical Methods in Computer Science
- Publisher
- Centre pour la Communication Scientifique Directe (CCSD)
- Volume
- Volume 22, Issue 3
- Publication date
- 14 July 2026
- Language
- EN