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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
115 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 ...
user avatar
  • 293
3 votes
0 answers
106 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 ...
user avatar
6 votes
1 answer
215 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 =...
user avatar
  • 290
5 votes
1 answer
222 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_\...
user avatar
4 votes
3 answers
270 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} = \...
user avatar
0 votes
0 answers
76 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 ...
user avatar
6 votes
1 answer
245 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}$, ...
user avatar
5 votes
1 answer
335 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?
user avatar
4 votes
1 answer
216 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 ...
user avatar
2 votes
1 answer
123 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 α? ...
user avatar
4 votes
1 answer
287 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 ...
user avatar
5 votes
0 answers
236 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 ...
user avatar
  • 105
4 votes
3 answers
324 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 ...
user avatar
4 votes
1 answer
186 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$...
user avatar
7 votes
1 answer
439 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?
user avatar
4 votes
1 answer
220 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]$-...
user avatar
4 votes
3 answers
424 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 ...
user avatar
3 votes
2 answers
172 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 ...
user avatar
3 votes
1 answer
356 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 ...
user avatar
  • 185
14 votes
2 answers
516 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 ...
user avatar
0 votes
1 answer
356 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 ...
user avatar
  • 19
2 votes
0 answers
189 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, ...
user avatar
  • 49.2k
1 vote
1 answer
219 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 ...
user avatar
3 votes
1 answer
197 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&...
user avatar
  • 2,385
5 votes
0 answers
186 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 ...
user avatar
6 votes
1 answer
302 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 ...
user avatar
  • 451
3 votes
0 answers
107 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 ...
user avatar
  • 63
11 votes
1 answer
643 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 ...
user avatar
  • 6,495
3 votes
0 answers
47 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 ...
user avatar
6 votes
1 answer
277 views

For which ordinals do we have $V_\alpha = L_\alpha$?

Some elements of $L$ become constructible only in levels higher than its rank level. So I ask: Let $V$ be such that $V = L$. For which ordinals $\alpha$ do we have $V_\alpha = L_\alpha$? Indeed, we ...
user avatar
3 votes
1 answer
206 views

A connected topological space whose points cannot be connected by irreducible components

Does there exist a topological space $X$ with the following properties? $X$ is connected. The set of irreducible components of $X$ is locally finite. Not every pair of points in $X$ can be "connected ...
user avatar
  • 6,504
2 votes
2 answers
487 views

Veblen function with uncountable ordinals & beyond

Disclaimer: I am not a professional mathematician. Background: I have been researching large countable ordinals for awhile & I think the Veblen function is particularly eloquent. My understanding ...
user avatar
9 votes
1 answer
478 views

Does every cofinal branch through Kleene's O compute true arithmetic?

My question concerns cofinal branches through Kleene's $O$, which is a set of natural numbers and a computably enumerable relation $<_O$ on this set that provides ordinal denotations for any ...
user avatar
3 votes
1 answer
393 views

From a constructive perspective, what are the ordinal numbers?

From a constructive and computational perspective, what are the ordinal numbers? On the one hand, it seems you can represent ordinal numbers symbolically using something like Cantor Normal Form ...
user avatar
  • 3,321
16 votes
1 answer
823 views

Has the exponentiation of ordinals a nice geometric model?

It is well known that the sum $\alpha+\beta$ of two ordinals $\alpha,\beta$ can be defined "geometrically" as the order type of the sum $(\{0\}\times \alpha)\cup(\{1\}\times\beta)$ endowed ...
user avatar
  • 32.9k
5 votes
1 answer
241 views

Is Axiom of Choice equivalent to its version for families of sets, indexed by ordinals? [duplicate]

Is Axiom of Choice equivalent to the following statement? Axiom of Ordinal Choice: For any ordinal $\lambda$ and any indexed family of sets $(X_\alpha)_{\alpha\in\lambda}$ there exists a function $...
user avatar
  • 32.9k
4 votes
0 answers
76 views

Infinite positions in 3D chomp

