JEDNOSTKA NAUKOWA KATEGORII A+

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

Tom 71 / 2023

Amitayu Banerjee, Alexa Gopaulsingh Bulletin Polish Acad. Sci. Math. 71 (2023), 1-21 MSC: Primary 03E25; Secondary 03E35, 05C63, 06A07. DOI: 10.4064/ba221221-6-6 Opublikowany online: 1 August 2023

Streszczenie

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.

Autorzy

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek