The Strength of Ramsey's Theorem For Pairs over trees: I. Weak König's Lemma

Abstract

Let ${\mathsf{TT}}_k^2$ denote the combinatorial principle stating that every $k$-coloring of pairs of compatible nodes in the full binary tree has a homogeneous solution, i.e. an isomorphic subtree in which all pairs of compatible nodes have the same color. Let ${\mathsf{WKL}}_0$ be the subsystem of second order arithmetic consisting of the base system ${\mathsf{RCA}}_0$ together with the principle (called Weak König's Lemma) stating that every infinite subtree of the full binary tree has an infinite path. We show that over ${\mathsf{RCA}}_0$, ${\mathsf{TT}}_k^2$ doe not imply ${\mathsf{WKL}}_0$. This solves the open problem on the relative strength between the two major subsystems of second order arithmetic.

24pages

References in corpus (1)

• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs