Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-19T03:14:13.104Z Has data issue: false hasContentIssue false

THE STRENGTH OF THE TREE THEOREM FOR PAIRS IN REVERSE MATHEMATICS

Published online by Cambridge University Press:  01 December 2016

LUDOVIC PATEY*
Affiliation:
LABORATOIRE PPS UNIVERSITÉ PARIS-DIDEROT - PARIS 7 CASE 7014, 75205 PARIS CEDEX 13 FRANCE E-mail: ludovic.patey@computability.fr URL: http://ludovicpatey.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

No natural principle is currently known to be strictly between the arithmetic comprehension axiom (ACA0) and Ramsey’s theorem for pairs ( $RT_2^2$ ) in reverse mathematics. The tree theorem for pairs ( $TT_2^2$ ) is however a good candidate. The tree theorem states that for every finite coloring over tuples of comparable nodes in the full binary tree, there is a monochromatic subtree isomorphic to the full tree. The principle $TT_2^2$ is known to lie between ACA0 and $RT_2^2$ over RCA0, but its exact strength remains open. In this paper, we prove that $RT_2^2$ together with weak König’s lemma (WKL0) does not imply $TT_2^2$ , thereby answering a question of Montálban. This separation is a case in point of the method of Lerman, Solomon and Towsner for designing a computability-theoretic property which discriminates between two statements in reverse mathematics. We therefore put the emphasis on the different steps leading to this separation in order to serve as a tutorial for separating principles in reverse mathematics.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2016