# Introductory real analysis: exercise 3:

Based on previous two blogs. (Reference: Introductory Real Analysis by Kolmogorov and Fomin, Dover Publishers):

Problem 1:Exhibit both a partial ordering and a simple ordering of the set of all complex numbers.

Problem 2:What is the minimal element of the set of all subsets of a given set X, partially ordered by set inclusion. What is the maximal element?

Problem 3: A partially ordered set M is said to be a directed set if, given any two elements $a, b \in M$, there is an element $c \in M$ such that $a < c, b. Are the partially ordered sets in the previous blog(s) Section 3.1 all directed sets?

Problem 4: By the greatest lower bound of two elements a and b of a partially ordered set M, we mean an element $c \in M$ such that $c \leq a, c \leq b$ and there is no element $d \in M$ such that $a < d \leq a, d \leq b$. Similarly, by the least upper bound of a and b, we mean an element $c \in M$ such that $a \leq c, b \leq c$ and there is no element $d \in M$ such that $a \leq d . By a lattice is meant a partially ordered set any two elements of which have both a greatest lower bound and a least upper bound. Prove that the set of all subsets of a given set X, partially ordered by set inclusion, is a lattice. What is the set theoretic meaning of the greatest lower bound and least upper bound of two elements of this set?

Problem 5: Prove that an order preserving mapping of one ordered set onto another is automatically an isomorphism.

Problem 6: Prove that ordered sums and products of ordered sets are associative, that is, prove that if $M_{1}, M_{2}, M_{3}$ are ordered sets, then

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

$(M_{1}.M_{2}).M_{3}=M_{1}.(M_{2}.M_{3})$ where the operations + and . are the same as defined in previous blog(s).

Comment: This allows us to drop the parentheses in writing ordered sums and products.

Problem 7:

Construct well-ordered sets with ordinals

$\omega + n$, $\omega + \omega$, $\omega + \omega + n$, $\omega + \omega + \omega$, $\ldots$.

Show that the sets are all countable.

Problem 8:

Construct well-ordered sets with ordinals

$\omega . n$, $\omega^{2}$, $\omega^{2}.n$, $\omega^{3}$, $\ldots$.

Show that the sets are all countable.

Problem 9:

Show that $\omega + \omega = \omega. 2$, $\omega + \omega + \omega = \omega. 3$, $\ldots$

Problem 10:

Prove that the set $W(\alpha)$ of all ordinals less than a given ordinal $\alpha$ is well-ordered.

Problem 11:

Prove that any non-empty set of ordinals is well-ordered.

Problem 12:

Prove that the set M of all ordinals corresponding to a countable set is itself uncountable.

Problem 13:

Let $\aleph_{1}$ be the power of the set M in the previous problem. Prove that there is no power m such that $\aleph_{0} .

More later,

Nalin Pithwa.

# Introductory Real Analysis: The well-ordering theorem, the axiom of choice,equivalent assertions

Reference: Introductory Real Analysis by Kolmogorov and Fomin, Dover Publications.

Section 3.7 The well-ordering theorem, the axiom of choice, and equivalent assertions:

Theorem 4 of previous blog shows that the powers of two well-ordered sets are always comparable. In 1904, Zermelo succeeded in proving the

Well-ordering theorem: Every set can be well-ordered.

It follows from the well-ordering theorem and Theorem 5 (of previous blog) that the powers of two arbitrary sets are always comparable, a fact already used earlier. Zermelo’s proof, which will not be given here, rests on the following basic:

AXIOM OF CHOICE:

Given any set M, there is a “choice function” f such that $f(A)$ is an element of A for every non-empty subset $A \subset M$.

We will assume the validity of the axiom of choice without further ado. In fact, without the axiom of choice we would be severely hampered in making set-theoretic constructions. However, it should be noted that from the standpoint of the foundations of set theory, there are still deep and controversial problems associated with the use of axiom of choice.

