Ordered Sets and Ordinal Numbers: Introductory Real Analysis: Kolmogorov and Fomin

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 a \in M).

ii) R is transitive (aRb and bRc together imply aRc)

iii) R is antisymmetric in the sense that aRb and bRa together imply a=b.

For example, if M is the set of all real numbers and aRb means that a<b, then R is partial ordering. (please verify!) This suggests writing a \leq b (or equivalently b \geq a) instead of aRb whenever R is a partial ordering, and we will do so from now on. Similarly, we write a < b if a \leq b, but a \neq b; and b > a if b \geq a but b \neq a.

The following examples give some idea of the generality of the concept of a partial ordering:

Example 1:

Any set M can be trivially partially ordered by setting a \leq b iff a=b.

Example 2:

Let M be the set of all continuous functions f, g, \ldots defined in a closed interval [\alpha, \beta]. Then, we get a partial ordering by setting f \leq g iff f(t) \leq g(t) for every t \in [\alpha, \beta].

Example 3:

The set of all subsets M_{1}, M_{2}, \ldots is partially ordered if and only if M_{1} \leq M_{2} means that M_{1} \subset M_{2}.

Example 4:

The set of all integers greater than 1 is partially ordered if “a \leq b” means that “b is divisible by a.”

Remark: An element of a of a partially ordered set is said to be maximal if a \leq b implies b=a and minimal if b \leq a implies b=a. 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 M^{'} be any two partially ordered sets, and let f be a one-to-one mapping of M onto M^{'}. Then, f is said to be order-preserving if a \leq b (where a, b \in M) implies f(a) \leq f(b) (in M^{'}). An order preserving mapping f such that f(a) \leq f(b) implies a \leq b is called an isomorphism. In other words, an isomorphism between two partially ordered sets M and M^{'} is a one-to-one mapping of M onto M^{'} such that f(a) \leq f(b) if and only if a \leq b. Two partially ordered sets M and M^{'} are said to be isomorphic (to each other) if there exists and isomorphism between them.

Example:

Let M be the set of positive integers greater than 1 partially ordered as in example 4 earlier. Let M^{'} be the same set partially ordered in the natural way, that is, in such a way that a \leq b if and only if b-a >0. Then, the mapping of M onto M^{'} carrying every integer n into itself is order-preserving, but NOT an isomorphism.

Some remarks:

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 a \leq b or b \leq a holds. In this case, a and b are said to be noncomparable. Thus, in general, the relation \leq 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 a, b \in M, either a <b, or b<a. 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 [0,1] 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 1,2,3,\ldots arranged in increasing order, with the usual meaning of the symbol <. The order type of this set is denoted by the symbol \omega. 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 \omega of the set of positive integers, there is another order type corresponding to the sequence: 1,3,5, \ldots, 2,4,6, \ldots 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 \aleph_{0} is infinite and in fact, uncountable.

Section 3.4 Ordered sets and products of ordered sets. 

Let M_{1} and M_{2} be two ordered sets of types \theta_{1} and \theta_{2} respectively. Then, we can introduce an ordering in the union M_{1} \bigcup M_{2} of the two sets by assuming that :

(i) a and b have the same ordering as in M_{1} if a,b \in M_{1}.

(ii) a and b have the same ordering as in M_{2} if a,b \in M_{2}

(iii) a <b if a \in M_{1} and b \in M_{2}.

(Verify that this is actually an ordering of M_{1} \bigcup M_{2}). The set M_{1} \bigcup M_{2} ordered in this way is called the ordered sum of M_{1} and M_{2} denoted by M_{1}+M_{2}. Note that the order of terms matters here, that is, in general M_{2}+M_{1} is not isomorphic to M_{1}+M_{2}. 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) :

M_{1}+M_{2}+M_{3}=(M_{1}+M_{2})+M_{3}

M_{1}+M_{2}+M_{3}+M_{4}=(M_{1}+M_{2}+M_{3})+M_{4},

and so on.

By the ordered sum of the types \theta_{1}+\theta_{2}, denoted by \theta_{1}+\theta_{2} we mean the order type of the set M_{1}+M_{2}.

