Constraint satisfaction problems, compactness and non-measurable sets

This paper establishes that the compactness of a finite relational structure is provable within Zermelo-Fraenkel set theory if the structure has width one, but implies the existence of non-measurable sets in three-dimensional space otherwise.

The Gist

Here is an explanation of the paper "Constraint Satisfaction Problems, Compactness and Non-Measurable Sets" by Claude Tardif, translated into everyday language with creative analogies.

The Big Picture: A Bridge Between Puzzles and Reality

Imagine you are trying to solve a massive, infinite puzzle. You have a set of rules (like a Sudoku grid or a map coloring game) and an infinite number of pieces to fit together.

This paper explores a fascinating connection between three seemingly unrelated worlds:

1. Computer Science: How hard is it to solve a specific type of logic puzzle?
2. Mathematical Logic: What "rules of the universe" (axioms) do we need to prove that a solution exists?
3. Physics/Geometry: Can we cut and rearrange a ball of clay to create two balls out of one (the Banach-Tarski paradox)?

The author, Claude Tardif, discovers a perfect divide (a "dichotomy"). He shows that some puzzles are so simple that we can prove they have solutions using basic, common-sense math. But other, slightly more complex puzzles require us to accept the existence of "ghostly" mathematical objects that defy our understanding of volume and measurement.

---

The Core Concept: The "Compactness" Test

Let's start with the idea of Compactness.

Imagine you are a detective trying to solve a crime in a city with infinite neighborhoods. You can't check every single house at once. Instead, you check every finite neighborhood.

• The Rule: If you can find a solution (a suspect, a map, a coloring) for every single finite neighborhood, does that guarantee a solution for the entire infinite city?

In math, this is called the Compactness Theorem.

• The Good News: For many simple puzzles, the answer is "Yes." If every small piece fits, the whole picture fits.
• The Bad News: For some complex puzzles, the answer is "No"—unless you use a very powerful, controversial mathematical tool called the Axiom of Choice. This tool allows you to make infinite choices simultaneously, even if you can't describe how you made them.

The Two Types of Puzzles

Tardif classifies these puzzles (called "Constraint Satisfaction Problems" or CSPs) into two camps based on how "wide" or complex their rules are.

Camp 1: The "Tree" Puzzles (Width 1)

Think of these puzzles as a family tree or a simple branching path. There are no loops or complex cycles.

• The Analogy: Imagine a game where you just have to make sure your left shoe matches your right shoe. It's simple.
• The Math: These puzzles are "Width 1."
• The Result: If a puzzle is a "Tree Puzzle," you do not need any fancy, controversial math axioms to prove a solution exists. Basic math (ZF) is enough. You can construct the solution step-by-step, like following a recipe.

Camp 2: The "Maze" Puzzles (Width > 1)

These puzzles have loops, cycles, and complex interdependencies.

• The Analogy: Imagine a maze where the path you take in the first room changes the rules in the tenth room, which changes the rules in the first room again. It's a tangled web.
• The Math: These puzzles have "Width > 1."
• The Result: To prove a solution exists for these, you must use the Axiom of Choice. But Tardif goes even further. He proves that if you assume these complex puzzles always have solutions (Compactness), you are forced to accept the existence of Non-Measurable Sets.

The "Ghost" in the Machine: Non-Measurable Sets

What is a Non-Measurable Set?

Imagine you have a block of clay. You can measure its volume (say, 1 liter).

• Measurable: You can cut the clay into pieces, and the sum of the pieces equals the whole.
• Non-Measurable: Imagine a "ghost" piece of clay. It exists, but if you try to measure it, the math breaks. It has no volume. It's like a shadow that has weight but no size.

In standard math (without the Axiom of Choice), we assume all sets are "measurable" (they have a size). But if you accept the Axiom of Choice, you can prove these "ghost" sets exist.

Tardif's Big Discovery:
He built a specific, infinite "Banach-Tarski Graph" (a maze made of rotations in 3D space).

1. If you assume this graph has a solution (a valid coloring), you are forced to admit that ghost sets (non-measurable sets) exist in 3D space.
2. Conversely, if you assume no ghost sets exist (everything has a measurable size), then this graph cannot have a solution, even though every tiny piece of it does have a solution.

The "Banach-Tarski" Connection

The paper uses the famous Banach-Tarski Paradox as a tool.

