# Questions tagged [ordinal-analysis]

In proof theory, ordinal analysis assigns ordinals to mathematical theories as a measure of their strength. If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory has a larger proof-theoretic ordinal than another it can often prove the consistency of the second theory.

22 questions
Filter by
Sorted by
Tagged with
70 views

### Why do we need ordinal representation systems?

Trying to learn about ordinal analysis and I keep seeing the concept of the natural ordinal representation system, for representing ordinals as relations on N. In particular the definition of an ...
85 views

### Higher order arithmetic, hierarchies and proof theoretic ordinals

I would like to consider a generalization of the notation $\Pi$ and $\Sigma$ used for the arithmetical hierarchy $(\Pi^0_n$, $\Sigma^0_n)$ and the analytical hierarchy $(\Pi^1_n$, $\Sigma^1_n)$ to ...
78 views

### Is there a sequence of extensions of ZFC where the corresponding sequence of proof theoretic ordinals has $\omega_1^{CK}$ as least upper-bound

I was reading this question on MO where they define an infinite sequence of extensions of ZF by creating iteratively a new theory which includes the consistency of the previous ones. The definition ...
119 views

### Is Goodstein's theorem equivalent to $\varepsilon_0$-induction over weak base theories (e.g. PRA)?

Is Goodstein's theorem equivalent to $\varepsilon_0$-induction over a weak base theory like PRA? I'm surprised this hasn't been asked here before (as far as I can tell).
55 views

### Turing degrees of subsets of Kleene $\mathcal{O}$ which are ordinal notations of subsets of the set of recursive ordinals

An ordinal $\alpha$ is said to be recursive if there is a recursive well-ordering of a subset of the natural numbers having the order type $\alpha$. The smallest ordinal that is not recursive is ...
38 views

### Equation to Specify Lexicographical Ordering?

I am not a mathematician, but I need to specify, precisely, a special way to sort an arbitrary list of ASCII strings1, with the addition of some special rules for a small set of specific characters. I ...
87 views

### Optimal bound for cost of cut elimination in infinitary logic with transfinite cut-rank in terms of Veblen's $\varphi$ function

The theorem I am referring to is Tait's sharpening of Gentzen's Cut Elimination Theorem in , which Schütte [2, p. 204, Theorem 22.8] also calls the second cut elimination theorem'' (here written ...
63 views

### Infinite ordinals in proof theory

I've been trying to get acquainted with proof theory (particularly ordinal analysis) as part of a school project, and am trying to tease out the story behind the appearance of infinite ordinals in a ...
94 views

### Proof-theoric ordinal of ETCS

What is the proof-theoric ordinal of Lawvere's elementary theory of the category of sets?
53 views

### At which ordinal this "counting" ordinal language would fail?

The language $FOL(=, \in , <, C)$ is mono-sorted first order predicate language with extra-logical primitives of equality (and its axioms), set membership, strict smaller than binary relation, and ...