Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
0answers
122 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 ...
5
votes
0answers
115 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
140 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. ...
1
vote
0answers
320 views

Why do some mathematicians believe that the notation $(x_n)_{n\in \omega}$ is better than $(x_n)_{n=0}^\infty$ or $(x_n)_{n\in \mathbb N}$ [closed]

It seems that there is a trend among certain set-theory-oriented mathematicians to prefer the notation $n\in \omega$ to $n\in \mathbb N$ even when dealing with things totally unrelated to ordinal ...
2
votes
0answers
81 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?. Splitting this as a separate question based upon suggestion in comments. Here is the statement of question. If we consider an ...
2
votes
1answer
277 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 \...
9
votes
0answers
434 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
197 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
192 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
213 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
104 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
206 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
212 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
99 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
234 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) | \...
16
votes
0answers
495 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
259 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$): ...
0
votes
0answers
75 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 ...
8
votes
4answers
854 views

Formalizations of The Matchstick Diagram Representation of Ordinals

The matchstick diagram is a really interesting and intuitive method of representing countable ordinals. However, because of how difficult it is to graphically represent ordinals with it, I started ...
2
votes
2answers
230 views

Connection between countable ordinals and Turing degrees

$\omega^{CK}_1$ is the supremum of all the recursive ordinals, where an ordinal $\alpha$ is recursive if there is a computable ordering of a subset of the naturals with order type $\alpha$. For a ...
4
votes
1answer
243 views

What ordinal corresponds to the T(3)?

Let's play a game. You start with the ordinal $\alpha$ and I start with the empty sequence. Each turn, you decrease your ordinal, and I add a tree (where each node can have one of three labels), ...
3
votes
0answers
35 views

Trace-Recursive Functions and Natural/Unnatural Operations

I have been quite hesitant to post this question. Due to the highly general nature of the question there is a possibility of a trivial answer. At a first glance at least, one gets the feeling that ...
8
votes
1answer
381 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 ...
7
votes
3answers
675 views

Do these ordinals exist?

