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

Banerjee, Amitayu and Gopaulsingh, Alexa (2023) On the Erdős–Dushnik–Miller theorem without AC. BULLETIN OF THE POLISH ACADEMY OF SCIENCES-MATHEMATICS, 71. pp. 1-21. ISSN 0239-7269

Preview

Text 2211.05665v4.pdf Available under License Creative Commons Attribution. Download (298kB) | Preview

Abstract

In 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 EDM (“If G = (VG, EG) is a graph such that VG is uncountable, then for all coloring f : [VG]2 → {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 DCℵ1 (where DCℵ1 is Dependent Choices for ℵ1, a weak choice form stronger than Dependent Choices (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 EDM with BPI (Boolean Prime Ideal Theorem), RT (Ramsey’s Theorem), De Bruijn–Erd˝os theorem for n-colorings, K˝onig’s Lemma and several other weak choice forms. Moreover, we answer a part of a question raised by Lajos Soukup.

Actions (login required)

Edit Item