Elementary patterns of resemblance (Q5935985)

This article is part of a series of planned papers (which started with the author's paper ``Ordinal arithmetic and \(\Sigma_1\)-elementarity'' [Arch. Math. Logic 38, No.~7, 449-460 (1999; Zbl 0936.03055)]) with the goal of providing an alternative approach for introducing ordinal notation systems and ultimately reaching the proof-theoretic ordinal of \(\Pi^1_2\)-CA. In the article under review, basic notions are explored which are expected to reach the strength of KP\textit{l}\(_0\) (more precisely, this is expected to be the ordinal of the core, see below). The approach taken is closely related to \(\Pi^1_2\)-logic. The main structure in this article is \(\mathcal{R}_1:= (\text{ORD},0,+,\leq,\leq_1)\), where ORD is the set of ordinals and \(\leq_1\) is defined recursively by \(\alpha \leq_1 \beta \Leftrightarrow (\alpha,0,+,\leq,\leq_1) \preceq_{\Sigma_1} (\beta,0,+,\leq,\leq_1)\). Function symbols in this article are always treated as partial functions. One easily sees that for instance \(\forall 0 < \xi < \alpha.\alpha \leq_1 \alpha + \xi \leftrightarrow \exists \beta.\alpha = \omega^{\omega^\xi \cdot \beta}\) and \(\forall 0 < \xi < \alpha.\alpha \leq_1 \alpha \cdot (1 + \xi) \leftrightarrow \exists \beta.\alpha = \varphi_\xi \beta\), further \(\forall 0 < \alpha.\alpha \leq_1 \alpha^2 \leftrightarrow \exists \beta.\alpha = \Gamma_\beta\). A finite substructure of \(\mathcal{R}_1\) which is minimal in the pointwise ordering of the collection of all finite substructures of \(\mathcal{R}_1\) isomorphic to it is called isominimal, and the set of ordinals occurring in some isominimal substructure of \(\mathcal{R}_1\) is called the core. A substructure \({\mathbf A}\) of \(\mathcal{R}_1\) is closed, if \(0 \in {\mathbf A} \) and \(\alpha_1 + \cdots + \alpha_n \in {\mathbf A} \) for indecomposables \(\alpha_i\) (i.e. \(\alpha_i\) that cannot be formed from other elements using function symbols and constants), \(\alpha_1 \geq \cdots \geq \alpha_n\) implies \(\alpha_1 + \cdots + \alpha_i \in {\mathbf A} \) and \(\alpha_i \in {\mathbf A} \). For fixed finite closed substructures \({\mathbf P} \) of \(\mathcal{R}_1\) there exists a unique isominimal substructure \({\mathbf P}^\ast \) of \(\mathcal{R}_1\) isomorphic to it, and therefore the set of pairs \(({\mathbf A},x)\), where \({\mathbf A} \) is a closed finite isominimal substructure of \(\mathcal{R}_1\) and \(x\) is an element of \({\mathbf A} \), forms an ordinal notation system for the core. The goal of this article is to introduce structures equivalent to this notion (and related ones). In Section 3, the additive structures, i.e. structures \(\{0,+,\leq\}\) with a reasonable side condition on \(+\), are considered, and the extension of finite structures by incrementing them by one sum (Definition 3.14) and by reflecting a set \(X\) below some \(a\) (essentially a collapsing operation in the sense of proof theory; Definition 3.16) is explored. In Section 4, additive patterns of resemblance of order one, in short patterns, which extend additive structures by an order \(\leq_1\) with reasonable conditions (Definition 4.2), are introduced. A pattern \({\mathbf P^+}\) formed from a pattern \({\mathbf P}\) by adding sums and by reflection is called exactly generated (Definition 4.9). In Section 5, coverings, which are essentially embeddings between patterns (Definition 5.1) are studied. A pattern is covered iff there is a covering of it into \(\mathcal{R}_1\) (Definition 5.4). By successively incrementing a pattern by adding sums and reflection, one can obtain from covered patterns \({\mathbf P}\) first an isominimal initial segment of \(\mathcal{R}_1\) and from this an isomorphic isominimal substructure \({\mathbf P^\ast}\) of \(\mathcal{R}_1\) (Lemma 5.8 and Theorem 5.9). From this it follows that if there exists a \(\kappa \) s.t. \(\kappa \leq_1 \alpha\) for all \(\alpha > \kappa \), then the least such \(\kappa \) is the core of \(\mathcal{R}_1\), provable in KP + infinity (Theorem 5.12). In Section 6, amalgamations are studied (Definition 6.5), which are roughly a notion of forming the union of patterns. Covered patterns have unique amalgamations (Theorem 6.7). In Definition 6.8 the structure \(\mathcal{C}_1\) of pointed covered patterns, i.e. covered patterns with an element, are introduced, and Theorem 6.10 shows that if every pattern is covered, then the collection of hereditarily finite pointed covered patterns is a recursive structure (provable in KP + infinity). In Section 7, in \(\text{I} \Sigma_0(\text{exp})\) the existence of unique amalgamations (Lemmas 7.12 and 7.13) is shown. The prestructure of pointed patterns \(\mathcal{P}_1\) is introduced, and it is shown (in \(\text{I} \Sigma_0(\text{exp})\)) that the ordering on \(\mathcal{P}_1\) fulfils the same recursive law as \(\leq_1\) (Theorem 7.24). It is shown (Theorem 8.5) that \(\mathcal{C}_1/\mathord{=}\) is the largest initial segment of the well-founded part of \(\mathcal{P}_1/\mathord{=}\) which is correct in \(\mathcal{P}_1/\mathord{=}\) (this notion was introduced in Definition 4.12), and that \(\mathcal{C}_1/\mathord{=}\) is (isomorphically) contained in the core of \(\mathcal{R}_1/\mathord{=}\). In Theorem 9.1, it is shown that the core of any reasonable analogue of \(\mathcal{R}_1\) is isomorphic to an initial segment of \(\mathcal{R}_1\) (provable in KP + infinity) and (provable in ZF, remark at the end of this section) isomorphic to the core itself. In Section 10, pure patterns, i.e. patterns in which the additive structure is omitted, are investigated and an alternative proof to that in the author's earlier paper [loc. cit.] is given that the core is \(\varepsilon_0\) in this case (Theorem 10.1). In Sections 11 and 12, the changes required when adding the Veblen function to additive patterns (of resemblance one) are explored. This is a very rich article, densely packed with interesting notions. Unfortunately, it is difficult to find out what exactly the author is aiming at.