| Title:
|
Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC (English) |
| Author:
|
Banerjee, Amitayu |
| Author:
|
Gyenis, Zalán |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
62 |
| Issue:
|
3 |
| Year:
|
2021 |
| Pages:
|
361-382 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
chromatic number of product of graphs |
| Keyword:
|
ultrafilter lemma |
| Keyword:
|
permutation model |
| Keyword:
|
Dilworth's theorem |
| Keyword:
|
chain |
| Keyword:
|
antichain |
| Keyword:
|
Loeb's theorem |
| Keyword:
|
application of Loeb's theorem |
| MSC:
|
03E25 |
| MSC:
|
03E35 |
| MSC:
|
05C15 |
| idMR:
|
MR4331288 |
| DOI:
|
10.14712/1213-7243.2021.028 |
| . |
| Date available:
|
2021-10-20T09:23:43Z |
| Last updated:
|
2023-10-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/149150 |
| . |
| Reference:
|
[1] Banaschewski B.: Algebraic closure without choice.Z. Math. Logik Grundlag. Math. 38 (1992), no. 4, 383–385. 10.1002/malq.19920380136 |
| Reference:
|
[2] Cowen R. H.: Generalizing König's infinity lemma.Notre Dame J. Formal Logic 18 (1977), no. 2, 243–247. 10.1305/ndjfl/1093887927 |
| Reference:
|
[3] Dilworth R. P.: A decomposition theorem for partially ordered sets.Ann. of Math. (2) 51 (1950), 161–166. 10.2307/1969503 |
| Reference:
|
[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. 10.1007/BF02579376 |
| Reference:
|
[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. 10.1007/s00153-019-00705-7 |
| Reference:
|
[6] Hall M. Jr.: Distinct representatives of subsets.Bull. Amer. Math. Soc. 54 (1948), 922–926. 10.1090/S0002-9904-1948-09098-X |
| Reference:
|
[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. 10.4064/fm-121-1-17-23 |
| Reference:
|
[8] Howard P., Rubin J. E.: Consequences of the Axiom of Choice.Mathematical Surveys and Monographs, 59, American Mathematical Society, Providence, 1998. Zbl 0947.03001, 10.1090/surv/059 |
| Reference:
|
[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. 10.1002/malq.201400089 |
| Reference:
|
[10] Howard P., Tachtsis E.: On vector spaces over specific fields without choice.MLQ Math. Log. Q. 59 (2013), no. 3, 128–146. Zbl 1278.03082, 10.1002/malq.201200049 |
| Reference:
|
[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 |
| Reference:
|
[12] Keremedis K.: The compactness of $2^{\mathbb{R}}$ and the axiom of choice.MLQ Math. Log. Q. 46 (2000), no. 4, 569–571. 10.1002/1521-3870(200010)46:4<569::AID-MALQ569>3.0.CO;2-J |
| Reference:
|
[13] Komjáth P., Totik V.: Problems and Theorems in Classical Set Theory.Problem Books in Mathematics, Springer, New York, 2006. |
| Reference:
|
[14] Loeb P. A.: A new proof of the Tychonoff theorem.Amer. Math. Monthly 72 (1965), no. 7, 711–717. 10.1080/00029890.1965.11970596 |
| Reference:
|
[15] Łoś J., Ryll-Nardzewski C.: On the application of Tychonoff's theorem in mathematical proofs.Fund. Math. 38 (1951), no. 1, 233–237. 10.4064/fm-38-1-233-237 |
| Reference:
|
[16] Tachtsis E.: On Martin’s axiom and forms of choice.MLQ Math. Log. Q. 62 (2016), no. 3, 190–203. 10.1002/malq.201400115 |
| Reference:
|
[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. 10.1017/jsl.2015.47 |
| Reference:
|
[18] Tachtsis E.: On the minimal cover property and certain notions of finite.Arch. Math. Logic. 57 (2018), no. 5–6, 665–686. 10.1007/s00153-017-0595-y |
| Reference:
|
[19] Tachtsis E.: Dilworth's decomposition theorem for posets in ZF.Acta Math. Hungar. 159 (2019), no. 2, 603–617. 10.1007/s10474-019-00967-w |
| Reference:
|
[20] Tachtsis E.: Łoś's theorem and the axiom of choice.MLQ Math. Log. Q. 65 (2019), no. 3, 280–292. 10.1002/malq.201700074 |
| . |
