<p>Ramsey’s theorem on countable infinite sets states that for all natural numbers <i>n</i>,&#xa0; for all finite colorings of the <i>n</i>-element subsets of some infinite countable set, there exists an infinite countable homogeneous subset. What if we seek a homogeneous subset that is also order-equivalent to the original set? Let <i>S</i> be a linearly ordered set and <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(n\in \mathbb {N}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation>. The big Ramsey degree of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(n\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation> in <i>S</i>, denoted <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(T(n,S)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, is the least natural number <i>t</i> such that, for any finite coloring of the size <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(n\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation> subsets of <i>S</i>, there exists <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(S'\subseteq S\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>S</mi> <mo>′</mo> </msup> <mo>⊆</mo> <mi>S</mi> </mrow> </math></EquationSource> </InlineEquation> such that (i) <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(S'\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>S</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> is order-equivalent to <i>S</i>, and (ii) if the coloring is restricted to the size <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(n\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation> subsets of <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(S'\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>S</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> then at most <i>t</i> colors are used. Mašulović &amp; Šobot (2021) showed that <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(T(n,\omega +\omega )=2^{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>ω</mi> <mo>+</mo> <mi>ω</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msup> <mn>2</mn> <mi>n</mi> </msup> </mrow> </math></EquationSource> </InlineEquation>. From this one can obtain <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(T(n,\zeta )=2^{n},\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>ζ</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msup> <mn>2</mn> <mi>n</mi> </msup> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\zeta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ζ</mi> </math></EquationSource> </InlineEquation> is the ordered set of integers. We give a direct proof that <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(T(n,\zeta )=2^{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>ζ</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msup> <mn>2</mn> <mi>n</mi> </msup> </mrow> </math></EquationSource> </InlineEquation>. Mašulović and Šobot (2021) also showed that for all countable ordinals <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\alpha &lt; \omega ^\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo>&lt;</mo> <msup> <mi>ω</mi> <mi>ω</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(n\in \mathbb {N}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(T(n,\alpha )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>α</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is finite. We find exact values of <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(T(n,\alpha )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>α</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for all ordinals <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(\alpha \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> less than <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(\omega ^\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>ω</mi> <mi>ω</mi> </msup> </math></EquationSource> </InlineEquation> and all <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(n\in \mathbb {N}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Big Ramsey Degrees of Countable Ordinals

  • Joanna Boyland,
  • William Gasarch,
  • Nathan Hurtig,
  • Robert Rust

摘要

Ramsey’s theorem on countable infinite sets states that for all natural numbers n,  for all finite colorings of the n-element subsets of some infinite countable set, there exists an infinite countable homogeneous subset. What if we seek a homogeneous subset that is also order-equivalent to the original set? Let S be a linearly ordered set and \(n\in \mathbb {N}\) n N . The big Ramsey degree of \(n\) n in S, denoted \(T(n,S)\) T ( n , S ) , is the least natural number t such that, for any finite coloring of the size \(n\) n subsets of S, there exists \(S'\subseteq S\) S S such that (i) \(S'\) S is order-equivalent to S, and (ii) if the coloring is restricted to the size \(n\) n subsets of \(S'\) S then at most t colors are used. Mašulović & Šobot (2021) showed that \(T(n,\omega +\omega )=2^{n}\) T ( n , ω + ω ) = 2 n . From this one can obtain \(T(n,\zeta )=2^{n},\) T ( n , ζ ) = 2 n , where \(\zeta \) ζ is the ordered set of integers. We give a direct proof that \(T(n,\zeta )=2^{n}\) T ( n , ζ ) = 2 n . Mašulović and Šobot (2021) also showed that for all countable ordinals \(\alpha < \omega ^\omega \) α < ω ω and \(n\in \mathbb {N}\) n N , \(T(n,\alpha )\) T ( n , α ) is finite. We find exact values of \(T(n,\alpha )\) T ( n , α ) for all ordinals \(\alpha \) α less than \(\omega ^\omega \) ω ω and all \(n\in \mathbb {N}\) n N .