In the ZF set theory ordinals are transitive sets which are well-ordered by $\in$. They are canonical representatives for well-orderings under order-isomorphism. In addition to the intriguing ordinal arithmetics, ordinals give a sturdy backbone to models of ZF and operate as a direct extension of ...

learn more… | top users | synonyms

31
votes
3answers
3k views

A transfinite epistemic logic puzzle: what numbers did Cheryl give to Albert and Bernard?

I expect that nearly everyone here at stackexchange is by now familiar with Cheryl's birthday problem, which spawned many variant problems, including a transfinite version due to Timothy Gowers. In ...
28
votes
7answers
3k views

Why do we classify infinities in so many symbols and ideas?

I recently watched a video about different infinities. That there is $\aleph_0$, then $\omega, \omega+1, \ldots 2\omega, \ldots, \omega^2, \ldots, \omega^\omega, \varepsilon_0, \aleph_1, \omega_1, \...
25
votes
6answers
1k views

Embedding ordinals in $\mathbb{Q}$

All countable ordinals are embeddable in $\mathbb{Q}$. For "small" countable ordinals, it is simple to do this explicitly. $\omega$ is trivial, $\omega+1$ can be e.g. done as $\{\frac{n}{n+1}:n\in \...
21
votes
1answer
390 views

What are some good open problems about countable ordinals?

After reading some books about ordinals I had an impressions that area below $\omega_1$ is thoroughly studied and there is not much new research can be done in it. I hope my impression was wrong. ...
21
votes
3answers
799 views

Conflicting definitions of “continuity” of ordinal-valued functions on the ordinals

I've encountered the following definition in Kunen, Levy, and other places: A function $\mathbf{F}:\mathbf{ON}\to\mathbf{ON}$ is continuous iff for every limit ordinal $\lambda$, we have $\mathbf{F}(\...
19
votes
4answers
848 views

Intuition for $\omega^\omega$

I'm trying to understand the ordinal number $\omega^\omega$ and I'm having a hard time. I think I understand what $\omega^2$ is. It's what I would get if I took countably many copies of $\omega$ and ...
18
votes
1answer
3k views

The cardinality of a countable union of countable sets, without the axiom of choice

One of my homework questions was to prove, from the axioms of ZF only, that a countable union of countable sets does not have cardinality $\aleph_2$. My solution shows that it does not have ...
17
votes
5answers
1k views

Why study cardinals, ordinals and the like?

Why is the study of infinite cardinals, ordinals and the like so prevalent in set theory and logic? What's so interesting about infinite cardinals beyond $\aleph _0 $ and $\mathfrak{c} $? It seems ...
16
votes
2answers
376 views

Is $(\pmb{1} + \pmb{\eta})\cdot\pmb{\omega_1} = \pmb{1} + \pmb{\eta}\cdot\pmb{\omega_1}$?

$\pmb{\eta}$ - order type of $\mathbb{Q}$. $\pmb{1}$ - order type of a singleton set. $\pmb{\omega_0}$ - order type of $\mathbb{N}$. $\pmb{\omega_1}$ - order type of the first uncountable ordinal. ...
16
votes
1answer
279 views

When does ordinal addition/multiplication commute?

I'm looking at basic ordinal arithmetic at the moment, and I am aware that in general, $\alpha+\beta\neq\beta+\alpha$ and $\alpha.\beta\neq\beta.\alpha$ for ordinals $\alpha,\beta$. My question is: ...
16
votes
1answer
501 views

Is there an axiomatic approach to ordinal arithmetic?

I've always wondered, is there an axiomatic approach to the arithmetic of ordinal numbers? If so, I imagine it would be on par with set theory in terms of its proof-theoretic strength.
15
votes
3answers
2k views

Countable compact spaces as ordinals

I heard at some point (without seeing a proof) that every countable, compact space $X$ is homeomorphic to a countable successor ordinal with the usual order topology. Is this true? Perhaps someone can ...
14
votes
3answers
460 views

How many positive numbers need to be added together to ensure that the sum is infinite?

The question in the title is naively stated, so let be make it more precise: Let $\sum_{n\in\alpha}a_n$ be an ordinal-indexed sequence of real numbers such that $a_n>0$ for each $n\in\alpha$, where ...
14
votes
1answer
726 views

Is it really impossible to lose the Hydra game?

In a number of blog posts I found the claim that the game described below cannot be lost, which is to say, every possible strategy is a winning strategy. In each case, a sketch proof is given that ...
14
votes
1answer
410 views

How do you find the smallest of homeomorphic ordinals?

I am trying to get a better feel for the topology of ordinals and just received a great answer to this question where the Cantor-Bendixson rank and degree turn out to be a complete homeomorphism ...
14
votes
2answers
294 views

The preorder of countable order types

Consider the set $\mathcal{O}$ of order types corresponding to all posets of cardinality at most $\aleph_0$. The set $\mathcal{O}$ is a preorder under embeddability of its elements (note that some ...
13
votes
10answers
949 views

What are the most prominent uses of transfinite induction outside of set theory?

What are the most prominent uses of transfinite induction in fields of mathematics other than set theory? (Was it used in Cantor's investigations of trigonometric series?)
13
votes
6answers
1k views

Principle of Transfinite Induction

I am well familiar with the principle of mathematical induction. But while reading a paper by Roggenkamp, I encountered the Principle of Transfinite Induction (PTI). I do not know the theory of ...
12
votes
4answers
814 views

I want to know why $\omega \neq \omega+1$.

In Kunen's book, Set Theory,chapter I.7, he said: $1+\omega=\omega \neq \omega+1$. I want to know why $\omega \neq \omega+1$.
11
votes
4answers
3k views

Examples of transfinite induction

I know what transfinite induction is, but not sure how it is used to prove something. Can anyone show how transfinite induction is used to prove something? A simple case is OK.
10
votes
3answers
1k views

Is the class of cardinals totally ordered?

In a Wikipedia article http://en.wikipedia.org/wiki/Aleph_number#Aleph-one I encountered the following sentence: "If the axiom of choice (AC) is used, it can be proved that the class of cardinal ...
10
votes
3answers
385 views

How many epsilon numbers $<\omega_1$ are there?

An epsilon number is an ordinal $\epsilon$ such that $\epsilon=\omega^\epsilon.$ What is the cardinality of the set of all epsilon numbers less than $\omega_1$? I'm asking this because of a proof I'...
10
votes
2answers
410 views

How many ordinals can we cram into $\mathbb{R}_+$, respecting order?

I've been pondering the following question. How can we measure the amount of "space" above an element $p$ in a partially ordered set $P$? One way would be to try to cram the elements of ...
10
votes
1answer
397 views

Linearly ordered sets “somewhat similar” to $\mathbb{Q}$

$\pmb{\eta}$ - order type of $\mathbb{Q}$. $\pmb{\eta} + \pmb{1}$ - order type of $\mathbb{Q}\cap(0, 1]$. $\pmb{\omega_1}$ - order type of the first uncountable ordinal. Let's say that a linear ...
10
votes
1answer
838 views

Uncountable ordinals without power set axiom

Assume $M$ is a set, in which all axioms of $ZF - P + (V=L)$ hold. Does then $M$ believe that there exists an uncountable ordinal? I mean, why should the class of all countable ordinal numbers be a ...
10
votes
1answer
249 views

When the ordinal sum equals the Hessenberg (“natural”) sum

Let $\alpha_1 \geq \ldots \geq \alpha_n$ be ordinal numbers. I am interested in necessary and sufficient conditions for the ordinal sum $\alpha_1 + \ldots + \alpha_n$ to be equal to the Hessenberg ...
10
votes
1answer
192 views

Is $\pmb{\eta}\cdot\pmb{\omega_1} = (\pmb{\eta} + \pmb{1})\cdot\pmb{\omega_1}$?

$\pmb{\eta}$ - order type of $\mathbb{Q}$. $\pmb{1}$ - order type of a singleton set. $\pmb{\omega_0}$ - order type of $\mathbb{N}$. $\pmb{\omega_1}$ - order type of the first uncountable ordinal. ...
10
votes
3answers
501 views

An order type $\tau$ equal to its power $\tau^n, n>2$

In this question we are concerned only with linear (aka total) order types. By a cardinality of an order type we understand a cardinality of an instance of this type, which obviously does not depend ...
9
votes
3answers
965 views

Uncountability of countable ordinals

According to Wikipedia, there are uncountably many countable ordinals. What is the easiest way to see this? If I construct ordinals in the standard way, $$1,\ 2,\ \ldots,\ \omega,\ \omega +1,\ \omega +...
9
votes
1answer
134 views

Commutative addition on the ordinals

It is well known that ordinal addition is not commutative (for example $\omega+1\neq 1+\omega$), but it is associative. My question regards a new kind of addition defined as: $$a\oplus b = \text{max}\{...
9
votes
2answers
1k views

Cardinal Arithmetic versus Ordinal Arithmetic

I am reading Philosophy, not Set Theory, so please excuse the naivety of my question. My question concerns the wildly different character of ordinal arithmetic versus cardinal arithmetic. The "...
9
votes
2answers
291 views

$\varepsilon$-number countability without choice

Let $\alpha\mapsto\varepsilon_\alpha$ be the enumeration of the $\varepsilon$-numbers--that is, those $\alpha$ such that $\omega^\alpha=\alpha$--by the ordinals. If we know that countable unions of ...
9
votes
2answers
269 views

Ordinal interpretation of Friedman's $n$?

I heard that Kruskal's tree theorem can be turned into a finite form that creates an extremely fast growing function because ordinals could be encoded into trees. On this wiki page it mentions that ...
9
votes
3answers
837 views

Curious facts about ordinal numbers

I have some notes about curious facts about ordinal numbers, for example that their addition is not commutative, multiplication is not distributive from the right hand side and that the exponent rule ...
9
votes
1answer
314 views

Infinite combinatorial games

Hercules vs. Hydra: Recall the story where every time Hercules cuts of a head, two more heads grow instead. Now suppose the following: The hydra starts off with one head, but every time Hercules cuts ...
9
votes
0answers
148 views

Raising a partial function to the power of an ordinal

Consider a set $X$, and let $f : X \rightarrow X$ denote a partial function. Then for natural $n$, we can define $f^n$ as iterated composition, e.g. $f^2 = f \circ f$. Now suppose that $X$ is also ...
9
votes
0answers
314 views

The structure of countable ordinals

Consider the recursively defined hyperoperation sequence $\circ_i$ $$\begin{array}{rcrclclcl} x& \small{+}&(y\ {\small+}1)&:=&x& &&{\small+}&1\\ x& \boldsymbol{+}&...
8
votes
4answers
2k views

Simple example of uncountable ordinal

Can you make a simple example of an uncountable ordinal? With simple I mean that it is easy to prove that the ordinal is uncountable. I know that the set of all the countable ordinals is an ...
8
votes
3answers
642 views

Ordinal exponentiation - $2^{\omega}=\omega$

This is my understanding of ordinal arithmetic - two ordinals are the same as one another if there is an order-preserving bijection between them. So for instance $$1+\omega = \omega$$ because if $...
8
votes
4answers
370 views

Is there an element with no fixed point and of infinite order in $\operatorname{Sym}(X)$ for $X$ infinite?

Let $X$ be an infinite set. Let $\operatorname {Sym}(X)$ denote the group of all bijections from $X$ onto itself. I have been thinking about the existence of elements of infinite order in this group. ...
8
votes
2answers
191 views

Non-measurable subset of $\omega_1$

Consider $\omega_1$ equipped with the order topology. Then Borel subsets of $\omega_1$ are precisely those which contain a closed and unbounded set or the complement contains such a set. There must be ...
8
votes
4answers
166 views

Is $0^\omega=1$?

According to a definition of ordinal exponentiation defined in Kunen's Set Theory: An Introduction to Independence Proofs (pp. 26), we define $$\begin{align} \alpha^0&=1\\ \alpha^{(\beta+1)}&...
8
votes
1answer
550 views

Can any infinite ordinal be expressed as the sum of a limit ordinal and a finite ordinal?

I've been browsing through Jech's and Levy's texts on set theory, and the ideas of ordinals come up fairly quickly. The idea of a limit ordinal is introduced, which is an ordinal with no maximum ...
8
votes
1answer
184 views

Do there exist totally ordered sets with the 'distinct order type' property that are not well-ordered?

Define that the order type of an element $x$ in a totally ordered set $X$ is the order type of $\{w \in X\mid w < x\}$. Under this definition, distinct elements of a well-ordered set have distinct ...
8
votes
4answers
846 views

Simple (even toy) examples for uses of Ordinals?

I want to describe Ordinals using as much low-level mathematics as possible, but I need examples in order to explain the general idea. I want to show how certain mathematical objects are constructed ...
8
votes
1answer
135 views

What classification of countable ordinals above $\omega_1^{CK}$ exists?

What classification of countable ordinals above the Church–Kleene ordinal $\omega_1^{CK}$ exists? Are there such things as $\omega_2^{CK}$, $\omega_{\omega_\omega^{CK}}^{CK}$ or $\omega_{\omega_{\...
8
votes
1answer
278 views

Do we get predicative ordinals above $\Gamma_0$ if we use hyperexponentiation?

I am trying to understand the Veblen hierarchy but I still find it confusing. The Feferman–Schütte ordinal, $\Gamma_0$, can be described as the set of all ordinals that can be written as finite ...
8
votes
1answer
291 views

If $\alpha$ is an indecomposable ordinal, why $\Gamma(\alpha\times{\alpha})=\alpha$?

Greets This is from exercise 3.4 of Thomas Jech's "Set Theory", stated: "Show that $\Gamma(\alpha\times{\alpha})\leq{\omega^{\alpha}}$. Thus $\Gamma(\alpha\times{\alpha})=\alpha$ for all ...
8
votes
1answer
229 views

If $\alpha\leq \beta,\gamma\leq \delta$ then $\alpha+\gamma\leq \beta+\delta$

The title is one of my homework assigments, (and the above greek letters are ordinal numbers) but this is the first one containing inequalities, and I dont really know how to do it. My guess is ...
8
votes
1answer
201 views

what does it mean that constructible universe is definable from ordinals?

I know how constructible universe is created, but I also separatedly read that the universe is definable from ordinals - so I am wondering what it really means.