Problem Set based on VII. Complete Metric Spaces

Posted on May 31, 2020May 31, 2020 by Nalin Pithwa

Problem 1.

Prove that the limit $f(t)$ of a uniformly convergent sequence of functions $\{ f_{n}(t)\}$ continuous on $[a,b]$ is itself a function continuous on $[a,b]$ .

Hint: Clearly,

$|f(t)-f(t_{0})| \leq |f(t) - f_{n}(t)|+|f_{n}(t) - f_{n}(t_{0})|+|f_{n}(t_{0}) - f(t_{0})|$ where $t, t_{0} \in [a,b]$ .

Use the uniform convergence to make the sum of the first and third terms on the right small for sufficiently large n. Then, use the continuity of $f_{n}(t)$ to make the second term small for t sufficiently close to $t_{0}$ .

Problem 2.

Prove that if R is complete, then the intersection $\bigcap_{n=1}^{\infty}S_{n}$ figuring in the theorem 2 consists of a single point. Theorem 2 is recalled here: Nested sphere theorem: A metric space R is complete if and only if nested sequence $S_{n} = \{ S[x_{n}, r_{n}]\}$ of closed spheres in R such that $t_{n} \rightarrow 0$ as $n \rightarrow \infty$ has a non empty intersection $\bigcap_{n=1}^{\infty}S_{n}$ .

Problem 3.

Prove that the space m is complete. Recall: Consider the set of all bounded infinite sequences of real numbers $x = (x_{1}, x_{2}, \ldots, x_{k}, \ldots)$ and let $\rho(x,y) = \sup_{k}|x_{k}-y_{k}|$ . This is a metric space which we denote by m.

Problem 4:

By the diameter of a subset A of a metric space R is meant the number $d(A) = \sup_{x, y \in A} \rho(x,y)$

Suppose R is complete and let $\{ A_{n}\}$ be a sequence of closed sets of R nested in the sense that

$A_{1} \supset A_{2} \supset \ldots \supset A_{n} \supset \ldots$

Suppose further that

$\lim_{n \rightarrow \infty} d(A_{n})=0$ .

Prove that the intersection $\bigcap_{n=1}^{\infty}A_{n}$ is non empty.

Problem 5.

A subset A of a metric space R is said to be bounded if its diameter $d(A)$ is finite. Prove that the union of a finite number of bounded sets is bounded.

Problem 6.

Give an example of a complete metric space R and a nested sequence $\{ A_{n}\}$ of closed subsets of R such that

$\bigcap_{n=1}^{\infty}A_{n} = \phi$ .

Reconcile this example with Problem 4 here.

Problem 7.

Prove that a subspace of a complete metric space R is complete if and only if it is closed.

Problem 8.

Prove that the real line equipped with the distance metric function

$\rho(x,y) = |\arctan{x} - \arctan{y}|$ is an incomplete metric space.

Problem 9.

Give an example of a complete metric space homeomorphic to an incomplete metric space.

Hint: Consider the following example we encountered earlier: The function $y = f(x) = \frac{2}{\pi}\arctan{x}$ establishes a homeomorphism between the whole real line $(-\infty, \infty)$ and the open interval $(-1,1)$ .

Comment: Thus, homeomorphic metric spaces can have different metric properties.

Problem 10:

Carry out the program discussed in the last sentence of the following example:

Ir R is the space of all rational numbers, then $R^{*}$ is the space of all real numbers, both equipped with the distance $\rho(x,y) = |x-y|$ . In this way, we can “construct the real number system.” However, there still remains the problem of suitably defining sums and products of real numbers and verifying that the usual axioms of arithmetic are satisfied.

Hint: If $\{ x_{n}\}$ and $\{ y_{n}\}$ are Cauchy sequences of rational numbers serving as “representatives” of real numbers $x^{*}$ and $y^{*}$ respectively, define $x^{*} = y^{*}$ as the real number with representative $\{ x_{n} + y_{n}\}$ .

I will post the solutions in about a week’s time.

Regards,

Nalin Pithwa.

mathhothouse01@gmail.com

+91 9742600025

Purva building, 5A

Flat 06

Thakur Complex, Near Dimple Arcade

Mumbai, Maharastra 400101

India

