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

• Autorzy: Banerjee Amitayu , Gopaulsingh Alexa

Identyfikatory

DOI

10.4064/ba221221-6-6

• Języki publikacji: EN

Abstrakty

EN

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 every 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 DCN1 (where DCN1 is Dependent Choices for N1, 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 to BPI (Boolean Prime Ideal Theorem), 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.

Słowa kluczowe

EN

Axiom of Choice; infinite graphs; Erdős–Dushnik–Miller theorem; Ramsey’s theorem; Boolean Prime Ideal Theorem; Fraenkel–Mostowski models of ZFA

• Wydawca: Instytut Matematyczny PAN
• Czasopismo: Bulletin of the Polish Academy of Sciences. Mathematics
• Rocznik: 2023
• Tom: Vol. 71, no 1
• Strony: 1--21
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Banerjee Amitayu

• Alfréd Rényi Institute of Mathematics, Budapest 1053, Hungary

• https://orcid.org/0000-0003-4156-7209

autor

Gopaulsingh Alexa

• Department of Logic Institute of Philosophy Eötvös Loránd University Budapest, Hungary

• https://orcid.org/0000-0001-7601-1804

Bibliografia

• [1] A. Banerjee, Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC, Comment. Math. Univ. Carolin., to appear.
• [2] A. Banerjee, Combinatorial properties and dependent choice in symmetric extensions based on Lévy collapse, Arch. Math. Logic 62 (2023), 369-399.
• [3] A. Banerjee and Z. Gyenis, Chromatic number of the product of graphs, graph homomorphisms, Antichains and cofinal subsets of posets without AC, Comment. Math. Univ. Carolin. 62 (2021), 361-382.
• [4] A. Blass, Ramsey’s theorem in the hierarchy of choice principles, J. Symbolic Logic 42 (1977), 387-390.
• [5] N. Brunner, Products of compact spaces in the least permutation model, Z. Math. Logik Grundlagen Math. 31 (1985), 441-448.
• [6] N. Brunner, Dedekind-Endlichkeit und Wohlordenbarkeit, Monatsh. Math. 94 (1982), 9-31.
• [7] B. Dushnik and E. W. Miller, Partially ordered sets, Amer. J. Math. 63 (1941), 600-610.
• [8] P. Howard, K. Keremedis, J. E. Rubin, A. Stanley and E. Tachtsis, Non-constructive properties of the real numbers, Math. Logic Quart. 47 (2001), 423-431.
• [9] P. Howard and J. E. Rubin, Consequences of the Axiom of Choice, Math. Surveys Monogr. 59, Amer. Math. Soc., Providence, RI, 1998.
• [10] L. Halbeisen and E. Tachtsis, On Ramsey Choice and Partial Choice for infinite families of n-element sets, Arch. Math. Logic 59 (2020), 583-606.
• [11] P. Howard, D. I. Saveliev and E. Tachtsis, On the set-theoretic strength of the existence of disjoint cofinal sets in posets without maximal elements, Math. Logic Quart. 62 (2016), 155-176.
• [12] P. Howard, D. I. Saveliev and E. Tachtsis, On the existence of cofinal well-founded subsets of posets without AC, preprint.
• [13] T. J. Jech, The Axiom of Choice, Stud. Logic Found. Math. 75, North-Holland, Amsterdam, 1973.
• [14] A. Karagila, Preserving Dependent Choice, Bull. Polish Acad. Sci. Math. 67 (2019), 19-29.
• [15] K. Keremedis, E. Tachtsis and E. Wajch, Several results on compact metrizable spaces in ZF, Monatsh. Math. 196 (2021), 67-102.
• [16] G. Kurepa, On two problems concerning ordered sets, Glasnik Mat.-Fiz. Astronom. Društvo Mat. Fiz. Hrvatske Ser. II 13 (1958), 229-234.
• [17] D. Pincus, Zermelo-Fraenkel consistency results by Fraenkel-Mostowski methods, J. Symbolic Logic 37 (1972), 721-743.
• [18] W. Sierpiński, Cardinal and Ordinal Numbers, Państwowe Wydawnictwo Naukowe, Warszawa, 1958.
• [19] E. Tachtsis, On a theorem of Kurepa for partially ordered sets and weak choice, Monatsh. Math. 199 (2022), 645-669.
• [20] E. Tachtsis, On the existence of permutations of infinite sets without fixed points in set theory without choice, Acta Math. Hungar. 157 (2019), 281-300.
• [21] E. Tachtsis, Łoś’s theorem and the axiom of choice, Math. Logic Quart. 65 (2019), 280-292.
• [22] E. Tachtsis, On the existence of almost disjoint and MAD families without AC, Bull. Polish Acad. Sci. Math. 67 (2019), 101-124.
• [23] E. Tachtsis, Dilworth’s decomposition theorem for posets in ZF, Acta Math. Hungar. 159 (2019), 603-617.
• [24] E. Tachtsis, On the minimal cover property and certain notions of finite, Arch. Math. Logic 57 (2018), 665-686.
• [25] E. Tachtsis, On Ramsey’s theorem and the existence of infinite chains or infinite anti-chains in infinite posets, J. Symbolic Logic 81 (2016), 384-394.
• [26] E. Tachtsis, On Martin’s Axiom and forms of choice, Math. Logic Quart. 62 (2016), 190-203.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).