{"id":"arxiv/2607.23891","url":"https://arxiv.org/abs/2607.23891","tags":["math.LO","math.CO"],"score":0,"title":"Frucht's theorem and other set-theoretic principles below the axiom of choice and the axiom of foundation","domain":"math.LO","source":"arxiv","authors":["Junhong Chen","Daheng Ju"],"reviews":0,"subject":"math.LO","summary":"We take the first step toward the study of set-theoretic principles below the axiom of choice $\\mathsf{AC}$ and the axiom of foundation $\\mathsf{AF}$ by studying Frucht's theorem, an ordinary mathematical theorem which is provable with either $\\mathsf{AC}$ or $\\mathsf{AF}$ but not provable without both, and its variants. Specifically, we propose a number of such principles, study the relations between these principles and the standard axioms, and prove provability and unprovability results using (infinite) graph-theoretic constructions and permutation models, which draw a preliminary map of…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-26","reactions":{}}