Abstract

We work with models of set theory where the Axiom of choice (AC) can consistently fail. We use the following theories.

• ZF (Zermelo–Fraenkel set theory without AC).
• ZFA (ZF with the axiom of extensionality weakened to allow the existence of atoms).

A weak choice principle W is a statement which satisfies the following properties: W is true in ZFC, W is not true in ZF (similarly ZFA), and ZF+W (similarly ZFA+W) does not imply AC. (I enclose a link of Ioanna Dimitriou's `Choiceless Grapher Project': A diagram creator for the hierarchy of weak choice principles connected to Howard–Rubin's `Consequences of the Axiom of Choice' book, bluehttps://cgraph.inters.co/).

Firstly, we study new relations of different combinatorial statements with weak choice principles in ZF and ZFA.

1. Variants of Chain/Antichain principle. A famous application of the infinite Ramsey's theorem (a weak choice principle) is the Chain/Antichain principle (abbreviated here as CAC), which states that `Any infinite partially ordered set contains either an infinite chain or an infinite antichain'. In 2016, Tachtsis investigated the possible placement of CAC in the hierarchy of weak choice principles.<sup>1</sup> Komjath–Totik (bluehttps://2n6pw521j10.blob.core.windows.net/2n6pw521j10/MTQ0MTkyMTQwMA==.pdf) proved the following variants of CAC, applying Zorn's lemma (which is equivalent to AC in ZF):
   • blue`If in a partially ordered set all antichains are finite and all chains are countable, then the set is countable'.
   • blue`If in a partially ordered set all chains are finite and all antichains are countable, then the set is countable'.
   We study the relations of weak choice principles and the above variants of CAC in ZF and ZFA (bluehttps://arxiv.org/abs/2009.05368.pdf, https://arxiv.org/pdf/1911.00434.pdf).

2. Chromatic number of the product of graphs. In 1985, Andras Hajnal applied the Compactness theorem for propositional logic (equivalent to the Ultrafilter lemma (UL) in ZF, a weak choice principle) to prove the statement blue`If the chromatic number of a graph $G_{1}$ is finite (say a natural number $k$), and the chromatic number of another graph $G_{2}$ is infinite, then the chromatic number of the product of $G_{1}$ and $G_{2}$ is $k$'.² The author and Zalan Gyenis observed that if $k=3$, then the above statement does not imply the axiom of choice restricted to 3 element sets in ZFA (and consequently does not imply UL in ZFA) (bluehttps://arxiv.org/pdf/1911.00434.pdf). We will see two open problems in this area.

3. Maximal Independent sets. In 2011, Harvey M. Friedman sketched a proof of the fact that AC is equivalent to the statement blue`Every graph has a maximal independent set' in ZF. We study new relations of weak choice principles and weaker versions of the above statement in ZF (bluehttps://arxiv.org/abs/2009.05368.pdf).

4. Cofinal subsets of posets. It is well known that AC implies the following statements.
   • blue`Every partially ordered set has a cofinal well-founded subset' (we abbreviate by CWF).
   • blue`Every partially ordered set without a maximal element has two disjoint cofinal subsets' (we abbreviate by CS).
   In 2016, Howard, Saveliev, and Tachtsis investigated the possible placement of CS in the hierarchy of weak choice principles. In 2017, Tachtsis investigated the possible placement of CWF in the hierarchy of weak choice principles. We study the new relations of CWF and CS with weak choice principles (bluehttps://arxiv.org/abs/2009.05368.pdf). We will also see some open problems in this area.

5. Dilworth's theorem. In 1950, Dilworth proved the statement blue`If $\mathbb{P}$ is an arbitrary poset, and $k$ is a natural number such that $\mathbb{P}$ has no antichains of size $k + 1$ while at least one $k$-element subset of $\mathbb{P}$ is an antichain, then $\mathbb{P}$ can be partitioned into $k$ chains' (we abbreviate by DT) using Teichmüller–Tukey Lemma (which is equivalent to AC in ZF). It is well-known that a proof of DT can be achieved by the $n$-coloring Theorem due to De Bruijn and Erdős (we note that the $n$-coloring theorem is a weak choice principle) for any integer $n$ greater than or equal to 3. In 2019, Tachtsis investigated the possible placement of DT in the hierarchy of weak choice principles. We study new relations of DT with weak choice principles (bluehttps://arxiv.org/pdf/1911.00434.pdf). We will see some open problems in this area.

6. A weaker form of Łoś's lemma. We recall the following weaker form of Łoś's lemma: blue`If $\mathcal{A}=\langle A, \mathcal{R}^{\mathcal{A}}\rangle$ is a non-trivial relational $\mathcal{L}$-structure over some language $\mathcal{L}$, and $\mathcal{U}$ be an ultrafilter on a non-empty set $I$, then the ultrapower $\mathcal{A}^{I}/\mathcal{U}$ and $\mathcal{A}$ are elementarily equivalent' (we abbreviate by LT). In 1975, Howard proved that LT + UL implies AC in ZF. In 2019, Tachtsis investigated the possible placement of LT in the hierarchy of weak choice principles. We study new relations of LT with weak choice principles (bluehttps://arxiv.org/pdf/1911.00434.pdf).

7. A graph homomorphism problem. Komjáth sketched a proof of the following generalization of the $n$-coloring Theorem due to De Bruijn and Erdős: blue`For any infinite graph $G=(V_{G}, E_{G})$ and any finite graph $H=(V_{H}, E_{H})$, if every finite subgraph of $G$ has a homomorphism into $H$, then so has $G$' abbreviated here as $\mathcal{P}_{G,H}$. We study new relations of $\mathcal{P}_{G,H}$ with weak choice principles.

2. Secondly, we study the status of Dependent Choice (a weak choice principle, abbreviated here as DC) and combinatorial properties in different symmetric extensions. We recall that symmetric extensions of the ground model $V$ are symmetric submodels of the forcing extension $V[G]$ (with respect to a generic filter $G$) containing the ground model $V$, where AC can consistently fail. We also recall that a symmetric extension of $V$ (denoted by $V(G)$) can be built up with respect to a forcing notion $\mathbb{P}$, a group of permutations $\mathcal{G}$ of $\mathbb{P}$, and a normal filter $\mathcal{F}$ of subgroups over $\mathcal{G}$. In such cases, we say that the symmetric extension is defined with respect to the tuple $\langle \mathbb{P},\mathcal{G},\mathcal{F}\rangle$ (we say symmetric system).

1. Preserving Dependent Choice. DC is equivalent to the Baire Category Theorem (which is a fundamental theorem in functional analysis), and other important theorems like the countable version of the Downward Löweinheim–Skolem theorem in ZF. On the other hand, AC has controversial applications like the existence of a non-Lebesgue measurable set of real numbers, Banach–Tarski Paradox, and the existence of a well-ordering of real numbers whereas DC does not have such counterintuitive consequences. In particular, DC is consistent with assumptions such as `All sets of reals are regular' for different versions of regularity (for example Lesbegue measurability). Thus it is often desirable to preserve DC in symmetric extensions.

   $DC_{\kappa}$ for an infinite well-ordered cardinal $\kappa$: Let $\kappa$ be an infinite well-ordered cardinal (i.e., $\kappa$ is an aleph). Let $S$ be a non-empty set and let $R$ be a binary relation such that for e$V$ery $\alpha<\kappa$ and every $\alpha$-sequence $s =(s_{\epsilon})_{\epsilon<\alpha}$ of elements of $S$ there exists $y \in S$ such that $s R y$. Then there is a function $f : \kappa \rightarrow S$ such that for every $\alpha<\kappa$, $(f\restriction \alpha) R f(\alpha)$.

   We note that $DC_{\aleph_{0}}$ is a reformulation of DC. We denote by $DC_{<\lambda}$ the assertion $(\forall\eta < \lambda)DC_{\eta}$. Moreover, $DC_{\lambda}$ implies $DC_{\kappa}$ if $\lambda>\kappa$ in ZF.

   In 2014, Asaf Karagila proved that if $V$ is a model of ZFC, $\mathbb{P}$ is a $\kappa$-closed notion of forcing, and $\mathcal{F}$ is $\kappa$-complete then $DC_{<\kappa}$ is preserved in the symmetric extension of $V$ in terms of symmetric system $\langle \mathbb{P},\mathcal{G},\mathcal{F}\rangle$. Let $V$ be a model of ZFC. Karagila wrote that if $\mathbb{P}$ is $\kappa$-c.c. and $\mathcal{F}$ is $\kappa$-complete, then $DC_{<\kappa}$ is preserved in the symmetric extension of $V$ in terms of symmetric system $\langle \mathbb{P},\mathcal{G},\mathcal{F}\rangle$.³ Moreover, the author and Karagila used the later result to answer a question of Apter (see bluehttps://www.impan.pl/pl/wydawnictwa/czasopisma-i-serie-wydawnicze/bulletin-polish-acad-sci-math/all/67/1/112842/preserving-dependent-choice). We observe the following inspired by the first result of Karagila.

   1. Let $V$ be a model of ZFC. blue If $\mathbb{P}$ is $\kappa$-distributive and $\mathcal{F}$ is $\kappa$-complete, then $DC_{<\kappa}$ is preserved in the symmetric extension of $V$ in terms of symmetric system $\langle \mathbb{P},\mathcal{G},\mathcal{F}\rangle$ (bluehttps://arxiv.org/abs/1903.05945v3).

   2. We also study that even if we start with a model $V$, which is a model of ZF + $DC_{\kappa}$ where AC can consistently fail, then we can still preserve $DC_{<\kappa}$ in a symmetric extension of $V$ in certain cases (bluehttps://arxiv.org/abs/1903.05945v3).

2. Proving Dimitriou's Conjecture. In 2011, Ioanna Dimitriou constructed a symmetric extension in her Ph.D. thesis. She conjectured that DC might fail in that model. We prove the conjecture (bluehttps://arxiv.org/abs/1903.05945v3).

3. Extending some results of Apter, Dimitriou, and Koepke. We carry forward a few research works of Apter, Dimitriou, and Koepke based on the behaviour of large cardinals in ZF (bluehttps://onlinelibrary.wiley.com/doi/abs/10.1002/malq.201800018). In particular, we observe that bluethe first supercompact cardinal can be the first uncountable regular cardinal in Gitik's symmetric extension. This extends the result of Apter, Dimitriou, and Koepke (see bluehttps://onlinelibrary.wiley.com/doi/abs/10.1002/malq.201110007) from 2014. We will see an open problem in this area. In 1985, Apter proved the consistency of the fact that all successor of regular cardinals can be weakly compact in presence of DC. We recall that in the hierarchy of large cardinals, a measurable cardinal is strictly stronger than a Ramsey cardinal, and a Ramsey cardinal is strictly stronger than a weakly compact cardinal. We observe that the statement blue`All successors of regular cardinals can be Ramsey (and not measurable)' does not imply countable choice (CC) in ZF. We also observe the existence of an infinitary Chang conjecture in two different symmetric extensions constructed by Apter–Koepke (from 2006) inspired by the methods of Dimitriou from her Ph.D. thesis (2011).

4. Reducing the large cardinal assumption of some results. In 2013, Apter–Cody worked on symmetric extensions based on supercompact Prikry Forcing to prove some consistency results on consecutive singular cardinals and continuum functions assuming a supercompact cardinal (bluehttps://projecteuclid.org/euclid.ndjfl/1361454970). We reduce the large cardinal assumption from a supercompact cardinal to a strongly compact cardinal (bluehttps://arxiv.org/abs/1903.05945v3) by working on a symmetric extension based on strongly compact Prikry Forcing and applying a recent result due to Usuba from 2019 (again we recall that in the hierarchy of large cardinals, a supercompact cardinal is strictly stronger than a strongly compact cardinal).

In this presentation, I shall discuss the new results (with more historical details, but without the technical details). We shall also discuss some open problems, and a direction for further studies in this area.