×

Normal forms for elementary patterns. (English) Zbl 1275.03154

In this paper the authors develop an ordinal notation system for the proof-theoretic ordinal of \(\mathrm{KP}\l_0\) based on patterns of resemblance of order one. A pattern of resemblance of order one (henceforth: pattern) is a finite structure in the language \((0,+,\leq,\leq_1)\) that is isomorphic to a substructure of \(R_1=(\mathrm{ORD},0,+,\leq,\leq_1)\) where \(\leq_1\) is defined inductively by specifying that \(a \leq_1 b\) iff \((a,0,+,\leq,\leq_1)\) is a \(\Sigma_1\) elementary substructure of \((b,0,+,\leq,\leq_1)\).
Patterns provide notations for ordinals in the following way. To a given pattern one associates the unique substructure \(X\) of \(R_1\) that is minimal in the pointwise ordering among all substructures of \(R_1\) isomorphic to \(P\) (such a structure is called isominimal). The pair \((P,a)\) where \(a\in P\) is then a notation for the corresponding ordinal in \(X\). Notations of this form are not unique as a given ordinal may appear in many different isominimal sets. The central result of the article is that amongst all isominimal structures containing a given ordinal there exists a minimal such one (Theorem 4.6). Moreover, the minimal candidate can be computed and thus a notation systems for all notatable ordinals constructed.
The resulting notation system plays an important role in the analysis of patterns of higher order; see [the authors, Ann. Pure Appl. Logic 163, No. 1, 23–67 (2012; Zbl 1273.03159)]. Although the article assumes familiarity with the subject, the authors do provide an accessible summary of the important definitions and theorems necessary for the results up to the uniqueness of minimal isominimal sets (Section 4). The remainder of the paper is devoted to computing the sets and refers heavily to [the second author, J. Symb. Log. 72, No. 2, 704–720 (2007; Zbl 1121.03081)].

MSC:

03F15 Recursive ordinals and ordinal notations
PDF BibTeX XML Cite
Full Text: DOI Euclid

References:

[1] W. Buchholz, E. A. Cichon, and A. Weiermann A uniform approach to fundamental sequences and hierarchies , Mathematical Logic Quarterly , vol. 40(1994), pp. 273-286. · Zbl 0812.03023
[2] T. J. Carlson Ordinal arithmetic and \(\Sigma_1\) -elementarity, Archive for Mathematical Logic , vol. 38(1999), pp. 449-460. · Zbl 0936.03055
[3] —- Elementary patterns of resemblance , Annals of Pure and Applied Logic , vol. 108(2001), pp. 19-77. · Zbl 1009.03026
[4] —- Patterns of resemblance of order 2 , Annals of Pure and Applied Logic , vol. 158(2009), pp. 90-124. · Zbl 1206.03050
[5] T. J. Carlson and G. Wilken Tracking chains of \(\Sigma_2\) -elementarity, submitted. · Zbl 0611.33004
[6] G. Wilken The Bachmann-Howard structure in terms of \(\Sigma_1\)-elementarity, Archive for Mathematical Logic , vol. 45(2006), pp. 807-829. · Zbl 1110.03053
[7] —- Assignment of ordinals to elementary patterns of resemblance , Journal of Symbolic Logic, vol. 72(2007), no. 2, pp. 704-720. · Zbl 1121.03081
[8] —- Ordinal arithmetic based on Skolem hulling, Annals of Pure and Applied Logic , vol. 145(2007), no. 2, pp. 130-161. · Zbl 1117.03063
[9] —- \(\Sigma_1\) -elementarity and Skolem hull operators, Annals of Pure and Applied Logic , vol. 145(2007), no. 2, pp. 162-175. · Zbl 1117.03064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.