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.
234 questions
0 votes
0 answers
33 views
Reference request: the $\omega_2$'th canonical function does not exist
For functions $f, g: \omega_1 \to \mathrm{Ord}$, put $f <^* g$ if $\{\gamma < \omega_1: f(\gamma) < g(\gamma)\}$ contains a club, likewise define $=^*$ and $\leq^*$ (notice that, assuming ...
- 2,043
7 votes
0 answers
137 views
the complexity of transfinite comparison sorting
The story of finitary deterministic comparison sorting is well-known: we have the naive $O(n^2)$-time algorithms like selection and insertion sorts; once we try divide-and-conquer recursion we ...
- 301
7 votes
0 answers
169 views
Reference request for an algebraic structure mimicking $\varepsilon_0$
Let $(R, +, 0, \cdot, 1)$ be a (unital) semiring equipped with a unary operation $f$ and a binary operation $\land$ such that $f(0) = 1$ $f(x + y) = f(x) f(y)$ $x \land y = y \land x$ $x \land (y \...
- 1,703
5 votes
0 answers
251 views
What's the Kleene–Brouwer order of the Paris–Harrington trees?
Given positive integers $d,r$. Let $T_{d,r}\subseteq\omega^{<\omega}$ consist of sequences $(a_1,\dotsc,a_n)$ such that there is a $r$-coloring of all of the $d$-element subsets of $\{1,2,\dotsc,n\}...
- 1,652
4 votes
0 answers
152 views
The height of the Wadge hierarchy on $\boldsymbol{\Delta}_n^*$ sets
We use $\mathbb{R}$ to mean Baire space, the “logician’s reals”, rather than the Euclidean reals. For $A, B \subseteq \mathbb{R}$, put $A \leq_W B$ iff $A = f^{-1}[B]$ for some continuous $f: \mathbb{...
- 2,043
2 votes
0 answers
250 views
Using dilators to formalize the intuitions about the size of small uncomputable ordinals
The least recursively inaccessible ordinal $I$, is, intuitively, the supremum of the ordinals that come from "recursively" iterating the function $\alpha\mapsto\omega^{CK}_\alpha$. For an ...
- 1,652
18 votes
1 answer
932 views
Where can I find a reference table for ordinal arithmetic?
I am working on a calculator for ordinal arithmetic. Ordinal arithmetic is extremely tricky. So much so that there have been academic papers on the very subject that got some results wrong. Not to ...
- 281
1 vote
0 answers
110 views
Cut-elimination in a Hilbert-type system?
I have a question regarding the paper "Provably computable functions and the fast growing hierarchy" by Buchholz and Wainer (1987). The authors perform their analysis on a Gentzen-type ...
- 1,184
4 votes
0 answers
121 views
Making multiplication closure work on surreal numbers as sign sequences
I've been trying to understand the form of induction used to prove multiplication closure on surreal numbers and I'm a bit stumped. In Gonshor's Introduction to the theory of surreal numbers he proves ...
- 41
9 votes
1 answer
690 views
Cardinals arising as the real vector space dimension of a Hilbert space
For each $p \in \mathbb{R}$ and each cardinal $\kappa$, write $\text{L}_{\text{p}}^{\kappa}$ for the $\text{L}_{\text{p}}$-space one obtains from completing a real vector space of cardinality $\kappa$ ...
user527915
9 votes
1 answer
354 views
Indiscernibles in the patterns of resemblance universe
Edit: The original version of this question was much more difficult, and due to its involvement of full elementarity in the patterns of resemblance universe, was likely unanswerable with current ...
- 2,848
3 votes
2 answers
213 views
Restriction of a locally finitely supported function on an ordinal is finitely supported?
This is a question about set theory. Let $f:\delta\rightarrow H$ be a function from an ordinal $\delta< \omega_1$ to an arbitrary abelian group $H$. Endow $\delta$ with the order topology. Let $f$ ...
- 97
19 votes
1 answer
819 views
Is the theory of ordinals in Cantor normal form with just addition decidable?
This seems like it should be a pretty well-studied question but I can't seem to find an easy answer: Is the theory $(\varepsilon_0, +, \omega^{\ \cdot}, 0, 1)$ decidable? From Is the theory of $(\...
- 1,442
5 votes
1 answer
249 views
Upper bound on natural ordinal sum
I am wondering if there are any known bounds on how large $a\oplus b$ can get, where $\oplus$ is natural ordinal addition? I know that $a+b \le a\oplus b$, but is it true, for example, that $a\oplus b ...
6 votes
1 answer
846 views
Which part(s) of this proof of Goodstein's Theorem are not expressible in Peano arithmetic?
EDIT: Noah Schweber helpfully points out that $\mathsf{ACA}_0$ is a conservative extension of Peano arithmetic in which certain aspects of my proof not expressible in Peano arithmetic are expressible. ...
- 902
4 votes
1 answer
378 views
Does Peano's axioms prove $\alpha$-induction for primitive recursive sequences for every concrete $\alpha < \varepsilon_0$?
It is well-known that Peano's axioms (PA) cannot prove $\varepsilon_0$-induction for primitive recursive sequences (PRWO($\varepsilon_0$)), because PA + PRWO($\varepsilon_0$) proves the consistency of ...
10 votes
1 answer
557 views
Is the theory of $(\operatorname{Ord}, <)$ decidable?
Over a sufficiently strong second-order theory (such as Morse-Kelley set theory), it's possible to define the truth of all first-order formulae in the language of sets. This allows us to construct the ...
- 618
1 vote
1 answer
199 views
Confusion regarding the requirements for a recursive ordinal notation
According to Wikipedia, an ordinal notation is a function that maps a subset of ordinal encodings to a subset of ordinals. It then mentions Gödel numbering which maps the set of well-formed formulae ...
- 13
5 votes
0 answers
254 views
Higher-order equivalence of ordinals
I wonder which ordinals are second-order equivalent, and similarly for other logical equivalences. Let the signature be fixed and include only <. For concreteness, let us first ask for the first ...
1 vote
1 answer
85 views
Reference for tree of bad sequences of WPO
I'm looking for a reference to give in Wikipedia for the following result: Let $X$ be a WPO. Let $T_X$ be the tree of bad sequnces of $X$, and let $o(X)$ be the ordinal height of the root of $T_X$. ...
- 1,184
3 votes
0 answers
1k views
Existence of a almost increase $\omega_1^{\omega_1}$ sequence mod $[\omega_1]^{<\omega_1}$ with length $\omega_2$
In my textbook, the author said that the sequence below is satisfied the requirement. $$\text{For }\alpha<\omega_1,\forall\gamma<\omega_1,g_\alpha(\gamma)=\alpha, \text{For }\omega_1\le\alpha<...
- 31
5 votes
2 answers
462 views
Properties of natural sum and product of ordinals
There seems to be no publicly available listing of properties of natural (or Hessenberg) addition and multiplication of ordinals. So I'm trying to make one. Please confirm correctness of the following ...
- 1,184
0 votes
1 answer
217 views
Is there a canonical mapping between countable transfinite ordinals and $\omega$? What about recursive ordinals?
Consider $\omega^2$. We can build a simple bijection between the ordinal and $\omega$ similarly to how the bijection between $\mathbb{Q}$ and $\mathbb{N}$ can be built. I was wondering if there is a ...
- 103
1 vote
0 answers
82 views
Is this extension of n-th derivatives to ordinal-indexed derivatives trivial? [duplicate]
Let $f$ be a function defined everywhere on the real line, which is infinitely differentiable everywhere, in other words, $f$ is everywhere smooth. I define the $\omega$-th derivative, where $\omega$ ...
- 2,183
6 votes
2 answers
838 views
In the constructive theory of direct categories, is it decidable whether an arbitrary morphism is an identity or not?
I'm wondering what the legit definition of direct categories should be in constructive mathematics. I must admit I don't even know in what literature I should look for the definition. I would ...
- 410
5 votes
2 answers
744 views
Embedding large countable ordinals into the complex plane
Consider large countable ordinals (e.g. $\epsilon_0$ which is not "large", but still interesting). These are countable sets, so they inject into the complex plane ( or even the real line). ...
- 613
11 votes
3 answers
836 views
Does negative trichotomy hold for constructive ordinals?
I don't know if there is a standard term for this, but by "negative trichotomy" I mean ¬ (¬ 𝐴 < 𝐵 ∧ ¬ 𝐴 = 𝐵 ∧ ¬ 𝐵 < 𝐴). This holds for constructive real numbers as an easy ...
- 447
1 vote
2 answers
315 views
A few questions about Tychonoff plank
In the Morita's following article (K. Morita. Some properties of M-spaces), constructing an space $X$ and defining an identification on it. My first question is how to prove that $S$ is countably ...
- 1,661
4 votes
0 answers
170 views
Parameter-free $\alpha$-recursivity versus weakened Turing machines with oracles
In the quest to find a transfinite extension of recursivity which matches intuition, mentioned also in my previous question, Discord user onion5 came up with an idea that expressed precisely how I ...
- 148
4 votes
0 answers
190 views
Simple $(\alpha+1)$-recursive well-orders with order type $|\alpha\text{-recursive}|$
In the following, $L_\alpha$ is the $\alpha$-th level of the constructible hierarchy, $\alpha$-recursive means definable in $L_\alpha$ by a $\Delta_1$ formula. $|\alpha\text{-recursive}|$ is the ...
- 148
6 votes
0 answers
242 views
Iterated $\Pi^1_1$-reflection and non-Gandiness underrepresented in ordinal analyses?
This is a copy of Math StackExchange question #4395977, which I felt was more appropriate for MathOverflow. Note on terminology: "admissible", "$(^+)$-stable", and "$\Pi^1_1$-...
- 2,848
2 votes
0 answers
240 views
How closely do ordinal collapsing functions relate to Skolem hulls?
Ordinal collapsing functions appear in proof theory, and they are used to name large countable ordinals by using uncountable ordinals. Previously I posted a question about why $\psi(\alpha)$ is ...
- 2,848
5 votes
1 answer
571 views
How to solve this exercise about large countable ordinals?
In this note (Notes on Higher Type ITTM-recursion, 2021) written by Philip Welch, I'm trying to solve exercise 3.5(i), but I don't know how to solve it. The problem is: assume that $L_{\gamma_0}<_{...
- 1,652
17 votes
1 answer
518 views
End-extension which Mostowski collapses a fake well ordering
Assume $\alpha$ is admissible, $R\in L_\alpha$ is a linear order that don't have any infinite descending chain in $L_\alpha$. Is there always an end extension $M$ of $L_\alpha$, such that $M\vDash KP$ ...
- 1,652
6 votes
1 answer
659 views
Parameter-free effective cardinals
In the paper "Effective cardinals and determinacy in third order arithmetic" by Juan Aguilera, effective cardinals is defined. I'm curious about its little variation, parameter-free ...
- 1,652
2 votes
1 answer
342 views
Is stable ordinals in non-well-founded model the same as well founded models?
Let $BST$ be the axiom system $KP$ - $\Delta_0$ collection. For an ordinal $\alpha$, we say that $\alpha$ is $\varphi$-$\Sigma_n$-stable, if there is a $\beta>\alpha$ satisfies the formula $φ$ such ...
- 1,652
6 votes
0 answers
219 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 ...
- 519
7 votes
1 answer
405 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$ ...
- 1,652
7 votes
1 answer
529 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) ...
- 1,039
24 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-...
- 343
5 votes
1 answer
410 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 \...
- 2,206
1 vote
1 answer
348 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 \...
- 531
8 votes
3 answers
638 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_\...
- 531
6 votes
2 answers
599 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_{...
- 507
4 votes
1 answer
584 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 $...
- 1,652
2 votes
1 answer
294 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 ...
- 1,039
3 votes
0 answers
442 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,328
1 vote
0 answers
249 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 ...
- 13k
4 votes
0 answers
211 views
Slicing large countable ordinal properties, from $\Pi_3$-reflection to $\Sigma_2$-admissibility
Edit 2024: This post was based on an incorrect premise, as can be seen by my conversation with Farmer S in the comments. However the mistake I made and the conversation in comments may be instructive (...
- 2,848
6 votes
1 answer
486 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 ...
- 43.8k