Redirected from Ordinal
A natural number can be used for two purposes: to describe the size of a set, or to describe the position of an element in a sequence. While in the finite world these two concepts coincide, when dealing with infinite sets one has to distinguish between the two. The size aspect leads to cardinal numbers, which were also discovered by Cantor, while the position aspect is generalized by the ordinal numbers described here.
One can (and usually does) define the natural number n as the set of all smaller natural numbers:
Viewed this way, every natural number is a wellordered set: the set 4 for instance has the elements 0,1,2,3 which are of course ordered as 0<1<2<3 and this is a wellorder. A natural number is smaller than another if and only if it is an element of the other.
We don't want to distinguish between two wellordered sets if they only differ in the "notation for their elements", or more formally: if we can pair off the elements of the first set with the elements of the second set in a onetoone fashion and such that if one element is smaller than another in the first set, then the partner of the first element is smaller than the partner of the second element in the second set, and vice versa. Such a onetoone correspondence is called an order isomorphism and the two wellordered sets are said to be orderisomorphic.
With this convention, one can show that every finite wellordered set is orderisomorphic to one (and only one) natural number. In this case, an equivalent definition for finite is that the opposite order is also wellordered, or that every subset has a maximal element.
This provides the motivation for the generalization: we want to construct ordinal numbers as special wellordered sets in such a way that every wellordered set is orderisomorphic to one and only one ordinal number. The following definition improves on Cantor's approach and was first given by John von Neumann:
Note that the natural numbers are ordinals by this definition. For instance, 2 is an element of 4={0,1,2,3}, and 2 is equal to {0,1} and so it is a subset of {0,1,2,3}.
It can be shown by transfinite induction that every wellordered set is orderisomorphic to exactly one of these ordinals.
Furthermore, the elements of every ordinal are ordinals themselves. Whenever you have two ordinals S and T, S is an element of T if and only if S is a subset of T, and moreover, either S is an element of T, or T is an element of S, or they are equal. So every set of ordinals is totally ordered. And in fact, much more is true: Every set of ordinals is wellordered. This important result generalizes the fact that every set of natural numbers is wellordered and it allows us to use transfinite induction liberally with ordinals.
Another consequence is that every ordinal S is a set having as elements precisely the ordinals smaller than S. This statement completely determines the settheoretic structure of every ordinal in terms of other ordinals. It's used to prove many other useful results about ordinals. One example of these is an important characterization of the order relation between ordinals: every set of ordinals has a supremum, the ordinal gotten by taking the union of all the ordinals in the set. Another example is the fact that the collection of all ordinals is not a set. Indeed, since every ordinal contains only other ordinals, it follows that every member of the collection of all ordinals is also its subset. Thus, if that collection were a set, it would have to be an ordinal itself by definition; then it would be its own member, which contradicts the Axiom of Regularity. (See also the BuraliForti paradox).
To define the sum S + T of two ordinal numbers S and T, one proceeds as follows: first the elements of T are relabeled so that S and T become disjoint, then the wellordered set S is written "to the left" of the wellordered set T, meaning one defines an order on S∪T in which every element of S is smaller than every element of T. The sets S and T themselves keep the ordering they already have. This way, a new wellordered set is formed, and this wellordered set is orderisomorphic to a unique ordinal, which is called S + T. This addition is associative and generalizes the addition of natural numbers.
The first transfinite ordinal is ω, the set of all natural numbers. Let's try to visualize the ordinal ω+ω: two copies of the natural numbers ordered in the normal fashion and the second copy completely to the right of the first. If we write the second copy as {0'<1'<2',...} then ω+ω looks like
You should now be able to "see" that ω + 4 + ω = ω + ω for example.
To multiply the two ordinals S and T you write down the wellordered set T and replace each of its elements with a different copy of the wellordered set S. This results in a wellordered set, which defines a unique ordinal; we call it ST. Again, this operation is associative and generalizes the multiplication of natural numbers.
Here's ω2:
One of the distributive laws holds for ordinal arithmetic: R(S+T) = RS + RT. One can actually "see" that. However, the other distributive law (T+U)R = TR + UR is not generally true: (1+1)ω is equal to 2ω = ω while 1ω + 1ω equals ω+ω. Therefore, the ordinal numbers do not form a ring.
One can now go on to define exponentiation of ordinal numbers and explore its properties. Ordinal numbers present an extremely rich arithmetic. There are ordinal numbers which can not be reached from ω with a finite number of the arithmetical operations addition, multiplication and exponentiation. The smallest such is denoted by ε_{0}. ε_{0} is still countable, but there are also uncountable ordinals. The smallest uncountable ordinal may be identified with the set of all countable ordinals, and is usually denoted by ω_{1}.
The ordinals also carry an interesting order topology by virtue of being totally ordered. In this topology, the sequence 0, 1, 2, 3, 4, ... has limit ω and the sequence ω, ω^ω, ω^(ω^ω), ... has limit ε_{0}. Ordinals which don't have an immediate predecessor can always be written as a limit like this and are called limit ordinals. The topological spaces ω_{1} and its successor ω_{1}+1 are frequently used as the textbook examples of noncountable topologies. For example, in the topological space ω_{1}+1, the element ω_{1} is in the closure of the subset ω_{1} even though no sequence of elements in ω_{1} has the element ω_{1} as its limit.
Some special limit ordinals can be used to measure the size or cardinality of sets. These are the cardinal numbers.
Search Encyclopedia

Featured Article
