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
0
votes
0answers
121 views

Cantor normal form [closed]

Every ordinal number $α$ can be uniquely written as ${\displaystyle \omega ^{\beta _{1}}c_{1}+\omega ^{\beta _{2}}c_{2}+\cdots +\omega ^{\beta _{k}}c_{k}}$, where $k$ is a natural number, ${\...
4
votes
1answer
157 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
2answers
314 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
1answer
54 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
1answer
289 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
2answers
456 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
1answer
165 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
0answers
179 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
1answer
197 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
1answer
154 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
0answers
150 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 ...
5
votes
1answer
269 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
0answers
102 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 ...
11
votes
1answer
507 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
0answers
35 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 ...
6
votes
1answer
251 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 ...
3
votes
1answer
155 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 ...
2
votes
2answers
377 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 ...
9
votes
1answer
439 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 ...
3
votes
1answer
339 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 ...
16
votes
1answer
708 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 ...
6
votes
1answer
221 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 $...
4
votes
0answers
59 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 \...
10
votes
2answers
422 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 ...
22
votes
4answers
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 ...
5
votes
1answer
174 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 $...
5
votes
0answers
149 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 ...
0
votes
1answer
97 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'...
10
votes
1answer
398 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 ...
2
votes
0answers
195 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 (...
6
votes
0answers
234 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$. ...
5
votes
1answer
173 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?
4
votes
1answer
458 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]. ...
12
votes
0answers
295 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 ...
2
votes
1answer
459 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 "...
0
votes
2answers
344 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 ...
5
votes
0answers
162 views

Weaker versions of Gandy ordinals

Gostanian's paper "The next admissible ordinal" (see https://www.sciencedirect.com/science/article/pii/0003484379900251 ), is concerned with the supremum of the $\alpha$-recursive ordinals for various ...
4
votes
3answers
574 views

Compact definition of ordinals

This question is about von Neumann's informal definition of ordinals as "sets of all smaller ordinals" and was discussed in this math.stackexchange question. When trying to formalize this definition, ...
9
votes
1answer
598 views

Computable models of the ordinal numbers

It's known, for example in the answer to this question: Is there a computable model of ZFC? that ZFC has no computable model. My questions is: is there a model of ZFC for which the order relation on ...
2
votes
1answer
240 views

Generalizing König's Lemma

In some recent work, I need a strengthening of König's Lemma to "trees" of arbitrary ordinal heights. Trees, in this context, are really just well-founded partially ordered sets. See, for instance, ...
5
votes
1answer
241 views

Capturing the $\omega_1^{\mathrm{CK}}$-th stage of Gödel's constructible hierarchy

For an ordinal $\alpha$, let $L_\alpha$ be the $\alpha^{th}$ set of Gödel's constructible hierarchy and let $\omega_1^{\mathrm{CK}}$ be the first non-recursive ordinal or the first admissible ordinal ...
-6
votes
1answer
223 views

Is the least ordinal containing all countable ordinals defined by a formula an element of itself? (Out of date, see below)

[UPDATE] The question has been updated and is mostly unrelated to the question above the line. The updated question is below the line. The following argument supports a "yes" answer; is it convincing?...
2
votes
0answers
96 views

Coloring triples in trees

Definitions Let us say a tree is a partially ordered set $(P, \leqslant )$ such that for any $t\in P$, the ancestor set $\{s\in P: s\leqslant t\}$ is finite and linearly ordered. We let $MAX(P)$ ...
4
votes
1answer
351 views

Function on the set of limit countable ordinals

Let $\Lambda$ be the set of all countable limit ordinals. Does there exist an injective function $f:\Lambda\to\omega_1$ with the properties: $\forall \lambda\in\Lambda:~f(\lambda)<\lambda$ $\...
3
votes
0answers
111 views

Simple transfinite generalization of $p$-adic integers

One way to define the ring of $p$-adic integers is as a quotient of the formal power series semiring $\Bbb N[[x]]/(x-p)$. One can likewise start with the formal power series ring $\Bbb Z[[x]]/(x-p)$ ...
1
vote
1answer
169 views

Countable union of well ordered sets [closed]

Assume I have a sequence $(A_i)_{i<\omega}$ of well-ordered subsets of an ordered set $S$. Assume that $A:=\underset{i<\omega}{\cup}A_i$ is also well-ordered. Let $\alpha$ be an ordinal upper ...
1
vote
1answer
229 views

An Apparent Incongruity

I thought of a certain point that seems to point to an apparent incongruity. Hopefully someone would promptly point out the logical mistake and/or some implicit assumption that may not hold under a ...
3
votes
0answers
129 views

Partial well-ordering of formulas

Given a theory $T$, for arbitrary formulas $φ$ and $ψ$ that provably in $T$ denote an ordinal, set $[φ]_T < [ψ]_T$ iff provably in $T$, the ordinal denoted by $φ$ is less than the ordinal denoted ...
3
votes
1answer
269 views

Hartogs' Number of the Reals and $\Theta$ without choice

There are two important numbers that in some meaningful sense describe "how well-orderable" the reals are: Hartogs' Number $H(\Bbb R)$, also notated as $\aleph(\Bbb R)$, the least ordinal/well-...
1
vote
0answers
185 views

Is it possible to construct a formal language that allows to refer to specific real numbers that encode ordinals accidentally writable by an ITTM?

Let $A$ denote a particular (fixed) algorithm to encode ordinals as real numbers. The exact technical description of $A$ is irrelevant for this question: it can be any algorithm that is mathematically ...