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.
217
questions
9
votes
2
answers
637
views
Order type of $\alpha$-computable well-orderings
One of the nice features of the first admissible ordinal after $\omega$, i.e. $\omega_1^{CK}$, is that it is the collection of ordinals whose order type is that of a computable well-ordering on $\...
- 1,278
1
vote
1
answer
83
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 ...
- 225k
5
votes
0
answers
155
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 ...
4
votes
0
answers
145
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 (...
- 1,278
3
votes
1
answer
273
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 ...
- 2,758
0
votes
0
answers
25
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,074
6
votes
0
answers
150
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$-...
- 1,278
3
votes
0
answers
100
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
2
votes
1
answer
303
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 $...
CommunityBot
- 1
5
votes
1
answer
875
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 (...
- 1,278
5
votes
2
answers
202
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,074
6
votes
1
answer
508
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,278
2
votes
1
answer
668
views
Transfinite sums related to a sequence
Given a sequence $S$ indexed by the finite ordinals, a limit ordinal $\alpha$, and $k \in \mathbb{N}$, define $S_{\alpha+k}$(the extension of $S$ to $\alpha+k$) to be the sum over the products of all $...
CommunityBot
- 1
6
votes
2
answers
470
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_{...
- 281
5
votes
1
answer
260
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, ...
- 1,278
6
votes
3
answers
308
views
Does the rank (=height) of a well partial order bound its type (=length, =stature)?
Terminology and context
(This should all be standard, but is recalled because terminology sometimes varies, and also to put the question into perspective.)
A partially ordered set is called well-...
- 121
0
votes
1
answer
98
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 ...
- 19.2k
1
vote
0
answers
72
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,063
10
votes
2
answers
496
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 ...
- 406
6
votes
2
answers
679
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 ...
- 48k
11
votes
4
answers
1k
views
Surreal numbers, ultrapowers of $\Bbb R$, ordinal-valued functions and the slow-growing hierarchy
Philip Ehrlich's paper “The Absolute Arithmetic Continuum and the Unification of All Numbers Great and Small”, The Bulletin of Symbolic Logic 18 (1) 2012, pp. 1-45. claims as a theorem that, in NBG, $\...
- 9,312
5
votes
2
answers
524
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).
...
- 2,971
2
votes
0
answers
150
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 ...
- 1,278
17
votes
1
answer
416
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,725
15
votes
3
answers
1k
views
Ordinals in constructive mathematics ? (references)
I'm looking for references presenting a constructive treatment of the theory of ordinals. By constructive I mean valid in the internal logic of a topos (so no axiom of choice and no law of excluded ...
- 8,006
5
votes
1
answer
444
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,278
1
vote
2
answers
220
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 ...
- 9,910
4
votes
0
answers
108
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
126
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 ...
- 225k
2
votes
1
answer
157
views
Ordering patterns of projecta by least witness
Let $J$ denote Jensen's modification of the constructible hierarchy. For an ordinal $\alpha$ and an $n\in\mathbb N^+$, let $\rho_n^{J_\alpha}$ denote the $\Sigma_n$-projectum of $J_\alpha$, the least $...
- 1,278
8
votes
1
answer
482
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 =...
- 1,278
14
votes
2
answers
886
views
Who wins infinite Hex?
In this game, you start with a square. Alice tries to connect the top side to the bottom side, and Bob tries to connect the left side to the right side, like in Hex. Unlike in Hex, Alice and Bob use ...
- 5,831
24
votes
5
answers
3k
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 ...
- 33.9k
1
vote
0
answers
120
views
Can every set be ordinal definable?
From Wikipedia:
OD is not necessarily transitive, and need not be a model of ZFC.
This obviously means that, assuming ZFC is consistent, there is a model $M \models \mathrm{ZFC}$ so that $\mathrm{OD}...
- 704
9
votes
0
answers
293
views
Mapping graphs to ordinals
Robertson-Seymour theorem implies that graph minor relation is a well-quasi-ordering, which means (among other things) that this relation can be extended to a well-order, and other result says that ...
- 1,278
2
votes
1
answer
208
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,278
27
votes
5
answers
3k
views
What is induction up to $\varepsilon_0$?
This is a question asked out of curiosity, and because I can't understand the Wikipedia page.
I have often been told that PA cannot prove the validity of induction up to $\varepsilon_0$, which has ...
- 33.9k
7
votes
1
answer
321
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$ ...
- 8,752
6
votes
0
answers
141
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 ...
- 449
7
votes
1
answer
388
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) ...
- 225k
5
votes
1
answer
226
views
An ordinal not $\Sigma_1$ stable in alpha must be in the hull of smaller parameters in $L_\alpha$
This concerns an assertion of Sy Friedman in [1], Lemma 2, which claims that, under certain conditions, if $\beta$ is not 0 and not $\Sigma_1$-stable in $\alpha$, i.e. $L_\beta\prec_1 L_\alpha$, then $...
- 5,632
8
votes
2
answers
1k
views
How this set of functions is ordered?
Notation:
$k, m, n$ are non-negative integers
$f, g, h$ are functions $\mathbb{N} \to \mathbb{N}$
$f^k$ is $k$-th iterate of the function $f$: $f^0(n)=n, f^{k+1}(n)=f^k(f(n))$
$f \prec g$ means ...
- 2,575
22
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-...
- 323
1
vote
1
answer
277
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 ...
- 2,774
5
votes
1
answer
354
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,076
2
votes
1
answer
195
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 α? ...
- 1,278
1
vote
1
answer
194
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 \...
- 8,752
8
votes
3
answers
509
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_\...
- 38.2k
13
votes
1
answer
1k
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 ...
- 1
14
votes
1
answer
1k
views
Peano arithmetic vs. fast-growing hierarchy with pathological fundamental sequences
Fundamental sequence for a countable limit ordinal $\alpha$ is an increasing sequence $\{\alpha[i]\}$ of ordinals of length $\omega$ such that $\lim_{i\rightarrow\omega}\alpha[i]=\alpha$. There are ...
- 4,618