# 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.

38 questions
Filter by
Sorted by
Tagged with
1 vote
81 views

### Are finitist systems the ones with a proof-theoretic ordinal of at most $\omega^\omega$?

The proof-theoretic ordinal of $\mathsf{EFA}$ and $\mathsf{RCA}_0^*$ are $\omega^3$ and the one of $\mathsf{PRA}$, $\mathsf{I\Sigma1}$, $\mathsf{RCA}_0$, etc. is $\omega^\omega$. See https://ncatlab....
1 vote
61 views

### How large is $f_{\Gamma_{0}}(2)$ in the Fast-Growing Hierarchy?

If my ordinal arithmetic is correct, $f_{\Gamma_{0}}(2)=f_{\epsilon_{\epsilon_0}}(2)$ so $$f_{\epsilon_{\omega}}(2)\ll f_{\Gamma_{0}}(2)\ll f_{\epsilon_{\epsilon_1}}(2),$$ but that doesn't show ...
124 views

### Why do we define the proof-theoretic ordinal of a theory the way we do when there are unnatural well-orderings out there?

The proof-theoretic ordinal of first-order arithmetic ($\mathsf{PA}$) is $\varepsilon_{0}$. However, in pages 3 and 4 of Andreas Weiermann's Analytic combinatorics, proof-theoretic ordinals, and phase ...
• 4,362
72 views

### Is there a model of KP with no $\emptyset'$ ordinal notation for the Bachmann-Howard ordinal?

The Bachmann-Howard ordinal (BHO) is a large recursive ordinal defined using ordinal collapsing functions. Kripke-Platek set theory (KP) is a fragment of ZF obtained by removing powerset, swapping ...
• 1,207
1 vote
268 views

### What is the least upper bound ordinal of my linear n-symbol partition ordinal (ordinal that contain all finite string of finite different symbol)?

Note: The "partition" here isn't relate to the partition at all. Note: For the detail of "ordinal that contain all finite string of finite different symbols", see the "Edit&...
265 views

### What, precisely, does it mean to represent an ordinal on a computer?

Two closely related questions about ordinals that I found quite confusing at first and couldn't find a satisfactory answer online (self-answering): I've heard sentences like "$\omega^{CK}$ is ...
1 vote
109 views

### What is the proof theoretic ordinal of $\mathsf{B\Sigma}_{2}^{0}$?

The proof-theoretic strength of a theory is measured by the $\mathsf{\Pi}_{1}^{1}$-ordinal of the theory and it is called the proof-theoretic ordinal (PTO) of the theory (there are other ordinal ...
• 4,362
200 views

### What are the proof-theoretic strengths of Ramsey's theorems?

The proof-theoretic strength of a theory is measured by the $\mathsf{\Pi}_{1}^{1}$-ordinal of the theory (indeed, there are other ordinal analyses, like the $\Pi_{2}^{0}$-ordinal of the theory). ...
• 4,362
85 views

### When should one use transfinite induction?

I've come across it multiple times now in proof theory papers that authors use (sometimes quite elaborate) inductions in order to prove easy results. The most striking example is the following, where ...
• 682
276 views

### What is an example of a statement equivalent to $\omega^{\omega}$-induction?

If $\alpha$ is a countable ordinal and $A$ is the set of natural numbers having well-ordering of type $\alpha$, does this mean that $\alpha$-induction (transfinite induction up to $\alpha$) is ...
• 4,362
222 views

• 21
159 views

### Question on An Explicit Enumeration of Ordinals

Question: What is the first countable ordinal that doesn't appear in the sequence $T$ defined below and is that ordinal equal to $\{ t_i : t_i \in T\}$? Introduction: Making a Sequence $T$ based on ...
166 views

### What is the lowest layer of the Constructible Universe which is a model of $ZFC-P$?

This answer says that the smallest ordinal $\lambda$ such that $L_\lambda$ is a model of $ZFC$ isn’t easy to describe, other than to say that $\omega_1^{CK}<\lambda<\omega_1$. But my question ...
• 10.2k
111 views

### Does there exist a notion of "growth rate", big-O notation, etc for ordinal (normal) functions?

Given some $f: \Bbb N \to \Bbb N$, we have various ways to talk about how fast it's growing: big-O notation, little-o notation, and so on. These are a good way to compare growth rates, so we can talk ...
• 7,878
163 views

### Modifying the "base" of Veblen's hierarchy to exceed $\Gamma_0$

The Veblen hierarchy is usually defined with $\varphi_0(x) = \omega^x$. As a result, we can define the Feferman–Schütte ordinal as the first fixed point of the function $\varphi_\alpha(0) = \alpha$. ...
• 7,878
460 views

### How do we know PA is incomparable with PRA + $\epsilon_0$?

Gödel 2 says that no subtheory of PA can prove Con$_{PA}$, and even though most natural theories $T$ extending PA can prove Con$_{PA}$, this is relatively uninteresting since anyone doubting the ...
397 views

### Is there a "solution" to the ordinal game?

Even though I have almost no background in logic, I find the idea of ordinal notation quite interesting. It seems that the idea is to come up with notation to define larger and larger numbers, until ...
• 1,305
1 vote
488 views

### Conway Notation for Large Countable Ordinals

I have not previously seen anything online that dives deeply into On: In Conway's notation On denotes the ordinal numbers (and No denotes the set of all surreal Numbers). Basically the elements of ...
• 231