I've recently come back to investigating ordinal chomp. See A winning move for the first player in $3 \times 3 \times \omega$ Ordinal Chomp for a definition. I made a new discovery, that the position \...
user avatar
  • 2,265
10 votes
2 answers
479 views

Transfinite algorithms

The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily ...
user avatar
  • 28.7k
22 votes
4 answers
2k views

What's the use of countable ordinals? (prompted by a remark of Tim Gowers)

In a typically lucid and helpful page of notes for students, A beginner’s guide to countable ordinals, Tim Gowers explains how the countable ordinals can be “constructed rigorously in a way that ...
user avatar
  • 1,469
5 votes
1 answer
181 views

How far does this restricted definition on $\mathcal{O}$ goes?

$\mathcal{O}$ notation describes an onto function $f:\mathcal{O} \rightarrow \omega_{CK}$. In calculating all values $n \in \mathbb{N}$ such that $f(n)=\alpha$, when $\alpha$ is a limit, all indexes $...
user avatar
  • 755
5 votes
0 answers
185 views

$Π_2$ strength of KP

I am looking for a characterization of the $Π_2$ statements provable in KP. Here, KP (often denoted KPω) is the Kripke-Platek set theory, including infinity and full induction on ordinals. Here is ...
user avatar
0 votes
1 answer
117 views

Can I find the definition of Jager's ordinal collapsing functions?

http://cantorsattic.info/index.php?title=J%C3%A4ger%27s_collapsing_functions_and_%CF%81-inaccessible_ordinals&action=edit Sadly, Cantor's attic is making an error. This is all I know about Jager'...
user avatar
  • 281
10 votes
1 answer
429 views

Examples of proofs using induction or recursion on a big recursive ordinal

There are many proofs use induction or recursion on $\omega$, or on an arbitary (may be uncountable) ordinal. Are there some good examples of proofs which use a big but computable ordinal? The ...
user avatar
  • 445
3 votes
1 answer
331 views

Smallest ordinal modelling $\aleph_1$?

Let $X_1$ be the class of all ordinals $\alpha$ such that there exists a transitive model $M$ of ZF(C) such that $M$ thinks that $\alpha$ is $\aleph_1$. Every class of ordinals has a minimum element (...
user avatar
6 votes
0 answers
268 views

What is proof-theoretic ordinal of weak first-order arithmetic?

According to Wikipedia(https://en.wikipedia.org/wiki/Ordinal_analysis) and nlab(https://ncatlab.org/nlab/show/ordinal+analysis), a proof-theoretic ordinal of $\mathsf{PRA}$ is $\omega^\omega$. ...
user avatar
  • 178
5 votes
1 answer
183 views

Club filter basis in $\omega_1$

My question is about existing of basis of club filter club($\omega_1$) with cardinality $c$. Does it exist?
user avatar
  • 1,095
4 votes
1 answer
554 views

Which ordinal is larger, the supremum of ordinals writable by iterated Infinite Time Turing Machines or the smallest $\Sigma_2^1$-reflecting ordinal?

The ordinal $\tau_1$ corresponds to $\lambda^{\textit{it}}$ (the supremum of all ordinals writable by iterated ITTMs) — see Definition 3.1 in the paper “ITTMs with Feedback” [Robert S. Lubarsky]. ...
user avatar
13 votes
0 answers
333 views

Is it an open problem whether fast-growing hierarchies can be defined without fundamental sequences?

Googology Wiki says this, concerning the relation between fast-growing hierarchies defined for all countable ordinals, and the existence of a system of assigning a canonical fundamental sequence to ...
user avatar
2 votes
1 answer
511 views

Relation between $\eta$ and $\omega^L_1$

I posted this question on MSE (link: Eventual Writability (general)) about 10 days ago. The current version of this question is a highly abridged version of the one posted there. Let's write "...
user avatar
  • 755
0 votes
2 answers
401 views

Why do ordinal collapsing functions use regular cardinals?

Inaccessible cardinals are defined as regular strong limit cardinal, and weakly inaccessible cardinals as regular weak limit cardinal. These cardinals are used by some ordinal collapsing functions. My ...
user avatar