{"id":"arxiv/2609.33873","url":"https://arxiv.org/abs/2609.33873","tags":["math.LO"],"score":0,"title":"Compactness Principles for CSPs and the Axiom of Chocie","domain":"math.LO","source":"arxiv","authors":["Anthony Li","Ishin Shan","Matthew Snodgrass","Riley Thornton","Rui Zhou"],"reviews":0,"subject":"math.LO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-27","reactions":{}}