# VI. Countable sets: My notes.

Reference:

1. Introduction to Topology and Modern Analysis by G. F. Simmons, Tata McGraw Hill Publications, India.
2. Introductory Real Analysis — Kolmogorov and Fomin, Dover Publications, N.Y.(to some extent, I have blogged this topic based on this text earlier. Still, it deserves a mention/revision again).
3. Topology : James Munkres.

The subject of this section and the next — infinite cardinal numbers — lies at the very foundation of modern mathematics. It is a vital instrument in the day to day work of many mathematicians, and we shall make extensive use of it ourselves (in our beginning studying of math ! :-)). This theory, which was created by the German mathematician Georg Cantor, also has great aethetic appeal, for it begins with ideas of extreme simplicity and develops through natural stages into an elaborate and beautiful structure of thought. In the course of our discussion, we shall answer questions which no one before Cantor’s time thought to ask, and we shall ask a question which no one can answer to this day…(perhaps !:-))

Without further ado, we can say that cardinal numbers are those used in counting, such as the positive integers (or natural numbers) 1, 2, 3, …familiar to us all. But, there is much more to the story than this.

The act of counting is undoubtedly one of the oldest of human activities. Men probably learned to count in a crude way at about the same time as they began to develop articulate speech. The earliest men who lived in communities and domesticated animals must have found it necessary to record the number of goats in the village herd by means of a pile of stones or some similar device. If the herd was counted in each night by removing one stone from the pile for each goat accounted for, then stones left over would have indicated strays, and herdsmen would have gone out to search for them. Names for numbers and symbols for them like our 1, 2, 3, …would have been superfluous. The simple yet profound idea of a one-to-one correspondence between the stones and the goats would have fully met the needs of the situation.

In a manner of speaking, we ourselves use the infinite set

$N = \{ 1, 2, 3, \ldots\}$

of all positive integers as “pile of stones.” We carry this set around with us as part of our intellectual equipment. Whenever we want to count a set, say, a stack of dollar bills, we start through the set N and tally off one bill against each positive integer as we come to it. The last number we reach, corresponding to the last bill, is what we call the number of bills in the stack. If this last number happens to be 10, then “10” is our symbol for the number of bills in the stack, as it also is for the number of our fingers, and for the number of our toes, and for the number of elements which can be put into one-to-one correspondence with the finite set $\{ 1,2,3, \ldots, 10\}$. Our procedure is slightly more sophisticated than that of the primitive savage man. We have the symbols 1, 2, 3, …for the numbers which arise in counting; we can record them for future use, and communicate them to other people, and manipulate them by the operations of arithmetic. But the underlying idea, that of the one-to-one correspondence, remains the same for us as it probably was for him.

The positive integers are adequate for our purpose of counting any non-empty finite set, and since outside of mathematics all sets appear to of this kind, they suffice for all non-mathematical counting. But in the world of mathematics, we are obliged to consider many infinite sets, such as the set of positive integers itself, the set of all integers, the set of all rational numbers, the set of all real numbers, the set of all points in a plane, and so on. It is often important to be able to count such sets, and it was Cantor’s idea to do this, and to develop a theory of infinite cardinal numbers, by means of one-to-one correspondence.

In comparing the sizes of two sets, the basic concept is that of numerical equivalence as defined in the previous section. We recall that two non-empty sets are numerically equivalent if there exists a one-to-one mapping of a set onto the other, or — and this amounts to the same thing — if there can be found a one-to-one correspondence between them. To say that two non-empty finite sets are numerically equivalent is of course to say that they have the same number of elements in the ordinary sense. If we count one of them, we simply establish a one-to-one correspondence between its elements and a set of positive integers of the form $\{1,2,3, \ldots, n \}$ and we then say that n is the number of elements possessed by both, or the cardinal number of both. The positive integers are the finite cardinal numbers. We encounter many surprises as we follow Cantor and consider numerical equivalences for infinite sets.

The set $N = \{ 1,2,3, \ldots\}$ of all positive integers is obviously “larger” than the set $\{ 2,4,6, \ldots\}$ of all even positive integers, for it contains this set as a proper subset. It appears on the surface that N has “more” elements. But it is very important to avoid jumping to conclusions when dealing with infinite sets, and we must remember that our criterion in these matters is whether there exists a one-to-one correspondence between the sets (not whether one set is a proper subset or not of the other) . As a matter of fact, consider the “pairing”

$1,2,3, \ldots, n, \ldots$

$2,4,6, \ldots, 2n, \ldots$

serves to establish a one-to-one correspondence between these sets, in which each positive integer in the upper row is matched with the even positive integer (its double) directly below it, and these two sets must therefore be regarded as having the same number of elements. This is a very remarkable circumstance, for it seems to contradict our intuition and yet is based only on solid common sense. We shall see below, in Problems 6 and 7-4, that every infinite set is numerically equivalent to a proper subset of itself. Since this property is clearly not possessed by any finite set, some writers even use it as the definition of an infinite set.

In much the same way as above, we can show that N is numerically equivalent to the set of all even integers:

$1, 2, 3,4, 5,6, 7, \ldots$

$0,2,-2,4,-4,4,6,-6, \ldots$

Here, our device is start with zero and follow each even positive integer as we come to it by its negative. Similarly, N is numerically equivalent to the set of all integers:

$1,2,3,4,5,6,7, \ldots$

$0,1,-1, 2, -2, 3, -3, \ldots$

It is of considerable interest historical interest to note that Galileo had observed in the early seventeenth century that there are precisely as many perfect squares (1,4,9,16,25, etc.) among the positive integers as there are positive integers altogether. This is clear from the “pairing”:

$1,2,3,4,5, \ldots$

$1^{2}, 2^{2}, 3^{2}, 4^{2}, 5^{2}, \ldots$

It struck him as very strange that this should be true, considering how sparsely strewn the squares are among all the positive integers. But, the time appears not to have been ripe for the exploration of this phenomenon, or perhaps he had other things on his mind; in any case, he did not follow up his idea.

These examples should make it clear that all that is really necessary in showing that an infinite set X is numerically equivalent to N is that we be able to list the elements of X, with a first, a second, a third, and so on, in such a way that it is completed exhausted by this counting off of its elements. It is for this reason that any infinite set which is numerically equivalent to N is said to be countably infinite. (Prof. Walter Rudin also, in his classic on mathematical analysis, considers a countable set to be either finite or countably infinite. ) We say that a set is countable it is non-empty and finite (in which case it can obviously be counted) or if it is countably infinite.

One of Cantor’s earliest discoveries in his study of infinite sets was that the set of all positive rational numbers (which is very large : it contains N and a great many other numbers besides) is actually countable. We cannot list the positive rational numbers in order of size, as we can the positive integers, beginning with the smallest, then the next smallest, and so on, for there is no smallest, and between any two there are infinitely many others. We must find some other way of counting them, and following Cantor, we arrange them not not in order of size, but according to the size of the sum of numerator and denominator. We begin with all positive rationals whose numerator and denominator sum add up to 2: there is only one $\frac{1}{1}=1$. Next, we list (with increasing numerators) all those for which this sum is 3: $\frac{1}{2}, \frac{2}{1}=2$. Next, all those for which the sum is 4: $\frac{1}{3}, \frac{2}{2}=1, \frac{3}{1}=3$. Next, all those for which this sum is 5: $\frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}=4$. Next, all those for which this sum is 6: $\frac{1}{5}, \frac{2}{4}, \frac{3}{3}=1, \frac{4}{2}=2, \frac{5}{1}=5$. And, so on. If we now list all these together from the beginning, omitting those already listed when we come to them, we get a sequence like:

$1, 1/2, 2, 1/3, 1/4, 2/3, 3/2, 4, 1/5, 5, \ldots$

which contains each positive rational number once and only once. (There is a nice schematic representation of this : Cantor’s diagonalization process; please google it). In this figure, the first row contains all positive rationals with numerator 1, the second all with numerator 2, and so on. Our listing amounts to traversing this array of numbers in a zig-zag manner (again, please google), where of course, all those numbers already encountered are left out.

It is high time that we christened the infinite cardinal number we have been discussing, and for this purpose, we use the first letter of the Hebrew alphabet, $\bf{aleph_{0}}$. We say that $\aleph_{0}$ is the number of elements in any countably infinite set. Our complete list of cardinal numbers so far is

$1, 2, 3, \ldots, \aleph_{0}$.

We expand this list in the next section.

Suppose now that m and n are two cardinal numbers (finite or infinite). The statement that m is less than n (written m < n) is defined to mean the following: if X and Y are sets with m and n elements, then (i) there exists a one-to-one mapping of X into Y, and (ii) there does not exist a mapping of X onto Y. Using this concept, it is easy to relate our cardinal numbers to one another by means of:

$1<2<3< \ldots < \aleph_{0}$.

With respect to the finite cardinal numbers, this ordering corresponds to their usual ordering as real numbers.

Regards,

Nalin Pithwa

# V. Exercises: Partitions and Equivalence Relations

Reference: Topology and Modern Analysis, G. F. Simmons, Tata McGraw Hill Publications, India.

1. Let $f: X \rightarrow Y$ be an arbitrary mapping. Define a relation in X as follows: $x_{1} \sim x_{2}$ means that $f(x_{1})=f(x_{2})$. Prove that this is an equivalence relation and describe the equivalent sets.

Proof : HW. It is easy. Try it. 🙂

2. In the set $\Re$ of real numbers, let $x \sim y$ means that $x-y$ is an integer. Prove that this is an equivalence relation and describe the equivalence sets.

Proof: HW. It is easy. Try it. 🙂

3. Let I be the set of all integers, and let m be a fixed positive integer. Two integers a and b are said to be congruent modulo m — symbolized by $a \equiv b \pmod {m}$ — if a-b is exactly divisible by m, that is, if $a-b$ is an integral multiple of m. Show that this is an equivalence relation, describe the equivalence sets, and state the number of distinct equivalence sets.

Proof: HW. It is easy. Try it. 🙂

4. Decide which one of the three properties of reflexivity, symmetry and transitivity are true for each of the following relations in the set of all positive integers: $m \leq n$, $m < n$, $m|n$. Are any of these equivalence relations?

Proof. HW. It is easy. Try it. 🙂

5. Give an example of a relation which is (a) reflexive, but not symmetric or transitive. (b) symmetric but not reflexive or transitive. (c) transitive but not reflexive or symmetric (d) reflexive and symmetric but not transitive (e) reflexive and transitive but not symmetric. (f) symmetric and transitive but not reflexive.

Solutions. (i) You can try to Google (ii) Consider complex numbers (iii) there are many examples given in the classic text “Discrete Mathematics” by Rosen.

6) Let X be a non-empty set and $\sim$ a relation in X. The following purports to be a proof of the statement that if this relation is symmetric and transitive, then it is necessarily reflexive: $x \sim y \Longrightarrow y \sim x$ ; $x \sim y$ and $y \sim x \Longrightarrow x$; therefore, $x \sim x$ for every x. In view of problem 5f above, this cannot be a valid proof. What is the flaw in the reasoning? 🙂

7) Let X be a non-empty set. A relation $\sim$ in X is called circular if $x \sim y$ and $y \sim x \Longrightarrow z \sim x$, and triangular if $x \sim y and x \sim z \Longrightarrow y \sim z$. Prove that a relation in X is an equivalence relation if and only if it is reflexive and circular if and only if it is reflexive and triangular.

HW: Try it please. Let me know if you need any help.

Regards,

Nalin Pithwa.

PS: There are more examples on this topic of relations in Abstract Algebra of I. N. Herstein and Discrete Mathematics by Rosen.

# V. Partitions and Equivalence Relations: My Notes

References:

1. Topology and Modern Analysis, G F Simmons, Tata McGraw Hill Publications, India.
2. Toplcs in Algebra, I N Herstein.
3. Abstract Algebra, Dummit and Foote.
4. Topology by James Munkres.

In the first part of this section, we consider a non-empty set X, and we study decompositions of X into non-empty subsets which fill it out and have no elements in common with one another. We give special attention to the tools (equivalence relation) which are normally used to generate such decompositions.

A partition of X is a disjoint class $\{ X_{i} \}$ of non-empty subsets of X whose union if the full set X itself. The $X_{i}$‘s are called the partition sets. Expressed somewhat differently, a partition of X is the result of splitting it, or subdividing it, into non-empty subsets in such a way that each element of X belongs to one and only one of the given subsets. ]

