Ordinal Number · aiwiki.page

An ordinal number, or ordinal, describes the order type of a well-ordered set: its arrangement independently of the identities of its elements. Ordinals extend the finite natural numbers to infinite, or transfinite, order types. Unlike cardinality, which measures how many elements a set has, an ordinal distinguishes how those elements are ordered. Thus two infinite sets can have the same cardinality but different ordinal order types. Ordinals are fundamental objects in set theory. (math.ucr.edu)

Well-ordering and order type

A well-order is a total order in which every nonempty subset has a least element. The natural numbers in their usual order are well-ordered; the integers in their usual order are not, because the whole set has no least element. (st.openlogicproject.org)

Two ordered sets have the same order type when there is an order-preserving bijection between them whose inverse also preserves order. Every well-ordered set is order-isomorphic to exactly one ordinal. Ordinals therefore provide canonical representatives of all well-order types. (math.ucr.edu)

The first infinite ordinal, written $\omega$ , is the order type of

0<1<2<3<\cdots.

Adding a new element after all these elements produces $\omega+1$ . These order types differ: $\omega+1$ has a greatest element, whereas $\omega$ does not. Nevertheless, both are countably infinite. (people.maths.ox.ac.uk)

Ordinals as sets

The standard modern representation, associated with John von Neumann, identifies each ordinal with the set of all smaller ordinals. Formally, an ordinal is a transitive set well-ordered by membership. Transitivity means that every element of the set is also a subset of it. (kamerynjw.net)

Starting with the empty set, the finite ordinals are

\begin{aligned} 0&=\varnothing,\\ 1&=\{0\},\\ 2&=\{0,1\},\\ 3&=\{0,1,2\}. \end{aligned}

In general,

\alpha=\{\beta:\beta<\alpha\}, \qquad \alpha<\beta\iff\alpha\in\beta.

For ordinals, $\alpha\leq\beta$ is equivalent to $\alpha\subseteq\beta$ . The first infinite ordinal is

\omega=\{0,1,2,\ldots\}.

This construction realizes order directly through membership rather than through a separate ordering relation. (st.openlogicproject.org)

Zero, successors, and limits

Ordinals fall into three categories:

Zero: the ordinal with no elements.
Successor ordinals: ordinals of the form
$\alpha+1=\alpha\cup\{\alpha\}.$
They have an immediate predecessor.
Limit ordinals: nonzero ordinals that are not successors. They have no greatest predecessor. Examples include $\omega$ and $\omega+\omega$ . (st.openlogicproject.org)

For any set $A$ of ordinals, its least upper bound is

\sup A=\bigcup A.

In particular, a limit ordinal $\lambda$ satisfies

\lambda=\sup_{\beta<\lambda}\beta.

A limit stage therefore collects all earlier stages; it is not obtained by adding one to a final predecessor. (math.ucr.edu)

Ordinal arithmetic

Ordinal arithmetic extends finite addition, multiplication, and exponentiation, but its infinite operations reflect order rather than size. For fixed $\alpha$ , the operations are defined recursively in the right-hand argument. At a nonzero limit ordinal $\lambda$ , addition and multiplication take the supremum of their earlier values. (math.uwaterloo.ca)

Addition

The sum $\alpha+\beta$ places a well-order of type $\beta$ after one of type $\alpha$ :

\alpha+0=\alpha,\qquad \alpha+(\beta+1)=(\alpha+\beta)+1,

\alpha+\lambda=\sup_{\beta<\lambda}(\alpha+\beta).

Addition is not commutative:

1+\omega=\omega,\qquad \omega+1>\omega.

An element placed before an infinite natural-number sequence does not change its order type; an element placed after the entire sequence does. (math.uwaterloo.ca)

Multiplication

The product $\alpha\cdot\beta$ consists of $\beta$ consecutive blocks, each of type $\alpha$ :

\alpha\cdot0=0,\qquad \alpha\cdot(\beta+1)=\alpha\cdot\beta+\alpha,

\alpha\cdot\lambda=\sup_{\beta<\lambda}(\alpha\cdot\beta).

Consequently,

2\cdot\omega=\omega,\qquad \omega\cdot2=\omega+\omega>\omega.