Given an ordinal $\alpha$, I define $F_{n}(\alpha)$ as follows: $F_0(\alpha)=\alpha$ $F_{n+1}(\alpha)$ is the smallest $\beta$ such that no first-order $\phi$ in the language of $\{\in\}$ has $(\...
9
votes
1answer
250 views

Stability for the Gödel and Jensen hierarchies

Notations: Let $L_\alpha$ stand for the Gödel constructible hierarchy ($L_0=\varnothing$ and $L_{\alpha+1} = \mathrm{def}(L_\alpha)$ is the set of definable subsets of $L_\alpha$ and $L_\delta = \...
2
votes
2answers
243 views

Finite Number of Registers and Computable Well-Orderings

I have added the formal definition of the function $address$. The question is divided in two parts. This is important because of two reasons. First due to the length of the question. Secondly if one ...
7
votes
0answers
153 views

$Π^0_1$ Proof Ordinals

Natural theories extending EFA (exponential/elementary function arithmetic) are well-ordered by $Π^0_1$ provability, and we would like a formal definition of the well-ordering that is robust yet as ...
2
votes
0answers
46 views

Splitting of ordinals of oscillation ranks of a Baire $1$ function

Denny and Tang proved that Theorem $2.3$ Let $(f_n)$ be a sequence in $\mathfrak{B}_1(K)$ converging pointwise to a function $f.$ Suppose $\sup\{ \beta(f_n):n\in\mathbb{N} \} \leq \beta_0$ and $\...
4
votes
0answers
109 views

On the proof of a normal form theorem for ordinal (primitive) recursion

Consider the following statement (which follows easily from various results found in the literature): (†) There exists a primitive recursive (“p.r.”) relation $T$ on the ordinals such that, if $(...
2
votes
1answer
226 views

Mapping between Notations

As in my other question, it is assumed that the (total) function describing a given notation is denoted as $address:p\rightarrow \Bbb{N}$ and assumed to be bijective. Suppose we are given two ...
12
votes
1answer
314 views

About primitively recursively recognizable ordinals

Preliminary: I believe the notion of primitive recursive functions on ordinals is standard and unproblematic (the main difference with the finite case is that one needs to introduce a $\sup$ or $\...
7
votes
1answer
196 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 $\...
5
votes
2answers
329 views

What two ordinals are these (based on definable ordinals)?

Let $D$ be the set of definable ordinals. An ordinal s is definable if there is a predicate $p$ (in the language of (first-order) set theory), such that $p(x) \iff x=s$ for all $x$. This is definitely ...
4
votes
1answer
173 views

Are two recursive well-orderings with the same order type recursively isomorphic?

Let $\leq_1$ and $\leq_2$ be recursive well-orderings of $\omega$ that have the same order type. Is there necessarily a recursive bijection $f$ such that $f(x)\leq_1f(y)\iff x\leq_2y$? If this does ...
12
votes
1answer
540 views

The surreal version of $e$

For a sequence $(x_{\alpha})$ of surreal numbers indexed by the set of all ordinal numbers, we say that $\lim x_{\alpha}=l$ ($l$ is a surreal number) if for each surreal $\epsilon>0$, there exists ...
9
votes
1answer
412 views

Is every ordinal the nimber of a ring?

This question is about the game of Noetherian rings, see MO/93276. Here I will include the zero ring in order to get better formulas. The nimber of a Noetherian ring is an ordinal number. It is ...
7
votes
0answers
155 views

First order axioms for primitive recursion in Takeuti's theory of ordinal numbers

In this article, Takeuti has introduced a theory of ordinal numbers, which in his own words, is intended to be a first order theory: The theory of ordinal numbers we are to develop is based on the ...
2
votes
1answer
359 views

careful exposition of transfinite recursion

Given a well ordered set W and a family of sets X(w) indexed by the elements w of W, transfinite recursion allows one often to define a function f on W that takes values f(w) in X(w). (I distinguish ...
6
votes
1answer
283 views

Existence of well-ordering of epsilon_0 in weak theories

In a discussion on a youtube video on the hydra game I jokingly mentioned how everyone was assuming that $\varepsilon_0$ was well-ordered. This lead to a bit of disagreement (in a nice way!) about the ...
2
votes
1answer
442 views

Predicative definition and existence of ordinal numbers

I was thinking about ordinal numbers recently, after I have read the wiki article about impredicativity. Now I have trouble to find a predicative definition of ordinal numbers, or even a "...
5
votes
1answer
399 views

On a characterization of the recursively inaccessible ordinals

For a given set of numbers $A$, let $O^A$ be the hyperjump of $A$. It is possible to iterate inductively the hyperjump of a set, through the computable ordinals, in a way that the $\alpha$-th ...
12
votes
1answer
365 views

Ramsey Theorem for the class ORD

Is it true that given a (definable) 2-coloring of the ORD (class of ordinals), $\chi:[ORD]^{2}\rightarrow\lbrace 0,1\rbrace$, there exists an unbounded $H\subseteq ORD$ which is homogenous, i.e., $\...
4
votes
1answer
258 views

What countable ordinals are called $\kappa_\alpha$?

Jervell has a notation for countable ordinals up to the small Veblen ordinal using trees: • Herman Ruge Jervell, How to wellorder finite trees and get good ordinal notations, Berkeley Logic ...
3
votes
2answers
179 views

What are the minimal requirements for the definable hyperreal field plus transfer?

It is interesting that to prove the transfer principle for the definable hyperreal field, one requires no more choice than for proving, for instance, the countable additivity of the Lebesgue measure. ...
5
votes
2answers
163 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-...
10
votes
0answers
341 views

Computing the ordinal of a rational language well-partially-ordered by the subword relation

Let $\Sigma$ be a finite set or "alphabet", $\Sigma^*$ the free monoid on $\Sigma$ or set of "words". If $w,w'\in \Sigma^*$, write $w\leq w'$ when $w$ is a "subword" of $w'$, i.e., can be obtained by ...
10
votes
2answers
400 views

Is there a modern account of Veblen functions of *several* variables?

Veblen $\phi$ functions extend the $\xi \mapsto \phi(\xi) := \omega^\xi$ and the $\xi \mapsto \phi(1,\xi) := \varepsilon_\xi$ functions on the ordinals by repeatedly taking fixed points (I won't ...
4
votes
1answer
285 views

Reference request, proof about well-ordering of ordinals

I am looking for a second order proof that ordinals are well-ordered up to $\epsilon_0$. So, starting with encoding those ordinals in numbers, defining the < relation on those encoded ordinals and ...
12
votes
1answer
364 views

Is ordinal arithmetic more complicated than classical arithmetic?

Consider the first-order language $\mathcal{L}_{\text{OA}}:=(+,\cdot,0,1)$; in this language, we can formulate statements of ordinal arithmetic. Clearly, the theory $T_{\text{OA}}$ of $(\text{On},+,\...
7
votes
4answers
667 views

Direct axiomatization of ordinal and cardinal numbers

Again, this question is related (**) to a previous one: in standard books on basic set theory, after stating the axioms of ZFC, ordinal numbers are introduced early on. Afterwards cardinals appear: ...