Ordinal number? |
Did you mean | Travel | Economics | Finance | Marketing | Business | Culture | Geography | History | Life | Mathematics | Science | Society | Technology | New site added |
| Add a link on the top of this Ordinal number page Express submission by secure payment ! |
Commonly, ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc., whereas a cardinal number says "how many there are": one, two, three, four, etc. (See How to name numbers.)
An ordinal scale defines a total preorder of objects; the scale values themselves have a total order; names may be used like "bad", "medium", "good"; if numbers are used they are only relevant up to strictly monotonically increasing transformations (order isomorphism). See also level of measurement.
In mathematics, ordinal numbers are an extension of the natural numbers to accommodate infinite sequences, introduced by Georg Cantor in 1897. It is this generalization which will be explained below.
Have to see |
Contents |
|
Introduction
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 notion of size leads to cardinal numbers, which were also discovered by Cantor, while the position is generalized by the ordinal numbers described here.
In set theory, the natural numbers are commonly constructed as sets, such that each natural number is the set of all smaller natural numbers:
- 0 = {} (empty set)
- 1 = {0} = { {} }
- 2 = {0,1} = { {}, { {} } }
- 3 = {0,1,2} = {{}, { {} }, { {}, { {} } }}
- 4 = {0,1,2,3} = { {}, { {} }, { {}, { {} } }, {{}, { {} }, { {}, { {} } }} }
etc.
Viewed this way, every natural number is a well-ordered set: the set 4, for instance, has the elements 0, 1, 2, 3 which are of course ordered as 0 AND1lt; 1 AND1lt; 2 AND1lt; 3. 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 well-ordered 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 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 one-to-one correspondence is called an order isomorphism (or a strictly increasing function) and the two well-ordered sets are said to be order-isomorphic.
Under this convention, one can show that every finite well-ordered set is order-isomorphic to one (and only one) natural number. This provides the motivation for the generalization to infinite numbers.
Modern definition and first properties
We want to construct ordinal numbers as special well-ordered sets in such a way that every well-ordered set is order-isomorphic to one and only one ordinal number. The following definition improves on Cantor's approach and was first given by John von Neumann:
- A set S is an ordinal if and only if S is totally ordered with respect to set containment and every element of S is also a subset of S.
(Here, "set containment" is another name for the subset relationship.) Such a set S is automatically well-ordered with respect to set containment. This relies on the axiom of well foundation: every nonempty set S has an element a which is disjoint from S.
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 well-ordered set is order-isomorphic 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 proper 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 well-ordered. This important result generalizes the fact that every set of natural numbers is well-ordered 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 set-theoretic 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 obtained 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 Burali-Forti paradox).
An ordinal is finite if and only if the opposite order is also well-ordered, which is the case if and only if each of its subsets has a greatest element.
Other definitions
There are other modern formulations of the definition of ordinal. Each of these is essentially equivalent to the definition given above. One of these definitions is the following. A class S is element-transitive (or e-transitive) if, whenever x is an element of y and y is an element of S, then x is an element of S. An ordinal is then defined to be a class S which is e-transitive, and such that every member of S is also e-transitive.
Arithmetic of ordinals
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 well-ordered set S is written "to the left" of the well-ordered 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 well-ordered set is formed, and this well-ordered set is order-isomorphic 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'AND1lt;1'AND1lt;2',w/.} then ω+ω looks like
- 0 AND1lt; 1 AND1lt; 2 AND1lt; 3 AND1lt; w/. AND1lt; 0' AND1lt; 1' AND1lt; 2' AND1lt; w/.
This is different from ω because in ω only 0 does not have a direct predecessor while in ω+ω the two elements 0 and 0' don't have direct predecessors. Here's 3 + ω:
- 0 AND1lt; 1 AND1lt; 2 AND1lt; 0' AND1lt; 1' AND1lt; 2' AND1lt; w/.
and after relabeling, this just looks like ω itself: we have 3 + ω = ω. But ω + 3 is not equal to ω since the former has a largest element and the latter doesn't. So our addition is not commutative.
You should now be able to see that (ω + 4) + ω = ω + (4 + ω) = ω + ω for example.
To multiply the two ordinals S and T you write down the well-ordered set T and replace each of its elements with a different copy of the well-ordered set S. This results in a well-ordered 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:
- 00 AND1lt; 10 AND1lt; 20 AND1lt; 30 AND1lt; w/. AND1lt; 01 AND1lt; 11 AND1lt; 21 AND1lt; 31 AND1lt; w/.
and we see: ω2 = ω + ω. But 2ω looks like this:
- 00 AND1lt; 10 AND1lt; 01 AND1lt; 11 AND1lt; 02 AND1lt; 12 AND1lt; 03 AND1lt; 13 AND1lt; w/.
and after relabeling, this looks just like ω and so we get 2ω = ω. Multiplication of ordinals is not commutative.
Distributivity partially holds for ordinal arithmetic: R(S+T) = RS + RT. 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.
A ring-like structure such as this, with only the left distributive law, is called a (left) nearring: however, ordinals are not quite a nearring either because they do not admit additive inverses (negation). Since a ring without negation is sometimes referred to as a rig, the ordinals may be said to form a left nearrig: a nearring without negation.
One can now go on to define exponentiation of ordinal numbers. For finite exponents, this should be obvious, for instance ω2 = ωω using the operation of ordinal multiplication. But instead this can be visualized as a set of ordered pairs of natural numbers, ordered by a variant of lexicographical order which puts the least significant position first:
- (0,0) AND1lt; (1,0) AND1lt; (2,0) AND1lt; (3,0) AND1lt; w/. AND1lt; (0,1) AND1lt; (1,1) AND1lt; (2,1) AND1lt; (3,1) AND1lt; w/. AND1lt; (0,2) AND1lt; (1,2) AND1lt; (2,2) AND1lt; w/.
And similarly for any finite n, ωn can be visualized as the set of n-tuples of natural numbers.
Then for ωω, we might try to visualize the set of infinite sequences of natural numbers. However, if we try to use any variant of lexicographical order on this set, we find it is not well-ordered. We must add the restriction that only a finite number of elements of the sequence are different from zero. Now our ordering works, and it looks like the ordering of natural numbers written in decimal notation, except with digit positions reversed, and with arbitrary natural numbers instead of just the digits 0-9:
- (0,0,0,w/.) AND1lt; (1,0,0,0,w/.) AND1lt; (2,0,0,0,w/.) AND1lt; w/. AND1lt;
- (0,1,0,0,0,w/.) AND1lt; (1,1,0,0,0,w/.) AND1lt; (2,1,0,0,0,w/.) AND1lt; w/. AND1lt;
- (0,2,0,0,0,w/.) AND1lt; (1,2,0,0,0,w/.) AND1lt; (2,2,0,0,0,w/.)
- AND1lt; w/. AND1lt;
- (0,0,1,0,0,0,w/.) AND1lt; (1,0,1,0,0,0,w/.) AND1lt; (2,0,1,0,0,0,w/.)
- AND1lt; w/.
So in general, raise an ordinal S to the power of an ordinal T, we write down copies of the well-ordered set T, and then replace each element with some element of S, with the restriction that all but a finite number of elements of the sequence must be the first element of S. We find 1ω = 1, 2ω = ω, 2ω + 1 = ω2 = ω + ω. We also have the expected exponentiation laws (ST)U = STU and ST + U = STSU.
Cantor normal form
Ordinal numbers present an extremely rich arithmetic. Every ordinal number α > 0 can be uniquely written as 
, where 
are positive integers, and 
are ordinal numbers (possibly βk = 0). This decomposition of α is called the Cantor normal form of α, and can be considered the positional base-ω numeral system. The highest exponent β1 is called the degree of α, and satisfies 
. In case β1 AND1lt; α, we have a finite representation of α with integers only (attached to a skeleton of ωs, additions, multiplications, and exponentiations).
There are ordinal numbers which cannot be reached from ω with a finite number of the arithmetical operations addition, multiplication and exponentiation. The smallest such is denoted by ε0. This ordinal is very important in many induction proofs, because for many purposes, transfinite induction is only required up to ε0. Note that 
, so that 
.
ε0 is still countable. There exist uncountable ordinals. The smallest uncountable ordinal is equal to the set of all countable ordinals, and is usually denoted by ω1.
Topology and limit ordinals
The ordinals also carry an interesting order topology by virtue of being totally ordered. In this topology, the sequence 0, 1, 2, 3, 4, w/. has limit ω and the sequence ω, ω^ω, ω^(ω^ω), w/. has limit ε0. Ordinals which don't have an immediate predecessor can always be written as a limit of a net of other ordinals (but not necessarily as the limit of a sequence, i.e. as a limit of countably many smaller ordinals) and are called limit ordinals; the other ordinals are the successor ordinals.
The topological spaces ω1 and its successor ω1+1 are frequently used as text-book examples of non-countable topological spaces. 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. The space ω1 is first-countable, but not second-countable, and ω1+1 has neither of these two properties.
Some special ordinals can be used to measure the size or cardinality of sets. These are the cardinal numbers.
See also
References
- Conway, J. H. and Guy, R. K. "Cantor's Ordinal Numbers." In The Book of Numbers. New York: Springer-Verlag, pp. 266-267 and 274, 1996.
- Sierpinski, W. (1965). Cardinal and Ordinal Numbers (2nd ed.). Warszawa: Pantswowe Wydawnictwo Naukowe. Also defines ordinal operations in terms of the Cantor Normal Form.