How do ordinals measure the strength and computational power of formal theories? This paper is concerned with the connection between ordinal representation systems and theories established in ordinal analyses. It focusses on results which explain the nature of this connection in terms of semantical and computational notions from model theory, set theory, and generalized recursion theory.

Elementary patterns of resemblance notate ordinals up to the ordinal of Pi^1_1-CA_0. We provide ordinal multiplication and exponentiation algorithms using these notations.

We construct a machine that knows its own code, at the price of not knowing its own factivity.

Taking up ordinal notations derived from Skolem hull operators familiar in the field of infinitary proof theory we develop a toolkit of ordinal arithmetic that generally applies whenever ordinal structures are analyzed whose combinatorial complexity does not exceed the strength of the system of set theory. The original purpose of doing so was inspired by the analysis of ordinal structures based on elementarity invented by T.J. Carlson, see [T.J. Carlson, Elementary patterns of resemblance, Annals of Pure and Applied Logic 108 (...) 19–77], [G. Wilken, Σ1-Elementarity and Skolem hull operators, Annals of Pure and Applied Logic 145 162–175], and [G. Wilken, Assignment of ordinals to patterns of resemblance, The Journal of Symbolic Logic ]. Within the arithmetical context laid bare in this work, the “-numbers” play a role analogous to the role epsilon numbers play in the ordinal arithmetic based on the notion of Cantor normal form. (shrink)

We investigate the extent to which structures consisting of sequences of forests on the same underlying set are well-quasi-ordered under embeddings.

This article provides a detailed comparison between two systems of collapsing functions. These functions play a crucial role in proof theory, in the analysis of patterns of resemblance, and the analysis of maximal order types of well partial orders. The exact correspondence given here serves as a starting point for far reaching extensions of current results on patterns and well partial orders. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

The Bachmann-Howard structure, that is the segment of ordinal numbers below the proof theoretic ordinal of Kripke-Platek set theory with infinity, is fully characterized in terms of CARLSON’s approach to ordinal notation systems based on the notion of Σ1-elementarity.

The exact correspondence between ordinal notations derived from Skolem hull operators, which are classical in ordinal analysis, and descriptions of ordinals in terms of Σ1-elementarity, an approach developed by T.J. Carlson, is analyzed in full detail. The ordinal arithmetical tools needed for this purpose were developed in [G. Wilken, Ordinal arithmetic based on Skolem hulling, Annals of Pure and Applied Logic 145 130–161]. We show that the least ordinal κ such that κ<1∞ 19–77] and described below) is the proof theoretic (...) ordinal of the set-theoretic system , confirming a claim of Carlson. Moreover, we characterize the class of all ordinals κ such that κ<1∞ and provide an ordinal arithmetical analysis of Carlson’s entire structure in the style of [T.J. Carlson, Ordinal arithmetic and Σ1-elementarity, Archive for Mathematical Logic 38 449–460]. (shrink)

We will investigate patterns of resemblance of order 2 over a family of arithmetic structures on the ordinals. In particular, we will show that they determine a computable well ordering under appropriate assumptions.

A notation for an ordinal using patterns of resemblance is based on choosing an isominimal set of ordinals containing the given ordinal. There are many choices for this set meaning that notations are far from unique. We establish that among all such isominimal sets there is one which is smallest under inclusion thus providing an appropriate notion of normal form notation in this context. In addition, we calculate the elements of this isominimal set using standard notations based on collapsing functions. (...) This provides a capstone to the results in [2, 6, 8, 9, 7], using further refinement of ordinal arithmetic developed in [8] which then both allows for a simple characterization of normal forms for patterns of order one and will play a key role in the arithmetical analysis of pure patterns of order two, [5]. (shrink)