All Questions
Tagged with ordinals ordinal-analysis
25
questions
3
votes
1
answer
138
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,432
3
votes
1
answer
77
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,311
1
vote
0
answers
270
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
317
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,362
5
votes
0
answers
91
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 ...
- 684
2
votes
1
answer
285
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,432
3
votes
1
answer
263
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 $\...
- 10.3k
3
votes
1
answer
186
views
Link between a theory’s proof-theoretic ordinal and the fastest-growing function it can prove total
When I’ve tried to read up on proof-theory I’ve come across this point multiple times - that given a well-founded fast-growing hierarchy, the index of the fastest-growing function f that T can prove ...
- 427
3
votes
0
answers
184
views
Iterated $\Pi^1_1$-reflection and non-Gandiness underrepresented in ordinal analyses?
Edit: I now feel this question is more appropriate for MathOverflow, I will leave this copy for posterity.
Note on terminology: "admissible", "$(^+)$-stable", and "$\Pi^1_1$-...
- 1,311
2
votes
1
answer
150
views
What is the relevance of the fast-growing hierarchy in the definition of Yudkowsky’s number?
I’m struggling with a certain connection the author draws in defining a certain “huge” number. The number is defined as follows:
Let T be the first-order theory of Zermelo-Fraenkel set theory plus the ...
- 427
4
votes
1
answer
206
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 ...
- 427
0
votes
0
answers
233
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 ...
- 443
1
vote
1
answer
243
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 ...
- 443
0
votes
0
answers
129
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 ...
- 443
4
votes
1
answer
533
views
What is the proof theoretic ordinal of Homotopy Type theory?
The proof theoretic ordinal of Martin-Löf type theory is $\Gamma_0$.
What about HoTT and what about other flavors of type theory (the ones related to the lambda cube for instance)?
- 443