Reverse mathematics and well-ordering principles: a pilot study
type: Item
instance of: scholarly article
title: Reverse mathematics and well-ordering principles: a pilot study
zbMATH Open document ID: 1183.03008
author: Bahareh Afshari
author: Michael Rathjen
published in: Annals of Pure and Applied Logic
publication date: 2009-10-26T00:00:00Z
review text: This paper is part of the larger project of studying the proof-theoretic and computability-theoretic complexity of sentences of the form ``if \(X\) is well-ordered then \(f(X)\) is well-ordered'', where \(f\) is a function from linear ordering to linear orderings that maps ordinals to ordinals. It has turned out that, when \(f\) is a standard proof-theoretic function, a statement of this form is often equivalent to the existence of countable coded \(\omega \)-models for a particular theory \(T_f\) whose consistency can be proved by means of a cut-elimination theorem in infinitary logic which crucially involves the function \(f\). To illustrate this theme, the authors prove in this paper that the statement ``if \(X\) is well-ordered then \(\varepsilon_X\) is well-ordered'' is equivalent to \(\text{ACA}_0^+\). This result was first proved by \textit{A. Marcone} and \textit{A. Montalbán} [``The Veblen functions for computability theorists'' (to appear)] using computability-theoretic and combinatorial methods to code the \(\omega\)-Turing jump. The proof given here is principally proof-theoretic, the main techniques being Schütte's method of proof search (deduction chains) [\textit{K. Schütte}, Proof theory. Berlin-Heidelberg-New York: Springer-Verlag (1977; Zbl 0367.02012)] and cut elimination for a (small) fragment of \(\mathcal L_{\omega_1,\omega}\). It is remarkable how the same result has two such different proofs.
reviewed by: Antonio Montalbán
Mathematics Subject Classification ID: 03B30
Mathematics Subject Classification ID: 03F05
Mathematics Subject Classification ID: 03F15
Mathematics Subject Classification ID: 03F35
zbMATH DE Number: 5620636
zbMATH Keywords: reverse mathematics
zbMATH Keywords: well-ordering principles
zbMATH Keywords: Schütte deduction chains
zbMATH Keywords: countable coded \(\omega\)-models
zbMATH Keywords: ACA\(^+_0\)
MaRDI profile type: Publication
OpenAlex ID: W2155734270
cites work: Elementary descent recursion and proof theory
cites work: Q3773876
cites work: Reverse mathematics and ordinal exponentiation
cites work: Bar induction and \(\omega\) model reflection
cites work: Proof theory. An introduction
cites work: The role of parameters in bar rule and bar induction
cites work: Reverse mathematics and well-ordering principles
cites work: Q4143279
cites work: Q4220572
cites work: Q3140643
cites work: Descending sequences of degrees
DOI: 10.1016/J.APAL.2009.01.001
Recommended article: Reverse mathematics and well-ordering principles
Recommended article: Q3464624
Recommended article: Proof Pearl: Wellfounded Induction on the Ordinals Up to ε 0
Recommended article: Q3218108
Recommended article: Ordinal Analysis and the Infinite Ramsey Theorem
Recommended article: The Veblen functions for computability theorists
Recommended article: Reverse mathematics and the equivalence of definitions for well and better quasi-orders
Recommended article: Variation on a theme of Schütte
Recommended article: Well-Ordering Principles in Proof Theory and Reverse Mathematics
Recommended article: Tree Automata Make Ordinal Theory Easy
description: scientific article; zbMATH DE number 5620636