There are a number of assertions equivalent to the axiom of choice, that is, assertions each of which both implies and is implied by the axiom of choice. One of these is the well-ordering theorem, which obviously implies the axiom of choice. In fact, if an arbitrary set M can be well-ordered, then, by merely choosing the “first” element in each subset $A \subset M$, we get the function $f(A)$ figuring in the statement of the axiom of choice. On the other hand, the axiom of choice implies the well-ordering theorem, as already noted without proof.

To state further assertions equivalent to the axiom of choice, we need some more terminology:

DEFINITION 3:

Let M be a partially ordered set, and let A be any subset of M such that a and b are comparable for every $a, b \in A$. Then, A is called a chain (in M). A chain C is said to be maximal if there is no other chain C in M containing C on a proper subset.

DEFINITION 4:

An element a of a partially ordered set M is called an upper bound of a subset $M^{'} \subset M$, if $a^{'} < a$ for every $a^{'} \in M^{'}$.

We now have the vocabulary needed to state two other assertions equivalent to the axiom of choice:

Hausdorff’s Maximal Principle: Every chain in a partially ordered set M is contained in a maximal chain in M.

Zorn’s lemma:  If every chain in a partially ordered set M has an upper bound, then M contains a maximal element.

For the proof of the equivalence of the axiom of choice, the well-ordering theorem, Hausdorff’s maximal principle and Zorn’s lemma, we refer the reader elsewhere. Of these various equivalent assertions, Zorn’s lemma is perhaps the most useful.

Section 3.8 Transfinite Induction:

Mathematical propositions are very often proved by using the following familiar:

THEOREM 4: MATHEMATICAL INDUCTION:

Given a proposition $P(n)$ formulated for every positive integer n, suppose that :

i) P(1) is true.

ii) The validity of P(k) for all $k implies the validity of $P(n+1)$. Then, P(n) is true for all $n=1,2,\ldots$.

PROOF 4:

Suppose P(n) fails to be true for all $n=1,2,\ldots$ and let n, be the smallest integer for which $P(n)$ is false (the existence of such $n_{1}$ follows from the well-ordering of the positive integers). Clearly, $n_{1}>1$, so that $n_{1}-1$ is a positive integer. Therefore, $P(n)$ is valid for all $k \leq n_{1}-1$ but not for $n_{1}$. Contradiction!!

QED.

Replacing the set of all positive integers by an arbitrary well-ordered set, we get

THEOREM 4 (Transfinite induction):

Given a well-ordered set A, let $P(a)$ be a proposition formulated for every element $a \in A$. Suppose that

i) $P(a)$ is true for the smallest element of A

ii) The validity of $P(a)$ for all $a < a^{*}$ implies the validity of $P(a^{*})$. Then, $P(a)$ is true for all $a \in A$.

PROOF 4:

Suppose $P(a)$ fails to be true for all $a \in A$. Then, $P(a)$ is false for all a in some non empty subset $A^{*} \subset A$. By the well-ordering, $A^{*}$ has a smallest element $a^{*}$. Therefore, $P(a)$ is valid for all $a< a^{*}$ but not for $a^{*}$. Contradiction !!

QED.

Remark:

Since any set can be well-ordered, by the well-ordering theorem, transfinite induction can in principle be applied to any set M whatsoever. In practice, however, Zorn’s lemma is a more useful tool, requiring only that M be partially ordered.

Section 3.9: Historical Remarks:

Set theory as a branch of mathematics in its own right stems from the pioneer work of Georg Cantor (1845-1918). Originally met with disbelief, Cantor’s ideas subsequently became widespread. By now, the set theoretic point of view has become standard in the most diverse fields of mathematics. Basic concepts, like groups, rings, fields, linear spaces etc are habitually defined as sets of elements of an arbitrary kind obeying appropriate axioms.

Further development of set theory led to a number of logical difficulties, which naturally gave rise to attempts to replace “naive” set theory by a more rigorous axiomatic set theory. It turns out that certain set theoretic questions, which would at first seem to have “yes” or “no” answers, are in fact of a different kind. Thus, it was shown by Godel in 1940 that a negative answer to the question :”Is there an uncountable set of power less than that of the continuum” is consistent with set theory (axiomatized in a way we will not discuss here), but it was recently shown by Stephen Cohen that an affirmative answer to the question is also consistent in the same sense !!

