Section 3: Ordered sets and ordinal numbers:
Section 3.1: Partially ordered sets.
A binary relation R on a set M is said to be a partial ordering (and the set M is said to be partially ordered) if
i) R is reflexive (aRa for every ).
ii) R is transitive (aRb and bRc together imply aRc)
iii) R is antisymmetric in the sense that aRb and bRa together imply .
For example, if M is the set of all real numbers and aRb means that , then R is partial ordering. (please verify!) This suggests writing (or equivalently ) instead of aRb whenever R is a partial ordering, and we will do so from now on. Similarly, we write if , but ; and if but .
The following examples give some idea of the generality of the concept of a partial ordering:
Any set M can be trivially partially ordered by setting iff .
Let M be the set of all continuous functions defined in a closed interval . Then, we get a partial ordering by setting iff for every .
The set of all subsets is partially ordered if and only if means that .
The set of all integers greater than 1 is partially ordered if “” means that “b is divisible by a.”
Remark: An element of a of a partially ordered set is said to be maximal if implies and minimal if implies . Thus, in Example 4 above, every prime number (greater than 1) is a minimal element. (Of course, 1 is neither prime nor composite.)
Section 3.2: Order-preserving mappings. Isomorphisms:
Let M and be any two partially ordered sets, and let f be a one-to-one mapping of M onto . Then, f is said to be order-preserving if (where ) implies (in ). An order preserving mapping f such that implies is called an isomorphism. In other words, an isomorphism between two partially ordered sets M and is a one-to-one mapping of M onto such that if and only if . Two partially ordered sets M and are said to be isomorphic (to each other) if there exists and isomorphism between them.
Let M be the set of positive integers greater than 1 partially ordered as in example 4 earlier. Let be the same set partially ordered in the natural way, that is, in such a way that if and only if . Then, the mapping of M onto carrying every integer n into itself is order-preserving, but NOT an isomorphism.
Isomorphism between partially ordered sets is an equivalence relation as defined in an earlier blog of this series, being obviously reflexive, symmetric, and transitive. Hence, any given family of partially ordered sets can be partitioned into disjoint classes of isomorphic sets. Clearly, two isomorphic partially ordered sets can be regarded as identical in cases where it is the structure of the partial ordering than the specific nature of the elements of the sets that is of interest.
Some other remarks:
For those of you who are aware, compare now the concepts and some examples of homomorphisms and isomorphisms between two algebraic objects called groups with the above concepts. Two references for the same are: (i) Topics in Algebra by I N Herstein (2) Abstract Algebra by Dummit and Foote.
Some further remarks:
At this stage, it might even be useful to compare the concepts and examples of a cartesian product of two (non-empty) sets A and B; that of a relation R on set A and set B; that of a binary relation on a set A; that, of an equivalence relation on a set A; and also the basic meaning of a function from set A to set B. You will see that there are slight subtle differences.
Sec 3.3 Ordered Sets. Order Types:
Given two elements a and b of a partially ordered set M, it may turn out that neither of the relations or holds. In this case, a and b are said to be noncomparable. Thus, in general, the relation is defined only for certain pairs of elements, which is why M is said to be partially ordered. However, if M has no non-comparable elements, then M is said to be simply ordered or linearly ordered or ordered. In other words, a set M is ordered if it is partially ordered and if, given any two distinct elements , either , or . Obviously, any subset of an ordered set is itself ordered.
Each of the sets figuring in Examples 1 to 4 of Section 3.1 in this blog, is partially ordered, but not ordered. Simple examples of ordered sets are the set of all positive integers, the set of all rational numbers, the set of all real numbers in the and so on (with the usual relations of “greater than” and “less than”.)
Since an ordered set is a special kind of partially ordered set, the concepts of order-preserving mapping and isomorphism apply equally well to ordered sets. Two isomorphic ordered sets are said to have the same order type. Thus “type” is something shared by all isomorphic ordered sets, just as “power” is something shared by all equivalent sets (considered as ‘plain’ sets, without regard for possible orderings).
The simplest example of an ordered set is the set of all positive integers arranged in increasing order, with the usual meaning of the symbol <. The order type of this set is denoted by the symbol . Two isomorphic ordered sets obviously have the same power (because an isomorphism is a one-to-one correspondence). Thus, it makes sense to talk about the power corresponding to a given order type. The converse is not true, since a set of a given power can in general be ordered in many different ways. It is only in the finite case that the number of elements in a set uniquely determines its type, designated by the same symbol n as the number of elements in the set. For example, besides the “natural” order type of the set of positive integers, there is another order type corresponding to the sequence: where odd and even numbers are separately arranged in increasing order but any odd number precedes any even number. It can be shown that the number of distinct order types of a set of power is infinite and in fact, uncountable.
Section 3.4 Ordered sets and products of ordered sets.
Let and be two ordered sets of types and respectively. Then, we can introduce an ordering in the union of the two sets by assuming that :
(i) a and b have the same ordering as in if .
(ii) a and b have the same ordering as in if
(iii) if and .
(Verify that this is actually an ordering of ). The set ordered in this way is called the ordered sum of and denoted by . Note that the order of terms matters here, that is, in general is not isomorphic to . More generally, we can define the ordered sum of any finite number of ordered sets by writing (this will be an exercise problem after this blogged section) :
and so on.
By the ordered sum of the types , denoted by we mean the order type of the set .
Consider the order types and . It is easy to see that . In fact, if finitely many terms are written to the left of the sequence , we again get a set of the same type (Quiz: why?). On the other hand, the order type , that is the order type of the set (***) :
is obviously not equal to .
(Note: ***: In the above listing of elements of the set, we have used the usual curly braces notation, but with the emphasis on the order as shown.)
Again, let and be two ordered sets of types and respectively, Suppose we replace each element of by a “replica” of the set . Then, the resulting set, denoted by is the set of all pairs where and ordered in such a way that:
(i) if for arbitrary
(ii) if .
Note that the order of factors matters here, that is, in general is not isomorphic to . The ordered product of any finite number of ordered sets can be defined by writing (again a problem in the exercise later):
and so on. By the ordered product of the types and , denoted by , we mean the order type of the set .
Section 3.5. Well-ordered sets. Ordinal numbers.
A key concept in the theory of ordered sets is given by:
DEFINITION 1: An ordered set M is said to be well-ordered if every non-empty subset A of M has a smallest (or, “first“) element, that is, an element such that for every .
Example 1: Every finite ordered set is obviously well-ordered.
Example 2: Every non-empty subset of a well-ordered set is itself well-ordered.
Example 3: The set M of numbers in the interval is ordered but not well-ordered. It is true that M has a smallest element, namely, the number 0 but the subset of M consisting of all positive rational numbers has no smallest element.
DEFINITION 2: The order type of a well-ordered set is called an ordinal number or simply, an ordinal. If the set is infinite, the ordinal is said to be transfinite. (NB: This is a good place to point out that the terms “cardinal number” and “power” of a set are synonymous).
Example 4: The set of positive integers arranged in increasing order is well-ordered, and hence, its order type is a transfinite ordinal. The order type of the set is also an ordinal.
Example 5: The set is ordered but not well-ordered. It is true that any non empty subset A of this set has a largest element (that is, an element such that ) for every ), but in general set A will not have a smallest element. In fact, the given set itself has no smallest element. Hence, the order type of given set is denoted by is not an ordinal number.
THEOREM 1. The ordered sum of a finite number of well-ordered sets is itself a well-ordered set.
PROOF 1: Let M be an arbitrary subset of the ordered sum and let be the first of the sets , (namely, the set with the smallest index) containing elements of M. Then, is a subset of the well-ordered set and as such has a smallest element . Clearly, is the smallest element of M itself. QED.
COROLLARY: The ordered sum of a finite number of ordinal numbers is itself an ordinal number.
Thus, new ordinal numbers can be constructed from any given set of ordinal numbers. For example, starting from the positive integers, (that is, the finite ordinal numbers) and the ordinal number , we can construct the new ordinal numbers :
, , , , and so on.
THEOREM 2: The ordered product of two well-ordered sets is itself a well-ordered set.
Let M be an arbitrary subset of so that M is a set of ordered pairs with . The set of all second elements b of pairs in M is a subset of , and as such has a smallest element since is well-ordered. Let denote this smallest element, and consider all pairs of the form contained in M. The set of all first elements a of these pairs is a subset of , and as such has a smallest element since is well-ordered. Let denote this smallest element. Then, the pair is clearly the smallest element of M. QED.
The ordered product of a finite number of well-ordered sets is itself a well-ordered set.
The ordered product of a finite number of ordinal numbers is itself an ordinal number.
Thus it makes sense to talk about ordinal numbers and so on. It is also possible to define such ordinal numbers as .
Section 3.6 Comparison of ordinal numbers:
If and are two ordinal numbers, then they either coincide or else one is larger than the other. As we now show, the same is true for transfinite ordinal numbers. We begin by observing that every element of a well-ordered set M determines an (initial section) P, the set of all such that , and a remainder Q, the set of all such that . Given any two ordinal numbers and , Let M and N be well-ordered sets of order type and . Then, we say that
i) if M and N are isomorphic;
ii) if M is isomorphic to some section of N
iii) if N is isomorphic to some section of M.
(note that this definition makes sense for finite and ).
Let f be an isomorphism of a well-ordered set A onto some subset . Then, for all .
Proof of lemma:
If there are elements such that , then there is a least such element since A is well-ordered. Let be this element, and let . Then , and hence, , since f is an isomorphism. But, then is not the smallest element such that . Contradiction! QED.
It follows from the lemma that a well-ordered set A cannot be isomorphic to any of its sections, since if A were isomorphic to the section determined by a, then clearly . In other words, the two relations
, are incompatible, and so are , . Moreover, the two relations , are incompatible, since otherwise we could use the transitivity to deduce , which is impossible the lemma. Therefore, if one of the three relations
, , ….II
holds, the other two are automatically excluded. We must still show that one of the relations in II above always holds, thereby proving that any two ordinal numbers are always comparable.
Two given ordinal numbers and always satisfy one and only of the relations: , and .
Let be the set of all ordinals . Any two numbers and in are comparable (Recall the meaning of and use the fact that a section of a section of a well-ordered set is itself a section of a well-ordered set) and the corresponding ordering of makes it a well-ordered set of type . In fact, if a set is of type , then by definition, the ordinals less than are the types of well-ordered sets isomorphic to sections of A. Hence, the ordinals themselves are in one-one correspondence with the elements of A. In other words, the elements of a set of type can be numbered by using the ordinals less than : .
Now, let and be two ordinals. Then, and are well-ordered sets of types and , respectively. Moreover, let be the intersection of the sets A and B, that is, the set of all ordinals less than both and . Then, C is well-ordered, of type , say. We now show that . If , then obviously . On the other hand, if , then C is a section of A and hence, . In fact, let , . Then, and are comparable, that is, either or . But, is impossible, since then . Therefore, and hence, C is a section of A, which implies . Moreover, is the first element of the set . Thus, , as asserted, and similarly, . The case , is impossible, since then and . But then on the one hand and on the other hand. It follows that there are only three possibilities:
and and ,
that is, and are comparable.
Let A and B be well-ordered sets. Then, either A is equivalent to B or one of the sets is of greater power than the other, that is, the powers of A and B are comparable.
There is a definite power corresponding to each ordinal. But we have just seen that ordinals are comparable, and so are the corresponding powers.
[[recall the definition of inequality of powers given in Sec 2.5 in the blog series of Kolmogorov and Fomin). (Reproduced here for the sake of helping the memory: Given any two sets M and N, suppose M and N are equivalent. Then, M and N are said to have the same power. Roughly speaking, “power” is something shared by equivalent sets. If M and N are finite, then M and N have the same number of elements, and the concept of the power of a set reduces to the usual notion of the number of elements in a set. The power of the set is and sets which are equivalent to the set are said to have the power of the continuum, c. For the powers of finite sets, that is, for the set of positive integers, we have the notions of “greater than” or “less than”, as well as the notion of equality. These concepts can be extended to infinite sets. If A and B are two sets with powers m(A) and m(B) respectively, either , or A is equivalent to a subset of B such that no subset of B is equivalent to A, then by analogy with the final case, m(A) is less than m(B).]]
To be continued soon,