×

zbMATH — the first resource for mathematics

Combinatorial principles weaker than Ramsey’s theorem for pairs. (English) Zbl 1118.03055
The authors present the reverse mathematics and computability theory of the Chain-Antichain Principle (CAC) and the Ascending or Descending Sequence Principle (ADS). They split each of these principles into a stable version (analogous to stable Ramsey’s Theorem) and a cohesion principle (analogous to COH). They show that all these principles are incomparable with WKL\(_0\), and provide additional computability-theoretic and conservation results. Applying recent work on DNR by Hirschfeldt, Jockusch, Kjos-Hanssen, Lempp, and Slaman, they conclude that CAC does not prove Ramsey’s Theorem for pairs and two colors, settling a long-standing open question of P. A. Cholak, C. G. Jockusch, and T. A. Slaman [“On the strength of Ramsey’s theorem for pairs”, J. Symb. Log. 66, 1–55 (2001; Zbl 0977.03033)].

MSC:
03F35 Second- and higher-order arithmetic and fragments
03D80 Applications of computability and recursion theory
06A07 Combinatorics of partially ordered sets
03E05 Other combinatorial set theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Logic Year 1979–1980 859 pp 132–142– (1981)
[2] Model theory of algebra and arithmetic 834 pp 312–337– (1980)
[3] Systems of second order arithmetic with restricted induction I (abstract) 41 pp 557–558– (1976)
[4] Handbook of recursive mathematics 138–139 pp 823–976– (1998)
[5] A set with no infinite low subset in either it or its complement 66 pp 1371–1381– (2001)
[6] Jump equivalence of the hyperhyperimune sets 37 pp 598–600– (1972)
[7] On the strength of Ramsey’s Theorem for pairs 66 pp 1–55– (2001) · Zbl 0977.03033
[8] Mathematical Logic Quarterly 50 pp 628–636– (2004)
[9] Comparing DNR and WWKL 69 pp 1089–1104– (2004)
[10] Fundamenta Mathematicae 16 pp 386–389– (1930)
[11] Logic Colloquium ’69 (1971)
[12] Mathematical Logic Quarterly 39 pp 515–530– (1993)
[13] Transactions of the American Mathematical Society 173 pp 33–56– (1972)
[14] Ramsey’s Theorem and recursion theory 37 pp 268–280– (1972)
[15] Infinite chains and antichains in computable partial orderings 66 pp 923–934– (2001)
[16] Annals of Pure and Applid Logic 93 pp 103–113– (1998)
[17] Metamathematics of first-order arithmetic (1998) · Zbl 0889.03053
[18] Arithmetic, Proof Theory, and Computational Complexity (Prague, 1991) 23 pp 185–196– (1993)
[19] Algebra and Logic 12 pp 67–77– (1973)
[20] Archive for Mathematical Logic 30 pp 171–180– (1990)
[21] Subsystems of second order arithmetic (1999) · Zbl 0909.03048
[22] Handbook of mathematical logic pp 631–652– (1977)
[23] Notre Dame Journal of Formal Logic 36 pp 570–582– (1995)
[24] Linear orderings 98 (1982)
[25] Logic Colloquium ’77 96 pp 199–209– (1978)
[26] Located sets and reverse mathematics 65 pp 1451–1480– (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.