Infinitary combinatorics

<h2 id="ramsey-theory-for-infinite-sets">Ramsey theory for infinite sets</h2>
Write 
 
 
 
 κ
 ,
 λ
 
 
 {\displaystyle \kappa ,\lambda }
 
 for ordinals, 
 
 
 
 m
 
 
 {\displaystyle m}
 
 for a <a href="/facts/Cardinal_number/ccoKwU4R">cardinal number</a> (finite or infinite) and 
 
 
 
 n
 
 
 {\displaystyle n}
 
 for a natural number. Erdős & Rado (1956) introduced the notation

κ
          →
          (
          λ
          
            )
            
              m
            
            
              n
            
          
        
      
    
    {\displaystyle \displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}

as a shorthand way of saying that every <a href="/facts/Partition_of_a_set/VeP9g8CA">partition</a> of the set 
 
 
 
 [
 κ
 
 ]
 
 n
 
 
 
 
 {\displaystyle [\kappa ]^{n}}
 
 of 
 
 
 
 n
 
 
 {\displaystyle n}
 
-element <a href="/facts/Subset/SJGERmbA">subsets</a> of 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 into 
 
 
 
 m
 
 
 {\displaystyle m}
 
 pieces has a homogeneous set of order type 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
. A homogeneous set is in this case a subset of 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 such that every 
 
 
 
 n
 
 
 {\displaystyle n}
 
-element subset is in the same element of the partition. When 
 
 
 
 m
 
 
 {\displaystyle m}
 
 is 2 it is often omitted. Such statements are known as partition relations.
Assuming the <a href="/facts/Axiom_of_choice/1Ura2HTh">axiom of choice</a>, there are no ordinals 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 with 
 
 
 
 κ
 →
 (
 ω
 
 )
 
 ω
 
 
 
 
 {\displaystyle \kappa \rightarrow (\omega )^{\omega }}
 
, so 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is usually taken to be finite. An extension where 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is almost allowed to be infinite is the notation

κ
 →
 (
 λ
 
 )
 
 m
 
 
 <
 ω
 
 
 
 
 
 {\displaystyle \displaystyle \kappa \rightarrow (\lambda )_{m}^{<\omega }}

which is a shorthand way of saying that every <a href="/facts/Partition_of_a_set/VeP9g8CA">partition</a> of the set of finite subsets of 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 into 
 
 
 
 m
 
 
 {\displaystyle m}
 
 pieces has a subset of order type 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
 such that for any finite 
 
 
 
 n
 
 
 {\displaystyle n}
 
, all subsets of size 
 
 
 
 n
 
 
 {\displaystyle n}
 
 are in the same element of the partition. When 
 
 
 
 m
 
 
 {\displaystyle m}
 
 is 2 it is often omitted.
Another variation is the notation

κ
          →
          (
          λ
          ,
          μ
          
            )
            
              n
            
          
        
      
    
    {\displaystyle \displaystyle \kappa \rightarrow (\lambda ,\mu )^{n}}

which is a shorthand way of saying that every coloring of the set 
 
 
 
 [
 κ
 
 ]
 
 n
 
 
 
 
 {\displaystyle [\kappa ]^{n}}
 
 of 
 
 
 
 n
 
 
 {\displaystyle n}
 
-element subsets of 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 with 2 colors has a subset of order type 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
 such that all elements of 
 
 
 
 [
 λ
 
 ]
 
 n
 
 
 
 
 {\displaystyle [\lambda ]^{n}}
 
 have the first color, or a subset of order type 
 
 
 
 μ
 
 
 {\displaystyle \mu }
 
 such that all elements of 
 
 
 
 [
 μ
 
 ]
 
 n
 
 
 
 
 {\displaystyle [\mu ]^{n}}
 
 have the second color.
Some properties of this include: (in what follows 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 is a cardinal)