Problem Set based on VI. Convergence, open and closed sets.

Posted on April 5, 2020April 13, 2020 by Nalin Pithwa

Problem 1.

Give an example of a metric space R and two open spheres $S(x,r_{1})$ , $S(y, r_{2})$ in R such that $S(x, r_{1}) \subset S(y,r_{2})$ although $r_{1}> r_{2}$ .

Problem 2:

Prove that every contact point of a set M is either a limit point of M or is an isolated point of M.

Comment. In particular, $[M]$ can only contain points of the following three types:

a) Limit points of M belonging to M.

b) Limit points of M which do not belong to M.

c) Isolated points of M.

Thus, $[M]$ is the union of M and the set of all its limit points.

Problem 3:

Prove that if $x_{n}\rightarrow x$ and $y_{n} \rightarrow y$ as $n \rightarrow \infty$ then $\rho(x_{n},y_{n}) \rightarrow \rho(x,y)$ .

Hint : use the following problem: Given a metric space $(X,\rho)$ prove that $|\rho(x,z)-\rho(y,u)| \leq |\rho(x,y)|+|\rho(z,u)|$

Problem 4:

Let f be a mapping of one metric space X into another metric space Y. Prove that f is continuous at a point $x_{0}$ if and only if the sequence $\{ y_{n}\} = \{ f(x_{n})\}$ converges to $y=f(x_{0})$ whenever the sequence $x_{n}$ converges to $x_{0}$ .

Problem 5:

Prove that :

(a) the closure of any set M is a closed set.

(b) $[M]$ is the smallest closed set containing M.

Problem 6:

Is the union of infinitely many closed sets necessarily closed? How about the intersection of infinitely many open sets? Give examples.

Problem 7:

Prove directly that the point $\frac{1}{4}$ belongs to the Cantor set F, although it is not the end point of any of the open interval deleted in constructing F. Hint: The point $\frac{1}{4}$ divides the interval $[0,1]$ in the ratio $1:3$ and so on.

Problem 8:

Let F be the Cantor set. Prove that

(a) the points of the first kind form an everywhere dense subset of F.

(b) the numbers of the form $t_{1}+t_{2}$ where $t_{1}, t_{2} \in F$ fill the whole interval $[0,2]$ .

Problem 9:

Given a metric space R, let A be a subset of R, and $x \in R$ . Then, the number $\rho(A,x) = \inf_{a \in A}\rho(a,x)$ is called the distance between A and x. Prove that

(a) $x \in A$ implies $\rho(A,x)=0$ but not conversely

(b) $\rho(A,x)$ is a continuous function of x (for fixed A).

(d) $[A]=A \bigcup M$ , where M is the set of all points x such that $\rho(A,x)=0$ .

Problem 10:

Let A and B be two subsets of a metric space R. Then, the number $\rho(A,B)= \inf_{a \in A, b \in B}\rho(a,b)$ is called the distance between A and B. Show that $\rho(A,B)=0$ if $A \bigcap B \neq \phi$ , but not conversely.

Problem 11:

