What does it mean for a well ordering to have length ω? ω^ω?

Question

From what I understand, an ordinal is the position of an element in a set. For example, in [2,4,6....] the element [4] has ordinal 2 (please correct me if I'm wrong).

What does it mean to have ordinal ω? Is this the ordinal of infinity?

What is the meaning of ω^ω?

Answer 1

There's some confusion going on here about what an ordinal is, so let me start at the beginning.

A linear order is a set $S$ together with a binary relation on $S$, $\prec$, with some reasonable properties:

• (transitivity) $a\prec b$ and $b\prec c$ implies $a\prec c$; and

• (trichotomy) For all $a, b\in S$, exactly one of the following holds:

  • $a\prec b$;

  • $b\prec a$; or

  • $a=b$.

Some examples of linear orders include $\mathbb{Z},\mathbb{Q},\mathbb{R},\mathbb{N}$ with the usual orderings, but there are other weird ones too (like the Sharkovskii order, an important object in dynamical systems theory).

Now, amongst all linear orders, we're interested in the ones with a particular property: well-orderedness.

A linear order $(S, \prec)$ is well-ordered if it has no infinite descending sequence $s_0\succ s_1\succ s_2\succ . . .$; equivalently, if every nonempty subset of $S$ has a $\prec$-least element.

For instance, the naturals are well-ordered, but the integers, the rationals, and the reals (with the usual orderings anyways) are not.

The interest in well-orders mainly comes from the fact that they support proof by induction:

Exercise: suppose $(S, \prec)$ is a well-order, and $P$ is some property of elements of $S$ such that $P(s)$ holds whenever $\forall t\prec s(P(t))$. Then $P(s)$ holds for all $s\in S$. HINT: consider the set $\{s: \neg P(s)\}$. . .

Now it turns out that well-orderings "look like $\mathbb{N}$ with stuff at the end." For example, consider the ordering on the naturals we get by "moving $1$ to the front": $$2\prec 3\prec 4\prec . . . \prec 1.\quad (\forall m, n\in\mathbb{N}[m\prec n\iff 1<m<n \mbox{ or } n=1, m\not=1]).$$ This is also a well-ordering (exercise).

Now let's go back to ordinals. One usage of ordinals is to name terms in a sequence; that's the one you mention in the OP. In set theory, though, the more common usage is to name the shape (or order type) of a sequence. What do I mean by that? Well, $$2, 1, -117$$ has three terms - I'm going to say it has order-type $3$. Similarly, $$1, 2, 3$$ has order-type $3$.

"$\omega$" is the symbol we use to describe the order type of $$1\prec 2\prec 3\prec . . .,$$ that is, of the natural numbers with the usual ordering. Now here's the fun bit: what is the order type of the well-order $2\prec 3\prec 4\prec . . . \prec 1$ described above?

Well, consider the map $f: x\mapsto x+1$. This gives an order-preserving bijection from the naturals with their usual order, to this weird order except $1$. Basically, this new well-order has ordertype . . . $\omega+1$!

We can make longer and longer well-orderings. For example, the order type of $$1\prec 3\prec 5\prec 7\prec . . . \prec 2\prec 4\prec 6\prec 8\prec . . . .$$ is $\omega+\omega$.

This should hopefully give some intuition behind what ordinals (= order-types of well-orderings) are doing. I've stopped short of ordinal exponentiation, but I think getting a good grounding in what ordinals mean, intuitively, is more important at first.

Answer 2

To be precise an ordinal number is an equivalence class defined on well-ordered sets where two are equivalent if and only if there exists an ordering preserving bijection between them.

These ordinal numbers are ordered themselves: ordinal number $x$ is lower then ordinal number $y$ if and only if there exists an ordering preserving injection between some members of corresponding equivalence classes. Thus we can order ordinal numbers and there's a theorem stating that every set of ordinal numbers is well ordered. Thus it produces an ordinal number as well.

Examples:

1. $[\emptyset]$ is the smallest ordinal
2. $[\emptyset] < [\{1\}]$ and there's nothing between them
3. $[\emptyset] < [\{1\}] < [\{1 < 2\}]$ and there's nothing between them
4. $[\emptyset] < [\{1\}] < [\{1 < 2\}] < [\{1 < 2 < 3\}]$ and there's nothing between them

and so on. Brackets $[]$ denote "equivalence class" and note that $<$ inside brackets $[]$ denotes how the sets are ordered and external $<$ denotes how those well-ordered sets are related to each other.

By convenience we use the same symbol for numbers and finite ordinals, i.e.

$$0 := [\emptyset]$$ $$n := [\{1 < \cdots < n\}]$$

Now the interesting thing is when you hit infinity. Note that if you take the set of natural numbers $\mathbb{N} = \{1 < 2 < 3 < \cdots\}$ then it is bigger then any finite set. In particular

$$[\{1 < \cdots < n\}] < [\mathbb{N}]$$

And it can be shown that $\mathbb{N}$ is the smallest ordinal with this property. This ordinal was named omega:

$$\omega := [\mathbb{N}]$$

In particular we have a sequence of ordinals:

$$(0 < 1 < 2 < 3 < \cdots) < \omega$$

But here's something interesting: we can increase that set (in the sense of well ordering, the cardinality doesn't change). Consider $X = \mathbb{N}\cup \{\alpha\}$ where $\alpha$ is just a symbol (element not in $\mathbb{N}$) and define $\alpha > n$ for any $n\in\mathbb{N}$. This set is bigger then $\mathbb{N}$ and actually it defines the very next ordinal after $\omega$, denoted $\omega + 1$.

This construction can go on so you get $\omega+2, \omega+3, \ldots$ and by going to the limit (the idea similar to the one above) we get $\omega\cdot 2 = \omega+\omega$.

This construction goes on as well so you get $\omega\cdot 2, \omega\cdot 3,\omega\cdot 4, \ldots$ and now by going to the limit we obtain $\omega^{2}$.

Again we can repeat the construction: $\omega^{3}, \omega^{4}, \ldots$ and by taking a limit we finally arrive at $\omega^{\omega}$.

Note that this is not the end. The construction can be extended even further to $\omega^{\omega^{\omega}}, \omega^{\omega^{\omega^{\omega}}}, \ldots$ without ever reaching the end of those (which is beyond the size of any set).