Example:

Consider the order types \omega and n. It is easy to see that n + \omega = \omega. In fact, if finitely many terms are written to the left of the sequence 1,2,3,\ldots, k, \ldots, we again get a set of the same type (Quiz: why?). On the other hand, the order type \omega + n, that is the order type of the set (***) :

\{ 1,2,3, \ldots, k, \ldots, a_{1}, a_{2}, \ldots, a_{n}\} is obviously not equal to \omega.

(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 M_{1} and M_{2} be two ordered sets of types \theta_{1} and \theta_{2} respectively, Suppose we replace each element of M_{2} by a “replica” of the set M_{1}. Then, the resulting set, denoted  by M_{1}.M_{2} is the set of all pairs (a,b) where a \in M_{1} and a \in M_{2} ordered in such a way that:

(i) (a_{1},b_{1})<(a_{2},b_{2}) if b_{1}<b_{2} for arbitrary a_{1},a_{2}

(ii) (a_{1},b)<(a_{2},b) if a_{1}<a_{2}.

Note that the order of factors matters here, that is, in general M_{2}.M_{1} is not isomorphic to M_{1}.M_{2}. The ordered product of any finite number of ordered sets can be defined by writing (again a problem in the exercise later):

M_{1}.M_{2}.M_{3}=(M_{1}.M_{2}).M_{3}

M_{1}.M_{2}.M_{3}.M_{4}=(M_{1}.M_{2}.M_{3}).M_{4}

and so on. By the ordered product of the types \theta_{1} and \theta_{2}, denoted by \theta_{1}.\theta_{2}, we mean the order type of the set M_{1}.M_{2}.

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 \mu such that \mu <a for every a \in A.

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 [0,1] 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 1,2,\ldots, k, \ldots arranged in increasing order is well-ordered, and hence, its order type \omega is a transfinite ordinal. The order type \omega + n of the set \{1,2,\ldots, k, \ldots, a_{1}, a_{2}, \ldots, a_{n} \} is also an ordinal.

Example 5: The set \{ \ldots, -k, \ldots, -3,-2,-1\} 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 \mathscr{v} such that a <mathscr{v}) for every a \in A), 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 \omega^{*} is not an ordinal number.

THEOREM 1The ordered sum of a finite number of well-ordered sets M_{1}, M_{2}, \ldots, M_{n} is itself a well-ordered set.

PROOF 1: Let M be an arbitrary subset of the ordered sum M_{1}+M_{2}+\ldots+M_{n} and let M_{k} be the first of the sets M_{1}, M_{2}, \ldots, M_{n}, (namely, the set with the smallest index) containing elements of M. Then, M \bigcap M_{k} is a subset of the well-ordered set M_{k} and as such has a smallest element \mu. Clearly, \mu is the smallest element of M itself. QED.

COROLLARYThe 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 \omega, we can construct the new ordinal numbers :

\omega + n, \omega + \omega, \omega + \omega + n, \omega + \omega + \omega, and so on.

THEOREM 2The ordered product of two well-ordered sets M_{1}, M_{2} is itself a well-ordered set. 

Proof 2:

Let M be an arbitrary subset of M_{1}\dot M_{2} so that M is a set of ordered pairs (a,b) with a \in M_{1}, b\in M_{2}. The set of all second elements b of pairs in M is a subset of M_{2}, and as such has a smallest element since M_{2} is well-ordered. Let b_{1} denote this smallest element, and consider all pairs of the form (a,b_{1}) contained in M. The set of all first elements a of these pairs is a subset of M_{1}, and as such has a smallest element since M_{1} is well-ordered. Let a_{1} denote this smallest element. Then, the pair (a,b) is clearly the smallest element of M. QED.

COROLLARY 1:

The ordered product of a finite number of well-ordered sets is itself a well-ordered set.

COROLLARY 2:

The ordered product of a finite number of ordinal numbers is itself an ordinal number.

Thus it makes sense to talk about ordinal numbers \omega . n, \omega^{2}, \omega^{2} . n, \omega^{3}, \ldots and so on. It is also possible to define such ordinal numbers as \omega^{\omega}, \omega^{\omega^{\omega}}, \ldots.

