Questions tagged [ordinal-numbers]
An ordinal is the order type of a well-ordered set. The first few ordinals are $0, 1, 2, \dots, \omega, \omega+1, \dots$ where $\omega$ is the order type of $\mathbb{N}$, and $\omega+1$ is the order type of $\mathbb{N}$ together with a maximum element.
196
questions
6
votes
0
answers
101
views
Proof of Theorem Concerning Conway's "Nim Field"
I have a question about the proof of theorem 44 in "On Numbers and Games" on page 58, concerning the "Nim field" ${ON}_2$. As background, ${ON}_2$ turns the ordinals into a field ...
- 71
6
votes
1
answer
191
views
Which one of the following two ordinals is larger?
We say that $\alpha$ is $\Sigma_n$-extendable (to $\beta$), if there is $\beta>\alpha$ such that $L_\alpha$ is a $\Sigma_n$ elementary submodel of $L_\beta$.
First ordinal: the least $\alpha_0$ ...
7
votes
1
answer
306
views
Gaps in the ordinals writable by Ordinal Turing Machines with a single countable parameter
Let $W(\alpha)$ denote the set of all (countable) ordinals writable by Ordinal Turing Machines with a single (countable) parameter $\alpha$, i.e. each computation starts with a single ($\alpha$-th) ...
- 899
20
votes
1
answer
2k
views
Why do we need "canonical" well orders?
(I asked this question on Math.SE earlier but received no response and am therefore moving it here, please note that I realise this question is probably incredibly naïve for the experienced set-...
- 303
5
votes
1
answer
325
views
A possible flaw in Theorem 14.17 in Kurt Schütte's -Proof Theory-
Reading Chapter V, pages (73-97) in Proof Theory (Springer, 1977), by Kurt Schütte, I have encountered a peculiar problem which puzzles me.
On page 96, a map $\rm{Nr}:\overline{\rm{OT}}\rightarrow \...
- 2,016
1
vote
1
answer
104
views
Recursively inaccessible ordinals and non locally countable ordinals
This answer seems to imply that: for an ordinal $\alpha$, to be recursively inaccessible (i.e. $\alpha$ is admissible and limit of admissible) implies to be not locally countable (i.e. $L_\alpha \...
- 471
8
votes
3
answers
455
views
Elementary countable submodels in Gödel's universe
By the downward Lowenheim-Skölem theorem we can find two countable ordinals $\alpha < \beta$ such that $L_\alpha \prec L_{\omega_1}$ and $L_\beta \prec L_{\omega_1}$. That is, $L_\alpha$ and $L_\...
- 471
5
votes
2
answers
382
views
Replacement axiom and the von Neumann hierarchy
Within ZFC, the von Neumann hierarchy consists of sets $V_\alpha$ indexed by ordinals, subject to the following conditions:
$V_0=\varnothing$.
$V_{\alpha+1}=\mathcal P(V_\alpha)$.
$V_\lambda=\bigcup_{...
- 269
1
vote
0
answers
122
views
What's the order type of the following set?
Fix a positive integer n. Assume $Lan=\{R_0,R_1,...,R_n\}$ be a language of first order logic, where every $R_i$ is a 2-ary relation symbol.
Assume $M$ is an Lan-model, where the underlying set is $...
2
votes
1
answer
213
views
What is the meaning of $\alpha^{+L}$ for $\alpha$ an infinite countable ordinal?
Condition (a) of lemma 3.4 in the paper “Countable ranks at the first and second projective levels” [M. Carl, P. Schlicht, P. Welch] is
$\alpha^{+L} = \omega_1,$
where $\alpha$ denotes any infinite ...
- 899
3
votes
0
answers
255
views
An alternative definition of computable ordinals
An ordinal $\alpha$ is said to be computable if there is a computable relation on a subset of integers that is well-ordered and its order type equals $\alpha$.
But let's consider well-founded trees on ...
- 1,238
1
vote
0
answers
141
views
Can we have a proper class of infinitely descending infinite ordinals?
Working in $\sf ZF-Reg.$, can we have a transitive model $M$ of $\sf ZF$ such that there exists a proper class (i.e. a subset of $M$ that is not an element of $M$) of infinitely descending infinite ...
- 7,050
5
votes
1
answer
170
views
How to build large recursive ordinals using Dillator and/or Ptykes?
I've only recently learned about Girard's theory of Dilators and Ptykes, and I find this theory very elegant, but it is not clear at all to me whether/how it can be used to produce ordinal notations ...
- 37.4k
1
vote
1
answer
118
views
Ordering patterns of projecta by least witness
Let $J$ denote Jensen's modification of the constructible hierarchy. For an ordinal $\alpha$ and an $n\in\mathbb N^+$, let $\rho_n^{J_\alpha}$ denote the $\Sigma_n$-projectum of $J_\alpha$, the least $...
- 514
2
votes
0
answers
204
views
The supremum of ordinals eventually writable by Ordinal Turing Machines with an oracle for the class of stabilization ordinals
This question is based on the assumption that all computations start with no ordinal parameters (i.e. the input is empty).
The term “stabilization time of a machine” for this question implies the ...
- 899
4
votes
1
answer
227
views
Existence of a particular function that maps an arbitrary set of ordinals to a single ordinal
Does there exist a function $f$ that satisfies all of the following three properties?
The function converts an arbitrarily large (empty, finite, countably/uncountably infinite) set of ordinals to a ...
- 899
3
votes
0
answers
99
views
How closely do ordinal collapsing functions relate to Mostowski collapse?
Ordinal collapsing functions (such as Rathjen's $\psi_\pi$-functions, not the Levy collapse function) name large countable ordinals by mapping larger ordinals below some "large" ordinal, ...
- 514
8
votes
1
answer
489
views
Where was the Cantor normal form theorem first proved?
We all take for granted the theorem that every ordinal $\alpha > 0$ has a Cantor normal form, and there are plenty of proofs of it, some of which are on this site. However, where was it proved? Was ...
- 560
2
votes
2
answers
162
views
Diagonalization over a normal function and its derivatives on transfinite ordinals
Let $\Phi(0,\beta)$ a normal function from $On$ to $On$, and let $\Phi(\alpha,\beta)$ be the $\alpha$-th derivative of $\Phi(0,\beta)$. For example, let $\Phi(0,\beta)=\aleph_\beta$. Then, all ...
- 21
12
votes
2
answers
936
views
Is there a proof of strong normalisation that uses ordinal numbers?
I am currently trying to find a proof for strong normalisation of an extension of $\lambda$-calculus.
I've tried several approaches and one would be to assign an ordinal number $\operatorname{cs}(t)$ ...
- 193
3
votes
0
answers
207
views
Is this recursion theoretic analogue of a criterion of weakly compact cardinal accurate?
Jensen proved that, if V=L, and $\kappa$ is a regular cardinal, then if for any stationary $A\subseteq \kappa$, the set $\{\alpha\mid A \text{ is stationary below }\alpha\}$ is stationary in $\kappa$, ...
2
votes
1
answer
172
views
When does $\Pi_2$-reflection on $X$ fail to imply iterated $\Pi_1$-reflection on $X$?
Let lowercase Greek letters denote ordinals. Recall from Richter and Aczel's "Inductive definitions and reflecting properties of admissible ordinals", for a set of formulae $\Gamma$ and a ...
- 514
3
votes
0
answers
125
views
Can the essence of the $0^\#$ LCA be weakened to an axiom not requiring uncountable cardinals?
"$0^\#$ exists" is an informally stated large cardinal axiom that is to be understood as "there is an uncountable set of Silver indiscernibles", "every uncountable cardinal is ...
- 482
7
votes
1
answer
324
views
How could we define "recursively greatly Mahlos"?
A common action in set theory is making a large cardinal axiom "recursive", i.e. turning it from a large uncountable cardinal to a large countable ordinal. For example:
Recursively regular =...
- 560
7
votes
2
answers
398
views
Can countable ordinals start gaps of every order in the constructible universe?
Define "$\alpha$ starts a gap of order $n+1$ and length $\beta$" iff $\mathcal P^n(\omega)\cap (L_{\alpha+\beta}\setminus L_\alpha)=\emptyset\land\forall\gamma\in\alpha: L_\alpha\setminus L_\...
- 482
4
votes
3
answers
430
views
Set theory: fixed points of $n \mapsto \varepsilon_n$ and $n \mapsto \omega_n$
For an ordinal number $\alpha$, the epsilon number $\varepsilon_\alpha$ is defined as the "$\alpha$-th" fixed point of the map $n \mapsto \omega^n$, i.e. $\omega^{\varepsilon_\alpha} = \...
- 83
0
votes
0
answers
103
views
How to define BHO alternatives below admissible ordinals?
Bachmann-Howard ordinal is a recursive ordinal. It's not that large compared to those proof-theoretic ordinals of stronger theories, but the definition of BHO is sufficient to illustrate how ...
7
votes
1
answer
288
views
If $L_\alpha \vDash ZFC$, then do we have $L_{\alpha+1} \vDash \alpha\text{ is inaccessible}$?
Here we choose the definition of "is a cardinal" as there is no surjective map from a smaller ordinal to it.
It's easy to prove that, if $L_{\alpha+1} \vDash\ \alpha\text{ is inaccessible}$, ...
5
votes
1
answer
374
views
Is this relation about elementary embedding transitive?
For ordinals $\alpha<\beta$, we say $\alpha<_{el}\beta$, if there is an elementary embedding with domain $L_\beta$ and critical point $\alpha$.
Is $<_{el}$ transitive?
7
votes
1
answer
294
views
Existence of a generalized stable ordinal
An ordinal $\alpha$ is called +1 stable, if $L_\alpha <_1 L_{\alpha+1}$
By considering $Σ_n$ elementary submodel we can generalize it.
I'm curious about its further generalizations.
Does there ...
2
votes
1
answer
168
views
Ordinal notations in α-recursion theory
Is there a theory about using α-recursion to compute ordinals?
For example, consider α-recursive well orders on α, what is the supreme of their order type? Is it the next admissible ordinal after α? ...
4
votes
1
answer
357
views
How large are the stabilization times of Ordinal Turing Machines with an oracle for the transfinite initial ordinals?
This question is based on the assumption that $V \ne L$ and we have $\omega_1^L < \omega_1$ (here $\omega_1^L$ is equal to the supremum of ordinals accidentally writable by no-oracle Ordinal Turing ...
- 899
5
votes
0
answers
336
views
What does $\omega^*$ mean? [closed]
I've recently found in some short article (source below) the symbol $\omega^*$ (generally, starred ordinal number), but without explanation what that symbol means. From the context I understood that ...
- 117
4
votes
3
answers
359
views
Countably infinite sets of ordinals as parameters for Ordinal Turing Machines
Let $A$ and $B$ denote two countably infinite sets of ordinals.
Let $W_A$ denote the supremum of ordinals writable by Ordinal Turing Machines with the set $A$ given as the source of parameters. That ...
- 899
4
votes
1
answer
209
views
Is there a real $x$ which is eventually writable from an ordinal parameter $\alpha < \omega_1$, but not from $\omega_1$?
According to Lemma 3.14 in the paper “Recognizable sets and Woodin cardinals: Computation beyond the constructible universe”, there is a real $x$ in $L$ which is recognizable from some ordinal $\alpha$...
- 899
8
votes
1
answer
490
views
Is the supremum of L-definable cardinals silver-indiscernible
Let $\kappa$ be the supremum of ordinals first order definable in L without parameters. Assume $0^\sharp$ exists. Is $\kappa$ the least silver indiscernible ordinal?
4
votes
1
answer
248
views
How to compare three supremums of ordinals eventually writable by Ordinal Turing Machines?
This question implies that we have fixed: (i) a particular enumeration of Ordinal Turing machines; (ii) a particular way to encode an ordinal by an infinite binary sequence.
The class of $[1]$-...
- 899
4
votes
3
answers
456
views
How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?
Given a fixed enumeration of Infinite Time Turing Machines (ITTMs), let $M_i(x)$ denote a computation of an $i$-th ITTM, assuming that the input $x$ is a real (an infinite binary sequence).
Then the ...
- 899
3
votes
2
answers
263
views
Ordinal numbers reachable by primitive recursive ordinal functions in omega
$ \def \PRo {{\mathcal { PR } _ \omega}} $
The class of primitive recursive ordinal functions in the constant omega function (henceforth denoted by $ \PRo $) are defined by Jensen and Karp (1971) as ...
- 293
3
votes
1
answer
417
views
Cardinality of infinite towers of Alephs - can tower be more than countable?
Lets define function T as
$$T(0) = \aleph_0$$
$$T(1) = \aleph_{\aleph_0}$$
$$T(2) = \aleph_{\aleph_{\aleph_0}}$$
etc
No finite tower of alephs can reach the first inaccessible cardinal
My questions ...
- 185
14
votes
2
answers
584
views
Definability of Gödel's pairing function on ordinals
Given an infinite cardinal $\kappa$, Gödel's function is a well-known bijection $p:\kappa^2\to\kappa$.
Is $p$ definable in the structure $\langle\kappa;\in\rangle$?
Is $p$ definable in a bigger 2nd ...
- 2,281
0
votes
1
answer
486
views
What comes after the Bachmann Howard Ordinal?
I've read and known what the FGH is all the way up to a>Bachmann Howard ordinal which is ψ(Ω_2), the Googology Wiki, Wikipedia, Chris Bird articles, and YouTube don't show how the Fast Growing ...
- 19
2
votes
0
answers
206
views
Countable Fodor's Lemma?
Does Fodor's lemma fail for countable ordinals?
For the usual statement of Fodor's lemma to make sense, one needs well-behaved notions of club and stationary sets, which fail for countable ordinals, ...
- 55.4k
1
vote
1
answer
266
views
How large is the smallest ordinal larger than any “minimal ordinal parameter” for any pair of an Ordinal Turing Machine and a real?
In this question, the notation $P^x(\alpha)$ denotes a situation where a particular OTM-program $P$ performs a computation on input $x$ with an ordinal parameter $\alpha$, assuming that $x$ is written ...
- 899
3
votes
1
answer
234
views
Where can I read about Veblen functions / klammersymbols beyond the large Veblen ordinal?
So, I'm not sure to what extent this is a thing. John Baez mentions in this blog post that common large countable ordinals beyond the large Veblen ordinal can also "be defined as fixed points&...
- 2,565
5
votes
0
answers
214
views
Higher order arithmetic, hierarchies and proof theoretic ordinals
I asked this question on MSE some days ago but I have not received any answer so I have decided to post it here.
I would like to consider a generalization of the notation $\Pi$ and $\Sigma$ used for ...
- 161
6
votes
1
answer
324
views
Definability of ordinals in various signatures
Recently, I've been studying what the definable subsets of the countable ordinals "look like" from the perspective of bare-bones first order logic (not set theory) equipped with various ways ...
- 479
3
votes
0
answers
122
views
Trees of prescribed ordinal
My question is very imprecise, as I know very little about descriptive set theory.
In a problem I am thinking about I have a family of well-founded trees (finite sequences on $\cup_n X^n$ closed under ...
- 63
13
votes
1
answer
959
views
Intuition about ordinal fixed points $\alpha = \aleph_\alpha$
I wanted to ask for your intuition about ordinal fixed points $\alpha = \aleph_\alpha$, where $\aleph_\alpha$ stands for the $\alpha$-th Aleph number in the Aleph sequence of cardinalities.
For ...
- 6,627
3
votes
0
answers
65
views
Self-contained proof of WO of Buchholz's ordinal notation system
I would like a self-contained proof that the ordinal notation system defined by Buchholz in this paper is indeed well-ordered. Meaning, I would like a proof that does not rely on ordinals. Buchholz's ...
- 1,012