If X is the set $\{1,2,3,4,5 \}$, then $\{1,3,5 \}$, $\{2,4 \}$ and $\{1,2,3 \}$ and $\{ 4,5\}$ are two different partitions of X. If X is the set $\Re$ of all real numbers, then we can partition $\Re$ into the set of all rationals and the set of all irrationals, or into the infinitely many closed open intervals of the form $[n, n+1)$ where n is an integer. If X is the set of all points in the coordinate plane, then we can partition X in such a way that each partition set consists of all points with the same x coordinate (vertical lines), or so that each partition set consists of all points with the same y coordinate (horizontal lines).

Other partitions of each of these sets will readily occur to the reader. In general, there are many different ways in which any given set can be partitioned. These manufactored examples are admittedly rather uninspiring and serve only to make our ideas more concrete. Later in this section we consider some others which are more germane to our present purposes.

A binary relation in the set X is a mathematical symbol or verbal phrase, which we denote by R in this paragraph, such that for each ordered pair $(x,y)$ of elements of X the statement $x \hspace{0.1in} R \hspace{0.1in} y$ is meaningful, in the sense that it can be classified definitely as true or false. For such a binary relation, $x \hspace{0.1in} R \hspace{0.1in}y$ symbolizes the assertion that x is related by R to y, and $x \not {R} \hspace{0.1in}y$ the negation of this, namely, the assertion that x is not related by R to y. Many examples of binary relations can be given, some familiar and others less so, some mathematical and others not. For instance, if X is the set of all integers and R is interpreted to mean “is less than,” which of course is usually denoted by the symbol <, then we clearly have 6<7 and $5 \not < 2$. We have been speaking of binary relations, which are so named because they apply only to ordered pairs of elements, rather than to ordered triples, etc. In our work, we drop the qualifying adjective and speak simply of a relation in X, since we shall have occasion to consider only relations of this kind. {NB: Some writers prefer to regard a relation R in X as a subset R of $X \times X$. From this point of view, x R y and $x \not {R} y$ are simply equivalent ways of writing $(x,y) \in R$ and $(x,y) \notin R$. This definition has the advantage of being more tangible than our definition, and the disadvantage that few people really think of a relation in this way.” )

We now assume that a partition of our non-empty set X is given, and we associate with this partition a relation on X. This relation is defined to be in the following way: we say that x is equivalent to y and write this as $x \sim y$ (the symbol $\sim$ is pronounced “wiggle”.), if x and y belong to the same partition set. It is obvious that the relation $\sim$ has the following properties:

a) $x \sim x$ for every x (reflexivity)

b) $x \sim y \Longrightarrow y \sim x$ (symmetry)

c) $x \sim y \hspace{0.1in} and \hspace{0.1in} y \sim z \Longrightarrow x \sim z$ (transitivity)

This particular relation in X arose in a special way, in connection with a given partition of X, and its properties are immediate consequences of the definition. Any relation whatever in X which possesses these three properties is called an equivalence relation in X.

We have just seen that each partition of X has associated with it a natural equivalence relation in X. We now reverse the situation and prove that a given equivalence relation in X determines a natural partition of X.

Let $\sim$ be an equivalence relation in X; that is, assume that it is reflexive, symmetric, and transitive in the sense described above. If x is an element of X, the subset of X defined by $[x] = \{ y: y \sim x\}$ is called the equivalence set of x. The equivalence set of x is thus the set of all elements which are equivalent to x. We show that the class of all distinct equivalence sets forms a partition of X. By reflexivity, $x \in [x]$ for each element x in X, so each equivalence set is non-empty and their union is X. It remains to be shown that any two equivalence sets $[x_{1}]$ and $[x_{2}]$ are either disjoint or identical. We prove this by showing that if $[x_{1}]$ and $[x_{2}]$ are not disjoint, then they must be identical. Suppose that $[x_{1}]$ and $[x_{2}]$ are not disjoint, that is, suppose that they have a common element z. Since x belongs to both equivalence sets, $z \sim x_{1}$ and $z \sim x_{2}$, and by symmetry $x_{1} \sim z$. Let y be any element of $x_{1}$, so that $y \sim x_{1}$. Since $y \sim x_{1}$ and $x_{1} \sim z$, transitivity shows that $y \sim z$. By another application of transitivity, $y \sim z$ and $z \sim x_{2}$, imply that $y \sim x_{2}$ so that y is in $[x_{2}]$. Since y was arbitrarily chosen in $[x_{1}]$, we see by this that $[x_{1}] \subseteq [x_{2}]$. The same reasoning shows that $[x_{2}] \subseteq [x_{1}]$ and from this we conclude that $[x_{1}] = [x_{2}]$.

The above discussion demonstrates that there is no real distinction (other than a difference in language) between partitions of a set and equivalence relation by regarding elements as equivalent if they belong to the same partition set, and if we start with an equivalence relation, we get a partition by grouping together into subsets all elements which are equivalent to one another. We have here a single mathematical idea, which we have been considering from two different points of view, and the approach we choose in any particular application depends entirely on our own convenience. In practice, it is almost invariably the case that we use equivalence relations (which are usually easy to define) to obtain partitions (which are sometimes difficult to describe fully).

We now turn to several of the more important simple examples of equivalence relations.

Let I be the set of integers. If a and b are elements of this set, we write $a = b$ (and say that a equals b) if a and b are the same integer. Thus, $2+3=5$ means that the expression on the left and right are simply different ways of writing the same integer. It is apparent that = used in this sense is an equivalence relation in the set I:

i) a=a for every a

ii) $a=b \Longrightarrow b=a$

iii) $a=b \hspace{0.1in} b=c \Longrightarrow a=c$.

Clearly, each equivalence set consists of precisely one integer.

Another familiar example is this relation of equality commonly used for fractions. We remind the reader that, strictly speaking, a fraction is merely a symbol of the form a/b, where a and b are integers and b is not zero. The fractions 2/3 and 4/6 are obviously not identical, but nevertheless we consider them to be equal. In general, we say that two fractions a/b and c/d are equal, written $\frac{a}{b} = \frac{c}{d}$, if ad and bc are equal as integers in the usual sense (see the paragraph above). (HW quiz: show this is an equivalence relation on the set of fractions). An equivalence set of fractions is what we call a rational number. Every day usage ignores the distinction between fractions and rational numbers, but it is important to recognize that from the strict point of view it is the rational numbers (and not the fractions) which form part of the real number system.

Our final example has a deeper significance, for it provides us with the basic tool for our work of the next two sections.

For the remainder of all this section, we consider a relation between pairs of non-empty sets, and each set mentioned (whether we say so explicitly or not) is assumed to be non-empty. If X and Y are two sets, we say that X is numerically equivalent to Y if there exists a one-to-one correspondence between X and Y, that is, if there exists a one-to-one mapping of X onto Y. This relation is reflexive, since the identity mapping $i_{X}: X \rightarrow X$ is one-to-one onto; it is symmetric since if $f: X \rightarrow Y$ is one-to-one onto, then its inverse mapping $f^{-1}: Y \rightarrow X$ is also one-to-one onto; and it is transitive, since if $f: X \rightarrow Y$ and $g: Y \rightarrow Z$ are one-to-one onto, then $gf: X \rightarrow Z$ is also one-to-one onto. Numerical equivalence has all the properties of an equivalence relation, and if we consider it as an equivalence relation in the class of all non-empty subsets of some universal set U, it groups together into equivalence sets all those subsets of U which have the “same number of elements.” After we state and prove the following very useful but rather technical theorem, we shall continue in Sections 6 and 7 with an exploration of the implications of these ideas.

The theorem we have in mind — the Schroeder-Bernstein theorem: If X and Y are two sets each of which is numerically equivalent to a subset of the other, then all of X is numerically equivalent to all of Y. There are several proofs of this classic theorem, some of which are quite difficult. The very elegant proof we give is essentially due to Birkhoff and MacLane.

Proof:

Assume that $f: X \rightarrow Y$ is a one-to-one mapping of X into Y, and that $g: Y \rightarrow X$ is a one-to-one mapping of Y into X. We want to produce a mapping $F: X \rightarrow Y$ which is one-to-one onto. We may assume that neither f nor g is onto, since if f is, we can define F to f, and if g is, we can define F to be $g^{-1}$. Since both f and g are one-to-one, it is permissible to use the mappings $f^{-1}$ and $g^{-1}$ as long as we keep in mind that $f^{-1}$ is defined only on f(X) and $g^{-1}$ is defined only on g(Y). We obtain the mapping F by splitting both X and Y into subsets which we characterize in terms of the ancestry of their elements. Let x be an element of X. We apply $g^{-1}$ (if we can) to get the element $g^{-1}(x)$ in Y. If $g^{-1}(x)$ exists, we call it the first ancestor of x. The element x itself we call the zeroth ancestor of x. We now apply $f^{-1}$ to $g^{-1}(x)$ if we can, and if $(f^{-1}g^{-1})(x)$ exists, we call it the second ancestor of x. We now apply $g^{-1}$ to $(f^{-1}g^{-1})(x)$ if we can, and if $(g^{-1}f^{-1}g^{-1})(x)$ exists, we call it the third ancestor of x. As we continue this process of tracing back the ancestry of x, it becomes apparent that there are three possibilities — (1) x has infinitely many ancestors. We denote by $X_{i}$, the subset of X, which consists of all elements with infinitely many ancestors (2) x has an even number of ancestors, this means that x has a last ancestor (that is, one which itself has no first ancestor) in X. We denote by $X_{e}$ the subset of X consisting of all elements with an even number of ancestors. (3) x has an odd number of ancestors; this means that x has a last ancestor in Y. We denote by $X_{o}$ the subset of X which consists of all elements with an odd number of ancestors. The three sets $X_{i}$, $X_{e}$, $X_{o}$ form a disjoint class whose union is X. We decompose Y in just the same way into three subsets $Y_{i}$, $Y_{e}$, $Y_{o}$. It is easy to see that f maps $X_{i}$ onto $Y_{i}$, and $X_{e}$ onto $Y_{e}$, and that $g^{-1}$ maps $X_{o}$ onto $Y_{o}$, and we complete the proof by defining F in the following piecemeal manner:

$F(x) = f(x)$ if $x \in X_{i} \bigcup X_{e}$

and $F(x) = g^{-1}(x)$ if $x \in X_{o}$.

QED.

The Schroeder Bernstein theorem has great theoretical and practical significance. It main value for us lies in its role as a tool by means of which we can prove numerical equivalence with a minimum of effort for many specific sets. We put it to work in Section 7.

Regards,

Nalin Pithwa

# IV. Product of Sets: Exercises

Reference: Topology and Modern Analysis, G F Simmons, Tata McGraw Hill Publications, India.

Problems:

I) The graph of a mapping $f: X \rightarrow Y$ is a subset of the product $X \times Y$. What properties characterize the graphs of mappings among all subsets of $X \times Y$?

Solution I: composition.

II) Let X and Y be non-empty sets. If $A_{1}$ and $A_{2}$ are subsets of X, and $Y_{1}$ and $Y_{2}$ are subsets of Y, then prove the following

(a) $(A_{1} \times B_{1}) \bigcap (A_{2} \times B_{2}) = (A_{1} \bigcap A_{2}) \times (B_{1} \bigcap B_{2})$

(b) $(A_{1} \times B_{1}) - (A_{2} \times B_{2}) = (A_{1}-A_{2}) \times (B_{1}-B_{2}) \bigcup (A_{1} \bigcap A_{2}) \times (B_{1}-B_{2}) \bigcup (A_{1}-A_{2}) \times (B_{1} \bigcap B_{2})$

Solution IIa:

TPT: $(A_{1} \times B_{1}) \times (A_{2} \times B_{2}) = (A_{1} \bigcap A_{2}) \times (B_{1} \bigcap B_{2})$

This is by definition of product and the fact that the co-ordinates are ordered and the fact that $A_{1} \subseteq X$, $A_{2} \subseteq X$, $B_{1} \subseteq Y$, and $B_{2} \subseteq Y$.

Solution IIb:

Let $(a_{i}, b_{j}) \in A_{1} \times B_{1}$, but $(a_{i}, b_{j}) \notin A_{2} \times B_{2}$. So, the element may belong to $(A_{1}-A_{2}) \times (B_{1} - B_{2})$ or it could happen that it belongs to $A_{1} \times A_{1}$, but to $(B_{1}-B_{2})$ (here we need to remember that the element is ordered); so, also it could be the other way: it could belong to $(A_{1}-A_{2})$ but to $(B_{1} \bigcap B_{2})$ also. The same arguments applied in reverse establish the other subset inequality. Hence, done.

