Pure patterns of order 2

Abstract

We provide mutual elementary recursive order isomorphisms between classical ordinal notations, based on Skolem hulling, and notations from pure elementary patterns of resemblance of order $2$, showing that the latter characterize the proof-theoretic ordinal of the fragment ${\Pi }_1^1$-${\mathrm{CA}}_0$ of second order number theory, or equivalently the set theory ${\mathrm{KPl}}_0$. As a corollary, we prove that Carlson's result on the well-quasi orderedness of respecting forests of order $2$ implies transfinite induction up to the ordinal of ${\mathrm{KPl}}_0$. We expect that our approach will facilitate analysis of more powerful systems of patterns.

corrected Theorem 4.2 with according changes in section 3 (mainly Definition 3.3), results unchanged. The manuscript was edited, aligned with reference [14] (moving former Lemma 3.5 there), and argumentation was revised, with minor corrections in (the proof of) Theorem 4.2; results unchanged. Updated revised preprint; to appear in the APAL (2017)

References in corpus (1)

• Tracking chains revisited

Cited by in corpus (3)

• Tracking chains revisited
• Pure ${\Sigma }_2$-Elementarity beyond the Core
• Fundamental sequences based on localization