Compactness Principles for CSPs and the Axiom of Chocie

Abstract

We can associate a compactness principle $\mathcal K_{\mathcal{D}}$ to the Constraint Satisfaction Problem (CSP) with constraint library $\mathcal{D}$. These principles were studied by Kat\'ay, T\'oth, and Vidny\'anszky and by Rorabaugh, Tardif, and Wehlau. We expand their work comparing the strength of $K_{\mathcal{D}}$ for varying structures $\mathcal{D}$. We characterize the structures whose compactness principles are provable from ZF; these turn out to be the width-1 structures. We compare some important compactness principles, namely those of $2\text{SAT}$, $3\text{LIN}2$, and $K_2$, settling a question of Kat\'ay, T\'oth, and Vidny\'anszky. And, we find an infinite chain and an infinite anti-chain of compactness principles related to directed cycles and finite choice.