Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [ordinal-analysis]

The tag has no usage guidance.

0
votes
1answer
57 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 ...
4
votes
0answers
45 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 ...
2
votes
1answer
39 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$. ...
4
votes
1answer
83 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 ...
0
votes
0answers
46 views

What is the ‘strength’ of a mathematical theory?

As someone who is unfamiliar with ordinal analysis, I was confused to read the Wikipedia entry explaining that ordinal analysis is the evaluation of a mathematical theory’s strength which is (measured?...
4
votes
2answers
105 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
vote
1answer
111 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 ...
0
votes
0answers
71 views

How is the minimum ordinal to reach TRUE ARITHMETIC starting from PA?

Let be $PA_0 =PA$, Let be ,for every ordinal $\alpha$ , $PA_{\alpha+1} =PA_\alpha + Con(PA_\alpha )$ and if $\alpha$ is limit ordinal let be $PA_\alpha = \cup_{\beta<\alpha} PA_\beta$. 1) Is ...
11
votes
1answer
208 views

Small proof-theoretic ordinals

Where to find proofs of the following: 1) proof-theoretic ordinal of $I\Sigma_0$, which is Robinson's Q arithmetic with induction on $\Sigma_0$ formulas, is $\omega^2$? 2) proof-theoretic ordinal of ...
1
vote
1answer
95 views

Has the proof theoretic ordinal of $MLTT + M$ been studied?

By $MLTT + M$ I mean basic Martin Lof type theory with general $M$-types. It well known that the proof-theoretic ordinal of $MLW$ (MLTT with W-types) is the Bachmann-Howard ordinal, but is the proof ...
5
votes
2answers
269 views

proof theoretic ordinal for Robinson's arithmetic

Does a theory like Robinson's arithmetic have a proof-theoretic ordinal? If so, what is it?