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
1
vote
2answers
271 views
+50

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
346 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
282 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
616 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 with the ...
7
votes
1answer
196 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
39 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 \...
8
votes
1answer
257 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
156 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
120 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
0answers
122 views

What is the bijection from $\omega_1^{CK}$ to the natural numbers?

A while back, I learned about the Church-Kleene ordinal and I wondered, since we know that it is countable, what is the bijection from $\omega_1^{CK}$ to $\mathbb{N}$?
0
votes
1answer
81 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
369 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
187 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
209 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
166 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
368 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]. ...
9
votes
0answers
167 views

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

Googleology 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
406 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
294 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
151 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
532 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
570 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
216 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
211 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
194 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
94 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
330 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
92 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
130 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
225 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
124 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
260 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
182 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 ...
7
votes
0answers
192 views

Natural examples of recursive pseudowellorderings

Question: What are some natural examples of recursive pseudowellorderings? By natural, I mean in the style of reasonable ordinal notation systems as opposed to dependent on a Gödel numbering or an ...
4
votes
0answers
211 views

Ordinal analysis and nonrecursive ordinals

Ordinal analysis is typically described as characterizing recursive ordinals in a theory $T$, but there is a sense in which it can characterize all $T$-ordinals, even those that are nonrecursive. ...
2
votes
1answer
270 views

Relation of $\omega_{\omega_1+1}^{CK}$ to some other ordinals

This was posted as a side question in Formal definition of this ordinal? and was split as a separate question based upon suggestion in comments there. Assume an ordinary ORM model (call it $C_1$). ...
2
votes
1answer
355 views

Formal definition of this ordinal?

Few days I asked this question (https://math.stackexchange.com/questions/2907733/simple-ordinal-question) on MSE. Summary of the question is that I defined a certain function over ordinals $x \mapsto \...
10
votes
0answers
451 views

Which finite sets could be packed into a square?

This question is inspired by an interesting visualization of the finite levels of von Neumann's hierarchy on Adam P. Goucher's blog, Complex Projective 4-Space. The problem starts with a two-...
8
votes
1answer
216 views

Is the measurable space $(\omega_1,\mathcal{P}(\omega_1))$ separable?

Here $\omega_1$ is the first uncountable ordinal, and $\mathcal{P}(\omega_1)$ denotes the power set of $\omega_1$. Separable means countably generated as a $\sigma$-algebra.
7
votes
1answer
226 views

Reference Request: Existence of Ordinal Rank Theory?

Notations: Recall that $\omega_1$ is the first uncountable ordinal. Let $X$ be a Polish space (completely metrizable and separable) and $F(X)$ be the collection of all real-valued functions on $X.$ ...
4
votes
2answers
447 views

Ordinal vs. cardinal dimension

$\newcommand{\Ord}{\operatorname{Ord}}$When does it make sense to define the dimension of a space to be an infinite ordinal, instead of restricting to infinite cardinals? We would essentially have to ...
4
votes
0answers
122 views

$\omega_1$-like elementary chains from long countable elementary chains

For some countable first-order theory $T$, if we have a linearly ordered set $I$ and an elementary chain $\{\mathfrak{A}_i\}_{i\in I}$ we can form a structure $\mathfrak{A}_{I}^\star = (\bigcup_{i\in ...
2
votes
3answers
221 views

Example of an $\omega_1$ decreasing chain of dense semicontinua?

In his well-known paper Bellamy constructs an indecomposable continua with exactly two composants. The setup is as follows: We have an inverse-system $\{X(\alpha); f^\alpha_\beta: \beta,\alpha < \...
0
votes
1answer
233 views

Large cardinals disproving J=L

Given $J_\alpha$ denotes the $1+\alpha$th term in the Jensen Hierarchy and $J=\bigcup_{\alpha\in On}J_\alpha$, are there any known large cardinals $\mathfrak{K}$ such that $\text{ZFC}+\mathfrak{K}$ is ...
1
vote
0answers
104 views

Ordinal corresponding to well-quasi-order on graphs

Let $K$ be an infinite cardinal. Then, by the Robertson–Seymour theorem, the set of graphs with fewer than $K$ vertices and edges form a well-quasi-order. In terms of $K$, what is the maximal order ...
2
votes
0answers
274 views

What is the Proof-Theoretic Ordinal of KPh?

If we work in this notation: $$C_0 (\alpha, \beta) = \beta \cup \lbrace 0 \rbrace$$ $$C_{n+1} (\alpha, \beta) = \lbrace \gamma + \delta, \omega^\gamma, \Omega_{\gamma}, I_{\gamma}, \psi_\pi(\eta) | \...
17
votes
0answers
603 views

Ramsey's theorem for the first uncountable ordinal

Sierpiński proved that a version of Ramsey's theorem for colourings of pairs of countable ordinals fails miserably by comparing the ordering of $\omega_1$ with the linear ordering of (a subset of) the ...
5
votes
1answer
296 views

A question about ordinal analysis

I have several questions related to ordinal analysis. According to [1], here are the proof-theoretic ordinal of some well-known theories (using $|T|$ do denotate the proof-theoretic ordinal of $T$): ...
1
vote
1answer
123 views

Mapping Between Notations - 2

As the name implies, this question is somewhat similar in spirit to the previous question I asked with same title. This question is also about existence (or lack thereof) of certain possibilities ...