Let $M_{K}$ be the set of all functions f in $C_{[a,b]}$ satisfying a Lipschitz condition, that is, the set of all f such that $|f(t_{1}-f(t_{2})| \leq K|t_{1}-t_{2}|$ for all $t_{1}, t_{2} \in [a,b]$ , where K is a fixed positive number. Prove that:

a) $M_{K}$ is closed and in fact is the closure of the set of all differentiable functions on $[a,b]$ such that $|f^{'}(t)| \leq K$

(b) the set $M = \bigcup_{K}M_{K}$ of all functions satisfying a Lipschitz condition for some K is not closed;

Problem 12:

An open set G in n-dimensional Euclidean space $R^{n}$ is said to be connected if any points $x,y \in G$ can be joined by a polygonal line(by a polygonal line we mean a curve obtained by joining a finite number of straight line segments end to end.) lying entirely in G. For example, the open disk $x^{2}+y^{2}<1$ is connected, but not the union of the two disks $x^{2}+y^{2}<1$ , $(x-2)^{2}+y^{2}<1$ (even though they share a contact point). An open subset of an open set G is called a component of G if it is connected and is not contained in a larger connected subset of G. Use Zorn’s lemma to prove that every open set G in $R^{n}$ is the union of no more than countably many pairwise disjoint components.

Comment: In the case $n=1$ , that is, the case on the real line, every connected open set is an open interval, possibility one of the infinite intervals $(-\infty, \infty)$ , $(a, \infty)$ or $(-\infty, b)$ . Thus, theorem 6 (namely: Every open set G on the real line is the union of a finite or countable system of pairwise disjoint open intervals) on the structures of open sets on the line is tantamount to two assertions:

(i) Every open set on the line is the union of a finite or countable number of components.

(ii) Every open connected set on the line is an open interval.

The first assertion holds for open sets in $R^{n}$ (and, in fact, is susceptible to further generalizations), while the second assertion pertains specifically to the real line.

Cheers,

Happy analysis !!

Nalin Pithwa

Introductory Real Analysis: Exercise 3 solutions: related to set theory

Posted on January 15, 2020January 15, 2020 by Nalin Pithwa

Problem 1:

Exhibit both a partial ordering and a simple ordering on the set of complex numbers.

Solution I:

Recall the definition of a partial ordering: A binary relation R on a set M is said to be a partial ordering (and the set M itself 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) aRb and bRa together imply $a=b$ (anti symmetric).

Recall the definition of a simple ordering or totally ordered or (just) ordered set: a set M is said to be ordered if it is a partially ordered set and if, given any two distinct elements $a, b \in M$ , either $a < b$ or $b < a$ .

Let us consider the following relation R on the set of complex numbers, C:

consider any two elements $z_{1}, z_{2} \in C$ such that $z_{1}=x_{1}+i y_{1}$ and $z_{2} = x_{2}=iy_{2}$ . We define a relation $z_{1}Rz_{2}$ if and only if $x_{1} \leq x_{2}$ and $y_{1} \leq y_{2}$ . Clearly, this is both a partial ordering on C as well as total ordering on C.

Now consider the following relation K on the set of complex numbers:

We define the relation K as: $z_{1}Kz_{2}$ if and only if $\frac{x_{1}}{y_{1}} = \frac{x_{2}}{y_{2}}$ where $x_{1}, y_{1}, x_{2}, y_{2} \in \Re$ . Clearly, if any one of $y_{1}$ or $y_{2}$ is zero, then the complex numbers $z_{1}$ and $z_{2}$ are non-comparable. So this could be a partial ordering but not a total ordering on the set of 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?

Solution 2:

Recall the definition: An element “a” of a partially ordered set is said to be maximal if $aRb$ implies $b=a$ and minimal if $bRa$ implies b=a.

Note that in the above definition, element “a” is our given/chosen element to be compared with other elements of the set. So, clearly, if the partial ordering is set inclusion, the minimal element is the null set $\phi$ and the maximal element is the given set X itself.

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 \leq c$ and $b \leq c$ . Are the following partially ordered sets directed sets also ?

PS: in the above we use the notation $aRb$ or equivalently, $a \leq b$ to mean one and the same thing.

Question 3a: Any set M can be trivially partially ordered by setting $a \leq b$ if and only if $a=b$ .

Answer 3a: Clearly, this is a trivial directed set.

Question 3b: 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$ if and only if $f(t) \leq g(t)$ for every $t \in [\alpha, \beta]$ . Is this also a directed set ?

Answer 3b: We need to choose two arbitrary elements say $f_{1}$ and $f_{2}$ of the given set of continuous functions on $[\alpha, \beta]$ . Our desired “element” could be $f_{3}= |f_{1}(t)|+|f_{2}(t)|$ again defined on $[\alpha, \beta]$ . Then, the given set becomes a directed set.

Note that the function $y=f(x) = |x|$ is continuous at zero also (but not differentiable at zero).

Question 3c:

Set inclusion.

Answer 3: Clearly, given any two arbitrary subsets, both are contained always in the given big set M or X. So, this is again a directed set.

Question 3d: The set of all integers greater than 1 is partially ordered if $a \leq b$ means that “b is divisble by a.”

Answer 3: So let us consider two arbitrary positive integers, both greater than 1, call them a and b. We want to know if there exist a positive integer, also greater than 1, call it c such that $a \leq c$ and $b \leq c$ ? That is, “c is divisible by a” and “c is divisible by b”. Clearly, c can be least common multiple of a and b. So, yes, this is also a directed set.

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$ and $c \leq b$ and there is no element $d \in M$ such that $c < 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 < c$ and $b \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 M, 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 ?

Solution 4:

It can be easily checked that the null set is the greatest lower bound and the set M itself if the least upper bound. (PS: these are the minimal and maximal elements of this set M respectively.)

Problem 5:

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

Solution 5:

By definition.

Problem 6:

Prove that ordered sums and products of ordered sets are associative, that is, prove that if $M_{1}, M_{2}$ and $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})$

