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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-26 Page: https://delphi.science/r/arxiv/2607.23891 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…