# 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.