We will continue to exercises based on last two blogs now,

Regards,

Nalin Pithwa.

# 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, 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 , or $b. 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 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} for arbitrary $a_{1},a_{2}$

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

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  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 ) 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, 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), 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}, and hence, $f(b_{0}), since f is an isomorphism. But, then $a_{0}$ is not the smallest element such that $f(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). 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

# Second Problem Set from Kolmogorov and Fomin: Introductory Real Analysis

$bf{Problem 1}$.

Prove that a set with an uncountable subset is itself uncountable.

$\bf{Problem 2}$.

Let M be any infinite set and let set A be any countable set. Prove that $M \sim M\bigcup A$.

$\bf{Problem 3}$.

Prove that each of the following sets is countable:

(a) The set of all numbers with two distinct decimal representations (like 0.50000…and 0.49999…).

(b) The set of all rational points in the plane (that is, points with rational coordinates)

(c) The set of all rational intervals (That is, intervals with rational end points)

(d) The set of all polynomials with rational coefficients.

$\bf{Problem 4}$.

A number $\alpha$ is called algebraic if it is a root of a polynomial equation with rational coefficients. Prove that the set of all algebraic numbers is countable.

$\bf{Problem 5}$

Prove the existence of uncountably many transcendental numbers, that is, numbers which are not algebraic. Hint: Use Theorems 2 and 5 of previous blog(s).

$\bf{Problem 6}$

Prove that the set of all real functions (more generally, functions taking values in a set containing at least two elements) defined on a set M is of power greater than the power of M. In particular, prove that the power of the set of all real functions (continuous and discontinuous) defined in the interval $[0,1]$ is greater than c. Hint: Use the fact that the set of all characteristic functions (that is, functions taking values 0 and 1) on M is equivalent to the set of all subsets of M.

$\bf{Problem7}$

Give an indirect proof of the equivalence of the closed interval $[a,b]$, the open interval $(a,b)$ and the half-open interval $[a,b)$ or $(a,b)$. Hint: Use theorem 7 (the Cantor-Bernstein theorem).

$\bf{Problem8}$

Prove that the union of a finite set of a finite or countable number of sets each of power c is itself of power c.

$\bf{Problem9}$

Prove that the each of the following sets has the power of the continuum:

(a) The set of all infinite sequences of positive integers.

(b) The set of all ordered n-tuples of real numbers.

(c) The set of all infinite sequences of real numbers.

$\bf{Problem10}$

Develop a contradiction inherent in the notion of the “set of all sets which are not members of themselves”. Hint: Is this set a member of itself? Comment: Thus, we will be careful to sets which are “too big,” like the “set of all sets”.

We will go through the solutions of the above soon,

Cheers,

Nalin Pithwa

# Uncountability of the real numbers: Kolmogorov and Fomin

Reference: Introductory Real Analysis by Kolmogorov and Fomin.

Several examples of countable sets were given earlier, and many more examples of such sets could be given. In fact, according to Theorem 2(refer previous blog(s)), the union of a finite or countable number of countable sets is itself countable. It is now natural to ask whether there exist sets which are uncountable. The existence of such sets is shown by:

$\bf{Theorem5}$

$\bf{The \hspace{0.1in}set \hspace{0.1in}of \hspace{0.1in}real \hspace{0.1in}numbers \hspace{0.1in}in \hspace{0.1in}the \hspace{0.1in}closed \hspace{0.1in}unit \hspace{0.1in}interval \hspace{0.1in}[0,1] \hspace{0.1in}is \hspace{0.1in}uncountable.}$

$\bf{Proof}$

Suppose we have managed to count some or all of the real numbers in $[0,1]$, arranging them in a list:

$\alpha_{1}=0.a_{11}a_{12}a_{13}\ldots a_{1n}\ldots \ldots$

$\alpha_{2}=0.a_{21}a_{22}a_{23}\ldots a_{2n}\ldots \ldots$

$\alpha_{3}=0.a_{31}a_{32}a_{33}\ldots a_{3n}\ldots \ldots$

$\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots$