PS: comment: this allows us to drop the parentheses in writing ordered sums and products.

where the operations are as defined below:

Let $M_{1}$ and $M_{2}$ be two ordered sets of type $\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 orderiing as in $M_{2}$ if $a, b \in M_{2}$ (iii) $a \leq b$ if $a \in M_{1}$ and $b \in M_{2}$ .

In this case/example, the ordered sum or union of three ordered sets $M_{1}, M_{2}, M_{3}$ would mean that any two elements a, b would have the same ordering if $a, b \in M_{1}$ , or $a, b \in M_{2}$ or $a,b \in M_{3}$ . Also, comparing with ordered sum of two ordered sets, we can say that $a \leq b$ if and only if $a \in M_{1}, b \in M_{2}$ or $a \in M_{1}, b \in M_{3}$ , or $a \in M_{2}, b \in M_{3}$ . In such a case, the ordered sum is also associative.

The operation of ordered product of two ordered sets is defined as follows: $M_{1}. M_{2}$ is the set of all pairs $(a,b)$ where $a \in M_{1}$ and $b \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}$ , and (ii) $(a_{1},b) < (a_{2}, b)$ if $a_{1} < a_{2}$ .

So, if we have three ordered sets $M_{1}, M_{2}, M_{3}$ , we can define their ordered product $M_{1}.M_{2}.M_{3}$ as consisting of all ordered triples such that (i) $(a_{1}, b_{1}, c_{1}) < (a_{2}, b_{2}, c_{2}) < (a_{3}, b_{3}, c_{3})$ if and only if $b_{1}<b_{2}<b_{3}$ and $c_{1} < c_{2} < c_{3}$ for arbitrary $a_{1}, a_{2}, a_{3}$ , and (ii) $(a_{1}, b, c) < (a_{2}, b, c) < (a_{3}, b, c)$ if $a_{1}<a_{2}<a_{3}$ ; $(a, b_{1}, c) < (a, b_{2}, c) < (a, b_{3}, c)$ if $b_{1}<b_{2}<b_{3}$ ; $(a,b, c_{1})< (a,b,c_{2}) < (a,b, c_{3})$ of $c_{1} < c_{2} < c_{3}$ . In such a case, the product is well-defined and is also associative. (any comments ??)

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.

Solution 7:

$\omega + n$ : $\{ 1,2,3,\ldots, a_{1}, a_{2}, \ldots, a_{n}\}$ . This is countable because there can be bijection from the set $Z^{+}$ to the given set: $1 \rightarrow a_{1}$ , $2 \rightarrow a_{2}$ , $\ldots$ , $n \rightarrow a_{n}$ , $n+1 \rightarrow 1$ , $n+2 \rightarrow 2$ , $\ldots$

$\omega + \omega$ : $\{1,2,3, \ldots, 1,2,3, \ldots \}$ , this is also countable as it can be put in one-to-one correspondence with $Z^{+}$ .

$\omega + \omega + n$ ; $\{ 1,2, 3, \ldots, 1, 2, 3, \ldots, a_{1}, a_{2}, a_{3}, \ldots, a_{n}\}$ . This is also countable in the same manner as the first example.

$\omega + \omega + \omega$ : $\{ 1,2, 3, \ldots, 1,2, 3, \ldots, 1,2,3, \ldots\}$ : this can be put in one-to-one correspondence with $Z^{+}$

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.

Solution 8:

First let us recall the definition: 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$ .

Ans 1: $\omega.n$ is set : $M= \{(1,a_{1}), (2,a_{2}), (3, a_{3}), \ldots, (n, a_{n}), (n+1, a_{1}), (n+2, a_{2}), \ldots \}$ . This set is ordered clearly by the definition of ordered product of two ordered sets; and this is well-ordered if we define the first element to be $(1, a_{1})$ .

