Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC

Banerjee, Amitayu

Commentationes Mathematicae Universitatis Carolinae, Tome 64 (2023) no. 2, pp. 137-159.

Résumé

In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles. $\circ$ $\mathcal{P}_{\rm lf,c}$ (Every locally finite connected graph has a maximal independent set). $\circ$ $\mathcal{P}_{\rm lc,c}$ (Every locally countable connected graph has a maximal independent set). $\circ$ CAC$^{\aleph_{\alpha}}_{1}$ (If in a partially ordered set all antichains are finite and all chains have size $\aleph_{\alpha}$, then the set has size $\aleph_{\alpha}$) if $\aleph_{\alpha}$ is regular. $\circ$ CWF (Every partially ordered set has a cofinal well-founded subset). $\circ$ $\mathcal{P}_{G,H_{2}} $ (For any infinite graph $ G=(V_{G}, E_{G}) $ and any finite graph $ H=(V_{H}, E_{H})$ on 2 vertices, if every finite subgraph of $G$ has a homomorphism into $H$, then so has $G$). $\circ$ If $ G=(V_{G},E_{G}) $ is a connected locally finite chordal graph, then there is an ordering ``$$" of $V_{G}$ such that $\{w v \colon \{w,v\} \in E_{G}\}$ is a clique for each $v\in V_{G}$.

Détail

DOI : 10.14712/1213-7243.2023.028

Classification : 03E25, 03E35, 05C69, 06A07
Keywords: variants of chain/antichain principle; graph homomorphism; maximal independent sets; cofinal well-founded subsets of partially ordered sets; axiom of choice; Fraenkel--Mostowski (FM) permutation models of ZFA + $\neg$ AC