$\alpha_{n}=0.a_{n1}a_{n2}a_{n3}\ldots a_{nn} \ldots \ldots$

$\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots$

where $a_{ik}$ is the $k^{th}$ digit in the decimal expansion of the number $\alpha_{i}$. Consider the decimal $\beta=0.b_{1}b_{2}b_{3}\ldots b_{n}\ldots\ldots$ constructed as follows: For $b_{1}$ choose any digit (from 0 to 9) different from $a_{11}$, for $b_{2}$ any digit different from $a_{22}$, and so on, and in general, for $b_{n}$ any digit different from $a_{nn}$. Then, the decimal $\beta$ cannot coincide with any decimal in the first list. In fact, $\beta$ differs from $\alpha_{1}$ in at least the first digit, from $\alpha_{2}$ in at least the second digit, and so on, since in general $b_{n} \neq a_{nn}$ for all n. Thus, no list of real numbers in the interval $[0,1]$ can include all the real numbers in $[0,1]$.

The above argument must be refined slightly since certain numbers, namely those of the form $\frac{p}{10^{q}}$, can be written as decimals in two ways, either with an infinite run of zeros or an infinite run of nines. For example, $\frac{1}{2}=\frac{5}{10}=0.500000\ldots=0.499999\ldots$, so that the fact that two decimals are distinct does not necessarily mean that they represent real numbers. However, this difficulty disappears if in constructing $\beta$, we require that $\beta$ contain neither zeros nor nines, for example, by setting $b_{n}=2$ if $a_{nn}=1$ and $b_{n}=1$ if $a_{nn}=1$.

Thus, the set $[0,1]$ is uncountable. Other examples of uncountable sets equivalent to $[0,1]$ are:

(i) The set of points in any closed interval $[a,b]$.

(ii) The set of points on the real line.

(iii) The set of points in any open interval $(0,1)$.

(iv) The set of points in the plane or in space.

(v) The set of all points on a sphere or inside a sphere.

(vi) The set of all lines in the plane

(vii) The set of all continuous real functions of one or several variables.

The fact that the sets (i) and (ii) are equivalent to $[0,1]$ is proved as in examples 1 and 3 (previous blog) while the fact that the sets (iii) to (vii) are equivalent to $[0,1]$ is best proved $\it{indirectly}$ (problems 7 and 9 in the following exercise).

$\bf{The \hspace{0.1in}power \hspace{0.1in}of \hspace{0.1in}a \hspace{0.1in}set}$

Given any two sets M and N, suppose M and N are equivalent. Then, M and N are said to have the same $\it{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 $\mathscr{Z^{+}}$ of all positive integers, and hence, the power of any countable set, is denoted by the symbol $\aleph_{0}$, read as “aleph null.” A set equivalent to the set of real numbers in the interval $[0,1]$ and hence, to the set of all real numbers, is said to have the power of the $\it{continuum}$, denoted by $c$, or often by $\aleph$.

For the powers of finite sets, that is, for the positive integers, we have the notions of “greater than” and “less than,” as well as the notions of equality. We now show how these concepts are extended to the case of of infinite sets.

Let A and B be any two sets, with powers $m(A)$ and $m(B)$, respectively. If A is equivalent to B, then $m(A)=m(B)$ by definition. If A is equivalent to a subset of B and if no subset of A is equivalent to B, then, by analogy with the finite case, it is natural to regard $m(A)$ is less than $m(B)$ or $m(B)$ as greater than $m(A)$. Logically, however, there are two further possibilities:

i) B has a subset equivalent to A, and A has a subset equivalent to B;

ii) A and B are not equivalent, and neither has a subset equivalent to the other.

In case (i), A and B are equivalent and hence, have the same power, as shown soon by the Cantor-Bernstein theorem (Theorem 7 below). Case (ii) would obviously show the existence of powers that cannot be compared, but it follows from the well-ordering theorem that this case is actually impossible. Therefore, taking both of these theorems on faith, we see that any two sets A and B either have the same power or else satisfy one of the relations $m(A) or $m(A)>m(B)$. For example, it is clear that $\aleph_{0}. ($\bf{Quiz \hspace{0.1in} why}$).

