Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
variants of chain/antichain principle; graph homomorphism; maximal independent sets; cofinal well-founded subsets of partially ordered sets; axiom of choice; Fraenkel--Mostowski (FM) permutation models of ZFA + $\neg$ AC
variants of chain/antichain principle; graph homomorphism; maximal independent sets; cofinal well-founded subsets of partially ordered sets; axiom of choice; Fraenkel--Mostowski (FM) permutation models of ZFA + $\neg$ AC
Summary:
In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles. $\circ$ $\mathcal{P}_{\rm lf,c}$ (Every locally finite connected graph has a maximal independent set). $\circ$ $\mathcal{P}_{\rm lc,c}$ (Every locally countable connected graph has a maximal independent set). $\circ$ CAC$^{\aleph_{\alpha}}_{1}$ (If in a partially ordered set all antichains are finite and all chains have size $\aleph_{\alpha}$, then the set has size $\aleph_{\alpha}$) if $\aleph_{\alpha}$ is regular. $\circ$ CWF (Every partially ordered set has a cofinal well-founded subset). $\circ$ $\mathcal{P}_{G,H_{2}} $ (For any infinite graph $ G=(V_{G}, E_{G}) $ and any finite graph $ H=(V_{H}, E_{H})$ on 2 vertices, if every finite subgraph of $G$ has a homomorphism into $H$, then so has $G$). $\circ$ If $ G=(V_{G},E_{G}) $ is a connected locally finite chordal graph, then there is an ordering ``$<$" of $V_{G}$ such that $\{w < v \colon \{w,v\} \in E_{G}\}$ is a clique for each $v\in V_{G}$.
References:
[1] Banerjee A., Gyenis Z.: Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC. Comment. Math. Univ. Carolin. 62 (2021), no. 3, 361–382. MR 4331288
[2] Delhommé C., Morillon M.: Spanning graphs and the axiom of choice. Rep. Math. Logic 40 (2006), 165–180. MR 2207308
[3] Diestel R.: Graph Theory. Grad. Texts in Math., 173, Springer, Berlin, 2017. MR 3644391 | Zbl 1218.05001
[4] Friedman H. M.: Invariant maximalilty and incompleteness. Foundations and Methods from Mathematics to Neuroscience, CSLI Lecture Notes, 213, CSLI Publications, Stanford, 2014, pages 25–51. MR 3617852
[5] Fulkerson D. R., Gross O. A.: Incidence matrices and interval graphs. Pacific J. Math. 15 (1965), 835–855. DOI 10.2140/pjm.1965.15.835 | MR 0186421
[6] Füredi Z.: The number of maximal independent sets in connected graphs. J. Graph Theory 11 (1987), no. 4, 463–470. DOI 10.1002/jgt.3190110403 | MR 0917193
[7] Galvin F., Komjáth P.: Graph colorings and the axiom of choice. Period. Math. Hungar. 22 (1991), no. 1, 71–75. DOI 10.1007/BF02309111 | MR 1145937
[8] 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 | MR 0815579
[9] 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 | MR 4123294
[10] Herrlich H., Howard P., Tachtsis E.: On special partitions of Dedekind- and Russell-sets. Comment. Math. Univ. Carolin. 53 (2012), no. 1, 105–122. MR 2880914
[11] Howard P., Keremedis K., Rubin J. E., Stanley A., Tachtsis E.: Non-constructive properties of the real numbers. MLQ Math. Log. Q. 47 (2001), no. 3, 423–431. DOI 10.1002/1521-3870(200108)47:3<423::AID-MALQ423>3.0.CO;2-0 | MR 1847458
[12] 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 | MR 1637107 | Zbl 0947.03001
[13] 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 | MR 3509700
[14] 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 | MR 3066735 | Zbl 1278.03082
[15] Jech T. J.: The Axiom of Choice. Stud. Logic Found. Math., 75, North-Holland Publishing Co., Amsterdam, American Elsevier Publishing, New York, 1973. MR 0396271 | Zbl 0259.02052
[16] Komjáth P.: A note on uncountable chordal graphs. Discrete Math. 338 (2015), 1565–1566. DOI 10.1016/j.disc.2015.03.022 | MR 3345591
[17] Komjáth P., Totik V.: Problems and Theorems in Classical Set Theory. Probl. Books in Math., Springer, New York, 2006. MR 2220838
[18] Läuchli H.: Coloring infinite graphs and the Boolean prime ideal theorem. Israel J. Math. 9 (1971), 422–429. DOI 10.1007/BF02771458 | MR 0288051
[19] 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 | MR 0190896
[20] Mycielski J.: Some remarks and problems on the coloring of infinite graphs and the theorem of Kuratowski. Acta Math. Acad. Sci. Hungar. 12 (1961), 125–129. DOI 10.1007/BF02066677 | MR 0130686
[21] Spanring C.: Axiom of choice, maximal independent sets, argumentation and dialogue games. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2014, pages 91–98.
[22] 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 | MR 3480974
[23] 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 | MR 3828886
[24] 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 | MR 4022152
[25] 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 | MR 4030955
Search
Partner of
