Three forms of the Erdős–Dushnik–Miller theorem
Volume 272 / 2026
Fundamenta Mathematicae 272 (2026), 171-203
MSC: Primary 03E25; Secondary 03E35, 05C63
DOI: 10.4064/fm250514-20-7
Published online: 14 January 2026
Abstract
We continue the study of the Erdős–Dushnik–Miller theorem (A graph with an uncountable set of vertices has either an infinite independent set or an uncountable clique) in set theory without the axiom of choice. We show that there are three inequivalent versions of this theorem and we give some results about the positions of these versions in the deductive hierarchy of weak choice principles. Furthermore, we settle some open problems from Tachtsis [Monatsh. Math. 203 (2024), 677–693] and from Banerjee and Gopaulsingh [Bull. Polish Acad. Sci. Math. 71 (2023), 1–21].