Ans 2: $\omega^{2} = \omega. \omega$ : this set can be constructed as $M= \{ (1,1), (1,2),(1,3), \ldots, (2,1), (2,2), (2,3), \ldots, \}$ and we can define the first element as $(1,1)$ so that it becomes well-ordered under the usual definition of product of two ordered sets.

Ans 3: $\omega^{2}.n = \omega. \omega. n$ : this set can be constructed as follows as an ordered product of three ordered sets: $M = \{ (1,1,a_{1}), (1,1,a_{2}), (1,1,a_{3}), \ldots, (1,1,a_{n}), (1,2,a_{1}), (1,2,a_{2}), (1,2,a_{3}), \ldots, (1, 2, a_{n}), \ldots\}$ . We see that this is also well-ordered if we define the first element to be $(1,1,a_{1})$ and “order or list or count” them as shown. (any comments ? )

Ans 4: $\omega^{3}= \omega.\omega.\omega$ : this can be well-ordered as above with clearly the first element to be $(1,1,1)$ . (any comments?)

PS: the explicit listing shows that all the above sets are clearly countable.

More later,

Cheers,

Nalin Pithwa

Introductory real analysis: exercise 3:

Posted on November 28, 2019November 29, 2019 by Nalin Pithwa

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<c$ . 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 <c, b \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} <m< \aleph_{1}$ .

More later,

Nalin Pithwa.

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

Posted on November 24, 2019November 28, 2019 by Nalin Pithwa

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.

Solutions to Kolmogorov and Fomin: Second problem set (previous blog)

Posted on November 1, 2019January 14, 2020 by Nalin Pithwa

Problem 1:

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

Proof 1:

That is, to prove that: if a set X has an uncountable subset Y, then set X itself is uncountable.

That is, to prove that (contra-positive): If a set X is NOT uncountable, then the set X does NOT contain an uncountable subset.

That is, to prove that: if a set X is countable, then the set X contains a countable subset, which is quite true.

Problem 2:

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

Proof 2:

We know that an infinite subset is equivalent to a proper subset of itself. And, that every infinite set contains a countable subset. So, here, set M is equivalent to a proper countable subset, say B of it. Hence, $M \sim B$ . Also, any two countable sets are equivalent, by definition. So, $M \sim B \sim A \sim M \bigcup A$ . QED.

Problem 3:

Prove that each of the following sets is countable:

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

(b) The set of all rational points in the plane (that is, points with rational co-ordinates).

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

Proof 3a:

Such numbers are of the form $\frac{p}{10^{q}}=\alpha$ , say. Let us say, that the “height” of $\alpha$ is given by $|p|+q$ . For example, $\frac{1}{10^{1}}=0.1000\ldots=0.09999\ldots$ has “height” 2; and $\frac{2}{10^{1}}$ has “height” 3 etc. Clearly, all such numbers can be arranged in one-one correspondence with the set of positive integers, and it is therefore countable. (For details, refer text section or a previous blog detailing why rational numbers are countable.) QED.

Proof 3b:

Because $|Q \times Q| = |N \times N|=|N|=\aleph_{0}$ . QED.

Proof 3c:

This is a subset of the set in 3b. And, we know that every subset of a countable set is countable. QED.

Proof 3d:

this deals with a cardinality of cross product of two sets, and more than two sets.

Just as $|Q \times Q|=|N \times N|=|N|=\aleph_{0}$ , so also

$|Q^{n}|=|N|=\aleph_{0}$ . QED.

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.

Instead, we prove the following:

(PS: the proof of the above is almost same as 3d.)

A real number r is called an algebraic number if r is a solution to a polynomial equation:

$p(x) = a_{0}+a_{1}x+a_{2}x^{2}+\ldots+a_{m}x^{m}=0$ with integral coefficients. Prove that the set A of algebraic numbers is countable.

Proof:

Once again, we need to prove the following first: The set $\mathscr{P}$ of all polynomials $p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots + a_{m}x^{m}$ with integral coefficients is countable:

