Lecture
In set theory, an ordinal number, or ordinal (Lat. ordinalis — ordinal), is the order type of a well-ordered set. As a rule, ordinal numbers are identified with hereditarily transitive sets. Ordinals are one of the extensions of the natural numbers, differing both from the integers and from the cardinal numbers. Like other kinds of numbers, they can be added, multiplied, and raised to a power. Infinite ordinal numbers are called transfinite (Lat. trans — beyond, across + finitio — border, limit). Ordinals play a key role in the proof of many theorems of set theory — in particular, thanks to the associated principle of transfinite induction.
Ordinal numbers were introduced by Georg Cantor in 1883 as a way of describing infinite sequences, as well as of classifying sets possessing a certain ordered structure. He discovered ordinal numbers by chance while working on a problem related to trigonometric series.
Sets 
and 
have the same cardinality if a bijective correspondence can be established between them (that is, if one can indicate a function 
that is simultaneously injective and surjective: to each 
from there corresponds a unique 
from , and each 
from is the image of a unique from ).
Suppose that partial orders 
and 
are given on the sets and respectively. Then the partially ordered sets 
and 
are called order-preserving isomorphic if there exists a bijective mapping under which the given order is preserved. In other words, 
if and only if 
. Any well-ordered set is order-preserving isomorphic to the naturally ordered set of ordinal numbers less than some particular ordinal (equal to the order type of ).
Finite ordinal (and cardinal) numbers are the numbers of the natural series: 0, 1, 2, …, since any two total orderings of a finite set are order-preserving isomorphic. The smallest infinitely large ordinal number 
is identified with the cardinal number 
. However, in the case of transfinite numbers greater than , ordinals — compared with cardinal numbers — make it possible to express a finer classification of sets, based on information about their ordering. While all countable sets are described by a single cardinal number, equal to , the number of countable ordinals is infinitely large and, moreover, uncountable:
In this case addition and multiplication do not possess the property of commutativity: thus, 
coincides with , but differs from 
; similarly 
, but not equal to 
. The set of all countable ordinals forms the first uncountable ordinal number 
, corresponding to the cardinal number 
(the number following ). Well-ordered cardinal numbers are identified with their initial ordinals, that is, the minimal ordinals of the corresponding cardinality. The cardinality of an ordinal number defines a «many-to-one» correspondence between the classes of ordinal and cardinal numbers.
Usually an arbitrary ordinal 
is defined as the order type of the set of ordinals strictly less than . This property makes it possible to represent any ordinal number as the set of ordinals strictly less than itself. All ordinal numbers can be divided into three categories: zero, a successor ordinal number, and a limit ordinal number (the latter differ in their cofinality). For a given class of ordinal numbers one can indicate its -th element — in other words, the elements of the class can be indexed (counted). Such a class will be closed and unbounded provided that the indexing function is continuous and never stops. The Cantor normal form makes it possible to represent any ordinal number uniquely as a finite sum of ordinal powers of . Nevertheless, such a form cannot be used as the basis for a universal system of notation for ordinal numbers, because of the presence in it of self-referential representations: for example, 
. One can define ever larger ordinal numbers, but as they grow their description becomes more complicated. Any ordinal number can be represented as a topological space by assigning to it the order topology. Such a topology will be discrete if and only if the corresponding ordinal does not exceed a countable cardinal number, that is, is less than or equal to . A subset will be open in the order topology if and only if it is cofinite or does not contain as an element.
Natural numbers (to which, in this case, 0 also belongs) have two main uses: describing the size of some set and describing the position of an element in a given sequence. In the case of finite sets these notions coincide; up to isomorphism there is a unique way to arrange the elements of a finite set as a sequence. In the case of infinite sets, however, it is necessary to distinguish the notion of size and the associated cardinal numbers from the notion of position, whose generalization is the ordinal numbers described in this article. This is because an infinite set, while possessing a uniquely determined size (cardinality), can be well-ordered in more than one non-isomorphic way.
Whereas the notion of the cardinal number associated with a set does not require any structure to be given on it, ordinals are closely connected with a special kind of sets, which are called well-ordered (in essence these notions are so close that some mathematicians make no distinction between them). This term denotes a linearly ordered set (that is, a set with some uniform way of choosing the smallest and largest value for an arbitrary pair of elements) in which there are no infinitely decreasing sequences (although infinitely increasing ones may exist), or — in an equivalent formulation — a set in which any nonempty subset contains a smallest element. Ordinal numbers can be used both to denote the elements of any given well-ordered set (the smallest element gets the label 0, the one following it — the label 1, the next — 2, «and so on»), and to measure the «size» of the entire set by indicating the smallest ordinal that is not a label of any element of the set. Such a «size» is called the order type of the set.
Any ordinal number is defined by the set of preceding ordinals: in fact, the most common definition of an ordinal number identifies it with the set of preceding ordinals. Thus, the ordinal 42 is the order type of the set of preceding ordinals, that is, of the ordinals from 0 (the smallest ordinal) to 41 (the immediate predecessor of 42), and is usually identified with the set 
. The converse is also true: any downward-closed set of ordinals — that is, one such that for any ordinal 
and an arbitrary ordinal 
the ordinal 
is also an element of — is itself an ordinal (or can be identified with one).
Up to this point we have mentioned only finite ordinals, coinciding with the natural numbers. Besides them there also exist infinite ordinals: the smallest among them is the order type of the natural numbers (finite ordinals) , which can even be identified with the set of natural numbers itself (indeed: the set of natural numbers is downward-closed and, like any set of ordinals, is well-ordered, — consequently, it can be identified with the corresponding ordinal number, which exactly corresponds to the definition of ).
Probably a more intuitive idea of ordinal numbers can be obtained by considering several of their first representatives: as already mentioned above, the set of ordinals begins with the natural numbers 
After all the natural numbers comes the first infinite ordinal , followed by , 
, 
, and so on. (The exact meaning of addition will be defined later, so regard this notation as a mere shorthand.) After all such numbers come (that is, 
), 
, 
, and so on, then 
, and after it — 
. Further, the set of ordinals that can be written in the form 
, where 
and 
— are natural numbers, must also possess a corresponding ordinal number: this number will be 
. It will be followed by 
, 
,…, 
, then 
and — much later — 
(«epsilon-null») (the examples listed give an idea of comparatively small countable ordinals). This process can be continued indefinitely (the expression of «indefiniteness» — is precisely the strong side of ordinal numbers: strictly speaking, when we, enumerating ordinal numbers, use the expression «and so on», we thereby define an ordinal number of larger size). The smallest uncountable ordinal is the set of all countable ordinals and is denoted .
To denote ordinal numbers, lowercase Greek letters 
are usually used. This article adheres to such notation.
Every nonempty subset of a well-ordered set contains a smallest element. Under the axiom of dependent choice, this statement is equivalent to the fact that the set is linearly ordered and contains no infinitely decreasing sequences — the latter formulation is probably easier to visualize. In practice, the importance of the notion of well-orderedness is explained by the possibility of applying transfinite induction, the main idea of which reduces to the following: any property that passes from the predecessors of an element to the element itself must hold for all elements (belonging to the given well-ordered set). If the computational states (of a computer program or a game) can be well-ordered so that each successive step is «less» than the previous one, then the computation process is guaranteed to terminate.
Further, we do not want to distinguish two well-ordered sets if they differ only in the «labeling of their elements», or, in more formal language, if the elements of the first set can be matched with the elements of the second in such a way that in an arbitrarily taken pair of elements of one set the first is less than the second if and only if the same relation holds between their corresponding partners from the second set. Such a one-to-one correspondence is called an order-preserving isomorphism, and two well-ordered sets are called order-preserving isomorphic, or else similar (such similarity is obviously an equivalence relation). If two well-ordered sets are order-preserving isomorphic, then the corresponding isomorphism is unique: this circumstance makes it possible to regard the mentioned sets as practically identical and serves as a basis for the search for a «canonical» representation of isomorphism types (classes). Ordinal numbers not only play the role of such a representation, but also provide us with a canonical labeling of the elements of any well-ordered set.
In other words, we want to introduce the notion of an ordinal as a class of isomorphisms of well-ordered sets, that is, an equivalence class based on the relation of «order-preserving isomorphism». With such an approach, however, there is one technical difficulty: an equivalence class defined in this way turns out to be too large to fit the definition of a set from the point of view of the standard formalization of set theory according to Zermelo–Fraenkel. Nevertheless, this difficulty does not create serious problems. By an ordinal we will mean the order type of an arbitrary set in such a class.
In the original definition of an ordinal number, which can be found, for example, in Principia Mathematica, the order type of some well-ordering is understood as the set of all well-orderings similar to it (order-preserving isomorphic): in other words, an ordinal number is indeed an equivalence class of well-ordered sets. In ZFC theory and related axiomatic systems of set theory, such a definition is unacceptable, since the corresponding equivalence classes are too large to be considered sets. Nevertheless, this definition can be used in type theory and in Quine's axiomatic set theory (New Foundations), as well as other similar systems (in which it makes it possible to formulate an alternative and rather unexpected way of resolving the Burali-Forti paradox of the greatest ordinal number).
Instead of defining an ordinal as an equivalence class of well-ordered sets, we will identify it with a concrete set that serves as the canonical representation of the given class. Thus, an ordinal will be a certain well-ordered set, and any well-ordered set will be similar to exactly one ordinal number.
The standard definition, proposed by von Neumann, is as follows: any ordinal is a well-ordered set consisting of all the ordinals less than it. In symbolic notation: 
. Expressed in more formal language,
A set is an ordinal if and only if it is strictly well-ordered by the relation 
and each element of S is simultaneously its subset.
Note that, in accordance with this definition, the natural numbers are ordinals. Thus, 2 belongs to 4 = {0, 1, 2, 3} and at the same time equals {0, 1}, that is, is a subset of {0, 1, 2, 3}.
Using transfinite induction, one can show that any well-ordered set is similar to exactly one ordinal — in other words, an order-preserving bijective correspondence can be established between them.
Moreover, the elements of any ordinal are themselves ordinals. If and 
— are arbitrary ordinals, then belongs to if and only if is a proper subset of . Further, for any ordinals and one of the relations holds: either 
, or 
, or 
. Thus, any set of ordinals possesses linear ordering and, in addition, is well-ordered. This result serves as a generalization of the well-orderedness of the natural numbers.
It follows from this that the elements of an arbitrary ordinal exactly coincide with the ordinals strictly less than . Every set of ordinals, for example, has a supremum, which is the ordinal equal to the union of all the ordinal numbers contained in the given set. By virtue of the axiom of union, such an ordinal always exists, regardless of the size of the original set.
The class of all ordinal numbers is not a set. Otherwise it could be proved that such a set is itself an ordinal number and, consequently, its own element, which contradicts the strict -orderedness. This statement is called the Burali-Forti paradox. The class of ordinal numbers is denoted in various ways: «Ord», «ON», or «∞».
An ordinal number is finite if and only if it is well-ordered not only by the natural order but also by the opposite order — this condition is satisfied if and only if each of its subsets contains a largest element.
In modern mathematics there also exist other approaches to defining ordinal numbers. Thus, under the axiom of regularity, the following statements about a set x are equivalent:
. For a set 
we define a binary relation 
, consisting of those pairs 
such that 
or 
. A set is called transitive if 
implies 
. A set is called an ordinal if it is transitive and 
— is a well-ordered set. The listed definitions are inapplicable in set theories without the axiom of foundation. In theories with urelements, the definitions must be refined, since urelements are excluded from among the elements of an ordinal number.
If — is a limit ordinal, and — is some set, then an -indexed sequence of elements of is a function from into . The definition of a transfinite sequence or ordinal-indexed sequence introduced in this way is a generalization of the notion of a sequence. An ordinary sequence corresponds to the case 
.
— is an ordinal number, then each element of — is an ordinal number.
exactly one of the following relations holds: 
(in particular, any ordinal number, regarded as a set, is well-ordered by the relation ), with 
— the smallest element of the set , 
— an ordinal number greater than or equal to any of the elements of the set . The expressions 
and 
for ordinal numbers are equivalent. Below it is understood that ordinal numbers are compared by means of the relation 
there exists a unique ordinal number isomorphic to (in particular, for any set of ordinal numbers there exists a unique ordinal number isomorphic to it). coincides with the set of all ordinal numbers less than .
— is the smallest ordinal number (and hence it is an element of any other ordinal number). is called a successor if either it equals , or there exists an immediately preceding 
; in other words, if there exists 
but no other ordinal number 
can be inserted between them. In the latter case it is said that — is the ordinal number following , and one writes: 
(sometimes simply 
, which turns out to be consistent with the notation for the sum of ordinal numbers). is also counted among the limit ordinal numbers).
It is the smallest limit ordinal number and the smallest infinite (namely countable) ordinal number. The ordinal number following it is 
can be written as 
or, what is the same, 
is bounded above and has a least upper bound, which is denoted 
In this case 
— is a limit ordinal number or , then 
otherwise 
, where 
, 
, and 
are ordinal numbers. The form makes it possible to find expansions like the following: 
where the third rule applies in the case when 
is a limit ordinal number.
which makes it possible to write the sum of several terms without parentheses.
it follows that 
and 
then there exists a unique ordinal for which 
which makes it possible to write the product of several factors without parentheses.
Comments