ℵ
 
 0
 
 
 →
 (
 
 ℵ
 
 0
 
 
 
 )
 
 k
 
 
 n
 
 
 
 
 
 {\displaystyle \displaystyle \aleph _{0}\rightarrow (\aleph _{0})_{k}^{n}}
 
 for all finite 
 
 
 
 n
 
 
 {\displaystyle n}
 
 and 
 
 
 
 k
 
 
 {\displaystyle k}
 
 (<a href="/facts/Ramsey%2527s_theorem/VS6K8jGk">Ramsey's theorem</a>).

ℶ
 
 n
 
 
 +
 
 
 →
 (
 
 ℵ
 
 1
 
 
 
 )
 
 
 ℵ
 
 0
 
 
 
 
 n
 +
 1
 
 
 
 
 
 {\displaystyle \displaystyle \beth _{n}^{+}\rightarrow (\aleph _{1})_{\aleph _{0}}^{n+1}}
 
 (the <a href="/facts/Erd%25C5%2591s%25E2%2580%2593Rado_theorem/KRUa11Uk">Erdős–Rado theorem</a>.)

2
            
              κ
            
          
          ↛
          (
          
            κ
            
              +
            
          
          
            )
            
              2
            
          
        
      
    
    {\displaystyle \displaystyle 2^{\kappa }\not \rightarrow (\kappa ^{+})^{2}}
  
 (the Sierpiński theorem)

2
            
              κ
            
          
          ↛
          (
          3
          
            )
            
              κ
            
            
              2
            
          
        
      
    
    {\displaystyle \displaystyle 2^{\kappa }\not \rightarrow (3)_{\kappa }^{2}}

κ
 →
 (
 κ
 ,
 
 ℵ
 
 0
 
 
 
 )
 
 2
 
 
 
 
 
 {\displaystyle \displaystyle \kappa \rightarrow (\kappa ,\aleph _{0})^{2}}
 
 (the <a href="/facts/Erd%25C5%2591s%25E2%2580%2593Dushnik%25E2%2580%2593Miller_theorem/7PrBpyfc">Erdős–Dushnik–Miller theorem</a>)
In choiceless universes, partition properties with infinite exponents may hold, and some of them are obtained as consequences of the <a href="/facts/Axiom_of_determinacy/yztrbXJY">axiom of determinacy</a> (AD). For example, <a href="/facts/Donald_A._Martin/KsNsJnDP">Donald A. Martin</a> proved that AD implies

ℵ
            
              1
            
          
          →
          (
          
            ℵ
            
              1
            
          
          
            )
            
              2
            
            
              
                ℵ
                
                  1
                
              
            
          
        
      
    
    {\displaystyle \displaystyle \aleph _{1}\rightarrow (\aleph _{1})_{2}^{\aleph _{1}}}

<h2 id="strong-colorings">Strong colorings</h2>
<a href="/facts/Wac%25C5%2582aw_Sierpi%25C5%2584ski/ywT4mREz">Wacław Sierpiński</a> showed that the Ramsey theorem does not extend to sets of size 
 
 
 
 
 ℵ
 
 1
 
 
 
 
 {\displaystyle \aleph _{1}}
 
by showing that 
 
 
 
 
 2
 
 
 ℵ
 
 0
 
 
 
 
 ↛
 (
 
 ℵ
 
 1
 
 
 
 )
 
 2
 
 
 2
 
 
 
 
 {\displaystyle 2^{\aleph _{0}}\nrightarrow (\aleph _{1})_{2}^{2}}
 
. That is, Sierpiński constructed a coloring of pairs of <a href="/facts/Real_numbers/R02gw5Pb">real numbers</a> into two colors such that for every uncountable subset of real numbers 
 
 
 
 X
 
 
 {\displaystyle X}
 
, 
 
 
 
 [
 X
 
 ]
 
 2
 
 
 
 
 {\displaystyle [X]^{2}}
 
 takes both colors. Taking any set of real numbers of size 
 
 
 
 
 ℵ
 
 1
 
 
 
 
 {\displaystyle \aleph _{1}}
 
 and applying the coloring of Sierpiński to it, we get that 
 
 
 
 
 ℵ
 
 1
 
 
 ↛
 (
 
 ℵ
 
 1
 
 
 
 )
 
 2
 
 
 2
 
 
 
 
 {\displaystyle \aleph _{1}\not \rightarrow (\aleph _{1})_{2}^{2}}
 
. Colorings such as this are known as strong colorings<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> and studied in set theory. Erdős, Hajnal & Rado (1965) introduced a similar notation as above for this.
Write 
 
 
 
 κ
 ,
 λ
 
 
 {\displaystyle \kappa ,\lambda }
 
 for ordinals, 
 
 
 
 m
 
 
 {\displaystyle m}
 
 for a cardinal number (finite or infinite) and 
 
 
 
 n
 
 
 {\displaystyle n}
 
 for a natural number. Then

κ
          ↛
          [
          λ
          
            ]
            
              m
            
            
              n
            
          
        
      
    
    {\displaystyle \displaystyle \kappa \nrightarrow [\lambda ]_{m}^{n}}

is a shorthand way of saying that there exists a coloring of the set 
 
 
 
 [
 κ
 
 ]
 
 n
 
 
 
 
 {\displaystyle [\kappa ]^{n}}
 
 of 
 
 
 
 n
 
 
 {\displaystyle n}
 
-element subsets of 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 into 
 
 
 
 m
 
 
 {\displaystyle m}
 
 pieces such that every set of order type 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
 is a rainbow set. A rainbow set is in this case a subset 
 
 
 
 A
 
 
 {\displaystyle A}
 
 of 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 such that 
 
 
 
 [
 A
 
 ]
 
 n
 
 
 
 
 {\displaystyle [A]^{n}}
 
 takes all 
 
 
 
 m
 
 
 {\displaystyle m}
 
 colors. When 
 
 
 
 m
 
 
 {\displaystyle m}
 
 is 2 it is often omitted. Such statements are known as negative square bracket partition relations.
Another variation is the notation

κ
        ↛
        [
        λ
        ;
        μ
        
          ]
          
            m
          
          
            2
          
        
      
    
    {\displaystyle \kappa \nrightarrow [\lambda ;\mu ]_{m}^{2}}

which is a shorthand way of saying that there exists a coloring of the set 
 
 
 
 [
 κ
 
 ]
 
 2
 
 
 
 
 {\displaystyle [\kappa ]^{2}}
 
 of 2-element subsets of 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 with 
 
 
 
 m
 
 
 {\displaystyle m}
 
 colors such that for every subset 
 
 
 
 A
 
 
 {\displaystyle A}
 
 of order type 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
 and every subset 
 
 
 
 B
 
 
 {\displaystyle B}
 
 of order type 
 
 
 
 μ
 
 
 {\displaystyle \mu }
 
, the set 
 
 
 
 A
 ×
 B
 
 
 {\displaystyle A\times B}
 
 takes all 
 
 
 
 m
 
 
 {\displaystyle m}
 
 colors.
Some properties of this include: (in what follows 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 is a cardinal)

2
            
              κ
            
          
          ↛
          [
          
            κ
            
              +
            
          
          
            ]
            
              2
            
          
        
      
    
    {\displaystyle \displaystyle 2^{\kappa }\nrightarrow [\kappa ^{+}]^{2}}
  
 (Sierpiński)

ℵ
            
              1
            
          
          ↛
          [
          
            ℵ
            
              1
            
          
          
            ]
            
              2
            
          
        
      
    
    {\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]^{2}}
  
 (Sierpiński)

