Constraint satisfaction problems, compactness and non-measurable sets

Claude Tardif ORCID:0000-0003-3855-989X · 2025

Read Constraint satisfaction problems, compactness and non-measurable sets by Claude Tardif ORCID:0000-0003-3855-989X (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-14838.txt.

Introduction

Claude Tardif links a compactness trait of constraint problems to deep questions in set theory, in work from twenty twenty-five. A finite structure counts as compact when maps from any infinite structure into it can be checked on finite parts alone. Whether such claims need strong axioms was open.

Tardif shows the answer turns on a trait called width. For width one structures, compactness can be proved inside the standard axiom system of Zermelo and Fraenkel, with no extra assumptions. For all other cases, compactness forces the existence of non measurable sets in three dimensional space. Those sets cannot arise from the basic axioms alone. The result ties a computer science notion to the foundations of measure.

Catalog record

CREATORClaude Tardif ORCID:0000-0003-3855-989X
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-14838

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Constraint satisfaction problems, compactness and non-measurable sets Claude Tardif ORCID:0000-0003-3855-989X Abstract . A finite relational structure A A is called compact if for any infinite relational structure B B of the same type, the existence of a homomorphism from B B to A A is equivalent to the existence of homomorphisms from all finite substructures of B B to A A . We show that if A A has width one, then the compactness of A A can be proved in the axiom system of Zermelo and Fraenkel, but otherwise, the compactness of A A implies the existence of non-measurable sets in 3 3 -space. 1. Introduction A graph is bipartite if and only if does not contain an odd cycle. Already in 1916, König [ Kön16 ] acknowledged that this theorem requires the axiom of choice for the infinite case. One of the two possible colourings must be selected for each connected component. Later in 1961, Mycielski [ Myc61 ] proved that in the infinite case, König’s theorem is precisely equivalent to the axiom of choice for sets of pairs. Now, consider the statement that a digraph admits a homomorphism to the transitive tournament T_{2} on two vertices if and only if it admits no homomorphism from the directed path P_{2} with two consecutive arcs. Even in the infinite case, it requires no version of the axiom of choice. Indeed, if there are no homomorphic images of P_{2} , every vertex is a source or a sink, possibly both, and we can define a homomorphism to T_{2} by mapping all sources to the source of T_{2} and all other vertices to the sink. A finite relational structure A is called compact if the existence of a homomorphism from a structure B to A is equivalent to the existence of homomorphisms from all finite substructures of B to A . The axiom of choice implies the all-encompassing compactness theorem, which implies that every finite relational structure is compact. More precisely, the compactness theorem is equivalent to the ultrafilter axiom, which states that any filter on a set can be extended to an ultrafilter. It is weaker than the axiom of choice. In graph theory, the compactness of the complete graphs is called the de Bruijn-Erdős theorem, after the 1951 result of de Bruijn and Erdős [ dBE51 ] . Later in 1971, Läuchli [ Läu71 ] proved that for any n\geq 3 , the compactness of the complete graph K_{n} already implies the ultrafilter axiom. Thus, viewed as an axiom, the statement “ K_{3} is compact” is stronger than “ K_{2} is compact”, and it is at least as strong as “ A is compact” for any finite relational structure A . Recently, the following generalisation of Läuchli’s result was obtained by Kátay, Tóth, and Vidnyánszky. Theorem 1 ( [ KTV24 ] ) . Let A be a finite relational structure. Then the compactness of A implies the ultrafilter axiom if and only A does not admit a cyclic polymorphism. The “cyclic polymorphisms” involved will be defined in Section 2 . They provide the criterion separating the simple from the complex in the dichotomy of constraint satisfaction problems. For a given relational structure A , the corresponding constraint satisfaction problem \mbox{CSP}(A) is the problem of deciding whether an input structure B admits a homomorphism to A . Bulatov [ Bul17 ] and Zhuk [ Zhu20 ] independently proved that \mbox{CSP}(A) is polynomial if A admits a cyclic polymorphism, and NP-complete otherwise. This dichotomy between tractable and intractable constraint satisfaction problems is the one that had been conjectured by Feder and Vardi [ FV99 ] . Note that in the context of algorithmic complexity, this is a conditional dichotomy, as it relies on the hypothesis \mbox{NP}\neq\mbox{P} which is not proved. However, the dichotomy of Theorem 1 is unconditional. Thus the set-theoretic setting supports the hypothesis \mbox{NP}\neq\mbox{P} ; the constraint satisfaction problems that are hypothetically hardest correspond precisely to the compactness axioms that are provably the most general. Now at the bottom end of the hierarchy, we find T_{2} , whose compactness does not rely on any axiom outside of ZF, the axiom system of Zermelo and Fraenkel. The constraint satisfaction problem \mbox{CSP}(T_{2}) is polynomial, and more precisely, it can be solved by the “consistency check” algorithm which will be presented in Section 2 . The consistency check algorithm is arguably the simplest algorithm for constraint satisfaction, as it is rediscovered by many Sudoku puzzle solvers with no background in computer science. A relational structure A is said to have “width 1 ” or “tree duality” if \mbox{CSP}(A) can be solved by the consistency check algorithm. In [ RTW17 ] , it is shown that if A has width 1 , then the statement “ A is compact” can be proved in ZF without any additional axiom. Once again this is a correspondence between algorithmic complexity and set theory, connecting some of the simplest constraint satisfaction problems with some of the simplest compactness results. Here we complete this correspondence as follows. Theorem 2 . Let A be a relational structure. If A does not have width 1 , then the axiom “ A is compact” implies the existence of a non-measurable set in \mathbb{R}^{3} . This is a dichotomy, with the structures of width 1 corresponding precisely to the compactness properties provable in ZF. We provide the relevant terminology in Section 2 . Section 3 provides a background in measure theory and its use here. We then give the proof of Theorem 2 in Section 4 and conclude with an open problem. 2. Terminology A type is a finite set \sigma=\{R_{1},\dots,R_{m}\} of relation symbols, each with an arity r(i) assigned to it. A relational structure of type \sigma is a (m+1) -tuple A=(V(A);R_{1}(A),\dots,R_{m}(A)) where V(A) is a nonempty set called the universe of A , and R_{i}(A) is an r(i) -ary relation on V(A) for each i . Let A and B be \sigma -structures, a homomorphism from B to A is a map \phi:V(B)\rightarrow V(A) such that \phi(R_{i}(B))\subseteq R_{i}(A) for all i=1,\dots,m . If V(B) is a subset of V(A) and the identity is a homomorphism from B to A , then B is called a substructure of A . The constraint satisfaction problem \mbox{CSP}(A) is the problem of determining whether an input structure B admits a homomorphism to A . The n -th power A^{n} of A has V(A)^{n} as universe, and for R_{i}\in\sigma , R_{i}(A^{n}) consists of all the r(i) -tuples (f_{1},\ldots,f_{r(i)}) such that for all j , (f_{1}(j),\ldots,f_{r(i)}(j))\in R_{i}(A) . (Note that an element of V(A)^{n} can be represented either as a function f:\{1,\ldots,n\}\rightarrow V(A) as above, or as an array (a_{1},\ldots,a_{n}) .) A polymorphism of arity n is a homomorphism \phi:A^{n}\rightarrow A . It is cyclic if it satisfies \phi(a_{1},\ldots,a_{n})=\phi(a_{2},\ldots,a_{n},a_{1}) . The existence of a cyclic polymorphism on A is the criterion used in Theorem 1 . Here we focus on structures that have totally symmetric polymorphisms of all arities, that is polymorphisms \phi:A^{n}\rightarrow A that satisfy \phi_{n}(f)=\phi_{n}(g) whenever f(\{1,\ldots,n\})=g(\{1,\ldots,n\}) . The existence of totally symmetric polymorphisms of all arities on A is equivalent to the existence of a single homomorphism \omega:\mathcal{U}(A)\rightarrow A , where \mathcal{U}(A) is

Read the complete text