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.
41 questions
1 vote
0 answers
62 views
Monotonicity of Hardy Computation breaks when switching addends?
I am working with ordinal arithmetic at the moment, more precisely with ordinals below epsilon zero. Further I am considering the Hardy computation as a ordinal indexed hierarchy of functions as ...
9 votes
0 answers
173 views
Transfinite induction and consistency statements
I'm interested in learning more about precise what transfinite induction results are equivalent to various consistency statements in arithmetic. Focusing on induction up to $\epsilon_0$, I see an ...
- 69.9k
2 votes
1 answer
864 views
Can Goodstein's theorem be proven in $\mathrm{PA + Con(PA)}$?
We define the Goodstein sequence $G_k(n)$ by first expressing $k$ in hereditary-base-$2$ notation (see the Wikipedia article for an explanation of this) and setting $G_k(2) = k$. Then to get $G_k(n + ...
- 937
3 votes
1 answer
197 views
How do we know some ordinal $n$ is the proof-theoretic ordinal of some theory?
This might be an elementary question, and I apologize for that. I've been dabbling in ordinal analysis / proof theory for a few days, back when I read W. Buchholz, “A new system of proof-theoretic ...
- 49
1 vote
1 answer
164 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 ...
- 63
4 votes
1 answer
229 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,602
3 votes
1 answer
123 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,761
1 vote
0 answers
281 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&...
5 votes
2 answers
514 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 ...
- 3,522
1 vote
1 answer
237 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,602
4 votes
1 answer
296 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,602
6 votes
0 answers
118 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 ...
- 714
2 votes
1 answer
361 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,602
3 votes
1 answer
586 views
What is the proof-theoretic ordinal of true arithmetic?
The proof theoretic ordinal of $PA$ is $\epsilon_0$. My question is, what is the proof-theoretic ordinal of true arithmetic, i.e. $Th(\mathbb{N})$? I’m assuming you get something bigger than $\...
1 vote
0 answers
52 views
Does "predicativitness" of class comprehension in $\sf MK$ affects the value of the class of all ordinals?
If we take $\sf MK$ and $\sf PMK$, the latter is just a weakening of the former by restricting the formulas in class comprehension to be relativised to sets which is by the way a mono-sorted version ...
- 4,777