ℵ
 
 1
 
 
 ↛
 [
 
 ℵ
 
 1
 
 
 
 ]
 
 3
 
 
 2
 
 
 
 
 
 {\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{3}^{2}}
 
 (<a href="/facts/Richard_Laver/YsbFHbgA">Laver</a>, <a href="/facts/Andreas_Blass/ECtcwz3X">Blass</a>)

ℵ
 
 1
 
 
 ↛
 [
 
 ℵ
 
 1
 
 
 
 ]
 
 4
 
 
 2
 
 
 
 
 
 {\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{4}^{2}}
 
 (<a href="/facts/Fred_Galvin/HC0J2BM5"> Galvin</a> and <a href="/facts/Saharon_Shelah/oI5WSK8p">Shelah</a>)

ℵ
 
 1
 
 
 ↛
 [
 
 ℵ
 
 1
 
 
 
 ]
 
 
 ℵ
 
 1
 
 
 
 
 2
 
 
 
 
 
 {\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{\aleph _{1}}^{2}}
 
 (<a href="/facts/Stevo_Todor%25C4%258Devi%25C4%2587/KePHnqzd">Todorčević</a>)

ℵ
 
 1
 
 
 ↛
 [
 
 ℵ
 
 1
 
 
 ;
 
 ℵ
 
 1
 
 
 
 ]
 
 
 ℵ
 
 1
 
 
 
 
 2
 
 
 
 
 
 {\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1};\aleph _{1}]_{\aleph _{1}}^{2}}
 
 (<a href="/facts/Justin_T._Moore/e8AXtqVP">Moore</a>)

2
 
 
 ℵ
 
 0
 
 
 
 
 ↛
 [
 
 2
 
 
 ℵ
 
 0
 
 
 
 
 
 ]
 
 
 ℵ
 
 0
 
 
 
 
 2
 
 
 
 
 
 {\displaystyle \displaystyle 2^{\aleph _{0}}\nrightarrow [2^{\aleph _{0}}]_{\aleph _{0}}^{2}}
 
 (<a href="/facts/Fred_Galvin/HC0J2BM5"> Galvin</a> and <a href="/facts/Saharon_Shelah/oI5WSK8p">Shelah</a>)
<h2 id="large-cardinals">Large cardinals</h2>
Several <a href="/facts/Large_cardinal/jkSeV92D">large cardinal</a> properties can be defined using this notation. In particular:

<ul><li><a href="/facts/Weakly_compact_cardinal/1cfcW9H1">Weakly compact cardinals</a> 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 are those that satisfy 
 
 
 
 κ
 →
 (
 κ
 
 )
 
 2
 
 
 
 
 {\displaystyle \kappa \rightarrow (\kappa )^{2}}
 
