Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC

Amitayu Banerjee

Commentationes Mathematicae Universitatis Carolinae (2023)

  • Volume: 64, Issue: 2, page 137-159
  • ISSN: 0010-2628

Abstract

top
In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles. ∘ 𝒫 lf , c (Every locally finite connected graph has a maximal independent set). ∘ 𝒫 lc , c (Every locally countable connected graph has a maximal independent set). ∘ CAC 1 ℵ α (If in a partially ordered set all antichains are finite and all chains have size ℵ α , then the set has size ℵ α ) if ℵ α is regular. ∘ CWF (Every partially ordered set has a cofinal well-founded subset). ∘ 𝒫 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 ). ∘ 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 : { w , v } ∈ E G } is a clique for each v ∈ V G .

How to cite

top

Banerjee, Amitayu. "Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC." Commentationes Mathematicae Universitatis Carolinae 64.2 (2023): 137-159. <http://eudml.org/doc/299170>.

@article{Banerjee2023,
abstract = {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 $\lbrace w < v \colon \lbrace w,v\rbrace \in E_\{G\}\rbrace $ is a clique for each $v\in V_\{G\}$.},
author = {Banerjee, Amitayu},
journal = {Commentationes Mathematicae Universitatis Carolinae},
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 + $\lnot $ AC},
language = {eng},
number = {2},
pages = {137-159},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC},
url = {http://eudml.org/doc/299170},
volume = {64},
year = {2023},
}

TY - JOUR
AU - Banerjee, Amitayu
TI - Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2023
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 64
IS - 2
SP - 137
EP - 159
AB - 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 $\lbrace w < v \colon \lbrace w,v\rbrace \in E_{G}\rbrace $ is a clique for each $v\in V_{G}$.
LA - eng
KW - 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 + $\lnot $ AC
UR - http://eudml.org/doc/299170
ER -

References

top
  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. MR4331288
  2. Delhommé C., Morillon M., Spanning graphs and the axiom of choice, Rep. Math. Logic 40 (2006), 165–180. MR2207308
  3. Diestel R., Graph Theory, Grad. Texts in Math., 173, Springer, Berlin, 2017. Zbl1218.05001MR3644391
  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. MR3617852
  5. Fulkerson D. R., Gross O. A., 10.2140/pjm.1965.15.835, Pacific J. Math. 15 (1965), 835–855. MR0186421DOI10.2140/pjm.1965.15.835
  6. Füredi Z., 10.1002/jgt.3190110403, J. Graph Theory 11 (1987), no. 4, 463–470. MR0917193DOI10.1002/jgt.3190110403
  7. Galvin F., Komjáth P., 10.1007/BF02309111, Period. Math. Hungar. 22 (1991), no. 1, 71–75. MR1145937DOI10.1007/BF02309111
  8. Hajnal A., 10.1007/BF02579376, Combinatorica 5 (1985), no. 2, 137–139. MR0815579DOI10.1007/BF02579376
  9. Halbeisen L., Tachtsis E., 10.1007/s00153-019-00705-7, Arch. Math. Logic 59 (2020), no. 5–6, 583–606. MR4123294DOI10.1007/s00153-019-00705-7
  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. MR2880914
  11. Howard P., Keremedis K., Rubin J. E., Stanley A., Tachtsis E., 10.1002/1521-3870(200108)47:3<423::AID-MALQ423>3.0.CO;2-0, MLQ Math. Log. Q. 47 (2001), no. 3, 423–431. MR1847458DOI10.1002/1521-3870(200108)47:3<423::AID-MALQ423>3.0.CO;2-0
  12. Howard P., Rubin J. E., 10.1090/surv/059, Mathematical Surveys and Monographs, 59, American Mathematical Society, Providence, 1998. Zbl0947.03001MR1637107DOI10.1090/surv/059
  13. Howard P., Saveliev D. I., Tachtsis E., 10.1002/malq.201400089, MLQ Math. Log. Q. 62 (2016), no. 3, 155–176. MR3509700DOI10.1002/malq.201400089
  14. Howard P., Tachtsis E., 10.1002/malq.201200049, MLQ Math. Log. Q. 59 (2013), no. 3, 128–146. Zbl1278.03082MR3066735DOI10.1002/malq.201200049
  15. Jech T. J., The Axiom of Choice, Stud. Logic Found. Math., 75, North-Holland Publishing Co., Amsterdam, American Elsevier Publishing, New York, 1973. Zbl0259.02052MR0396271
  16. Komjáth P., 10.1016/j.disc.2015.03.022, Discrete Math. 338 (2015), 1565–1566. MR3345591DOI10.1016/j.disc.2015.03.022
  17. Komjáth P., Totik V., Problems and Theorems in Classical Set Theory, Probl. Books in Math., Springer, New York, 2006. MR2220838
  18. Läuchli H., 10.1007/BF02771458, Israel J. Math. 9 (1971), 422–429. MR0288051DOI10.1007/BF02771458
  19. Loeb P. A., 10.1080/00029890.1965.11970596, Amer. Math. Monthly 72 (1965), no. 7, 711–717. MR0190896DOI10.1080/00029890.1965.11970596
  20. Mycielski J., 10.1007/BF02066677, Acta Math. Acad. Sci. Hungar. 12 (1961), 125–129. MR0130686DOI10.1007/BF02066677
  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., 10.1017/jsl.2015.47, J. Symb. Log. 81 (2016), no. 1, 384–394. MR3480974DOI10.1017/jsl.2015.47
  23. Tachtsis E., 10.1007/s00153-017-0595-y, Arch. Math. Logic 57 (2018), no. 5–6, 665–686. MR3828886DOI10.1007/s00153-017-0595-y
  24. Tachtsis E., 10.1007/s10474-019-00967-w, Acta Math. Hungar. 159 (2019), no. 2, 603–617. MR4022152DOI10.1007/s10474-019-00967-w
  25. Tachtsis E., 10.1002/malq.201700074, MLQ Math. Log. Q. 65 (2019), no. 3, 280–292. MR4030955DOI10.1002/malq.201700074

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.