Algebra Seminar talk
2025-10-17
Alexander Zach
pp-Constructability and Logical Compactness: Bridging CSP Hardness and Set-Theoretic Axioms
Abstract:
We study the relative strength of compactness axioms for finite relational structures when added to ZF. We use pp-constructability, a commonly employed concept in the study of Constraint Satisfaction Problems (CSPs). Analogous to the CSP-dichotomy, we show that if a structure pp-constructs K_3 (i.e., the related CSP is NP-complete), then its compactness axiom is equivalent to the Ultrafilter Lemma. In contrast, one can show that if a structure does not pp-construct K_3, its compactness axiom holds in ZF and is therefore strictly weaker.