Systems of iterated projective ordinal notations and combinatorial statements about binary labeled trees
type: Item
instance of: scholarly article
title: Systems of iterated projective ordinal notations and combinatorial statements about binary labeled trees
zbMATH Open document ID: 0691.03039
DOI: 10.1007/BF01630809
published in: Archive for Mathematical Logic
publication date: 1989-01-01T00:00:00Z
review text: A notation system \underbar{PRJ}(P) for ordinals is defined where P is a fixed given primitive recursive well-ordering of the natural numbers without last element. The terms of the system are called iterated projective ordinal notations, using the expression projective instead of collapsing. The elements \(\nu\) of P act as projective points \(\Omega_{\nu}\), the so-called projective functions \(D_{\nu}\) constitute terms less than \(\Omega_{\nu}\). The functions \(D_{\nu}\) are similar to the \(\psi\)-functions of \textit{W. Buchholz} [Ann. Pure Appl. Logic 32, 195-207 (1986; Zbl 0655.03038)] but are developed generalizing the D-functions of the author [ibid. 38, No.1, 1-121 (1988)]. The well-ordering proof for \underbar{PRJ}(P) is given using on one hand the fact that the set \({\mathfrak T}^ 2(P)\) of the binary trees labelled by elements of P is a well-quasi-ordering with respect to some suitably modified embedding relation [cf. the author's paper in J. Symb. Logic 55, p. 157 (1990)], and on the other hand \underbar{PRJ}(P) is mapped into \({\mathfrak T}^ 2(P)\) in such a way that the relation between trees is carried over to the ordinal terms. The relation between the notations of the system \underbar{PRJ}(P) and the Veblen-Bachmann-hierarchy is outlined. The functions \(\phi_{\alpha}\) of this hierarchy and fundamental sequences are defined in \underbar{PRJ}(P) and illustrated by an example. The \(\epsilon\)- and \(\Gamma\)-numbers are denoted in the setting of \underbar{PRJ}(P). The system OT(P) of ordinal terms defined by Buchholz [loc. cit.] for \(P=\omega\) is described in \underbar{PRJ}(P) and an embedding is established. Finally, using the well-known idea of Friedman's, it is shown that some \(\Pi^ 0_ 2\)-sentences concerning the well-quasi-ordering of certain sets of binary trees labelled with ordinals cannot be proved in the corresponding theories of iterated inductive definitions. The proof uses the restriction of the already mentioned mapping from \u…
Mathematics Subject Classification ID: 03F15
zbMATH DE Number: 4130377
zbMATH Keywords: reverse mathematics
zbMATH Keywords: well-ordering
zbMATH Keywords: iterated projective ordinal notations
zbMATH Keywords: D-functions
zbMATH Keywords: Veblen-Bachmann-hierarchy
zbMATH Keywords: well-quasi-ordering
zbMATH Keywords: binary trees
zbMATH Keywords: iterated inductive definitions
zbMATH Keywords: labelled trees
author: L. N. Gordeev
reviewed by: Helmut Pfeiffer
MaRDI profile type: Publication
cites work: Iterated inductive definitions and subsystems of analysis: recent proof-theoretical studies
cites work: A new system of proof-theoretic ordinal functions
cites work: An independence result for \((\Pi^ 1_ 1-CA)+BI\)
cites work: Q4040375
cites work: Proof-theoretical analysis: Weak systems of functions and classes
cites work: Generalizations of the one-dimensional version of the Kruskal-Friedman theorems
cites work: ϱ-inaccessible ordinals, collapsing functions and a recursive notation system
cites work: Majorisier Ungsrelationen und Fundamentalfolgen eines Ordinalzahlensystems von G. Jäger
cites work: Eine Erweiterung T(V') des Ordinalzahlensystems \(C_{\Omega}(\Lambda _ 0)\) von G. Jäger. (An extension T(V') of the ordinal system \(C_{\Omega}(\Lambda _ 0)\) by G. Jäger)
cites work: Proof theory. 2nd ed
full work available at URL: https://doi.org/10.1007/bf01630809
OpenAlex ID: W2065310207
Recommended article: A Combinatorial Theorem for Trees
Recommended article: Q2933462
Recommended article: Trees, ordinals and termination
Recommended article: On trees and tree dimension of ordered sets
Recommended article: A REFINED ENUMERATION OF p-ARY LABELED TREES
Recommended article: A bijection on ordered trees and its consequences
Recommended article: New Computational Paradigms
Recommended article: A REFINEMENT FOR ORDERED LABELED TREES
Recommended article: Q5308878
Recommended article: Q3765761
description: scientific article; zbMATH DE number 4130377