Sage Journals: Discover world-class research

Abstract

We investigate the reverse mathematics strength of Martin’s pointed tree theorem ( $MPT$ ) and one of its variants, weak Martin’s pointed tree theorem ( $wMPT$ ).

Keywords

Reverse mathematics algorithmic randomness Martin’s pointed tree theorem weak Martin’s pointed tree theorem

Get full access to this article

View all access options for this article.

References

Blass, Complexity of winning strategies, Discrete Mathematics 3 (1972), 295–300.

C.T.

Chong and

Yu, Maximal chains in the Turing degrees, The Journal of Symbolic Logic 72(4) (2007), 1219–1227.

R.G.

Downey and

D.R.

Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010.

L.A.

Harrington, Analytic determinacy and

0^{♯}

, The Journal of Symbolic Logic 43(4) (1978), 685–693.

L.A.

Harrington and

A.S.

Kechris, A basis result for

Σ_{3}^{0}

sets of reals with an application to minimal covers, Proceedings of the American Mathematical Society 53(2) (1975), 445–448.

C.G.

JockuschJr. and

R.I.

Soare,

Π_{1}^{0}

classes and degrees of theories, Transactions of the American Mathematical Society 173 (1972), 33–56.

Koellner and

W.H.

Woodin, Large cardinals from determinacy, in: Handbook of Set Theory,

Foreman and

Kanamori, eds, Springer, Netherlands, 2010, pp. 1951–2119.

Lerman, Degrees of Unsolvability, Perspectives in Mathematical Logic, Springer, Berlin, 1983.

D.A.

Martin, The axiom of determinateness and reduction principles in the analytical hierarchy, Bulletin of the American Mathematical Society 74 (1968), 687–689.

10.

D.A.

Martin and

J.R.

Steel, A proof of projective determinacy, Journal of the American Mathematical Society 2(1) (1989), 71–125.

11.

J.S.

Miller and

Yu, On initial segment complexity and degrees of randomness, Transactions of the American Mathematical Society 360(6) (2008), 3193–3210.

12.

Montalbán and

Shore, The strength of Turing determinacy within second order arithmetic, Fundamenta Mathematicae, to appear.

13.

Y.N.

Moschovakis, Descriptive Set Theory, 2nd edn, Mathematical Surveys and Monographs, Vol. 155, American Mathematical Society, Providence, RI, 2009.

14.

Nies, Computability and Randomness, Oxford Logic Guides, Vol. 51, Oxford Univ. Press, Oxford, 2009.

15.

Odifreddi, Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, Vol. 125, North-Holland, Amsterdam, 1989.

16.

G.E.

Sacks, Higher Recursion Theory, Perspectives in Mathematical Logic, Springer, Berlin, 1990.

17.

S.G.

Simpson, Subsystems of Second Order Arithmetic, Perspectives in Logic, 2nd edn, Cambridge Univ. Press, Cambridge, 2009.

18.

T.A.

Slaman and

J.R.

Steel, Definable functions on degrees, in: Cabal Seminar 81–85, Lecture Notes in Mathematics, Vol. 1333, Springer, Berlin, 1988, pp. 37–55.

19.

R.M.

Solovay, A model of set-theory in which every set of reals is Lebesgue measurable, Annals of Mathematics 2(92) (1970), 1–56.

20.

Steel, Determinateness and subsystems of analysis, PhD thesis, University of California, Berkeley, 1976.

On Martin’s pointed tree theorem

Abstract

Keywords

Get full access to this article

References