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áy, Tóth, and Vidnyánszky 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áy, Tóth, and Vidnyánszky. And, we find an infinite chain and an infinite anti-chain of compactness principles related to directed cycles and finite choice.