Ordinal Number

Here are some comments about ordinal number I have known.

Ordinal number is a “order-type” of sets which is used to represent the “length” or “size” of well-ordering sets like 0 = \emptyset, 1 = \{ \emptyset \}. It’s also an extension to \mathbb{N} since all of the natural number could be respresented by ordinal and it’s a proper superset as \omega = \mathbb{N} and \omega + 1 \neq \omega where \alpha + 1 = \alpha \cup \{ \alpha \} called successor of \alpha.

The following is a useful theorem to classify the well-ordering set by ordinal number,

Theorem. Every well-ordering set is isomorphic to an ordinal number.

With AC(Axiom of Choice), we could show that every set could be well-ordering by some order. However, this theorem is equivalent to AC and not provable without any other equivalent axioms.

Transfinite induction is a generalization of normal mathematical induction on \mathbb{N} to all ordinal numbers which states as follows,

Transfinite Induction. If we could prove the following,

  1. P(0) holds.
  2. If P(\alpha) holds, then P(\alpha + 1) holds.
  3. If \alpha is a nonzero limit ordinal number, and for all P(\beta) holds where \beta < \alpha, then P(\alpha) holds.

Then, P(\alpha) holds for all ordinal number \alpha.

Notice 3., the only different thing from usual mathematical induction is we have to deal with the case of limit ordinal number which defined as \alpha \neq \beta + 1 for all ordinal \beta.

We could define arithmetic on this, but however, there is something different. First, we have to deal with the limit ordinal by sequence. Second, the operation of addition, multiplication and exponentiation are not commutative.

Let me introduce the notion of sequence of ordinal first. The usual sequences  are defined on \mathbb{N} (or \omega) if it’s infinite or on \mathbb{Z}_{n} if it’s finite of length n. A transfinite sequence is a function defined on \{ \eta : \eta < \alpha \}. for some ordinal \alpha or just \{ a_{\eta} : \eta < \alpha \}. Sometimes, we could call a function defined on all ordinal number just “sequence”.

Then, we shall introduce the notion of limit of the sequence. \lim_{\eta \rightarrow \alpha} = \sup{} \{\gamma_{\eta} : \eta < \alpha\} where \gamma_{\eta} is a non-decreasing sequence, \alpha is some ordinal, and \sup is the least upper bound of this well-ording set (that is, the existence of \sup comes from it).

Now, we could define ordinal arithmetic as follows (by transfinite recursion).

Definition (Addition). For all ordinal numbers \alpha

  1. \alpha + 0 = \alpha
  2. \alpha + (\beta + 1) = (\alpha + \beta) + 1 for all \beta.
  3. \alpha + \beta = \lim_{\eta \rightarrow \beta} (\alpha + \eta) for all limit ordinal \beta > 0.

Definition (Multiplication).

  1. \alpha \cdot 0 = 0
  2. \alpha \cdot (\beta + 1) = (\alpha \cdot \beta) + \alpha
  3. \alpha \cdot \beta = \lim_{\eta \rightarrow \beta} \alpha \cdot \eta for all limit ordinal \beta

Definition (Exponentiation).

  1. \alpha^{0} = 1
  2. \alpha^{\beta + 1} = \alpha^{\beta} \cdot \alpha for all \beta
  3. \alpha^{\beta} = \lim_{\eta \rightarrow \beta} \alpha^{\eta} for all limit \beta > 0

By the above definition, there is a theorem called Cantor Normal Form which states that every ordinal number has one unique representation as a finite sum of \omega^{\beta}\cdot{}c where \beta is an ordinal, and c is a natural number. The concept of transfinite recusion could be apply to another generalization of well-ordering, the well-founded relation. Maybe it’s the next topic.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s