• The Paradox: In 3D space, if you use the Axiom of Choice, you can cut a sphere into a few pieces, rearrange them, and create two spheres of the same size as the original. This is impossible in the real world because it violates the conservation of volume.
• The Paper's Twist: Tardif uses the logic of this paradox to build a graph. He shows that trying to color this graph is mathematically identical to trying to measure a "ghost" object.
  • If you can color the graph, you can measure the ghost.
  • If you can't measure the ghost (because you assume all sets are measurable), you can't color the graph.

The "Sudoku" Analogy

To make it concrete, imagine a Sudoku puzzle.

• Simple Sudoku (Width 1): You can solve it by looking at one row, then one column, and making logical deductions. You don't need to guess. This corresponds to the "Tree" puzzles. Math is happy; no ghosts needed.
• Impossible Sudoku (Width > 1): Imagine a Sudoku where the rules change based on a hidden, infinite pattern. To prove a solution exists, you have to say, "There must be a way to fill this, even if I can't write down the steps."
  • Tardif says: "If you believe that solution exists, you are also believing in the existence of mathematical objects that have no volume."

Why Does This Matter?

This paper connects Computer Science (how hard is the problem?) with Set Theory (what are the rules of reality?).

1. The Easy Problems: The puzzles that computers can solve quickly (Polynomial time) are the ones that don't require "ghost" math. They are "safe" and constructive.
2. The Hard Problems: The puzzles that are likely impossible for computers to solve quickly (NP-complete) are the ones that require the most powerful, controversial axioms. They are tied to the existence of non-measurable sets.

The Conclusion:
The universe of math has a "safety line."

• On one side, we have simple, solvable puzzles that fit within basic logic.
• On the other side, we have complex puzzles that force us to step into a world where volume doesn't make sense and "ghost" sets exist.

Tardif's work tells us that the boundary between "easy to solve" and "hard to solve" in computer science is exactly the same boundary as the one between "basic math" and "math that requires non-measurable sets."

Summary in One Sentence

If a logic puzzle is simple enough to be solved by a computer, you don't need to believe in "ghost" mathematical objects to prove it has a solution; but if the puzzle is complex enough to be hard for computers, proving it has a solution forces you to accept that "ghost" objects (non-measurable sets) exist in our 3D world.

Technical Summary

Here is a detailed technical summary of the paper "Constraint Satisfaction Problems, Compactness and Non-Measurable Sets" by Claude Tardif.

1. Problem Statement

The paper investigates the logical strength required to prove the compactness of finite relational structures within the context of Constraint Satisfaction Problems (CSPs).

• Definition of Compactness: 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$.
• The Core Question: While the Axiom of Choice (AC) implies that all finite structures are compact, the author asks: What is the minimal set-theoretic strength required to prove the compactness of a specific structure $A$?
• Context: The paper explores the dichotomy between structures where compactness is provable in ZF (Zermelo-Fraenkel set theory without Choice) and those where proving compactness necessitates stronger axioms, specifically those implying the existence of non-measurable sets in $\mathbb{R}^3$.

2. Methodology

The author employs a synthesis of Model Theory, Algebraic Combinatorics, and Measure Theory to establish a dichotomy.

• Polymorphisms and Width 1: The analysis relies on the algebraic properties of structures, specifically the existence of cyclic polymorphisms and totally symmetric polymorphisms.
  • A structure has width 1 (or tree duality) if CSP($A$) can be solved by a "consistency check" algorithm. This is equivalent to the existence of a homomorphism from a specific structure $U(A)$ (built from non-empty subsets of $V(A)$) to $A$.
• The Banach-Tarski Construction: To prove that non-width-1 structures require strong axioms, the author constructs a specific infinite digraph $T$ (a "Banach-Tarski graph") based on the Banach-Tarski paradox.
  • This graph is constructed using a free group of rotation matrices acting on the sphere $S^2$.
  • A structure $C$ is defined on the product of the vertices of $T$ and the universe of $U(A)$.
• Measure Theoretic Contradiction: The proof assumes the negation of the conclusion (i.e., that all sets in $\mathbb{R}^3$ are measurable) and attempts to construct a homomorphism from $C$ to $A$.
  • It utilizes an adaptation of the Steinhaus theorem regarding the measure of sets invariant under specific group actions.
  • The argument shows that if all sets are measurable, the constructed homomorphism forces a contradiction regarding the measure of specific subsets ("Fish" sets) derived from the group action.

