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

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

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

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

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

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_\...

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_{...

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

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

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

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

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

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

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

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

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

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)$ ...

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

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

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

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_\...

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} = \...

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

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

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

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

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]$-...

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

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

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

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

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

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

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

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

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

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

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

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

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