$\bf{\it{Remark}}$. The very deep problem of the existence of powers between $\aleph_{0}$ and c is touched upon later (in this text or blog series). As a rule, however, the infinite sets encountered in analysis are either countable or else have the power of the continuum.

We have already noted that countable sets are the “smallest” infinite sets. It has also been shown that there are infinite sets of power greater than that of a countable set, namely, sets with the power of the continuum. It is natural to ask whether there are infinite sets of power greater than that of the continuum or, more generally, whether there is a “largest” power. These questions are answered by :

$\bf{Theorem6}$

Given any set M, let $\mathscr{M}$ be the set whose elements are all possible subsets of M. Then, the power of $\mathscr{M}$ is greater than the power of the original set M.

$\bf{Proof}$.

Clearly, the power of p of the set $\mathscr{M}$ cannot be less than the power $\mu$ of the original set M, since the “single-element subsets” (or “singletons”) of $M$ form a subset of $\mathscr{M}$ equivalent to M. Thus, we need only show that m and $\mu$ do not coincide. Suppose a one-to-one correspondence

$a\leftrightarrow A$, $b \leftrightarrow B$, $\ldots$

has been establshed between the elements a, b $\ldots$ of M and certain elements A, B, $\ldots$ of $\mathscr{M}$ (that is, certain subsets of M). Then, A, B $\ldots$ do not exhaust all the elements of $latex\mathscr{M}$, that is, all subsets of M. To see this, let $X$ be the set of elements of M which do not belong to their “associated subsets.” More exactly, if $a \leftrightarrow A$ we assign a to X if $a \notin A$, but not if $a \in A$. Clearly, X is a subset of M and hence, an element of $\mathscr{M}$. Suppose there is an element $x \in M$ such that $x \leftrightarrow X$, and consider whether or not x belongs to X. Suppose $x \notin X$. Then, $x \in X$, since, by definition, X contains $\it{every}$ element not contained in its associated subset. On the other hand, suppose $x \notin X$. Then, $x \in X$, since X consists precisely of those elements which do not belong to their associated subsets. In any event, the element x corresponding to the subset X must simultaneously belong to X and not belong to X. But, this is impossible!! It follows that there is no such element x. Therefore, no one-to-one correspondence can be established between the sets $M, \mathscr{M}$, that is, $m \neq \mu$. $\bf{QED}$.

Thus, given any set M, there is a set $\mathscr{M}$ of larger power, a $\mathscr{M^{*}}$ of still larger power, and so on, indefinitely. in particular, there is no set of”largest” power.

$\bf{Section6}$

$\bf{The \hspace{0.1in} Cantor \hspace{0.1in} Bernstein \hspace{0.1in} Theorem}$.

Now, we prove an important theorem already used in the preceding section:

$\bf{Theorem7}$, $\bf{Cantor\hspace{0.1in}-Berstein}$.

Given any two sets A and B, suppose A contains a subset $A_{1}$ equivalent to B, while B contains a subset B, equivalent to A. Then, A and B are equivalent.

$\bf{Proof}$.

By hypothesis, there is a one-to-one function f mapping A into $B_{1}$, and a one-to-one function g mapping B into $A_{1}$:

$f(A)=B_{1}\subset B$, and $g(B)=A_{1} \subset A$. therefore $A_{2}=gf(A)=g(f(A))=g(B_{1}) \subset g(B) = A_{1}\subset A$, that is, $g(B_{1})$ is a subset of A_{1} equivalent to all of A.

Similarly, $B_{1}=fg(B)=f(g(B))=f(A_{1})$ is a subset of $B_{1}$ equivalent to B. Let $A_{3}$ be the subset of A into which the mapping gf carries the set $A_{1}$, and let $A_{4}$ be the subset of A into which gf carries $A_{2}$. More generally, let $A_{k+2}$ be the set into which $A_{k}, k=1,2,\ldots$ is carried by gf.

Then, clearly

$A \supset A_{1} \supset A_{2} \supset \ldots \supset A_{k}\supset A_{k+1}\supset \ldots$