3. Key Contributions

A. The Main Theorem (Theorem 1.2)

The paper establishes a precise dichotomy linking algorithmic complexity to set-theoretic axioms:

Theorem: Let $A$ be a relational structure.

• If $A$ has width 1, the statement "$A$ is compact" is provable in ZF (without the Axiom of Choice).
• If $A$ does not have width 1, then the statement "$A$ is compact" implies the existence of a non-measurable set in $\mathbb{R}^3$.

B. Connection to the Ultrafilter Axiom

The paper contextualizes its results within the hierarchy of set-theoretic axioms:

• The Ultrafilter Axiom (every filter extends to an ultrafilter) is equivalent to the compactness of all finite structures.
• Previous work (K´atay, T´oth, Vidny´anszky) showed that compactness of $A$ implies the Ultrafilter Axiom iff $A$ lacks a cyclic polymorphism.
• Tardif's result refines this: If $A$ lacks width 1 (a stronger condition than lacking cyclic polymorphisms), compactness implies not just the Ultrafilter Axiom, but specifically the existence of non-measurable sets in 3D space.

C. Algorithmic Complexity vs. Set Theory

The paper reinforces the connection between the Feder-Vardi Dichotomy Conjecture (now a theorem by Bulatov and Zhuk) and set theory:

• Tractable CSPs (Polynomial time): Correspond to structures with cyclic polymorphisms (specifically width 1). Their compactness is "simple" (provable in ZF).
• Intractable CSPs (NP-complete): Correspond to structures lacking these polymorphisms. Their compactness is "complex," requiring axioms that generate non-measurable sets.
• Significance: This suggests that the hypothesis $P \neq NP$ is supported by set theory; the "hardest" computational problems correspond to the "strongest" compactness axioms.

4. Results and Proofs

• Proof of ZF Compactness for Width 1: The author reiterates that if $A$ has width 1, the consistency check algorithm (which iteratively prunes possible values) stabilizes. Since the algorithm is constructive and finite, it does not require the Axiom of Choice to prove that a global homomorphism exists if all finite substructures admit one.
• Proof of Non-Measurability for Non-Width 1:
  1. Assume $A$ is compact and all sets in $\mathbb{R}^3$ are measurable.
  2. Construct the Banach-Tarski graph $T$ and the structure $C$.
  3. By compactness, a homomorphism $\phi: C \to A$ exists.
  4. This homomorphism induces functions $f_p$ on the sphere.
  5. Using Lemma 4.3 (an adaptation of Steinhaus), the author proves that if the sets defined by the discrepancy of these functions are measurable, they must have measure zero.
  6. However, the group action properties (density of fixed points) force the existence of a point $p$ where the function behaves in a way that contradicts the assumption that all sets are measurable.
  7. Conclusion: The assumption that all sets are measurable must be false; thus, non-measurable sets must exist.

5. Significance and Open Problems

• Theoretical Unification: The paper provides a profound link between computational complexity (tractability of CSPs), algebraic logic (polymorphisms), and foundational mathematics (axioms of choice and measure theory). It suggests that the difficulty of solving a CSP is intrinsically linked to the set-theoretic resources required to prove its compactness.
• Borel Structures: The paper notes that while the Banach-Tarski graph $T$ admits a 2-coloring (homomorphism to $K_2$) under the assumption of compactness, this coloring cannot be a Borel set. This aligns with Thornton's work showing that for width-1 structures, the existence of an arbitrary homomorphism from a Borel structure implies the existence of a Borel homomorphism.
• Open Problem (Problem 5.1): The author poses a question regarding the compactness of $n$-colorability for graphs. Specifically, does the statement "If all finite subgraphs of $G$ are 3-colorable, then $G$ is $n$-colorable" (for $n \ge 6$) imply the Ultrafilter Axiom? This remains open, though it is conjectured to be equivalent to the Ultrafilter Axiom, mirroring the complexity of coloring 3-colorable graphs with a finite number of colors.

In summary, Tardif demonstrates that the boundary between "easy" and "hard" constraint satisfaction problems is not just computational but logical: the "hard" problems are those whose fundamental properties (compactness) cannot be established without invoking axioms that lead to the existence of non-measurable sets.