Ramsey's theorem

Apr 19, 2026 - 06:12
0 0
Ramsey's theorem

Fixed a reference. Please see Category:CS1 errors: dates.

← Previous revision Revision as of 00:40, 19 April 2026
Line 506: Line 506:
Also, let c: \N^2 \to \{1, 2, \dots, k\} be a ''k''-coloring of the complete graph on \N. It is a '''stable coloring''' iff \forall n\in \N, there exists some color i, such that c(n, m) = i for all large enough ''m''. The '''Stable Ramsey's Theorem for Pairs''' SRT^2_k is defined as Ramsey's theorem for when we stably k-color the edges of the complete graph on \N. This is a weakening on RT^2_k, since by definition, we have RT^2_k \vdash SRT^2_k.
Also, let c: \N^2 \to \{1, 2, \dots, k\} be a ''k''-coloring of the complete graph on \N. It is a '''stable coloring''' iff \forall n\in \N, there exists some color i, such that c(n, m) = i for all large enough ''m''. The '''Stable Ramsey's Theorem for Pairs''' SRT^2_k is defined as Ramsey's theorem for when we stably k-color the edges of the complete graph on \N. This is a weakening on RT^2_k, since by definition, we have RT^2_k \vdash SRT^2_k.


Over the system of [[RCA0|RCA0]], we have{{Cite book |last=Simpson |first=Stephen G. |title=Subsystems of second order arithmetic |date=2010 |publisher=Cambridge University Press |others=Association for Symbolic Logic |isbn=978-0-521-15014-9 |edition=2. ed., digitally print. version |series=Perspectives in logic |location=Cambridge New York Melbourne Madrid Cape Towon Singapore Sao Paulo Delhi Dubai Tokyo}}{{cite thesis |last=Hirst |first=Jeffry Lynn |title=Combinatorics in Subsystems of Second Order Arithmetic |date=1987-08 |type=PhD thesis |publisher=The Pennsylvania State University |url=https://www.proquest.com/docview/303611646 |url-access=subscription |id=ProQuest 303611646}}{{cite book |last=Hirschfeldt |first=Denis R. |title=Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles |date=2014 |publisher=World Scientific |isbn=9789814612630 |series=Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore |volume=28 |doi=10.1142/9208}}
Over the system of [[RCA0|RCA0]], we have{{Cite book |last=Simpson |first=Stephen G. |title=Subsystems of second order arithmetic |date=2010 |publisher=Cambridge University Press |others=Association for Symbolic Logic |isbn=978-0-521-15014-9 |edition=2. ed., digitally print. version |series=Perspectives in logic |location=Cambridge New York Melbourne Madrid Cape Towon Singapore Sao Paulo Delhi Dubai Tokyo}}{{cite thesis |last=Hirst |first=Jeffry Lynn |title=Combinatorics in Subsystems of Second Order Arithmetic |date=August 1987 |type=PhD thesis |publisher=The Pennsylvania State University |url=https://www.proquest.com/docview/303611646 |url-access=subscription |id=ProQuest 303611646}}{{cite book |last=Hirschfeldt |first=Denis R. |title=Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles |date=2014 |publisher=World Scientific |isbn=9789814612630 |series=Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore |volume=28 |doi=10.1142/9208}}


* RT^1_{<\infty} is the [[Pigeonhole principle#Infinite sets|infinite pigeonhole principle]].
* RT^1_{<\infty} is the [[Pigeonhole principle#Infinite sets|infinite pigeonhole principle]].
Read More