</li>
<li>α-<a href="/facts/Erd%25C5%2591s_cardinal/PfDGnKhn">Erdős cardinals</a> 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 are the smallest that satisfy 
 
 
 
 κ
 →
 (
 α
 
 )
 
 <
 
 ω
 
 
 
 
 {\displaystyle \kappa \rightarrow (\alpha )^{<\,\omega }}
 
</li>
<li><a href="/facts/Ramsey_cardinal/saLQ57RQ">Ramsey cardinals</a> 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
 are those that satisfy 
 
 
 
 κ
 →
 (
 κ
 
 )
 
 <
 
 ω
 
 
 
 
 {\displaystyle \kappa \rightarrow (\kappa )^{<\,\omega }}
 
</li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Dushnik, Ben; Miller, E. W. (1941), "Partially ordered sets", <a href="/facts/American_Journal_of_Mathematics/lkgftcD7">American Journal of Mathematics</a>, 63 (3): 600–610, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2371374">10.2307/2371374</a>, <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/10338.dmlcz%2F100377">10338.dmlcz/100377</a>, <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0002-9327">0002-9327</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2371374">2371374</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0004862">0004862</a></li></ul>
<ul><li><a href="/facts/Paul_Erd%25C5%2591s/63LoUTe1">Erdős, Paul</a>; <a href="/facts/Andr%25C3%25A1s_Hajnal/4gDj0N1Q">Hajnal, András</a>; <a href="/facts/Richard_Rado/QXBFIwBd">Rado, Richard</a> (1965), <a href="https://doi.org/10.1007/BF01886396">"Partition relations for cardinal numbers"</a>, Acta Math. Acad. Sci. Hung., 16 (1–2): 93–196, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01886396">10.1007/BF01886396</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0202613">0202613</a></li></ul>
<ul><li><a href="/facts/Paul_Erd%25C5%2591s/63LoUTe1">Erdős, Paul</a>; <a href="/facts/Andr%25C3%25A1s_Hajnal/4gDj0N1Q">Hajnal, András</a> (1971), "Unsolved problems in set theory", Axiomatic Set Theory ( Univ. California, Los Angeles, Calif., 1967), Proc. Sympos. Pure Math, vol. XIII Part I, Providence, R.I.: Amer. Math. Soc., pp. 17–48, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0280381">0280381</a></li>
<li><a href="/facts/Paul_Erd%25C5%2591s/63LoUTe1">Erdős, Paul</a>; <a href="/facts/Andr%25C3%25A1s_Hajnal/4gDj0N1Q">Hajnal, András</a>; Máté, Attila; <a href="/facts/Richard_Rado/QXBFIwBd">Rado, Richard</a> (1984), Combinatorial set theory: partition relations for cardinals, Studies in Logic and the Foundations of Mathematics, vol. 106, Amsterdam: North-Holland Publishing Co., <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-444-86157-2, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0795592">0795592</a></li>
<li><a href="/facts/Paul_Erd%25C5%2591s/63LoUTe1">Erdős, P.</a>; <a href="/facts/Richard_Rado/QXBFIwBd">Rado, R.</a> (1956), <a href="https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-62/issue-5/A-partition-calculus-in-set-theory/bams/1183520996.pdf">"A partition calculus in set theory"</a> (PDF), Bull. Amer. Math. Soc., 62 (5): 427–489, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0002-9904-1956-10036-0">10.1090/S0002-9904-1956-10036-0</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0081864">0081864</a></li>
<li><a href="/facts/Akihiro_Kanamori/d8QTYwzT">Kanamori, Akihiro</a> (2000), <a href="/facts/The_Higher_Infinite/AzqTTVPK">The Higher Infinite</a> (second ed.), Springer, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-00384-3</li>
<li><a href="/facts/Kenneth_Kunen/jbJNPJKV">Kunen, Kenneth</a> (1980), <a href="/facts/Set_Theory%3a_An_Introduction_to_Independence_Proofs/AlwgQM4g">Set Theory: An Introduction to Independence Proofs</a>, Amsterdam: North-Holland, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-444-85401-8</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Andreas Blass, Combinatorial Cardinal Characteristics of the Continuum, Chapter 6 in Handbook of Set Theory, edited by Matthew Foreman and Akihiro Kanamori, Springer, 2010 <a href="/wiki/Andreas_Blass" target="_blank">/wiki/Andreas_Blass</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Todd Eisworth, Successors of Singular Cardinals Chapter 15 in Handbook of Set Theory, edited by Matthew Foreman and Akihiro Kanamori, Springer, 2010 <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Rinot, Assaf, Tutorial on strong colorings and their applications, 6th European Set Theory Conference, retrieved 2023-12-10 <a href="https://blog.assafrinot.com/?p=4392" target="_blank">https://blog.assafrinot.com/?p=4392</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
</ol>

Infinitary combinatorics open-in-new

Infinitary combinatorics