It is as follows: For each pair of non-negative integers $(n,m)$ , let $P(n,m)$ be the set of all polynomials of degree m. in which $|a_{1}|+|a_{2}|+\ldots+|a_{m}|=n$ . Note that $P(n,m)$ is finite. Hence, $\mathscr{P}=\bigcup (P(n,m) : \hspace{0.1in} (n,m) \in N \times N)$ is countable since it is a countable family of countable sets. But $\mathscr{P}$ is not finite; hence, $\mathscr{P}$ is countable.

In part 2 we want to prove the following: a real number r is called an algebraic number if r is a solution to a polynomial equation: $p(x) = a_{0} + a_{1}x + a_{2}x^{2}+\ldots+a_{m}x^{m}=0$ with integral coefficients. Prove the set A of algebraic numbers is countable.

So, by the preceding sub-problem and its proof, the set of polynomial equations is countable. Let $E = \{ p_{1}(x)=0, p_{2}(x)=0, \ldots\}$ so that E is the set of polynomial equations.

Define: $A_{k} = \{ x: x \hspace{0.1in}is \hspace{0.1in}a \hspace{0.1in}solution \hspace{0.1in}of \hspace{0.1in} p_{k}(x)=0\}$ .

Since a polynomial of degree n can have at most n roots, each $A_{k}$ is finite. Therefore, $A = \bigcup \{ A_{k}: k \in \mathscr{Z}^{+}\}$ is a countable family of countable sets. So, A is countable.

QED.

Problem 5:

Prove that there exist uncountably many transcendental numbers, that is, numbers which are not algebraic.

Proof 5:

$\mathscr{R}$ is union of algebraic and transcendental numbers, and since the set of algebraic numbers is countable, whereas $\mathscr{R}$ is not, this implies that the set of transcendental numbers is uncountable. In fact, it has the power of the continuum.

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 only the values 0 and 1 ) on M is equivalent to the set of all subsets of M.

Proof 6:

We first use the following:

Given a non-empty set A with at least two elements, define its characteristic function as follows: $\chi_{A}: A \rightarrow \{ 0,1\}$ as $f(x)=1$ when $x \in A$ , and $f(x)=0$ when $x \notin A$ .

So, now, we first prove the following: Let A be any set and let $C(X)$ be the family of characteristic functions of X, that is, the family of functions $f:[0,1]$ . Then $\mathscr{P}(X) \sim C(X)$ , that is, the power set of X and the set of continuous functions on X are isomorphic, that is, there exists a bijection between these two.

Toward that end, let A be any other subset of X, that is, let $A \in \mathscr{P}(X)$ . Let $f: \mathscr{P}(X) \rightarrow C(X)$ be defined by $f(A) = \chi_{A}$ , that is, f maps each subset A of X into the characteristic function $\chi_{A}$ of A. Also, f is bijective. Hence, $\mathscr{P}(X) \sim C(X)$ . QED.

Problem 7:

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]$

Proof 7:

This is a direct application of the Cantor-Bernstein theorem: Given any two sets A and B, suppose that A contains a subset $A_{1}$ equivalent to B, while B contains a subset $B_{1}$ equivalent to A. Then, A and B are equivalent.

QED.

Problem 8:

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

Proof 8:

Because the union is still an uncountable set. In more polished language, the cardinal number of union of two sets is the sum of the cardinals. QED.

Problem 9:

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

9a) the set of all infinite sequences of positive integers.

9b) the set of all ordered n-tuples of real numbers.

9c) the set of all infinite sequences of real numbers.

Solution :

Solution 9a:

In this case, each sequence can be uniquely “represented” by a “real decimal number” lying between zero and one. Hence, such a set has the power of the continuum.

Solution 9b and 9c:

Similar argument.

QED.

MScMathematics

Tag: Kolmogorov and Fomin

Problem Set based on VII. Complete Metric Spaces

Problem Set based on VI. Convergence, open and closed sets.

Introductory Real Analysis: Exercise 3 solutions: related to set theory

Introductory real analysis: exercise 3:

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

Solutions to Kolmogorov and Fomin: Second problem set (previous blog)

Mathematics Hothouse shares:

Mathematics Hothouse shares:

Mathematics Hothouse shares:

Mathematics Hothouse shares:

Mathematics Hothouse shares:

Mathematics Hothouse shares: