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
1 answer
86 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 ...
mmiliauskas's user avatar
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 ...
Alexey Slizkov's user avatar
0 votes
0 answers
26 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$. ...
Gabriel Nivasch's user avatar
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<...
X X's user avatar
  • 31
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 ...
Gabriel Nivasch's user avatar
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 ...
Guillermo Mosse's user avatar
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$ ...
user107952's user avatar
  • 2,063
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 ...
gksato's user avatar
  • 317
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). ...
0x11111's user avatar
  • 493
10 votes
2 answers
498 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 ...
Jim Kingdon's user avatar
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 ...
Mehmet Onat's user avatar
  • 1,161
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 ...
Yto's user avatar
  • 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 ...
Yto's user avatar
  • 148
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$-...
C7X's user avatar
  • 1,308
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 ...
C7X's user avatar
  • 1,308
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}<_{...
Reflecting_Ordinal's user avatar
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$ ...
Reflecting_Ordinal's user avatar
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}...
Binary198's user avatar
  • 704
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 ...
Reflecting_Ordinal's user avatar
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 ...
Reflecting_Ordinal's user avatar
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 ...
interstice's user avatar
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$ ...
Reflecting_Ordinal's user avatar
7 votes
1 answer
389 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) ...
lyrically wicked's user avatar
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-...
Vivaan Daga's user avatar
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 \...
Victor's user avatar
  • 2,076
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 \...
Johan's user avatar
  • 531
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_\...
Johan's user avatar
  • 531
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_{...
ViHdzP's user avatar
  • 281
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 $...
Reflecting_Ordinal's user avatar
2 votes
1 answer
226 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 ...
lyrically wicked's user avatar
3 votes
0 answers
326 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 ...
Dan's user avatar
  • 1,288
1 vote
0 answers
159 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 ...
Zuhair Al-Johar's user avatar
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 (...
C7X's user avatar
  • 1,308
5 votes
1 answer
281 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 ...
Simon Henry's user avatar
  • 40.2k
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 $...
C7X's user avatar
  • 1,308
2 votes
0 answers
226 views

The supremum of ordinals eventually writable by Ordinal Turing Machines with an oracle for the class of stabilization ordinals

This question is based on the assumption that all computations start with no ordinal parameters (i.e. the input is empty). The term “stabilization time of a machine” for this question implies the ...
lyrically wicked's user avatar
4 votes
1 answer
255 views

Existence of a particular function that maps an arbitrary set of ordinals to a single ordinal

Does there exist a function $f$ that satisfies all of the following three properties? The function converts an arbitrarily large (empty, finite, countably/uncountably infinite) set of ordinals to a ...
lyrically wicked's user avatar
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, ...
C7X's user avatar
  • 1,308
8 votes
1 answer
522 views

Where was the Cantor normal form theorem first proved?

We all take for granted the theorem that every ordinal $\alpha > 0$ has a Cantor normal form, and there are plenty of proofs of it, some of which are on this site. However, where was it proved? Was ...
Binary198's user avatar
  • 704
2 votes
2 answers
172 views

Diagonalization over a normal function and its derivatives on transfinite ordinals

Let $\Phi(0,\beta)$ a normal function from $On$ to $On$, and let $\Phi(\alpha,\beta)$ be the $\alpha$-th derivative of $\Phi(0,\beta)$. For example, let $\Phi(0,\beta)=\aleph_\beta$. Then, all ...
Delta89's user avatar
  • 21
12 votes
2 answers
979 views

Is there a proof of strong normalisation that uses ordinal numbers?

I am currently trying to find a proof for strong normalisation of an extension of $\lambda$-calculus. I've tried several approaches and one would be to assign an ordinal number $\operatorname{cs}(t)$ ...
Zermelo-Fraenkel's user avatar
3 votes
0 answers
243 views

Is this recursion theoretic analogue of a criterion of weakly compact cardinal accurate?

Jensen proved that, if V=L, and $\kappa$ is a regular cardinal, then if for any stationary $A\subseteq \kappa$, the set $\{\alpha\mid A \text{ is stationary below }\alpha\}$ is stationary in $\kappa$, ...
Reflecting_Ordinal's user avatar
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 ...
C7X's user avatar
  • 1,308
3 votes
0 answers
149 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 ...
Boris Dimitrov's user avatar
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 =...
Binary198's user avatar
  • 704
7 votes
2 answers
468 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_\...
Boris Dimitrov's user avatar
4 votes
3 answers
646 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} = \...
FreakyByte's user avatar
0 votes
0 answers
143 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 ...
Reflecting_Ordinal's user avatar
7 votes
1 answer
377 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}$, ...
Reflecting_Ordinal's user avatar
5 votes
1 answer
401 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?
Reflecting_Ordinal's user avatar

1
2 3 4 5