Characterizations of ordinal analysis

Annals of Pure and Applied Logic 174 (4):103230 (2023)
  Copy   BIBTEX

Abstract

Ordinal analysis is a research program wherein recursive ordinals are assigned to axiomatic theories. According to conventional wisdom, ordinal analysis measures the strength of theories. Yet what is the attendant notion of strength? In this paper we present abstract characterizations of ordinal analysis that address this question. First, we characterize ordinal analysis as a partition of $\Sigma^1_1$-definable and $\Pi^1_1$-sound theories, namely, the partition whereby two theories are equivalent if they have the same proof-theoretic ordinal. We show that no equivalence relation $\equiv$ is finer than the ordinal analysis partition if both: (1) $T\equiv U$ whenever $T$ and $U$ prove the same $\Pi^1_1$ sentences; (2) $T\equiv T+U$ for every set $U$ of true $\Sigma^1_1$ sentences. In fact, no such equivalence relation makes a single distinction that the ordinal analysis partition does not make. Second, we characterize ordinal analysis as an ordering on arithmetically-definable and $\Pi^1_1$-sound theories, namely, the ordering wherein $T\leq U$ if the proof-theoretic ordinal of $T$ is less than or equal to the proof-theoretic ordinal of $U$. The standard ways of measuring the strength of theories are consistency strength and inclusion of $\Pi^0_1$ theorems. We introduce analogues of these notions---$\Pi^1_1$-reflection strength and inclusion of $\Pi^1_1$ theorems---in the presence of an oracle for $\Sigma^1_1$ truths, and prove that they coincide with the ordering induced by ordinal analysis.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,069

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Proof theory and ordinal analysis.W. Pohlers - 1991 - Archive for Mathematical Logic 30 (5-6):311-376.
Ordinal analysis by transformations.Henry Towsner - 2009 - Annals of Pure and Applied Logic 157 (2-3):269-280.
An ordinal analysis of parameter free Π12-comprehension.Michael Rathjen - 2005 - Archive for Mathematical Logic 44 (3):263-362.
A Simplified Ordinal Analysis of First-Order Reflection.Toshiyasu Arai - 2020 - Journal of Symbolic Logic 85 (3):1163-1185.
Σ 1 -elementarity and Skolem hull operators.Gunnar Wilken - 2007 - Annals of Pure and Applied Logic 145 (2):162-175.
Ordinal operations on graph representations of sets.Laurence Kirby - 2013 - Mathematical Logic Quarterly 59 (1-2):19-26.
Characterizations of Ordinal Numbers in Set Theory.S. A. Cook & Hao Wang - 1968 - Journal of Symbolic Logic 33 (1):113-113.
A note on Gentzen’s ordinal assignment.Annika Kanckos - 2019 - Archive for Mathematical Logic 58 (3-4):347-352.
Assignment of Ordinals to Patterns of Resemblance.Gunnar Wilken - 2007 - Journal of Symbolic Logic 72 (2):704 - 720.
An ordinal analysis of stability.Michael Rathjen - 2005 - Archive for Mathematical Logic 44 (1):1-62.

Analytics

Added to PP
2023-01-05

Downloads
15 (#834,700)

6 months
2 (#785,137)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

James Walsh
New York University

Citations of this work

No citations found.

Add more citations