On the Erdős–Dushnik–Miller theorem without AC

Amitayu Banerjee¹ ; Alexa Gopaulsingh²

¹ Alfréd Rényi Institute of Mathematics Budapest 1053, Hungary <a href="https://orcid.org/0000-0003-4156-7209">ORCID: 0000-0003-4156-7209</a>
² Department of Logic Institute of Philosophy Eötvös Loránd University Budapest, Hungary <a href="https://orcid.org/0000-0001-7601-1804">ORCID: 0000-0001-7601-1804</a>

Bulletin of the Polish Academy of Sciences. Mathematics, Tome 71 (2023) no. 1, pp. 1-21

Résumé

In $\mathsf {ZFA}$ (Zermelo–Fraenkel set theory with the Axiom of Extensionality weakened to allow the existence of atoms), we prove that the strength of the proposition $\mathsf {EDM}$ (“If $G=(V_{G}, E_{G})$ is a graph such that $V_{G}$ is uncountable, then for every coloring $f:[V_{G}]^{2}\rightarrow \{0,1\}$ either there is an uncountable set monochromatic in color $0$, or there is a countably infinite set monochromatic in color 1”) is strictly between $\mathsf {DC_{\aleph _{1}}}$ (where $\mathsf {DC_{\aleph _{1}}}$ is Dependent Choices for $\aleph _{1}$, a weak choice form stronger than Dependent Choices ($\mathsf {DC}$)) and Kurepa’s principle (“Any partially ordered set such that all of its antichains are finite and all of its chains are countable is countable”). Among other new results, we study the relations of $\mathsf {EDM}$ to $\mathsf {BPI}$ (Boolean Prime Ideal Theorem), $\mathsf {RT}$ (Ramsey’s theorem), De Bruijn–Erdős’ theorem for $n$-colorings, König’s lemma and several other weak choice forms. Moreover, we answer a part of a question raised by Lajos Soukup.

Détail

DOI : 10.4064/ba221221-6-6

Keywords: mathsf zfa zermelo fraenkel set theory axiom extensionality weakened allow existence atoms prove strength proposition mathsf edm graph uncountable every coloring rightarrow either there uncountable set monochromatic color there countably infinite set monochromatic color strictly between mathsf aleph where mathsf aleph dependent choices aleph weak choice form stronger dependent choices mathsf kurepa principle partially ordered set its antichains finite its chains countable countable among other results study relations mathsf edm mathsf bpi boolean prime ideal theorem mathsf ramsey theorem bruijn erd theorem n colorings nig lemma several other weak choice forms moreover answer part question raised lajos soukup