Section 3.6 Comparison of ordinal numbers:

If n_{1} and n_{2} 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 a of a well-ordered set M determines an (initial section) P, the set of all x \in M such that x<a, and a remainder Q, the set of all x \in M such that x \geq a. Given any two ordinal numbers \alpha and \beta, Let M and N be well-ordered sets of order type \alpha and \beta. Then, we say that

i) \alpha=\beta if M and N are isomorphic;

ii) \alpha < \beta if M is isomorphic to some section of N

iii) \alpha > \beta if N is isomorphic to some section of M.

(note that this definition makes sense for finite \alpha and \beta).

LEMMA:

Let f be an isomorphism of a well-ordered set A onto some subset B \subset A. Then, f(a) \geq a for all a \in A.

Proof of lemma:

If there are elements a \in A such that f(a)<a, then there is a least such element since A is well-ordered. Let a_{0} be this element, and let b_{0}=f(a_{0}). Then b_{0}<a_{0}, and hence, f(b_{0})<f(a_{0})=b_{0}, since f is an isomorphism. But, then a_{0} is not the smallest element such that f(a)<a. 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 f(a)<a. In other words, the two relations

\alpha=\beta, \alpha<\beta are incompatible, and so are \alpha=\beta, \alpha>\beta. Moreover, the two relations \alpha<\beta, \alpha>\beta are incompatible, since otherwise we could use the transitivity to deduce \alpha < \alpha, which is impossible the lemma. Therefore, if one of the three relations

\alpha<\beta, \alpha=\beta, \alpha>\beta….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.

THEOREM 3:

Two given ordinal numbers \alpha and \beta always satisfy one and only of the relations: \alpha=\beta, \alpha < \beta and \beta<\alpha.

Proof 3:

Let W(\alpha) be the set of all ordinals <\alpha. Any two numbers \gamma and \gamma^{'} in W(\alpha) are comparable (Recall the meaning of \gamma < \alpha, \gamma^{'}<\alpha 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 W(\alpha) makes it a well-ordered set of type \alpha. In fact, if a set A = \{ \ldots, a, \ldots, b, \ldots\} is of type \alpha, then by definition, the ordinals less than \alpha 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 \alpha can be numbered by using the ordinals less than \alpha: A = \{ a_{1}, a_{2}, \ldots, a_{n}, \ldots\}.

Now, let \alpha and \beta be two ordinals. Then, W(\alpha) and W(\beta) are well-ordered sets of types \alpha and \beta, respectively. Moreover, let C=A \bigcap B be the intersection of the sets A and B, that is, the set of all ordinals less than both \alpha and \beta. Then, C is well-ordered, of type \gamma, say. We now show that \gamma \leq \alpha. If C=A, then obviously \gamma=\alpha. On the other hand, if C \neq A, then C is a section of A and hence, \gamma < \alpha. In fact, let \xi \in C, \eta \in A - C. Then, \xi and \eta are comparable, that is, either \xi < \eta or \xi > \eta. But, \eta < \xi < \alpha is impossible, since then \eta \in C. Therefore, \xi < \eta and hence, C is a section of A, which implies \gamma < \alpha. Moreover, \gamma is the first element of the set A-C. Thus, \gamma < alpha, as asserted, and similarly, \gamma < \beta. The case \gamma < \alpha, \gamma < \beta is impossible, since then \gamma \in A-C and \gamma \in B-C. But then \gamma \notin C on the one hand and \gamma \in A \bigcap B = C on the other hand. It follows that there are only three possibilities:

\gamma=\alpha and \gamma = \beta and \alpha=\beta

\gamma=\alpha and \gamma< \beta and \alpha < \beta

\gamma < \alpha and \gamma = \beta and \alpha > \beta,

that is, \alpha and \beta are comparable.

QED.

THEOREM 4:

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.

PROOF 4:

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 \mathcal{Z_{+}} is \aleph_{0} and sets which are equivalent to the set [0,1] 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 m(A)=m(B), 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,

Regards,

Nalin Pithwa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.