Equivalences of promise compactness principles

Bertalan Bodor · 2026

Read Equivalences of promise compactness principles by Bertalan Bodor (2026) 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-2604-08365.txt.

Introduction

Bodor links a family of promise compactness claims to a classic set theory principle. For pairs of finite structures where the first maps homomorphically into the second, the claim runs as follows. A structure whose finite parts all map into the first must itself map into the second. When the pair lacks an Olšák polymorphism, Bodor shows, that claim matches the ultrafilter principle over ZF set theory. One payoff: a graph whose every finite part is 3 colorable and which admits a 5 coloring can in fact be 3 colored.

Catalog record

CREATORBertalan Bodor
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95289
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2604.08365

Browse the full library · About the Tower of Babel

Full text

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

Equivalences of promise compactness principles Bertalan Bodor 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 ( 𝔄 , 𝔅 ) 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šák polymorphism, then K ( 𝔄 , 𝔅 ) K_{(\mathfrak{A},\mathfrak{B})} is equivalent to the ultrafilter principle over ZF \operatorname{ZF} . This includes the statements K ( K 3 , K 5 ) K_{(K_{3},K_{5})} and K ( H 2 , H c ) K_{(H_{2},H_{c})} for all c ≥ 2 c\geq 2 where K n K_{n} denotes the clique of size n n and H k H_{k} denotes the ternary not-all-equal structure on a k k -element set. This means, for example, that in any ZF \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. 1. Introduction For a finite relational structure \mathfrak{A} we write K_{\mathfrak{A}} for the following statement. • For every relation structure \mathfrak{I} with the same signature as \mathfrak{A} if all finite substructures of \mathfrak{I} homomorphically map to \mathfrak{A} then so does \mathfrak{I} . We refer to the statement K_{\mathfrak{A}} as the compactness principle over \mathfrak{A} . Note that all statements K_{\mathfrak{A}} follow from the compactness theorem of propositional logic, and thus they are all theorems of \operatorname{ZFC} . In fact, we know that the compactness theorem (even for first-order logic), and thus all compactness principles K_{\mathfrak{A}} , follow already from the ultrafilter lemma which is strictly weaker than the axiom of choice [ Jec77 ] over \operatorname{ZF} . However, different compactness principles have different strengths in choiceless set theory. For instance, by a theorem of Läuchli [ Läu71 ] we know that K_{K_{3}} is in fact equivalent to the ultrafilter lemma over \operatorname{ZF} meaning that K_{K_{3}} is (one of) the strongest compactness principles. On the other hand, it is fairly easy to see that K_{K_{2}} is equivalent to \operatorname{AC}(2) , i.e., that axiom of choice for families of 2-element sets which is much weaker than the ultrafilter principle [ Jec77 ] . 1.1. CSPs and compactness principles For a relational structure \mathfrak{A} the CSP (constraint satisfaction problem) over \mathfrak{A} , denoted by \operatorname{CSP}(\mathfrak{A}) , is the computation problem where the input is any structure \mathfrak{I} with the same signature of \mathfrak{A} , and we need to decide whether \mathfrak{I} homomorphically maps to \mathfrak{A} . As has been observed at many places in the literature, the strength of K_{\mathfrak{A}} is closely related the computation complexity of the CSP over \mathfrak{A} ; in general the harder the CSP is over \mathfrak{A} the stronger the statement K_{\mathfrak{A}} seems to be [ RTW17 , KTV23 , Tar25 ] . For example \operatorname{CSP}(K_{3}) , i.e., 3-colourability of graphs, is \mathbf{NP} -complete whereas K_{K_{2}} , i.e., 2-colourability is polynomial time decidable. This observation can be formalized using the notion of primitive positive (or pp-) constructions : we say that a structure \mathfrak{A} pp-constructs a structure \mathfrak{B} if \mathfrak{B} is homomorphically equivalent to some pp-power of \mathfrak{A} [ BOP18 ] . One of the most important features of pp-constructions is that they give reductions between complexity of CSPs. More specifically, if \mathfrak{A} pp-constructs \mathfrak{B} then \operatorname{CSP}(\mathfrak{B}) polynomial time (in fact LOGSPACE) reduces to \operatorname{CSP}(\mathfrak{A}) [ BOP18 ] . Following the terminology of [ BPS25 ] we say that finite structure \mathfrak{A} is omniexpressive if it pp-constructs all finite structures. We know, for instance, that K_{3} is omniexpressive, and thus omniexpressivity is also equivalent to the pp-constructability of K_{3} . In particular, if \mathfrak{A} pp-constructs K_{3} then \operatorname{CSP}(\mathfrak{A}) is \mathbf{NP} -complete. On the other hand, it was shown independently by Bulatov [ Bul17 ] and Zhuk [ Zhu20 ] that all CSPs over not omniexpressive finite structures are solvable in polynomial time, thereby confirming the famous dichotomy conjecture by Feder and Vardi [ FV99 ] . As for compactness principles some analogous results were obtained in a recent work of Kátay, Tóth, and Vidnyánszky [ KTV23 ] . Here, it has been shown that if \mathfrak{A} pp-constructs \mathfrak{B} then K_{\mathfrak{A}} implies K_{\mathfrak{B}} . This implies immediately that all compactness principles over finite omniexpressive structures are equivalent to each other, and thus by the theorem of Läuchli, they are also equivalent to the ultrafilter lemma. On the other hand, we know if \mathfrak{A} is finite and not omniexpressive then K_{\mathfrak{A}} is strictly weaker than K_{K_{3}} . In fact, the following result is shown in the aforementioned paper. Theorem 1.1 ( [ KTV23 ] , Theorem 2.18) . There exists a model of \operatorname{ZF} where for a finite structure \mathfrak{A} the compactness principle K_{\mathfrak{A}} holds if and only if \mathfrak{A} is not omniexpressive. Note that combining the finite-domain CSP dichotomy theorem with Theorem 1.1 we obtain that \operatorname{CSP}(\mathfrak{A}) is \mathbf{NP} -hard if and only if K_{\mathfrak{A}} is equivalent to the ultrafilter lemma, unless \mathbf{P}=\mathbf{NP} . 1.2. Promise CSPs We call a pair of structures (\mathfrak{A},\mathfrak{B}) a promise template if \mathfrak{A} and \mathfrak{B} have the same signature and there is a homomorphism from \mathfrak{A} to \mathfrak{B} . A promise template (\mathfrak{A},\mathfrak{B}) is called finite if both \mathfrak{A} and \mathfrak{B} are finite. The promise CSP , or PCSP , over a finite promise template (\mathfrak{A},\mathfrak{B}) , denoted by \operatorname{PCSP}(\mathfrak{A},\mathfrak{B}) , is the decision problem where for an input \mathfrak{I} with the same signature as \mathfrak{A} (or \mathfrak{B}) we need to output • YES if \mathfrak{I} homomorphically maps to \mathfrak{A} , and • NO if \mathfrak{I} does not homomorphically map to \mathfrak{B} . The “promise” in this setting is that we are given an input where one of the two cases above holds. Note that in this notation \operatorname{CSP}(\mathfrak{A}) is the same as \operatorname{PCSP}(\mathfrak{A},\mathfrak{A}) . The notion of promise PCSPs was introduced in [ AGH17 ] , although some variations, such as approximate graph colourings (i.e., PCSPs over (K_{k},K_{c}) ) already appeared earlier in the literature [ GJ76 , DRS05 , GK04 , Hua13 , BG16 ] . As it turns out, pp-constructions, and thus also omniexpressivity, can be generalized to promise templates, and they still imply complexity reductions in the same way [ BBKO21 ] . For example, it follows from the results of [ BG16 ] that (K_{k},K_{2k-2}) is omniexpressive for all k\geq 3 , and therefore \operatorname{PCSP}(K_{k},K_{2k-2}) is \mathbf{NP} -complete. However, as opposed to finite-domain CSPs, there are many non-omniexpressive finite promise templates which are known to have hard PCSPs. Some notable examples are • (K_{k},K_{2k-1}) for k\geq 3 [ BBKO21 ] , • (K_{k},K_{c}) where k\geq 4 and c={k\choose\lfloor k/2\rfloor}-1 [ KOWŽ23 ] , • (C_{2k+1},K_{4}) for k\geq 1 where C_{\ell} denotes the cycle of length \ell [ AFO+25 ] , and • (H_{2},H_{c}) for c\leq 2 where H_{k} denotes the structures on a k -element set with a single ternary not-all-equal relation [ DRS05 ] . Further hardness results have been shown in [ AGH17 , FNO+23 ]

Read the complete text