Effectiveness for infinite variable words and the Dual Ramsey Theorem

&
Archive for Mathematical Logic 43 (4):543-555 (2004)
  Copy   BIBTEX

Abstract

We examine the Dual Ramsey Theorem and two related combinatorial principles VW(k,l) and OVW(k,l) from the perspectives of reverse mathematics and effective mathematics. We give a statement of the Dual Ramsey Theorem for open colorings in second order arithmetic and formalize work of Carlson and Simpson [1] to show that this statement implies ACA 0 over RCA 0 . We show that neither VW(2,2) nor OVW(2,2) is provable in WKL 0 . These results give partial answers to questions posed by Friedman and Simpson [3]

Categories

Keywords

Reprint years

DOI

10.1007/s00153-004-0216-4

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Symmetries between two Ramsey properties.Lorenz Halbeisen - 1998 - Archive for Mathematical Logic 37 (4):241-260.
Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
The polarized Ramsey’s theorem.Damir D. Dzhafarov & Jeffry L. Hirst - 2009 - Archive for Mathematical Logic 48 (2):141-157.
Reverse mathematics and Ramsey's property for trees.Jared Corduan, Marcia J. Groszek & Joseph R. Mileti - 2010 - Journal of Symbolic Logic 75 (3):945-954.
The Strength of the Rainbow Ramsey Theorem.Barbara F. Csima & Joseph R. Mileti - 2009 - Journal of Symbolic Logic 74 (4):1310 - 1324.
On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
A generalization of the Dual Ellentuck Theorem.Lorenz Halbeisen & Pierre Matet - 2003 - Archive for Mathematical Logic 42 (2):103-128.
On the strength of Ramsey's theorem for pairs.Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman - 2001 - Journal of Symbolic Logic 66 (1):1-55.
Combinatorial principles weaker than Ramsey's Theorem for pairs.Denis R. Hirschfeldt & Richard A. Shore - 2007 - Journal of Symbolic Logic 72 (1):171-206.
Ramsey’s theorem for trees: the polarized tree theorem and notions of stability. [REVIEW]Damir D. Dzhafarov, Jeffry L. Hirst & Tamara J. Lakins - 2010 - Archive for Mathematical Logic 49 (3):399-415.
A Simple Proof and Some Difficult Examples for Hindman's Theorem.Henry Towsner - 2012 - Notre Dame Journal of Formal Logic 53 (1):53-65.
A recursion theoretic analysis of the clopen Ramsey theorem.Peter Clote - 1984 - Journal of Symbolic Logic 49 (2):376-400.
A game‐theoretic proof of analytic Ramsey theorem.Kazuyuki Tanaka - 1992 - Mathematical Logic Quarterly 38 (1):301-304.
Enormous integers in real life.Harvey Friedman - manuscript

Analytics

Added to PP
2013-11-23

Downloads
422 (#44,820)

6 months
8 (#342,364)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Open questions in reverse mathematics.Antonio Montalbán - 2011 - Bulletin of Symbolic Logic 17 (3):431-454.
Borel combinatorics fail in HYP.Henry Towsner, Rose Weisshaar & Linda Westrick - 2022 - Journal of Mathematical Logic 23 (2).

Add more citations

References found in this work

Subsystems of Second Order Arithmetic.Stephen G. Simpson - 1999 - Studia Logica 77 (1):129-129.

Add more references