III) Let X and Y be non-empty sets, and let A and B be rings of subsets of X and Y, respectively. Show that the class of all finite unions of sets of the form $A \times B$ with $A \in \bf{A}$ and $B \in \bf{B}$ is a ring of subsets of $X \times Y$.

Solution III:

$\bigcup_{i=1}^{n}A_{i} \times B_{i} = \bigcup_{i=1}^{n}A_{i} \times \bigcup_{i=1}^{n}B_{i}$.

From question IIb above, the difference of any two pairs of sets is also in $X \times Y$.

Hence, done.

Regards,

Nalin Pithwa

# Notes II: Sets and Functions:

Reference I : Topology and Modern Analysis, G F Simmons, Tata McGraw Hill.

III. Functions:

Many kinds of functions occur in topology in a wide variety of situations. In our work, we shall need the full power of the general concept of a function, and since, its modern meaning is much broader and deeper than its elementary meaning, we discuss this concept in considerable detail and develop its main abstract properties.

Let us begin with a brief inspection of some simple examples. Consider the elementary function

$y=x^{2}$

of the real variable x. What do we have in mind when we call this a function and say that y is a function of x? In a nutshell, we are drawing attention to the fact that each real number x has a specific real number y linked to it, which can be calculated according to the rule (or law of correspondence) given by the formula. We have here a process which applied to a real number x does something to it (squares it) to produce another number y (the square of x). Similarly,

$y = x^{2}-3x$ and $y = (x^{2}+1)^{-1}$

are two other simple functions of the real variable x, and each is given by a rule in the form of an algebraic expression which specifies the exact manner in which the value of y depends on the value of x.

The rules for the functions we have just mentioned are expressed by formulas. In general, this is possible for functions of a very simple kind or for those which are sufficiently important to deserve a special symbol of their own. Consider for instance the function of the real variable x defined as follows: for each real number x, write x as an infinite decimal (using the scheme of decimal expansion in which infinite chains of 9s are avoided — in which for example, 1/4 is represented as 0.250000….rather than by 0.24999….); then, let y be the 59th digit after the decimal point. There is of course no standard formula for this but nevertheless it is a perfectly respectable function whose rule is given by a verbal description. On the other hand, the function $y=\sin{x}$ of the real variable x is so important that its rule, though fully as complicated as the one just defined is assigned the special symbol sin. When discussing functions in general, we work to allow for all sorts of rules and to talk about them all at once, so we simply employ non-committal notations like $y=f(x)$, $y=g(z)$, and so on.

Each of the functions mentioned above is defined for all real numbers x. The example $y = \frac{1}{x}$ shows that this restriction is much too severe, for this function is defined only for non zero values of x. Similarly, $y = \log{x}$ is defined only for positive values of x and $y = \arcsin{x}$ only for values of x in the interval $[-1,1]$. Whatever our conception of a function may be, it should certainly be broad enough to include examples like these, which are defined only for some values of the real variable x.

In real analysis, the notion of function is introduced in the following way. Let X be any non-empty set of real numbers. We say that a function $y=f(x)$ is defined on X if the rule f associates a definite real number y with each real number x in X. The specific nature of the rule f is totally irrelevant to the concept of a function. The set X is called the domain of the given function, and the set Y of all the values it assumes is called its range. If we speak of complex numbers here instead of real numbers, we have the notion of function as it is used in complex analysis.

This point of view towards functions is actually more general than is needed for aims of analysis, but it isn’t nearly general enough for our purposes. The sets X and Y above were taken to be sets of numbers. If we now remove even this restriction and allow X and Y to be completely arbitrary non-empty sets, then we arrive at the most inclusive concept of a function. By way of illustration, suppose that X is the set of all squares in a plane and that Y is the set of all circles in the same plane. We can define a function $y=f(x)$ by requiring that the rule f associate with each square x that circle y which is inscribed in it. In general, there is no need at all for either X or Y to be a set of numbers. All that is really necessary for a function is two non-empty sets X and Y and a rule f which is meaningful and unambiguous in assigning to each element x in X a specific element y in Y.

With these preliminary descriptive remarks, we now turn to the rather abstract but very precise ideas they are intended to motivate.

A function consists of three objects: two non-empty sets X and Y (which may be equal but need not be) and a rule f which assigns to each element x in X a single fully determined element y in Y. The y which corresponds in this way to a given x is usually written f(x), and is called the image of x under the rule f, or the value of f at the element x. (It is fun to draw some figures here). This notation is supposed to be suggestive of the idea that the rule f takes the element x and does something to it to produce the element $y = f(x)$. The rule f is often called a mapping or transformation or operator to amplify this concept of it. We then think of f as mapping x’s to y’s, or transforming x’s to y’s, or operating on x’s to produce y’s. The set X is called the domain of the function, and the set of all f(x)’s for all x’s in X is called its range. A function whose range consists of just one element is called a constant function.

We often denote by $f: X \rightarrow Y$ the function with rule f, domain X and range contained in Y. This notation is useful because the essential parts of the function are displayed in a manner which emphasizes that it is a composite object, the central thing being the rule or mapping f. You can try drawing a figure depicting a convenient way of picturing this function. (these notes don’t have my diagrams from the reference book) On the left, X and Y are different sets, and on the right they are equal — in which case we usually refer to f as a mapping of X into itself. If it is clear that from the context what the sets X and Y are, or if there is no real need to specify them explicitly, it is common practice to identify the function $f: X \rightarrow Y$ with the rule f, and to speak of f alone as if it were the function under consideration (without mentioning the sets X and Y).

It sometimes happens that two perfectly definite sets X and Y are under discussion and that a mapping of X into Y arises which has no natural symbol attached to it. If there is no necessity to invent a symbol for this mapping and if it is quite clear what the mapping is, it is often convenient to designate it by $x \rightarrow y$. Accordingly, the function $y=x^{2}$ mentioned in the beginning of this section can be written as $x \rightarrow x^{2}$ or $x \rightarrow y$ where y is understood to be the square of x.

A function f is called an extension of a function g (and g is called a restriction of f) if the domain of f contains the domain of g and $f(x) = g(x)$ for each x in the domain of y.

Most of mathematical analysis, both classical and modern, deals with functions whose values are real numbers or complex numbers. This is also true of those parts of topology which are concerned with the foundations of analysis. If the range of a function consists of real numbers, we call it a real function, similarly, a complex function is one whose range consists of complex numbers. Obviously, every real function is also complex. We lay very heavy emphasis on real and coomplex functions through out our work.

As a matter of usage, we generally prefer to reserve the term function for real or complex functions and to speak of mappings when dealing with functions whose values are not necessarily numbers.

Consider a mapping $f: X \rightarrow Y$. When we call f a mapping of X into Y, we mean to suggest by this that the elements f(x) — as x varies over all the elements of X — need not fill up Y; but if it definitely does happen that the range of f equals Y, or if we specifically want to assume this, then we call f a mapping of X onto Y. If two different elements in X always have different images under f, then we call f a one=to-one mapping of X into Y. If $f: X \rightarrow Y$ is both onto and one-to-one, then we can define its inverse mapping $f^{-1}: X \rightarrow Y$ as follows: for each y in Y, we find that unique element x in X such that $f(x)=y$ 9 x exists and is unique since f is onto and one-to-one); we then define x to be $f^{-1}(y)$. The equation $x = f^{-1}(y)$ is the result of solving $y=f(x)$ for x in just the same way as $x = \log{y}$ is the result of solving $e^{x}$ for x. Figure 7 illustrates the concept of the inverse of a mapping.

If f is a one-to-one mapping of X onto Y, it will sometimes be convenient to subordinate the conception of f as a mapping sending x’s over to y’s and to emphasize its role as a link between x’s an y’s. Each x has linked to it (or has corresponding to it) exactly one $x = f^{-1}(y)$. When we focus our attention on this aspect of a mapping which is one-to-one onto correspondence between X and Y, and $f^{-1}$ is a one-to-one correspondence between Y and X.

Now, consider an arbitrary mapping $f: X \rightarrow Y$. The mapping f which sends each element of X over to an element of Y induces the following important set mappings. If A is a subset of X, then the image f(A) is the subset of Y defined by

$f^{-1}(B) = \{ x : f(x) \in \hspace{0.1in} B\}$

and the second set mappings pull each B back to its corresponding $f^{-1}(B)$. It is often essential for us to know how these set mappings behave with respect to set inclusion and operations on sets. We develop most of their significant features in the following two paragraphs.

The main properties of the first set mapping are:

$f(\phi) = \phi$

$f(X) \subseteq Y$

$A_{1} \subseteq A_{2} \Longrightarrow f(A_{1}) \subseteq f(A_{2})$

$f(\bigcup_{i})A_{i} = \bigcup_{i}f(A_{i})$

$f(\bigcap_{i}A_{i}) \subseteq \bigcup_{i}f(A_{i})$….call these relations I.

The reader should convince himself of the truth of these statements. For instance, to prove (i) we would have to prove first that $f(\bigcup_{i}A_{i})$ is a subset of $\bigcup_{i}f(A_{i})$, and second that $\bigcup_{i}f(A_{i})$ is a subset of $f(\bigcup_{i}A_{i})$. A proof of the first of these set inclusions might run as follows: an element in $f(\bigcup_{i}A_{i})$ is the image of some element in $\bigcup_{i}A_{i}$, therefore, it is the image of an element in some $A_{i}$, therefore it is some $f(A_{i})$ and so finally it is in $\bigcup_{i}f(A_{i})$. The irregularities and gaps which the reader will notice in the above statements are essential features of this set mapping. For example, the image of an intersection need not equal the intersection of the images, because two disjoint sets can easily have images which are not disjoint. Furthermore, without special assumpitions (see Problem 6), nothing can be said about the relation between $f(A)^{'}$ and $f(A^{'})$.

The second set mapping is much better behaved. Its properties are satisfyingly complete, and can be stated as follows:

$f^{-1}(\phi) = \phi$ and $f^{-1}(Y) =X$;

$B_{1} \subseteq B_{2} \Longrightarrow f^{-1}(B_{1}) \subseteq f^{-1}(B_{2})$

$f^{-1}(\bigcup_{i}B_{i}) \Longrightarrow \bigcup_{i}f^{-1}(B_{i})$….(2)

$f^{-1}(\bigcap_{i}B_{i}) = \bigcap_{i}f^{-1}(B_{i})$….(3)

