Equivalences of promise compactness principles
Pith reviewed 2026-05-10 16:55 UTC · model grok-4.3
The pith
When a pair of finite structures lacks an Olšák polymorphism, its promise compactness principle is equivalent to the ultrafilter principle over ZF.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
If (A, B) is a pair of finite relational structures with a homomorphism from A to B and no Olšák polymorphism, then over ZF the statement K_(A,B) is equivalent to the ultrafilter principle. The statement K_(A,B) asserts that for every structure I with the same signature, if every finite substructure of I homomorphically maps to A then I homomorphically maps to B. In particular this equivalence holds for the pairs (K3, K5) and (H2, Hc) with c at least 2.
What carries the argument
The absence of an Olšák polymorphism on the pair (A, B), which serves as the condition allowing the compactness principle K_(A,B) to be shown equivalent to the ultrafilter principle.
If this is right
- K_(K3, K5) holds if and only if the ultrafilter principle holds over ZF.
- K_(H2, Hc) holds for each c at least 2 if and only if the ultrafilter principle holds over ZF.
- If the ultrafilter principle fails in a ZF model then for such pairs there exists a structure I where every finite substructure maps homomorphically to A but I itself does not map to B.
- The equivalence supplies a uniform algebraic criterion for when a homomorphism compactness statement is equivalent to the ultrafilter principle.
Where Pith is reading between the lines
- The presence or absence of specific polymorphisms may classify which other compactness statements in combinatorics are provable in ZF alone.
- Analogous equivalences could apply to further relational structures arising in constraint satisfaction beyond the clique and not-all-equal cases treated here.
- These results link infinite homomorphism problems directly to the existence of ultrafilters, suggesting a broader dictionary between algebraic conditions and choice axioms.
Load-bearing premise
The pair (A, B) has no Olšák polymorphism while still admitting a homomorphism from A to B.
What would settle it
A model of ZF set theory in which the ultrafilter principle fails but K_(K3, K5) still holds would falsify the claimed equivalence.
read the original abstract
For a pair of finite relational structures $(\mathfrak{A},\mathfrak{B})$ such that $\mathfrak{A}$ homomorphically maps to $\mathfrak{B}$ we denote by $K_{(\mathfrak{A},\mathfrak{B})}$ the following statement: for all structures $\mathfrak{I}$ with the same signature as $\mathfrak{A}$ if all finite substructures of $\mathfrak{I}$ homomorphically maps to $\mathfrak{A}$ then $\mathfrak{I}$ homomorphically maps to $\mathfrak{B}$. In this article, we show that if $(\mathfrak{A},\mathfrak{B})$ has no Ol\v{s}\'{a}k polymorphism, then $K_{(\mathfrak{A},\mathfrak{B})}$ is equivalent to the ultrafilter principle over $\operatorname{ZF}$. This includes the statements $K_{(K_3,K_5)}$ and $K_{(H_2,H_c)}$ for all $c\geq 2$ where $K_n$ denotes the clique of size $n$ and $H_k$ denotes the ternary not-all-equal structure on a $k$-element set. This means, for example, that in any $\operatorname{ZF}$ model, if every finitely 3-colourable graph can be coloured by 5 colours then all these graphs can in fact be coloured by 3 colours.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that for finite relational structures 𝔄 and 𝔅 with a homomorphism from 𝔄 to 𝔅 and no Olšák polymorphism, the promise compactness principle K_{(𝔄,𝔅)} is equivalent over ZF to the ultrafilter principle. Concrete instances include K_{(K_3,K_5)} and K_{(H_2,H_c)} for c≥2, with the forward direction holding generally and the reverse obtained via the algebraic condition on polymorphisms.
Significance. If correct, the result supplies an algebraic criterion (absence of Olšák polymorphism) that characterizes when certain homomorphism compactness statements are equivalent to the ultrafilter principle in ZF. It yields concrete equivalences for graph coloring and not-all-equal structures, clarifying the set-theoretic strength of promise problems without choice and connecting polymorphism theory to compactness principles.
minor comments (3)
- [Abstract] Abstract, line 3: the phrase 'all finite substructures of 𝔄 homomorphically maps to 𝔄' contains a grammatical error ('maps' should be 'map'); this recurs in the statement of K_{(𝔄,𝔅)} and should be corrected for precision.
- [Introduction] The paper would benefit from an explicit statement of the two directions of the equivalence (K ⇒ UP and UP ⇒ K) in a single theorem, with the algebraic precondition isolated; currently the reverse direction is only sketched via the no-Olšák condition.
- [Section 2] Notation for the structures K_n and H_k is introduced in the abstract but not recalled with a formal definition before the examples; a short preliminary section or paragraph defining cliques and the not-all-equal relation would improve readability.
Simulated Author's Rebuttal
We thank the referee for the positive assessment of our manuscript, the accurate summary of the main results, and the recommendation of minor revision. The referee's description correctly captures the algebraic condition (absence of Olšák polymorphisms) and the resulting equivalences to the ultrafilter principle, including the concrete cases for graph coloring and not-all-equal structures.
Circularity Check
No significant circularity; direct ZF equivalence proof
full rationale
The paper establishes an equivalence K_{(A,B)} ⇔ ultrafilter principle in ZF whenever (A,B) satisfies the algebraic precondition of having no Olšák polymorphism (with A → B). This is a standard model-theoretic reduction using the definitions of homomorphisms, polymorphisms, and finite relational structures; no step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation. The concrete instances (K_{(K3,K5)}, K_{(H2,Hc)}) are immediate corollaries of the general theorem rather than independent derivations that loop back to the inputs. The argument is self-contained against external ZF benchmarks and does not rename known results or smuggle ansatzes via citation.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math ZF set theory (Zermelo-Fraenkel without choice)
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.