On the strength of Ramsey's theorem for trees

2020 
Abstract Let TT 1 denote the principle that every finite coloring of the full binary tree has a homogeneous isomorphic subtree, i.e. one that is monochromatic. We show that over the system RCA 0 , the inductive strength of TT 1 is weaker than Σ 2 0 -induction. This follows from the main theorem that over the same system, TT 1 is Π 1 1 -conservative over Σ 2 0 -bounding plus the principle of the totality of the Ackermann function.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    14
    References
    2
    Citations
    NaN
    KQI
    []