Setting $D = \bigcap_{k=1}^{\infty}A_{k}$, we can represent A as the union of pairwise disjoint sets:

$A=(A-A_{1})\bigcup (A_{1}-A_{2})\bigcup (A_{2}-A_{3}) \bigcup \ldots \bigcup (A_{k}-A_{k+1})\bigcup \ldots \bigcup D$.

From the above, we can conclude that $A=D \bigcup M \bigcup N$, and $A_{1}=D \bigcup M \bigcup N_{1}$,

where $M = (A_{1}-A_{2}) \bigcup (A_{3}-A_{4}) \bigcup \ldots$

where $N=(A-A_{1})\bigcup (A_{2}-A_{3}) \bigcup \ldots$

where $N_{1}= (A_{2}-A_{3}) \bigcup (A_{4}-A_{3}) \bigcup \ldots$

But $A-A_{1}$ is equivalent to $A_{2}-A_{3}$ (the former is carried into the latter by the one-to-one function gf), $A_{2}-A_{3}$ is equivalent to $A_{4}-A_{3}$ and so on. Therefore, N is equivalent to $N_{1}$. It follows from the representations above that a one-to-one correspondence can be set up between the sets A and $A_{1}$. But, $A_{1}$ is equivalent to B, by hypothesis. Therefore, A is equivalent to B. $\bf{QED}$.

$\bf{Remark}$.

Here, we can even ‘afford the unnecessary luxury” of explicitly writing down a one-to-one function carrying A into B, that is, $\phi(a)=g^{-1}(a)$, if $a \in D \bigcup M$ and $\phi(a)=f(a)$, if $a \in D \bigcup N$.

$\bf{Note}$

The above proof is also as beautifully explained in General Topology, Schaum Series.

We will continue with exercises and their solutions soon,

Nalin Pithwa

# Set Theory, Relations, Functions: Kolmogorov and Fomin

Set Theory, Relations, Functions: Preliminaries: Part VIII

Set Theory, Relations, Functions: Preliminaries: part VIIIA

Set Theory, Relations, Functions: Preliminaries: Part IX: (tutorial problems)

Set Theory, Relations, Functions: preliminaries: part 10: more tutorial problems for practice

Towards Baby Analysis: Part I: INMO, IMO and CMI Entrance

# Dihedral groups explained by I N Herstein

Reference: Abstract Algebra, Third Edition, I N Herstein

First consider the following: Let S be the plane, that is, $S= \{ (x,y): x, y \in R\}$ and consider $f, g \in A(S)$ defined by $f(x,y)=(-x,y)$ and $g(x,y)=(-y,x)$; f is the reflection about the y-axis and g is the rotation through 90 degrees in a counterclockwise direction about the origin. We then define $G = \{ f^{i}g^{j}: i=0,1; j=0,1,2,3\}$, and let * in G be the product of elements in A(S). Clearly, $f^{2}=g^{4}=$ identity mapping;

$(f*g)(x,y)=(fg)(x,y)=f(g(x,y))=f(-y,x)=(y,x)$ and $(g*f)(x,y)=g(f(x,y))=g(-x,y)=(-y,-x)$

So $g*f=f*g$.

It is a good exercise to verify that $g*f=f*g^{-1}$ and G is a non-abelian group of order 8. This group is called the dihedral group of order 8. [Try to find a formula for $(f^{i}g^{j})*(f^{s}g^{t})=f^{a}g^{b}$ that expresses a, b in terms of i, j, s and t.

II) Let S be as in above example and f the mapping in above example. Let $n>2$ and let h be the rotation of the plane about the origin through an angle of $2\pi/n$ in the counterclockwise direction. We then define $G=\{ f^{k}h^{j}: k=0,1 ; j=0,1,2, \ldots, n-1\}$ and define the product * in G via the usual product of mappings. One can verify that $f^{2}=h^{n}=$ identity mapping and $fh=h^{-1}f$. These relations allow us to show that (with some effort) G is a non-abelian group of order 2n. G is called the dihedral group of order 2n.

More later,

Nalin Pithwa