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<n$ 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.

MScMathematics

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

Leave a Reply Cancel reply

Mathematics Hothouse shares:

Like this:

Related

Leave a Reply Cancel reply