$f^{-1}(B^{'}) = f^{-1}(B)^{'}$….(4)

Again, the reader should verify each of these statements for himself.

We discuss one more concept in this section, that of the multiplication or composition of mappings. If $y= f(x)=x^{2}+1$ and $z = g(y) = \sin{y}$

then these two functions can be put together to form a single function defined by $x = (gf)(x) = g(x^{2}+1)=\sin{(x^{2}+1)}$. One of the most important tools of calculus (the chain rule) explains how to differentiate functions of this kind. This manner of multiplying functions together is of basic importance for us as well, and we formulate it in general as follows. We define the product of these mappings, denoted by $gf: X \rightarrow Z$ by $(gf)(x) = g(f(x))$. In words, an element x in X is taken by f to the element f(x) in Y,and then g maps f(x) to g(f(x)) in Z. Figure 8 is a picture of this process. We observe that the two mappings involved here are not entirely arbitrary, for the set Y which contains the range of the first equals the domain of the second. More generally, the product of two mappings is meaningful whenever the range of the first is contained in the domain of the second. We have regarded f as the first mapping and y as the second, and in forming their product gf, their symbols have gotten turned around. This is a rather unpleasant phenomenon, for which we blame the occasional perversity of mathematical symbols. Perhaps it will help the reader to keep this straight in his mind if he will remember to read the product gf from right to left: first apply f, then g.

Problems:

To be continued next blog.

Regards,

Nalin Pithwa

# Problem Set based on VII. Complete Metric Spaces

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.

Purva building, 5A
Flat 06
Mumbai, Maharastra 400101
India

# VII. Complete Metric Spaces

Reference: Introductory Real Analysis by Kolmogorov and Fomin. Translated by Richard A. Silverman. Dover Publications.

Available on Amazon India and Amazon USA. This text book can be studied in parallel with Analysis of Walter Rudin.

7.1. Definition and examples:

The reader is presumably already familiar with the notion of completeness of the real line. (One good simple reference for this could be: Calculus and analytic geometry by G B Thomas. You can also use, alternatively, Advanced Calculus by Buck and Buck.)The real line is, of course, a simple example of a metric space. We now make the natural generalisation of the notion of completeness to the case of an arbitrary metric space.

DEFINITION 1:

A sequence $\{ x_{n}\}$ of points in a metric space R with metric $\rho$ is said to satisfy the Cauchy criterion if given any $\epsilon >0$, there is an integer $N_{\epsilon}$ such that $\rho(x_{n}, x_{n^{'}})<\epsilon$ for all $n,n^{'}> N_{\epsilon}$.

DEFINITION 2:

A subsequence $\{ x_{n}\}$ of points in a metric space R is called a Cauchy sequence (or a fundamental sequence ) if it satisfies the Cauchy criterion.

THEOREM 1:

Every convergent sequence $\{ x_{n}\}$ is fundamental.

Proof 1:

If $\{ x_{n} \}$ converges to a limit x, then, given any $\epsilon>0$, there is an integer $N_{\epsilon}$ such that

$\rho(x_{n}, x) \leq \frac{\epsilon}{2}$ for all $n > N_{\epsilon}$.

But, then

$\rho(x_{n}, x_{n^{'}}) \leq \rho(x_{n},x)+\rho(x_{n^{'}},x)<\epsilon$

for all $n, n^{'} >N_{\epsilon}$. QED.

DEFINITION 3:

A metric space R is said to be complete if every Cauchy sequence in R converges to an element of R. Otherwise, R is said to be incomplete.

Example 1:

Let R be the “space of isolated points” (discrete metric space) defined as follows: Define $\rho(x,y)=0$, if $x=y$; let $\rho(x,y)=1$, when $x \neq y$. Then, the Cauchy sequence in R are just the “stationary sequences,” that is, the sequences $\{ x_{n}\}$ all of whose terms are the same starting from some index n. Every such sequence is obviously convergent to an element of R. Hence, R is complete.

Example 2:

The completeness of the real line R is familiar from elementary analysis:

Example 3:

The completeness of the Euclidean n-space $\Re^{n}$ follows from that of $\Re^{1}$. In fact, let

$x^{(p)} = (x_{1}^{(p)}, x_{2}^{(p)}, \ldots, x_{n}^{(p)})$ where $p = 1, 2, \ldots$

be fundamental sequence of points in $\Re^{n}$. Then, given $\epsilon >0$, there exists an $N_{\epsilon}$ such that

$\Sigma_{n=1}^{\infty} (x_{k}^{(p)}-x_{k}^{(q)})^{2} < \epsilon^{2}$

for all $p, q > N_{\epsilon}$. It follows that

$|x_{k}^{(p)}-x_{k}^{(q)}|<\epsilon$ for $k=1,2,\ldots, n$ for all $p,q > N_{\epsilon}$, that is, each $\{x_{k}^{(p)} \}$ is a fundamental sequence in $\Re^{1}$.

Let $x = (x_{1}, \ldots, x_{n})$ where $x_{k} = \lim_{p \rightarrow \infty} x_{k}^{(p)}$

Then, obviously $\lim_{p \rightarrow \infty} x^{(p)} = x$.

This proves the completeness of $\Re^{n}$. The completeness of the spaces $R_{0}^{n}$ and $R_{1}^{n}$ introduced in earlier examples/blogs is proved in almost the same way. (HW: supply the details). QED.

Example 4:

Let $\{ x_{n}(t)\}$ be a Cauchy sequence in the function space $C_{[a,b]}$ introduced earlier. Then, given any $\epsilon >0$, there is an $N_{\epsilon}$ such that

$|x_{n}(t) - x_{n^{'}}(t)|< \epsilon$….I

for all $n, n^{'} > N_{\epsilon}$ and all $t \in [a,b]$. It follows that the sequence $\{ x_{n}(t)\}$ is uniformly convergent. But the limit of a uniformly convergent sequence of continuous functions is itself a continuous function (see Problem 1 following this Section). Taking the limit as $n^{'} \rightarrow \infty$ in I, we find that

$|x_{n}(t) - x(t)|\leq \epsilon$ for all $n > N_{\epsilon}$ and all $t \in [a,b]$, that is, $\{ x_{n}(t)\}$ converges in the metric space $C_{[a,b]}$ to a function $x(t) \in C_{[a,b]}$. Hence, $C_{[a,b]}$ is a complete metric space.

Example 5:

Next, let $x^{(n)}$ be a sequence in the space $l_{2}$ so that

$x^ {(n)} = (x_{1}^{(n)}, x_{2}^{(n)}, \ldots, x_{k}^{(n)}, \ldots)$

$\Sigma_{k=1}^{\infty}(x_{k}^{(n)})^{2} < \infty$, where $n = 1, 2, , \ldots$

Suppose further that $\{ x^{(n)}\}$ is a Cauchy sequence. Then, given any $\epsilon > 0$ there is a $N_{\epsilon}$ such that

$\rho^{2}(x^{(n)},x^{(n^{'})}) = \Sigma_{k=1}^{\infty}(x_{k}^{(n)}-x_{k}^{(n^{'})})^{2}< \epsilon$…let us call this II.

if $n, n^{'} > N_{\epsilon}$.

It follows that $(x_{k}^{(n)}-x_{k}^{(n^{'})})^{2} < \epsilon$ (for $k =1, 2, \ldots$)

That is, for every k the sequence $\{ x_{k}^{(n)}\}$ is fundamental and hence, convergent. Let

$x_{k} = \lim_{n \rightarrow \infty} x_{k}^{(n)}$, $x = (x_{1}, x_{2}, \ldots, x_{k}, \ldots)$

Then, as we now show, x is itself a point of $l_{2}$ and moreover, $\{ x^{(n)}\}$ converges to x in the $l_{2}$ metric space, so that $l_{2}$ is a complete metric space.

In fact, the Cauchy criterion here implies that $\Sigma_{k=1}^{M}(x_{k}^{(n)}-x_{k}^{(n^{'})})^{2}<\epsilon$ for any fixed M. …let us call this III.

Holding n fixed in III, and taking the limit as $n^{'} \rightarrow \infty$, we get

$\Sigma_{k=1}^{M}(x_{k}^{(n)}-x_{k})^{2} \leq \epsilon$….call this IV.

Since IV holds for arbitrary M, we can in turn take the limit of IV as $M \rightarrow \infty$, obtaining

$\Sigma_{k=1}^{\infty}(x_{k}^{(n)}-x_{k})^{2} \leq \epsilon$.

But, as we have learnt earlier in this series of blogs, the convergence of the two series $\Sigma_{k=1}^{\infty}(x_{k}^{(n)})^{2}$ and $\Sigma_{k=1}^{\infty}(x_{k}^{(n)}-x_{k})^{2}$ implies that of the series $\Sigma_{k=1}^{\infty}x_{k}^{2}$.

This proves that $x \in l_{2}$. Moreover, since $\epsilon$ is arbitrarily small, III implies that

$\lim_{n \rightarrow \infty}\rho( x^{(n)} ,x ) = \lim_{n \rightarrow \infty} \sqrt{\Sigma_{k=1}^{\infty} (x_{k}^{(n)}-x_{k})^{2}} = 0$

That is, $\{ x^{(n)}\}$ converges to x in the $l_{2}$ metric space, as asserted.

QED.

Example 6.

Consider the space $C_{[a,b]}^{2}$. To recap: consider the set of all functions continuous on the closed interval $[a,b]$ with the distance metric defined by: $\rho(x,y) = (\int_{a}^{b}|x(t)-y(t)|^{2}dt)^{\frac{1}{2}}$.

It is easy to show that the space $C_{[a,b]}^{2}$ is incomplete. If

$\phi_{n}(t) = -1$, if $-1 \leq t \leq -\frac{1}{n}$

$\phi_{n}(t) = nt$, if $-\frac{1}{n} \leq t \leq \frac{1}{n}$

$\phi_{n}(t) = 1$, if $\frac{1}{n} \leq t \leq 1$

then $\{ \phi_{n}(t)\}$ is a fundamental sequence in $C_{[a,b]}^{2}$ since

$\int_{-1}^{1}(\phi_{n}(t)-\phi_{n^{'}}(t))^{2} dt \leq \frac{2}{\min{ \{ n,n^{'}}\}}$

However, $\{ \phi_{n}(t)\}$ cannot converge to a function in $C_{[-1,1]}^{2}$. In fact, consider the discontinuous function

$\psi(t) = -1$, when $t \leq 0$

$\psi(t) = 1$, when $t \geq 0$.

Then, given any function $f \epsilon C_{[-1,1]}^{2}$, it follows from Schwarz’s inequality (obviously still valid for piecewise continuous functions) that

$(\int_{-1}^{1}(f(t)-\psi(t))^{2}dt)^{\frac{1}{2}} \leq (\int_{-1}^{1}(f(t)-\phi_{n}(t))^{2}dt)^{\frac{1}{2}} + (\int_{-1}^{1}(\phi_{n}(t) - \psi(t))^{2}dt)^{\frac{1}{2}}$

But the integral on the left is non-zero, by the continuity of f, and moreover, it is clear that

$\lim_{n \rightarrow \infty}\int_{-1}^{1}(\phi_{n}(t)-\psi(t))^{2}dt = 0$

Therefore, $\int_{-1}^{1}(f(t)-\phi_{n}(t))^{2}dt$ cannot converge to zero as $n \ rightarrow \infty$.

QED.

7.2 The nested sphere theorem.

A sequence of closed spheres $S[x_{1}, r_{1}], S[x_{2}, r_{2}], \ldots, S[x_{n}, r_{n}], \ldots$

in a metric space R is said to be nested (or decreasing) if

$S[x_{1}, r_{1}] \supset S[x_{2}, r_{2}] \supset \ldots \supset S[x_{n}, r_{n}] \supset \ldots$

Using this concept, we can prove a simple criterion for the completeness of R:

THEOREM 2: The Nested Sphere Theorem:

A metric space R is complete if and only if every nested sequence $\{ S_{n}\} = \{ S_{[x_{n}, r_{n}]}\}$ of closed spheres in R such that $r_{n} \rightarrow 0$ as $n \rightarrow \infty$ has a non empty intersection

$\bigcap_{n=1}^{\infty}S_{n}$.

Proof of the nested theorem:

Part I: Assume that R is complete and that if $\{ S_{n}\} = \{ S[x_{n}, r_{n}] \}$ is any nested sequence of closed spheres in R such that $r_{n} \rightarrow 0$ as $n \rightarrow \infty$, then the sequence $\{ x_{n}\}$ of centres of the spheres is fundamental because

$\rho(x_{n}, x_{n^{'}}) < r_{n}$ for $n^{'}>n$ and $r_{n} \rightarrow 0$ as $n \rightarrow \infty$. Therefore, $\{ x_{n} \}$ has a limit. Let

$x = \lim_{n \rightarrow \infty} x_{n}$.

Then, $x \in \bigcap_{n=1}^{\infty}S_{n}$

Not only that, we can in fact say that $S_{n}$ contains every point of the sequence $\{ x_{n}\}$ except possibly the points $x_{1}, x_{2}, \ldots, x_{n-1}$ and hence, x is a limit point of every sphere $S_{n}$. But, $S_{n}$ is closed, and hence, $x \in S_{n}$ for all n.

Conversely, suppose every nested sequence of closed spheres in R with radii converging to zero has a non empty intersection, and let $\{ x_{n}\}$ be any fundamental sequence in R. Then, x has a limit point in R. To see this, use the fact that $\{x_{n}\}$ is fundamental to choose a term $x_{n_{1}}$ of the sequence $\{ x_{n} \}$ such that

$\rho(x_{n}, x_{n_{1}}) < \frac{1}{2}$ for all $n \geq n_{1}$, and let $S_{1}$ be the closed sphere of radius 1 with centre $x_{n_{1}}$. Then, choose a term $x_{n_{1}}$ of $\{ x_{n}\}$ such that $n_{2} > n_{1}$ and $\rho(x_{n}, x_{n_{1}}) < \frac{1}{2^{2}}$ for all $n > n_{2}$, and let $S_{2}$ be the closed sphere of radius $\frac{1}{2}$ with centre $x_{n_{2}}$.

Continue this construction indefinitely, that is, once having chosen terms $x_{n_{1}}, x_{n_{2}}, \ldots, x_{n_{k}}$ (where $n_{1}), choose a term $x_{n_{k+1}}$ such that $n_{k+1}>n_{k}$ and

$\rho(x_{n}, x_{n_{k+1}}) < \frac{1}{2^{k+1}}$ for all $n \geq n_{k+1}$.

Let $S_{k+1}$ be the closed sphere of radius $\frac{1}{2^{n}}$ with centre $x_{n_{k+1}}$, and so on. This gives a nested sequence $S_{n}$ of closed spheres with radii converging to zero. By hypothesis, these spheres have a non empty intersection, that is, there is a point x in all the spheres. This point is obviously the limit of the sequence $\{ x_{n}\}$. But, if a fundamental sequence contains a subsequence converging to x, then the sequence itself must converge to x (HW quiz). That is,

$\lim_{n \rightarrow \infty}x_{n} =x$.

QED.

7.3 Baire’s theorem:

We know that a subset A of a metric space R is said to be nowhere dense in R if it is dense in no (open) sphere at all, or equivalently, if every sphere $S \subset R$ contains another sphere $S^{'}$ such that $S^{'} \bigcap A = \phi$. (Quiz: check the equivalence).

This concept plays an important role in the following:

THEOREM 3: Baire’s Theorem:

A complete metric space R cannot be represented as the union of a countable number of nowhere dense sets.

Proof of Theorem 3: Baire’s Theorem:

Suppose the contrary. Let $R = \bigcup_{n=1}^{\infty}A_{n}$ ….call this VI.

where every set $A_{n}$ is nowhere dense in R. Let $S_{0} \subset R$ be a closed sphere of radius 1. Since $A_{1}$ is nowhere dense in $S_{0}$, being nowhere dense in R, there is a closed sphere $S_{1}$ of radius less than $\frac{1}{2}$ such that $S_{1} \subset S_{0}$ and $S_{1} \bigcap A_{1} =\phi$. Since $A_{2}$ is nowhere dense in $S_{1}$, being nowhere dense in $S_{0}$, there is a closed sphere $S_{2}$ of radius less than $\frac{1}{3}$ such that $S_{2} \subset S_{1}$ and $S_{2} \bigcap A_{2} = \phi$, and so on. In this way, we get a nested sequence of closed spheres $\{ S_{n}\}$ with radii converging to zero such that

$S_{n} \bigcap A_{n} = \phi$, where $n=1,2,3,\ldots$

By the nested sphere theorem, the intersection $\bigcap_{n=1}^{\infty}S_{n}$ contains a point x. By construction, x cannot belong to any of the sets $A_{n}$, that is,

$x \notin \bigcup_{n=1}^{\infty}A_{n}$

It follows that $R \neq \bigcup_{n=1}^{\infty} A_{n}$ contrary to VI.

Hence, the representation VI is impossible.

QED.

COROLLARY TO Baire’s theorem:

A complete metric space R without isolated points is uncountable.

Proof:

Every single element set $\{ x\}$ is nowhere dense in R.

QED.

7.4 Completion of a metric space:

As we now show, an incomplete metric space can always be enlarged (in an essentially unique way) to give a complete metric space.

DEFINITION 4: Completion of a metric space:

Given a metric space R with closure $[R]$, a complete metric space $R^{*}$ is called a completion of R if $R \subset R^{*}$ and $[R]=R^{*}$, that is, if R is a subset of $R^{*}$ everywhere dense in $R^{*}$.

Example 1.

Clearly, $R^{*}=R$ if R is already complete. (Quiz: homework).

Example 2:

The space of all real numbers is the completion of the space of all rational numbers.

THEOREM 4:

Every metric space R has a completion. This completion is unique to within an isometric mapping carrying every point $x \in R$ into itself.

Proof of Theorem 4:

(The proof is somewhat lengthy but quite straight forward).

First , we prove the uniqueness showing that if $R^{*}$ and $R^{**}$ are two completions of R, then there is a one-to-one mapping $x^{**} = \phi(x^{*})$ onto $R^{**}$ such that $\phi(x)=x$ for all $x \in R$ and

$\rho_{1}(x^{*}, y^{*}) = \rho_{2}(x^{**}, y^{**})$….call this VII.

($y^{**}=\phi(y^{*})$), where $\rho_{1}$ is the distance metric in $R^{*}$ and $\rho_{2}$ the distance metric in $R^{**}$. The required mapping $\phi$ is constructed as follows: Let $x^{*}$ be an arbitrary point of $R^{*}$. Then, by the definition of a completion, there is a sequence $\{ x_{n}\}$ of points of R converging to $x^{*}$. The points of the sequence $\{ x_{n}\}$ also belong to $R^{**}$, where they form a fundamental sequence (quiz: why?). Therefore, $\{ x_{n}\}$ converges to a point $x^{**} \in R^{**}$ since $R^{**}$ is complete. It is clear that $x^{**}$ is independent of the choice of the sequence $\{ x_{n}\}$ converging to the point $x^{*}$ (homework quiz: why?). If we set $\phi(x^{*})=x^{**}$, then $\phi$ is the required mapping. In fact, $\phi(x)=x$ for all $x \in R$, since if $x_{n} \rightarrow x \in R$, then obviously $x = x^{*} \in R^{*}$, $x^{**}=x$. Moreover, suppose $x_{n} \rightarrow x^{*}$, $y_{n} \rightarrow y^{*}$ in $R^{*}$, while $x_{n} \rightarrow x^{**}$, $y_{n} \rightarrow y^{**}$. Then, if $\phi$ is the distance in R,

$\rho_{1}(x^{*},y^{*}) = \lim_{n \rightarrow \infty} \rho(x_{n}, y_{n}) = \lim_{n \rightarrow \infty}(x_{n}, y_{n})$…call this VIII.

While at the same time, $\rho_{2}(x^{**}, y^{**})=\lim_{n \rightarrow \infty}\rho_{2}(x_{n}, y_{n})=\lim_{n \rightarrow \infty}\rho(x_{n}, y_{n})$….call this VIII-A. But VIII and VIII-A imply VII.

We must now prove the existence of a completion of R. Given an arbitrary metric space R, we say that two Cauchy sequences $\{x_{n} \}$ and $\{\overline{x}_{n} \}$ in R are equilvalent and write $\{ x_{n}\} \sim \{ \overline{x}_{n}\}$

if $\lim_{n \rightarrow \infty} \rho(x_{n}, \overline{x}_{n})=0$

As anticipated by the notation and terminology, $\sim$ is reflective, symmetric and transitive, that is, $\sim$ is an equivalence relation. Therefore, the set of all Cauchy sequences of points in the space R can be partitioned into classes of equivalent sequences. Let these classes be the points of a new space $R^{*}$. Then, we define the distance between two arbitrary points $x^{*}, y^{*}$ by the formula

$\rho_{1}(x^{*}, y^{*}) = \lim_{n \rightarrow \infty} \rho(x_{n}, y_{n})$ ….call this IX.

where $\{ x_{n}\}$ is any “representative” of $x^{*}$ (namely, any Cauchy sequence in the class $x^{*}$) and $\{ y_{n}\}$ is any representative of $y^{*}$.

The next step is to verify that IX is indeed a distance metric. That is, also to check that IX exists, independent of the choice of sequence $\{x_{n} \} \in x^{*}$, $\{ y_{n} \} \in y^{*}$, and satisfies the three properties of a distance metric function. Given any $\epsilon >0$, it follows from the triangle inequality in R (this can be proved with a little effort: homework quiz) that

$|\rho(x_{n}, y_{n}) - \rho(x_{n^{'}},y_{n^{'}})| = |\rho(x_{n},y_{n}) -\rho(x_{n^{'}},y_{n}) + \rho(x_{n^{'}},y_{n}) - \rho(x_{n^{'}}, y_{n^{'}})|$

That is, $\leq |\rho(x_{n},y_{n}) -\rho(x_{n^{'}}, y_{n}) | + |\rho(x_{n^{'}}, y_{n}) - \rho(x_{n^{'}}, y_{n^{'}}) |$

that is, $\leq \rho(x_{n}, x_{n^{'}}) + \rho(y_{n}, y_{n^{'}}) \leq \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon$….call this X

for all sufficiently large $n$ and $n^{'}$.

Therefore, the sequence of real numbers $\{ x_{n}\} = \{ \rho(x_{n},y_{n})\}$ is fundamental and hence, has a limit. This limit is independent of the choice of $\{x_{n} \} \in x^{*}$, $\{ y_{n}\} \in y^{*}$. In fact, suppose that

$\{ x_{n}\}, \{ \overline{x}_{n}\} \in x^{*}$, $\{ y_{n}\}, \{ \overline{y}_{n} \in y^{*}$

Then,

$|\rho(x_{n}, y_{n}) - \rho(\overline(x)_{n}, \overline{y}_{n})| \leq \rho(x_{n}, \overline{x}_{n}) + \rho(y_{n}, \overline{y}_{n})$ by a calculation analogous to X. But,

$\lim_{n \rightarrow \infty} \rho(x_{n}, \overline{x}_{n}) = \lim_{n \rightarrow \infty}(y_{n}, \overline{y}_{n})=0$

since $\{ x_{n} \} \sim \{ \overline{x}_{n}\}$ and $\{ y_{n} \} \sim \{ \overline{y}_{n}\}$, and hence,

$\lim_{n \rightarrow \infty} \rho(x_{n}, y_{n}) = \lim_{n \rightarrow \infty} \rho(\overline{x}_{n}, \overline{y}_{n})$.

As for the three properties of a metric, it is obvious that

$\rho_{1}(x^{*}, y^{*}) = \rho_{1}(y^{*}, x^{*})$, and the fact that

$\rho_{1}(x^{*}, y^{*}) =0$ if and only if $x^{*}=y^{*}$ is an immediate consequence of the definition of equivalent Cauchy sequences.

To verify the triangle inequality in $R^{*}$, we start from the triangle inequality:

$\rho(x_{n}, z_{n}) \leq \rho(x_{n}, y_{n}) + \rho(y_{n}, z_{n})$

in the original space R, and then take the limit as $n \rightarrow \infty$, obtaining

$\lim_{n \rightarrow \infty} rho(x_{n}, z_{n}) \leq \lim_{n \rightarrow \infty} \rho(x_{n}, y_{n}+ \lim_{n \rightarrow \infty} \rho(y_{n}, z_{n})$

That is, $\rho_{1}(x^{*}, z^{*}) \leq \rho_{1}(x^{*}, y^{*}) + \rho_{1}(y^{*}, z^{*})$

We now come to the crucial step of showing that $R^{*}$ is a completion of R. Suppose that with every point $x \in R$, we associate the class $x^{*} \in R^{*}$ of all Cauchy sequences converging to x. Let

$x = \lim_{n \rightarrow \infty} x_{n}$, $y = \lim_{n \rightarrow \infty} y_{n}$

Then, clearly $\rho(x,y) = \lim_{n \rightarrow \infty}(x_{n}, y_{n})$

(the above too can be proven with a slight effort: HW quiz); while, on the other hand,

$\rho_{1}(x^{*}, y^{*}) = \lim_{n \rightarrow \infty} \rho(x_{n}, y_{n})$ by definition. Therefore,

$\rho(x,y) = \rho_{1}(x^{*}, y^{*})$ and hence, the mapping of R into $R^{*}$ carrying x into $x^{*}$ is isometric. Accordingly, we need no longer distinguish between the original space R and its image in $R^{*}$, in particular between the two metrics $\rho$ and $\rho_{1}$. In other words, R can be regarded as a subset of $R^{*}$. The theorem will be proved once we succeed in showing that

(i) R is everywhere dense in $R^{*}$, that is, $[R] = R$;

(2) $R^{*}$ is complete.

Towards that end, given any point $x^{*} \in R^{*}$ and any $\epsilon >0$, choose a representative of $x^{*}$, namely a Cauchy sequence $\{ x_{n}\}$ in the class $x^{*}$. Let N be such that $\rho(x_{n}, x_{n^{'}}) < \epsilon$ for all $n, n^{'} >N$. Then,

$\rho(x_{n}, x^{*}) = \lim_{n \rightarrow \infty} \rho(x_{n}, x_{n^{'}}) \leq \epsilon$ if $n >N$, that is, every neighbourhood of the point $x^{*}$ contains a point of R. It follows that $[R] = R$.

Finally, to show that $R^{*}$ is complete, we first note that by the very definition of $R^{*}$, any Cauchy sequence $\{ x_{n}\}$ consisting of points in R converges to some point in $R^{*}$, namely to the point $x^{*} \in R^{*}$ defined by $\{ x_{n}\}$. Moreover, since R is dense in $R^{*}$, given any Cauchy sequence $x_{n}^{*}$ consisting of points in $R^{*}$, we can find an equivalent sequence $\{ x_{n}\}$ consisting of points in R. In fact, we need only choose $x_{n}$ to be any point of R such that $\rho(x_{n}, x_{n}^{*}) < \frac{1}{n}$. The resulting sequence $\{ x_{n}\}$ is fundamental, and, as just shown, converges to a point $x^{*} \in R^{*}$. But, then the sequence $x_{n}^{*}$ also converges to $x^{*}$.

QED.

Example.

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

Regards,

Nalin Pithwa.

Purva building, 5A
Flat 06
Mumbai , Maharastra 400101
India

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

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

(c) $\rho(A,x)=0$ if and only if $x$ is a contact point of 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;

(c) The closure of M is the whole space $C_{[a,b]}$

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

# VI Convergence. Open and Closed Sets.

Reference: Introductory Real Analysis by Kolmogorov and Fomin.

Reference: Introduction to Analysis by Rosenlicht.

Reference: Analysis by Walter Rudin.

Sec 6.1 Closure of a set. Limit points.

By the open sphere (or open ball) $S(x_{0},r)$ in a metric space R we mean the set of points $x \in R$ satisfying the inequality $\rho(x_{0},r)

($\rho$ is the metric of R.)

Note: Any confusion between “sphere” meant in the sense of spherical surface and “sphere” meant in the sense of a solid sphere (or ball) will always be avoided by judicious use of the adjectives “open” or “closed.”

The fixed point $x_{0}$ is called the center of the sphere and the number r is called its radius. By the closed sphere (or closed ball) $S[x_{0},r]$ with center $x_{0}$ and radius r we mean the set of points $x \in R$ satisfying the inequality

$\rho(x_{0},x) \leq r$

An open sphere of radius $\epsilon$ with center $x_{0}$ will also be called an $\epsilon$neighbourhood of $x_{0}$ denoted by $O_{\epsilon}(x_{0})$.

A point $x \in R$ is called a contact point of a set $M \subset R$ if every neighbourhood of x contains at least one point of M. The set of all contact points of a set M is denoted by $[M]$ and is called the closure of M. Obviously, $M \subset [M]$, since every point of M is a contact point of M. By the closure operator in a metric space R, we mean the mapping of R carrying each set $M \subset R$ into its closure $[M]$.

Theorem 1:

The closure operator has the following properties:

1. If $M \subset N$, then $[M] \subset [N]$
2. $[[M]] = [M]$
3. $[M \bigcup N] = [M] \bigcup [N]$
4. $[\phi] = \phi$.

Proof I:

Property I is obvious.

Proof of property 2:

Let $x \in [[M]]$. Then, any given neighbourhood $O_{\epsilon}(x)$ contains a point $x_{1} \in [M]$. Consider the sphere $O_{\epsilon_{1}}(x_{1})$ of radius

$\epsilon_{1} = \epsilon - \rho(x,x_{1})$

PS: It helps to draw an illustrative diagram to understand this proof.

Clearly, $O_{\epsilon_{1}}(x_{1})$ is contained in $O_{\epsilon}(x)$. In fact, if $z \in O_{\epsilon_{1}}(x_{1})$ then $\rho(z,x_{1}) < \epsilon_{1}$ and hence, since $\rho(x,x_{1}) = \epsilon - \epsilon_{1}$, it follows from the triangle inequality that

$\rho(z,x) < \epsilon_{1} + (\epsilon - \epsilon_{1}) = \epsilon$,

That is, $z \in O_{\epsilon}(x)$. Since $x_{1} \in [M]$, there is a point $x_{2} \in M$ in $O_{\epsilon_{1}}(x)$. But then $x_{2} \in O_{\epsilon}(x)$ and hence, $x \in [M]$, since $O_{\epsilon}(x)$ is an arbitrary neighbourhood of x. Therefore, $[[M]] \subset [M]$. But, obviously $[M] \subset [[M]]$ and hence, $[[M]] = [M]$, as required.

Proof of property 3:

Let $x \in [M \bigcup N]$ and suppose $x \notin [M] \bigcup [N]$. Then, $x \notin [M]$ and $x \notin [N]$. But then there exist neighbourhoods $O_{\epsilon_{1}}(x)$ and $O_{\epsilon_{2}}(x)$ such that $O_{\epsilon_{1}}(x)$ contains no points of M while $O_{\epsilon_{1}}(x)$ contains no points of N. It follows that the neighbourhood $O_{\epsilon}(x)$, where $\epsilon=\min (\epsilon_{1}, \epsilon_{2})$, contains no points of either M or N, and hence no points of $M \bigcup N$, contrary to the assumption that $x \in [M \bigcup N]$. Therefore, $x \in [M] \bigcup [N]$, and hence,

$[M \bigcup N] = [M] \bigcup [N]$…call this I

since x is an arbitrary point of $[M \bigcup N]$. On the other hand, since $M \subset M \bigcup N$ and $N \subset M \bigcup N$, it follows that from property (i) that $[M] \subset [M \bigcup N]$ and $[N] \subset [M \bigcup N]$. But then,

$[M] \bigcup [N] \subset [M \bigcup N]$

which together with (i) implies that $[M \bigcup N] = [M] \bigcup [N]$.

Proof of property 4:

We observe that given any $M \subset R$,

$[M] = [M \bigcup \phi] = [M] \bigcup [\phi]$ by property (iii).

It follows that $[\phi] \subset [M]$. But this is possible for arbitrary M only if $[\phi] = \phi$. (Alternatively, the set with no elements can have no contact points!). QED.

Definition:

A point $x \in R$ is called a limit point of a set $M \subset R$ if every neighbourhood of x contains infinitely many points of M. The limit point may or may not belong to M. For example, if M is the set of rational numbers in the interval $[0,1]$, then every point of $[0,1]$, rational or irrational, is a limit point of M. (It is said that the rationals are dense in R; we will discuss this in detail later).

A point x belonging to a set M is called an isolated point of M if there is a (“sufficiently small”) neighbourhood of x containing no points of M other than x itself.

6.2 Convergence and limits.

A sequence of points $\{x_{n}, n \in N \}$ in a metric space R is said to converge to a point $x \in R$ if every neighbourhood $O_{\epsilon}(x)$ of x contains all points $x_{n}$ starting from a certain index (more exactly, if, given any $\epsilon >0$, there is an integer $N_{\epsilon}$ such that $O_{\epsilon}(x)$ contains all points $x_{n}$ with $n > N_{\epsilon}$). The point x is called the limit of the sequence $\{ x_{n}\}$, and we write $x_{n} \rightarrow x$ (as $n \rightarrow \infty$). Clearly, $\{ x_{n}\}$ converges to x if and only if

$\lim_{n \rightarrow \infty} \rho(x,x_{n}) = 0$.

It is an immediate consequence of the definition of a limit of a sequence that

(1) No sequence can have two distinct limits.

(2) If a sequence $\{ x_{n}\}$ converges to a point x, then so does every subsequence of $\{ x_{n}\}$.

(Details are filled in here: I believe it is helpful to write little proofs of little details…I call it playing with small pearls of math…: )

Proof of (1) : Let, if possible, a sequence $\{ x_{n}\}$ have two distinct limit points, namely, $x_{0}$ and $x_{0}^{'}$. Then, there exists a neigbourhood or open ball $O_{\epsilon/2}(x)$ which contains all points of the given sequence after some $N_{0} \in \mathscr{N}$. So also there exists a neighbourhood (again of radius $\epsilon/2$ about $x_{0}^{'}$ such that it contains all points of the given sequence after some natural number $N_{0}^{'} \in \mathscr{N}$.

But, we know that $\rho(x_{0},x_{0}^{'}) \leq \rho(x_{0},x) + \rho(x_{0}^{'},x) \leq \epsilon/2+\epsilon/2=\epsilon$. Which in turn means that the two “distinct limit points” lie in the same open ball. Hence, they cannot be distinct. Hence, a sequence can have only one limit point, and it is unique. QED.

Proof of (2):

Definition of subsequence: Given a sequence $\{ x_{n}\}$, where $n \in \mathscr{N}$, consider a strictly increasing sequence of positive integers (that is, $n_{1}, n_{2}, n_{3}, \ldots$ are positive integers and $n_{1}) : then the sequence $x_{n_{1}}, x_{n_{2}}, x_{n_{3}}, \ldots$ is called a subsequence of the original sequence $\{ x_{n}\}$.

Now, the claim is that: if a given sequence $\{ x_{n}\}$ converges to a limit point, so does every subsequence of the given sequence: —-

So, it is given that $\rho(x_{n},x) < \epsilon$ when $n > N$ for some natural number $N \in \mathscr{N}$. Since $n_{m} \geq m$ ( here m is some dummy variable, some appropriate positive integer) for all positive integers m, we have $\rho(x, x_{n_{m}})<\epsilon$ whenever $m > N$. This means that $\rho(x_{n_{m}},x)<\epsilon$, which is what we wanted to prove. QED.

THEOREM 2:

A necessary and sufficient condition for a point x to be a contact point of a set M is that there exists a sequence $\{ x_{n}\}$ of points of M converging to x.

PROOF 2:

The condition is necessary since if x is a contact point of M, then every neighbourhood $O_{\frac{1}{n}}(x)$ contains at least one point $x_{n} \in M$, and these points form a sequence $\{ x_{n}\}$ converging to M. The sufficiency is obvious. QED.

THEOREM 2′:

A necessary and sufficient condition for a point x to be a limit point of a set M is that there exists a sequence $\{ x_{n}\}$ of distinct points of M converging to x.

Proof 2′:

Clearly, if x is a limit point of M, then the points $x_{n} \in O_{\frac{1}{n}}(x) \bigcap M$ figuring in the proof of Theorem 2 (just above) can be chosen to be distinct. This proves the necessity and the sufficiency is again obvious. QED.

6.3 Dense subsets, Separable spaces:

Let A and B be two subsets of a metric space R. Then, A is said to be dense in B if $[A] \supset B$. In particular, A is said to be everywhere dense (in R) if $[A] = R$. A set A is said to be nowhere dense if it is dense in no (open) sphere at all. (Note; it is w.r.t. to the metric function defined in the space R.) (Famous example: The rationals are dense in $\Re$).

Example 1:

The set of all rational points is dense in the real line $\Re$.

proof 1:

We want to prove that $[Q] \supset \Re$. Clearly, as $Q \subset R$, the set of rationals are dense in rationals themselves. We only need to show that any irrational number is also a limit point of a sequence of rationals. For example, this is crystal clear: consider the sequence of decimal numbers (finitely many decimals) that we get by extracting square root of 2 by long division. The same applies to any other surd or irrational number. Hence, we can always find a rational sequence of numbers converging to an irrational number. Hence, the rationals are dense in the reals. QED.

Example 2:

The set of all points $x = (x_{1}, x_{2}, x_{3}, \ldots, x_{n})$ with rational co-ordinates is dense in each of the spaces $R^{n}$, $R_{0}^{n}$, $R_{1}^{n}$ introduced in the following examples (in earlier blog, and presented here again for handy reference):

2a’) the set of all ordered n-tuples $x=(x_{1}, x_{2}, x_{3}, \ldots, x_{n})$ of real numbers $x_{1}, x_{2}, x_{3}, \ldots, x_{n}$ with distance $\rho(x,y) = \sqrt{\Sigma_{k=1}^{n}(x_{k}-y_{k})^{2}}$ is a metric space denoted by $R^{n}$ and called n-dimensional Euclidean space (or, simply Euclidean n-space).

proof 2a’:

same proof as example 1. QED.

2b) the set of all ordered n-tuples $x=(x_{1}, x_{2}, x_{3}, \ldots, x_{n})$ of real numbers $x_{1}, x_{2}, x_{3}, \ldots, x_{n}$ with distance $\rho_{1}(x,y) = \Sigma_{k=1}^{n}|x_{k}-y_{k}|$ is a metric space denoted by $R_{1}^{n}$.

proof 2b:

same proof as example 1. QED.

2c) The set of all ordered n-tuples $x=(x_{1}, x_{2}, x_{3}, \ldots, x_{n})$ of real numbers $x_{1}, x_{2}, x_{3}, \ldots, x_{n}$ with distance $\rho_{0}(x,y) = \max_{1 \leq k \leq n}|x_{k}-y_{k}|$ is a metric space denoted by $R_{0}^{n}$.

proof 2c:

once again same proof as example 1 with minor differences. QED.

Example 3:

The set of all points $x = (x_{1}, x_{2}, x_{3}, \ldots, x_{k}, \ldots)$ with only finitely many non-zero co-ordinates, each a rational number, is dense in the space $l_{2}$ introduced in earlier blog (and presented here again for handy reference):

Definition of $l_{2}$ metric space: Let $l_{2}$ be the set of all infinite sequences $x = (x_{1}, x_{2}, x_{3}, \ldots, x_{k}, \ldots)$ of real numbers $x_{1}, x_{2}, \ldots, x_{k}, \ldots$ satisfying the convergence condition $\Sigma_{k=1}^{\infty} x_{k}^{2}< \infty$, where distance between points is defined by $\rho(x,y) = \sqrt{\Sigma_{k=1}^{\infty}(x_{k}-y_{k})^{2}}$.

Again, some detailed steps show that the  essence of this proof is also the fact that the rationals are dense in the reals.

Example 4: So, also, similarly, the set of all polynomials with rational coefficients is dense in both spaces $C_{[a,b]}$ and $C_{[a,b]}^{2}$. Let me reproduce the definitions of these spaces: The set $C_{[a,b]}$ of all continuous functions defined on the closed interval $[a,b]$ with distance $\rho(f,g)= \max_{a \leq t \leq b}|f(t)-g(t)|$ is a metric space. The set of all functions continuous on the interval $[a,b]$ with distance function defined by $\rho(x,y) = (\int_{a}^{b}[x(t)-y(t)]^{2}dt)^{\frac{1}{2}}$ is also a metric space denoted by $C_{[a,b]}^{2}$.

Definition:

A metric space is said to be separable if it has a countable everywhere dense subset.

Example 5:

The spaces $\Re^{1}$, $\Re^{n}$, $\Re_{0}^{n}$, $l_{2}$, $C_{[a,b]}$ and $C_{[a,b]}^{2}$ are all separable since the sets in Examples 1 to 4 above are all countable. (this can be easily verified).

Example 6:

The “discrete space” M described in Example 1 (reproduced here again) contains a countable everywhere dense subset and hence is separable if and only it is itself a countable set, since clearly $[M]=M$ in this case. (Put $\rho(x,y)=1$, when $x=y$ and $\rho(x,y)=0$ if $x \neq y$. Then, this space M is called the discrete metric space).

Example 7:

There is no countable everywhere dense set in the space m of all bounded sequences, introduced in an earlier blog ( To help recall, we present it here again: Consider the set of all bounded infinite sequences of real numbers $x = (x_{1}, x_{2}, \ldots, x_{n}, \ldots)$, and let $\rho(x,y) = \sup_{k}|x_{k}-y_{k}|$. This gives a metric space which we denote by m. The fact that it has the three properties of a metric is almost obvious.)

In fact, consider the set E of all sequences consisting exclusively of zeros and ones. Clearly, E has the power of continuum since there is a one-to-one correspondence between E and the set of all subsets of the set $\mathcal{Z_{+}} = \{1,2, \ldots, n, \ldots \}$ (what is the correspondence here? answer:) Now, the distance between any two points of E equals 1. Suppose we surround each point of E by an open sphere of radius $\frac{1}{2}$, thereby obtaining an uncountably infinite family of pairwise disjoint spheres. Then, if some set M is everywhere dense in m, there must be at least one point of M in each of the spheres. It follows that M cannot be countable and hence, that m cannot be separable.

Closed Sets:

We say that a subset M of a metric space R is closed if it coincides with its own closure, that is, if $[M]=M$. In other words, a set is called closed if it contains all its limit points (we will solve this problem as an exercise).

Example 1:

The empty set $\phi$ and the whole space R are closed sets.

Example 2:

Every closed interval $[a,b]$ on the real line is a closed set.

Example 3:

Every closed sphere in a metric space is a closed set. In particular, the set of all functions f in the space $C_{[a,b]}$ such that $|f(t)|\leq K$ (where K is a constant) is closed.

Example 4:

The set of all functions f in $C_{[a,b]}$ such that $|f(t)| (an open sphere) is not closed. The closure of the set is the closed sphere in the preceding example.

Example 5:

Any set consisting of a finite number of points is closed.

Theorem 3:

The intersection of arbitrary number of closed sets is closed. The union of a finite number of closed sets is closed.

Proof 3:

Given arbitrary sets $F_{\alpha}$ indexed by a parameter $\alpha$, let x be a limit point of the intersection $F = \bigcap_{\alpha}F_{\alpha}$

Then, any neighbourhood $O_{\epsilon}(x)$ contains infinitely many points of F, and hence, infinitely many points of each $F_{\alpha}$. Therefore, x is a limit point of each $F_{\alpha}$ and hence belongs to each $F_{\alpha}$, since the sets $F_{\alpha}$ are all closed. It follows that $x \in F_{\alpha}$ and hence that F itself is closed.

Next, let $F = \bigcup_{k=1}^{\infty}F_{k}$ be the union of a finite number of closed sets $F_{k}$, and suppose x does not belong to F. Then, x does not belong to any of the sets $F_{k}$, and hence, x cannot be a limit point of any of them. But then, for every k, there is a neighbourhood $O_{\epsilon_{k}}(x)$ containing no more than a finite number of points of $F_{k}$. Choosing

$\epsilon = \min (\epsilon_{1}, \epsilon_{2}, \ldots, \epsilon_{n})$

we get a neighbourhoood $O_{\epsilon}(x)$ containing no more than a finite number of points of F, so that x cannot be a limit point of F. This proves that a point $x \in F$ cannot be a limit point of F. Therefore, F is closed. QED.

6.5 Open sets.

A point x is called an interior point of a set M if x has a neighbourhood $O_{\epsilon}(x) \subset M$, that is, a neighbourhood consisting entirely of points of M. A set is said to be open if all points are interior points (with respect to that metric).

Example 1:

Every open interval $(a,b)$ on the real line is an open set. In fact, if $a < x < b$, choose $\epsilon = \min(x-a, b-x)$. Then, clearly $O_{\epsilon}(x) \subset (a,b)$.

Example 2:

Every open sphere $S(a,r)$ in a metric space is an open set. In fact, $x \in S(a,r)$ implies that $\rho(a,x). Hence, choosing $\epsilon = r - \rho(a,x)$ we have $O_{\epsilon}(x)=S(x,\epsilon) \subset S(a,r)$.

Example 3:

Let M be the set of of all functions f in $C_{[a,b]}$ such that $f(t) < g(t)$, where g is a fixed function in $C_{[a,b]}$. Then, M is an open subset of $C_{[a,b]}$.

Theorem 4:

A subset M of a metric space R is open if and only its complement $R-M$ is closed.

Proof of theorem 4:

If M is open, then every point $x \in M$ has a neighbourhood (entirely) contained in M. Therefore, no point $x \in M$ can be a contact point of $R - M$. In other words, if x is a contact point of $R-M$ then $x \in R-M$, that is, $R-M$ is closed.

Conversely, if $R-M$ is closed, then any point $x \in M$ must have a neighbourhood contained in M; since, otherwise every neighbourhood of x would contain points of $R-M$, that is, x would be a contact point of $R-M$, not in $R-M$. Therefore, M is open.

QED.

corollary to theorem 4:

The empty set $\phi$ and the whole space R are open sets.

Proof:

An immediate consequence of Theorem 4 and Example 1 in the previous section.

QED.

THEOREM 5:

The union of an arbitrary number of open sets is open. The intersection of a finite number of open sets is open.

Proof of theorem 5:

this is the dual of theorem 3. The proof is an immediate consequence of theorem 4 and DeMorgan laws. QED.

6.6 Open and closed sets on the real line:

The structure of open and closed sets in a given metric space can be quite complicated. This is true even for open and closed sets in a Euclidean space of two or more dimensions. In the one-dimensional case, however, it is an easy matter to give a complete description of all open sets (and, hence, of all closed sets).

Theorem 6:

Every open set G on the real line is the union of a finite or countable system of pairwise  disjoint open intervals.

Proof of theorem 6:

Let x be an arbitrary point of G. By the definition of an open set, there is at least one open interval containing x and contained in G. Let $I_{x}$ be the union of all such open intervals. Then, as we now show,

$I_{x}$ is itself an open interval.

proof:

In fact, let $a = \inf {I_{x}}$ and $b = \sup {I_{x}}$ where we allow the cases $-\infty=a$ and $+\infty=b$.

Then, obviously, $I_{x} \subset (a,b)$….call this II.

Moreover, let us assume that y is an arbitrary point of $(a,b)$ distinct from x, where, to be explicit, we assume that $a. Then, there is a point $y^{'}\in I_{x}$ such that $a < y^{'}. (HW: think, why!) Hence, G contains an open interval containing the points $y^{'}$ and $x$. But, then this interval also contains y, that is, $y \in I_{x}$. (The case $y>x$ is treated similarly. )

Moreover, $x \in I_{x}$, by hypothesis. It hence follows that $I_{x} \supset (a,b)$, and hence, by (II) that $I_{x}=(a,b)$. Thus, $I_{x}$ is itself an open interval, as asserted, in fact the open interval $(a,b)$.

Next, we want to show that $I_{x}$ is a union of countable, pairwise, disjoint open intervals. Let us proceed as follows:

By its very construction, the interval $(a,b)$ is contained in G and is not a subset of a larger interval contained in G. Moreover, it is clear that two intervals $I_{x}$ and $I_{x^{'}}$ corresponding to distinct points x and $x^{'}$ either coincide or else are disjoint (otherwise, $I_{x}$ and $I_{x^{'}}$ would both be contained in a larger interval $I_{x} \bigcup I_{x^{'}} = I \subset G$. There are no more than countably many such pairwise disjoint intervals $I_{x}$. In fact, choosing an arbitrary rational point in each $I_{x}$ we establish a one-to-one correspondence between the intervals $I_{x}$ and a subset of the rational numbers. Finally, it is obvious that

$G = \bigcup_{x}I_{x}$.

QED.

COROLLARY TO PROOF 6:

Every closed set on the real line can be obtained by deleting a finite or countable system of pairwise disjoint intervals from the line.

EXAMPLE 1:

Every closed interval $[a,b]$ is a closed set (here, a and b are necessarily finite).

EXAMPLE 2:

Every single element set $\{ x_{k}\}$ is closed.

EXAMPLE 3:

The union of a finite number of closed intervals and single element sets is a closed set.

EXAMPLE 4 (The CANTOR Set):

A more interesting example of a closed set on the real line can be constructed as follows:

Delete the open interval $(\frac{1}{3},\frac{2}{3})$ from the closed interval $F_{0}=[0,1]$ and let $F_{1}$ denote the remaining closed set, consisting of two closed intervals. Then, delete the open intervals $(\frac{1}{9}, \frac{2}{9})$ and $(\frac{7}{9}, \frac{8}{9})$ from $F_{1}$ and let $F_{2}$ denote the remaining closed set consisting of four closed intervals. Then, delete the “middle third” from each of these four intervals, getting a new closed set $F_{3}$, and so on. Continuing this process indefinitely, we get a sequence of closed sets $F_{n}$ such that

$F_{0} \supset F_{1} \supset F_{2} \supset \ldots \supset F_{n} \supset \ldots$

(such a sequence is said to be decreasing). The intersection

$F = \bigcap_{n=0}^{\infty}F_{n}$

of all these sets is called the CANTOR SET.

Clearly, F is closed, and is obtained from the unit interval $[0,1]$ by deleting a countable number of open intervals. In fact, at the nth stage of construction, we delete $2^{n-1}$ intervals, each of length $\frac{1}{3^{n}}$.

To describe the structure of the set $F_{n}$ we first note that F contains the points, 0,1, $\frac{1}{3}$, $\frac{2}{3}$, $\frac{1}{9}$, $\frac{2}{9}$, $\frac{7}{9}$, $\frac{8}{9}$, $\ldots$,….call this III.

that is, the end points of the deleted intervals (together with the points 0 and 1)

However, F contains many other points.

In fact, given any $x \in [0,1]$, suppose we write x in ternary notation, representing x as a series :

$x=\frac{a_{1}}{3}+\frac{a_{2}}{3^{2}}+\frac{a_{3}}{3^{3}}+\ldots + \frac{a_{n}}{3^{n}}+\ldots$…call this IV.

where each of the numbers $a_{1}, a_{2}, \ldots$ is 0, 1 or 2 in radix-3. Then, it is easy to see that x belongs to F if and only if x has a representation (IV) such that none of the numbers $a_{1}, a_{2}, \ldots, a_{n}, \ldots$ equals 1 (you need to think about this as HW!!)

Remarkably enough, the set F has the power of the continuum, that is, there are as many points in F as in the whole interval $[0,1]$, despite the fact that the sum of the lengths of the deleted intervals equals

$\frac{1}{3} + \frac{2}{3^{2}} + \frac{2^{2}}{3^{3}} + \ldots =1$

To see this, we associate a new point

$y=\frac{b_{1}}{2} + \frac{b_{2}}{2^{2}}+\ldots + \frac{b_{n}}{2^{n}}+\ldots$

with each point IV, where

$b_{n}=0$, if $a_{n}=0$; $b_{n}=1$; if $a_{n}=2$.

In this way, we set up a one-to-one correspondence between F and the whole interval $[0,1]$. It follows that F has the power of the continuum, as asserted. Let $A_{1}$ be the set of points III. Then,

$F = A_{1} \bigcup A_{2}$ where the set $A_{2}=F-A_{1}$ is uncountable, since $A_{1}$ is countable and F itself is not. The points of $A_{1}$ are often called “points of F of the first kind,” while those of $A_{2}$ are called “points of the second kind.”

QED.

# Solutions to System of Sets:

Reference: Introductory Real Analysis, Kolmogorov and Fomin. Dover Publications. Translated and edited by Richard A. Silverman:

Problem 1:

Let X be an uncountable set, and let $\mathscr{R}$ be the ring consisting of all finite subsets of X and their complements. Is $\mathscr{R}$ a $\sigma$-ring?

Solution 1:

Recall the definition: A ring of sets is called $\sigma$-ring if it contains the union $S= \bigcup_{n=1}^{\infty}A_{n}$ whenever it contains the sets $A_{1}, A_{2}, \ldots, A_{n}, \ldots$.

There are countably many finite subsets of X (given uncountable set) and their complements (also especially) so that the union of all these is the whole set X. Hence, X is a $\sigma$-ring as it is closed under countably many set unions. QED.

Problem 2:

Are open intervals Borel sets?

Solution 2:

Recall the following:

(1) Borel sets or B-sets are the subsets of the real line belonging to the minimal B-algebra  generated by the set of all closed intervals $[\alpha, \beta]$.

Problem 3:But a B-algebra is also a ring and is closed under differences/complements. Open intervals are complements of closed intervals. And, they belong hence to B-algebra. Note we still have to answer the question whether open sets are Borel sets and so we have to check if they are contained in a minimal B-algebra. As per the following theorem: Given any non-empty system of sets $\mathscr{S}$, there is a unique irreducible (minimal) B-algebra $\mathscr{B}(\mathscr{P})$ generated by the system $\mathscr{S}$ or the Borel closure of $\mathscr{P}$. So, yes indeed open sets are Borel sets. QED.

Problem 3A:

Let $y=f(x)$ be a function defined on a set M and taking values in a set N. Let $\mathscr{M}$ be a system of subsets of M, and let $f(\mathscr{M})$ denote the system of all images $f(A)$ of sets $A \in \mathscr{M}$. Moreover, let $\mathscr{N}$ be a system of subsets of N, and let $f^{-1}(\mathscr{N})$ denote the system of all preimages $f^{-1}(B)$ of sets $B \in \mathscr{N}$. Prove that:

i) If $\mathscr{N}$ is a ring, so is $f^{-1}(\mathscr{N})$.

ii) If $\mathscr{N}$ is an algebra, so is $f^{-1}(\mathscr{N})$

iii) If $\mathscr{N}$ is a B-algebra, so is $f^{-1}(\mathscr{N})$

iv) $\mathscr{R}(f^{-1}(\mathscr{N})) = f^{-1}(\mathscr{R}(\mathscr{N}))$ where $\mathscr{R}$ stands for a ring.

v) $\mathscr{B}(f^{-1}(\mathscr{N})) = f^{-1}(\mathscr{B}(\mathscr{N}))$ where $\mathscr{B}$ is irreducible or minimum Borel algebra generated by a non-empty system of sets $\mathscr{S}$.

Problem 3B:

Prove the following:

i) If $\mathscr{M}$ is a ring, so is $f(\mathscr{M})$.

ii) If $\mathscr{M}$ is an algebra, so is $f(\mathscr{M})$.

iii) If $\mathscr{M}$ is Borel-algebra, so is $f(\mathscr{M})$.

iv) $\mathscr{R}(f(\mathscr{M}))=f(\mathscr{R}(\mathscr{M}))$

v) $\mathscr{B}(f(M))=f(\mathscr{B}(\mathscr{M}))$ where $\mathscr{B}$ is irreducible minimum Borel algebra generated by a non-empty system of sets $\mathscr{S}$.

Solution 3A:

Part 1: Given mapping $f: M \rightarrow N$, that is, $y=f(x)$, Let $Y_{1}, Y_{2}, Y_{3}, \ldots$ be subsets of N and let $X_{1}, X_{2}, X_{3}, \ldots$ be subsets of M. Then, as it is given that $\mathscr{N}$ is a ring then :

$Y_{1} \bigcap Y_{2} \in \mathscr{N}$

$Y_{1}\bigcup Y_{2} \in \mathscr{N}$

$Y_{1}-Y_{2} \in \mathscr{N}$

$Y_{1} \triangle Y_{2} = (Y_{1}-Y_{2}) \bigcup (Y_{2}-Y_{1}) \in \mathscr{N}$

The above implies:

$f^{-1}(Y_{1}\bigcap Y_{2}) \in f^{-1}(\mathscr{N})$, that is, $f^{-1}(Y_{1}) \bigcap f^{-1}(Y_{2}) \in f^{-1}(\mathscr{N})$, that is, $X_{1} \bigcap X_{2} \in \mathscr{M}$.

Also, $Y_{1} \bigcup Y_{2} \in \mathscr{N}$ so that $f^{-1}(Y_{1} \bigcup Y_{2}) \in f^{-1}(\mathscr{N})$, that is, $f^{-1}(Y_{1}) \bigcup f^{-1}(Y_{2}) \in f^{-1}(\mathscr{N})$, that is, we conclude $X_{1} \bigcup X_{2} \in \mathscr{M}$.

Also, $Y_{1}-Y_{2} \in \mathscr{N}$ as $\mathscr{N}$ is a ring; so that $f^{-1}(Y_{1}-Y_{2}) \in f^{-1}(\mathscr{N})$ so that for some $X_{0}$, which is $f^{-1}(Y_{1}-Y_{0}) \longrightarrow f^{-1}(Y_{1}) - f^{-1}(Y_{0}) \in \mathscr{M}$

So, we have shown that the system of sets $\mathscr{M}$ is closed under set union, set intersection, set difference, and hence, also set symmetric difference. Hence, it is is a ring. QED.

Part ii:

We have already shown that $f^{-1}(\mathscr{N})$ is a ring, now $\mathscr{N}$ is also an algebra meaning a ring of sets with a unit element. Let it contain a unit E $\in \mathscr{N}$ such that if $Y_{0}$ is any set belonging to $\mathscr{N}$, then $Y_{0} \bigcap E = Y_{0}$. so that $f^{-1}(Y_{0} \bigcap E) = f^{-1}(Y_{0})$, hence, $f^{-1}(Y_{0}) \bigcap f^{-1}(E) = f^{-1}(Y_{0})$, which in turn implies that $f^{-1}(E)$ is a unit of $f^{-1}(\mathscr{N})$. Hence, $f^{-1}(\mathscr{N})$ is a ring of sets with a unit element, or in other words, an algebra of sets.

Part iii:

To prove that: if $\mathscr{N}$ is a Borel algebra, so is $f^{-1}(\mathscr{N})$. From parts i and ii above, $f^{-1}(\mathscr{N})$ is a ring with a unit or in other words, $f^{-1}(\mathscr{N})$ is an algebra. Moreover, if it contains $\bigcup_{k=1}^{\infty}Y_{k}$ whenever it contains the sets $Y_{1}, Y_{2}, Y_{3}, \ldots, Y_{n}, \ldots$ all of which are members of $\mathscr{N}$.

But for an arbitrary (finite or infinite) collection of sets:

$f^{-1}(\bigcup_{\alpha}A_{\alpha}) = \bigcup_{\alpha}f^{-1}(A_{\alpha})$

Now, $\bigcup_{k=1}^{\infty}Y_{k} \in \mathscr{N}$

hence $f^{-1}(\bigcup_{k=1}^{\infty}Y_{k}) \in f^{-1}(\mathscr{N})$

Consequently, $\bigcup_{k=1}^{\infty}f^{-1}(Y_{k}) \in f^{-1}(\mathscr{N})$, which in turn implies that $\mathscr{N}$ is a Borel algebra also. QED.

Part iv and part v:

Using parts i and iii above, these can be very easily proved.

Solutions 3b:

i) Prove: If $\mathscr{M}$ is a ring, so is $f(\mathscr{M})$. Note that $f: M \rightarrow N$, $y=f(x)$. Proof (i): As $\mathscr{M}$ is a system of subsets of M. and it is a ring, so if $A_{1} \in \mathscr{M}$, and $A_{2} \in \mathscr{M}$, it implies that $A_{1} \bigcup A_{2} \in \mathscr{M}$; $A_{1} \bigcap A_{2} \in \mathscr{M}$; $(A_{1}-A_{2}) \in \mathscr{M}$. We know that $f(A_{1}\bigcup A_{2}) = f(A_{1}) \bigcup f(A_{2}) \in f(\mathscr{M})$ and $f(A_{1} \bigcap A_{2}) \subset f(A_{1}) \bigcap f(A_{2}) \in f(\mathscr{M})$. And, quite obviously, $f(A_{1}-A_{2}) = f(A_{1}) - f(A_{2}) \in f(\mathscr{M})$ so that it is true that if $\mathscr{M}$ is a ring, then $f(\mathscr{M})$ is also a ring.

ii) Check if it is true or false: if $\mathscr{M}$ is an algebra, so is $f(\mathscr{M})$. Argument: As $\mathscr{M}$ is an algebra, it is already a ring. But additionally, $\mathscr{M}$ contains an element E such that $A_{1} \bigcap E= A_{1}$ (whenever $A_{1} \in \mathscr{M}$ but $f(A_{1} \bigcap E) \subset f(A_{1}) \bigcap f(E) \in f(\mathscr{M})$ but it need not be true that $f(E)$ is a unit element of $f(\mathscr{M})$. So, we can say that in case $\mathscr{M}$ is an algebra, then $f(\mathscr{M})$ may or may not be an algebra. QED.

iii) Check if it is true or false: If $\mathscr{M}$ is a Borel algebra, then so also $f(\mathscr{M})$ is also a Borel algebra. Argument: As in previous case, $f(\mathscr{M})$ may not have a unit element. So, $f(\mathscr{M})$ need not be a Borel algebra. QED.

iv) $\mathscr{R}(f(\mathscr{M})) = f(\mathscr{R}(\mathscr{M}))$. Check if this is true or false. Argument: Let $f(A_{1}) \in f(\mathscr{M})$, $f(A_{2}) \in \mathscr{M}$. By definition of a ring, $f(A_{1}) \bigcup f(A_{2}) \in f(\mathscr{M})$, $f(A_{1}) \bigcap f(A_{2}) \in f(\mathscr{M})$, $f(A_{1}) - f(A_{2}) \in f(\mathscr{M})$, hence we get the following: $f(A_{1} \bigcup A_{2}) \subset f(\mathscr{M})$; $f(A_{1} \bigcap A_{2}) \subset f(A_{1}) \bigcap f(A_{2}) \in f(\mathscr{M})$ and $f(A_{1}-A_{2}) = f(A_{1}) - f(A_{2}) \in f(\mathscr{M})$. This in turn means that $A_{1} \bigcup A_{2} \in \mathscr{M}$, $A_{1} \bigcap A_{2} \in \mathscr{M}$ and $A_{1} - A_{2} \in \mathscr{M}$. Hence, $LHS \subset RHS$. Similarly, we can show that $RHS \subset LHS$. QED.

v) $\mathscr{B}(f(\mathscr(M))) = f(\mathscr{B}(\mathscr{M}))$. Check if this is true or false. (We will discuss this later; meanwhile, if you wish, please try as homework and let me know).

Cheers,

Nalin Pithwa.