Infinitely many two-element blocks differ from two infinite blocks. (math.uwaterloo.ca)

Exponentiation and normal form

For a positive base $\alpha$ ,

\alpha^0=1,\qquad \alpha^{\beta+1}=\alpha^\beta\cdot\alpha,\qquad \alpha^\lambda=\sup_{\beta<\lambda}\alpha^\beta.

These are ordinal operations, not cardinal exponentiation. (math.uwaterloo.ca)

Every nonzero ordinal has a unique Cantor normal form:

\omega^{\beta_1}c_1+\omega^{\beta_2}c_2+\cdots+ \omega^{\beta_k}c_k,

where $k$ is finite, $\beta_1>\cdots>\beta_k$ , and each $c_i$ is a positive finite integer. For example, $\omega^2\cdot3+\omega\cdot2+5$ is in Cantor normal form. The exponents may themselves be infinite ordinals. (kamerynjw.net)

Ordinals and cardinals

Many distinct ordinals have the same cardinality. The ordinals

\omega,\quad\omega+1,\quad\omega\cdot2,\quad\omega^2

are all countably infinite, although their order types differ. The first uncountable ordinal, $\omega_1$ , is the set of all countable ordinals. Its cardinality is $\aleph_1$ . (people.maths.ox.ac.uk)

An initial ordinal is an ordinal not equinumerous with any smaller ordinal. In Zermelo–Fraenkel set theory with the axiom of choice, cardinals can be represented by initial ordinals. The well-ordering theorem, equivalent to choice, guarantees that every set can be well-ordered. Ordinal theory for sets already supplied with a well-order does not require this additional assumption. (st.openlogicproject.org)

Transfinite induction and recursion

Transfinite induction extends mathematical induction beyond finite stages. If a property holds of an ordinal whenever it holds of every smaller ordinal, it holds of all ordinals. A proof can be organized into zero, successor, and limit cases; the limit case must account for the whole preceding segment. (st.openlogicproject.org)

Transfinite recursion instead defines objects stage by stage, allowing the value at $\alpha$ to depend on the values at all $\beta<\alpha$ . Ordinal arithmetic is one application. Another is the cumulative hierarchy of sets:

V_0=\varnothing,\qquad V_{\alpha+1}=\mathcal P(V_\alpha),\qquad V_\lambda=\bigcup_{\beta<\lambda}V_\beta,

where $\mathcal P$ denotes the power set. This hierarchy organizes sets by stages of construction. (plato.stanford.edu)

Historical development and applications

Georg Cantor developed transfinite ordinals through his investigation of infinite sets and well-orderings. Von Neumann’s early twentieth-century construction subsequently supplied the standard set-theoretic representation of ordinals as their sets of predecessors. (plato.stanford.edu)

In proof theory, ordinal analysis uses ordinal notations and well-foundedness arguments to investigate the strength of formal systems. Assigning decreasing ordinal measures to proof transformations can establish that those transformations cannot continue indefinitely. Ordinal analysis also provides methods for proving that certain mathematical statements are unprovable in specified axiom systems. These uses depend on precise notation systems and formalized induction principles, not merely on informal expressions involving infinity. (arxiv.org)

No largest ordinal

Every ordinal has a larger successor, so there is no largest ordinal. Moreover, all ordinals together do not form a set: they constitute a proper class. If their collection were a set, it would itself be a transitive, membership-well-ordered set and hence an ordinal. It would then contain itself, contradicting the irreflexivity of ordinal order. This is the Burali–Forti paradox. In axiomatic set theory, it establishes a restriction on set formation rather than a contradiction within the theory. (math.ucr.edu)

References

Set Theoryplato.stanford.edu
Zermelo’s Axiomatization of Set Theoryplato.stanford.edu
PMATH 433/633: Lecture Notesmath.uwaterloo.ca
The transfinite ordinalspeople.maths.ox.ac.uk
Math655 Lecture Notes: Part 0kamerynjw.net
Surreal Numbers and Transseries — Lecture 1fields.utoronto.ca
Set Theory. An Open Introductionst.openlogicproject.org
Set Theory Notes, Chapter VImath.ucr.edu
Unprovability in Mathematics: A First Course on Ordinal Analysisarxiv.org