Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
chromatic number of product of graphs; ultrafilter lemma; permutation model; Dilworth's theorem; chain; antichain; Loeb's theorem; application of Loeb's theorem
chromatic number of product of graphs; ultrafilter lemma; permutation model; Dilworth's theorem; chain; antichain; Loeb's theorem; application of Loeb's theorem
Summary:
In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles. $\circ$ If in a partially ordered set, all chains are finite and all antichains are countable, then the set is countable. $\circ$ If in a partially ordered set, all chains are finite and all antichains have size $\aleph_{\alpha}$, then the set has size $\aleph_{\alpha}$ for any regular $\aleph_{\alpha}$. $\circ$ Every partially ordered set without a maximal element has two disjoint cofinal sub sets -- CS. $\circ$ Every partially ordered set has a cofinal well-founded subset -- CWF. $\circ$ Dilworth's decomposition theorem for infinite partially ordered sets of finite width -- DT. We also study a graph homomorphism problem and a problem due to A. Hajnal without AC. Further, we study a few statements restricted to linearly-ordered structures without AC.
References:
[1] Banaschewski B.: Algebraic closure without choice. Z. Math. Logik Grundlag. Math. 38 (1992), no. 4, 383–385. DOI 10.1002/malq.19920380136
[2] Cowen R. H.: Generalizing König's infinity lemma. Notre Dame J. Formal Logic 18 (1977), no. 2, 243–247. DOI 10.1305/ndjfl/1093887927
[3] Dilworth R. P.: A decomposition theorem for partially ordered sets. Ann. of Math. (2) 51 (1950), 161–166. DOI 10.2307/1969503
[4] Hajnal A.: The chromatic number of the product of two $\aleph_{1}$-chromatic graphs can be countable. Combinatorica 5 (1985), no. 2, 137–139. DOI 10.1007/BF02579376
[5] Halbeisen L., Tachtsis E.: On Ramsey choice and partial choice for infinite families of $n$-element sets. Arch. Math. Logic 59 (2020), no. 5–6, 583–606. DOI 10.1007/s00153-019-00705-7
[6] Hall M. Jr.: Distinct representatives of subsets. Bull. Amer. Math. Soc. 54 (1948), 922–926. DOI 10.1090/S0002-9904-1948-09098-X
[7] Howard P. E.: Binary consistent choice on pairs and a generalization of König's infinity lemma. Fund. Math. 121 (1984), no. 1, 17–23. DOI 10.4064/fm-121-1-17-23
[8] Howard P., Rubin J. E.: Consequences of the Axiom of Choice. Mathematical Surveys and Monographs, 59, American Mathematical Society, Providence, 1998. DOI 10.1090/surv/059 | Zbl 0947.03001
[9] Howard P., Saveliev D. I., Tachtsis E.: On the set-theoretic strength of the existence of disjoint cofinal sets in posets without maximal elements. MLQ Math. Log. Q. 62 (2016), no. 3, 155–176. DOI 10.1002/malq.201400089
[10] Howard P., Tachtsis E.: On vector spaces over specific fields without choice. MLQ Math. Log. Q. 59 (2013), no. 3, 128–146. DOI 10.1002/malq.201200049 | Zbl 1278.03082
[11] Jech T. J.: The Axiom of Choice. Studies in Logic and the Foundations of Mathematics, 75, North-Holland Publishing Co., Amsterdam, American Elsevier Publishing Co., New York, 1973. Zbl 0259.02052
[12] Keremedis K.: The compactness of $2^{\mathbb{R}}$ and the axiom of choice. MLQ Math. Log. Q. 46 (2000), no. 4, 569–571. DOI 10.1002/1521-3870(200010)46:4<569::AID-MALQ569>3.0.CO;2-J
[13] Komjáth P., Totik V.: Problems and Theorems in Classical Set Theory. Problem Books in Mathematics, Springer, New York, 2006.
[14] Loeb P. A.: A new proof of the Tychonoff theorem. Amer. Math. Monthly 72 (1965), no. 7, 711–717. DOI 10.1080/00029890.1965.11970596
[15] Łoś J., Ryll-Nardzewski C.: On the application of Tychonoff's theorem in mathematical proofs. Fund. Math. 38 (1951), no. 1, 233–237. DOI 10.4064/fm-38-1-233-237
[16] Tachtsis E.: On Martin’s axiom and forms of choice. MLQ Math. Log. Q. 62 (2016), no. 3, 190–203. DOI 10.1002/malq.201400115
[17] Tachtsis E.: On Ramsey's theorem and the existence of infinite chains or infinite anti-chains in infinite posets. J. Symb. Log. 81 (2016), no. 1, 384–394. DOI 10.1017/jsl.2015.47
[18] Tachtsis E.: On the minimal cover property and certain notions of finite. Arch. Math. Logic. 57 (2018), no. 5–6, 665–686. DOI 10.1007/s00153-017-0595-y
[19] Tachtsis E.: Dilworth's decomposition theorem for posets in ZF. Acta Math. Hungar. 159 (2019), no. 2, 603–617. DOI 10.1007/s10474-019-00967-w
[20] Tachtsis E.: Łoś's theorem and the axiom of choice. MLQ Math. Log. Q. 65 (2019), no. 3, 280–292. DOI 10.1002/malq.201700074
Search
Partner of
