As of May 31, 2023, we have updated our Code of Conduct.

# 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
Filter by
Sorted by
Tagged with
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 ...
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$ ...
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) ...
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-...
325 views

455 views

1 vote
122 views

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 ...
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 ...
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, ...
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 ...
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 ...
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)$ ...
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$, ...
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 ...
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 ...
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 =...
398 views

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 ...
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}$, ...
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?
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 ...
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 α? ...
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 ...
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 ...
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 ...
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$...
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?
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 $$-...
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 ...
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 ...
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 ...
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 ...
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 ...
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
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 ...
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&...
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 ...
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 ...
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 ...
### 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 ...