VI. Countable sets: My notes.


  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.


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.


Nalin Pithwa.

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

IV. Product of Sets

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

We shall often have occasion to weld together the sets of a given class into a single new set called their product (or their Cartesian product). The ancestor of this concept is the coordinate plane of analytic geometry, that is, a plane equipped with the normal rectangular coordinate axes. We give a brief description of this fundamental idea with a view to paving the way for our discussion of product of sets in general.

First, a few preliminary comments about the real line. We have already used this term several times before without any explanations, and of course what we mean by it is an ordinary geometric line whose points have been identified with — or coordinatized by — the set R of all real numbers. We use the letter R to denote the real line as well as the set of all real numbers, and we often speak of real numbers as if they were points on the real line, and of points on the real line as if they were real numbers. Let no be deceived into thinking that the real line is a simple thing, for its structure is exceedingly intricate. Our present view of it, however, is as naive and uncomplicated as the picture of it. Generally speaking, we assume that the reader is familiar with the simpler properties of the real line — those relating to inequalities (see problems section) and the basic algebraic operations of addition, subtraction, multiplication and division. One of the most significant facts about the real number system is perhaps less well known. This is the so-called least upper bound property. It asserts that every non empty set of real numbers which has an upper bound has a least upper bound. It is an easy consequence of this fact that a non empty set of real numbers which has a lower bound has a greatest lower bound. All these matters are developed rigorously on the basis of a small number of axioms, and detailed treatments can often be found in books on elementary abstract algebra.

To construct the coordinate plane, we now proceed as follows. We take two identical replicas of the real line, which we call the x axis and the y axis, and paste them on a plane at right angles to one another in such a way that they cross at the zero point on each. We know that usual picture. Now, let P be a point in the plane. We project P perpendicularly onto points Px and Py on the axes. If x and y are the coordinates of Px and Py on their respective axes, this process leads us from the point P to the uniquely determined ordered pair (x,y) of real numbers, where x and y are called the x coordinate and y coordinate of the point P. We can reverse the process, and starting with the ordered pair of real numbers, we can recapture the point. This is the manner in which we establish the familiar one-to-one correspondence between points P in the plane and ordered pairs (x,y) of real numbers. In fact, we think of a point in the plane (which is a geometric object) and its corresponding ordered pair of real numbers (which is an algebraic object) as being — to all intents and purposes — identical with one another. The essence of analytic geometry lies in the possibility of this exploiting this identification by using algebraic tools in geometric arguments and giving geometric interpretations to algebraic calculations.

The conventional attidute towards the coordinate plane in analytic geometry is that the geometry is the focus of interest and the algebra of ordered pairs is only a convenient tool. Here, we reverse this point of view. For us, the coordinate plane is defined to be the set of all ordered pairs (x,y) of real number. We can satisfy our desire for visual images by using the usual picture of the plane and by calling such an ordered pair a point, but this geometric lnaguage is more a convenience than a necessity.

Our notation for the coordinate plane is R \times R or R^{2}. This symbolism reflects the idea that the coordinate plane is the result of multiplying together two replicas of the real line R.

It is perhaps necessary to comment on one possible source of misunderstanding. When we speak of R^{2} as a plane, we do so only to establish an intuitive bond with the reader’s previous experience in analytic geometry. Our present attitude is that R^{2} is a pure set and has no structure whatsoever, because no structure has as yet been assigned to it. We remarked earlier (with deliberate vagueness) that a space is a set to which has been added some kind of algebraic or geometric structure. Later, we shall convert the set R^{2} into the space of analytic geometry by defining the distance between any two points (x_{1}, y_{1}) and (w_{2}, y_{2}) to be


This notion of distance endows the set R^{2} with a certain “spatial” character, which we shall recognize by calling the resulting space the Euclidean plane instead of the coordinate plane.

We assume that the reader is fully acquainted with the way in which the set C of all complex numbers can be identified (as a set) with the coordinate plane R^{2}. If z is a complex number, and if z has the standard form x+iy where x and y are real numbers, then we identify z with the ordered pair (x,y) and thus, with an element of R^{2}. The complex numbers, however, are much more than merely a set. They constitute a number system with the operations of addition, multiplication, conjugation, etc. When the coordinate plane R^{2} is thought of as consisting of complex numbers and is enriched by the algebraic structure it acquires in this way, it is called the complex plane. The letter C is used to denote either the set C of all complex numbers or the complex plane. Later, we shall make a space out of the complex plane.

Suppose now that X_{1} and X_{2} are two non empty sets. By analogy with our above discussion, their product X_{1} \times X_{2} is defined by the set of all ordered pairs (x_{1}, x_{2}) where x_{1} is in X_{1} and x_{2} is in X_{2}. In spite of the arbitrary nature of X_{1} and X_{2}, their product can be represented by a picture similar to the XY plane. The term product is applied to this set, and it is thought of as a result of multiplying together the sets X_{1} and X_{2} for the following reason: if X_{1} and X_{2} are finite sets with m and n elements, then clearly X_{1} \times X_{2} has mn elements. If f: X_{1} \rightarrow X_{2} is a mapping with domain X_{1} and range X_{2}, its graph is a subset of X_{1} \times X_{2} which consists of all ordered pairs of the form (x_{1}, f(x_{1})). We observe that this is an appropriate generalization of the concept of a graph of a function as it occurs in elementary mathematics.

This definition of the product of two sets extends easily to the definiion of product of n sets for any positive integer n. If X_{1}, X_{2}, X_{3}, \ldots, X_{n} are n sets where n is any positive integer, then their product X_{1} \times X_{2} \times X_{3} \times \ldots \times X_{n} is the set of all ordered tuples (x_{1}, x_{2}, \ldots, x_{n}) where x_{i} is in the set X_{i} for each subscript i. If the X_{i}‘s are all replicas of a single set X, that is, if

X_{1} = X_{2} = \ldots = X_{n} = X,

then their product is usually denoted by the symbol X^{n}.

These ideas specialize directly to yield the important sets R^{n} and C^{n}. R is just R, the real line; and R^{2} is the coordinate plane; R^{3} is the set of all ordered triples of real numbers — the set which underlies solid analytic geometry, and we assume that the reader is familiar with the manner in which this set arises, through the introduction of a rectangular coordinate system into three dimensional space. We can draw pictures here, just as in the case of the coordinate plane and use geometric language here as much as we please, but it must be understood that the mathematics of this set is the mathematics of ordered set of triples of real numbers and that pictures are merely an aid to the intuition. Once we fully this grasp this point of view, there is no difficulty whatsoever in advancing at once to the study of the set R^{n}, study of n-tuples of real numbers for any positive integer n. It is quite true that when n is greater than 3, it is no longer possible to draw the same kind of intuitively rich pictures, but at worst this is merely an inconvenience. We can and do continue to use suggestive geometric language, so all is not lost. The set C^{n} is defined similarly; it is the set of all ordered n-tuples (z_{1}, z_{2}, \ldots, z_{n}) of complex numbers. Both R^{n} and C^{n} are of fundamental importance in analysis and topology.

We emphasized that for the present the coordinate plane is to be considered merely as a set, but not as a space. Similar remarks apply to R^{n} and C^{n}. In due conrse, we shall impart form and content to each of these sets by suitable definitions. We shall convert them into Euclidean and n-unitary space which underlie and motivate so many developments in pure mathematics, and we shall explore some aspects of their algebraic and topological structures, But, as of now — and this is the point of view we insist on — they do not have any structure at all; they are merely sets.

As the reader doubtless suspects, we need not consider only products of finite classes of sets. The needs of topology compel us to extend these ideas to arbitrary classes of sets.

We defined the product X_{1} \times X_{2} \times \ldots \times X_{n} to be the set of all ordered n-tuples (x_{1}, x_{2}, \ldots, x_{n}) such that x_{i} is in X_{i} for each subscript i. To see how to extend this definition, we reformulate it as follows: We have an nidex set I, consisting of the integers from 1 to n, and corresponding to each index (or subscript) i we have a non-empty set X_{i}. The n-tuple (x_{1}, x_{2}, x_{3}, \ldots, x_{n}) is simply a function (call it x) defined on the index set I, with the restriction that its value x(i)=x_{i} is an element of the set X_{i} for each i in I. Our point of view here is that the function x is completely determined by and is essentially equivalent to the array (x_{1}, x_{2}, x_{3}, \ldots, x_{n}) of its values.

The way is now open for the definition of products in their full generality. Let \{ X_{i}\} be a non-empty class of non-empty sets, indexed by the elements i of an index set I. The sets X_{i} need not be different from one another; indeed, it may happen that they are all identical replicas of a single set, distinguished only different indices. The product of the sets X_{i}, written P_{i \in I}X_{i} is defined to be the set of all functions x defined on I such that x(i) is an element of the set X_{i} for each index i. We call X_{i} the ith coordinate set. When there can be no misunderstanding about the index set, the symbol P_{i \in I}X_{i} is often abbreviated to P_{i}X_{i}. The definition we have just given requires that each coordinate set be non-empty before the product can be formed. It will be useful if we extend this definition slightly by agreeing that if any of the X_{i}‘s are empty, then P_{i}X_{i} is also empty.

This approach to the idea of a product of a class of sets, by means of functions defined on the index set is useful mainly in giving the definition. In practice, it is much more convenient to use the subscript notation x_{i} instead of the function notation x(i). We then interpret the product P_{i}X_{i} as made up of elements x, each of which is specified by the exhibited array \{ x_{i}\} of it values in the respective coordinate sets X_{i}. We call x_{i} the ith coordinate of the element x = \{ x_{i}\}.

The mapping p_{i} of the product P_{i}X_{i} onto its ith coordinate set X_{i} which is defined by p_{i}(x) = x_{i} — that is, the mapping whose value at an arbitrary element of the product is the ith coordinate of that element — is called the projection onto the ith coordinate set. The projection p_{i} selects the ith coordinate of each element in its domain. There is clearly one projection for each element of the index set I, and the set of all projections plays an important role in the general theory of topological spaces.

We will continue with exercises on this topic in a later blog.


Nalin Pithwa

Notes II: Sets and Functions: problems and solutions

Let f: X \rightarrow Y, let A \subseteq X, let B \subseteq Y. Then,

f(A) = \{f(x): x \in A \}

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

I. The main properties of the first set mapping are:

1a) f(\phi) = \phi, f(X) \subseteq Y

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

1c) f(\bigcup_{i}A_{i}) = \bigcup_{i}f(A_{i})

1d) f(\bigcup_{i}A_{i}) \subseteq \bigcap_{i} f(A_{i})

Answer I:

1a: obvious by definition of f(A) or f.

1b: obvious by definition of f

1c: Let x_{0} \in \bigcup_{i}A_{i} so that for some one i we have f(x) \in f(A_{i}). That is, f(\bigcup_{i}A_{i}) \subseteq \bigcup_{i}f(A_{i}). Reversing the arguments, we get the other subset relation. So that f(\bigcup_{i}A_{i}) = \bigcup_{i}f(A_{i}). The image of the union is the union of images.

1d: Let x_{0} \in \bigcap_{i}A_{i} so that x_{0} belongs to each A_{i}. So that LHS is clearly a subset of \bigcap_{i}f(A_{i}).

II) Now, we want to verify the following useful/famous relations of the second set mapping:

2a) f^{-1}{(\phi)} = \phi, f^{-1}(Y) = X

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

2c) f^{-1}(\bigcup_{i}B_{i}) = \bigcup_{i}f^{-1}(B_{i})

2d) f^{-1}(\bigcap_{i}B_{i}) = \bigcap_{i}f^{-1}(B_{i})

2e) f^{-1}(B^{'}) = f^{-1}(B)^{'}

Answer 2a: obvious from definition.

Answer 2b: obvious from definition.

Answer 2c: Let y_{0} belong to at least one B_{i} so that x_{0} = f^{-1}(y_{0}) = f^{-1}(B_{i}) for some i. In other words, f^{-1}(\bigcup_{i}B_{i}) = \bigcup_{i}f^{-1}(B_{i})

Answer 2d:

TPT: f^{-1}(B^{'}) = f^{-1}(B)^{'}.

Let y_{0} \in f^{-1}(B^{'}).

Hence, f(y_{0}) \in B^{'}.

Hence, f(y_{0}) \in U-B, where U is the universal set

Hence, f(y_{0}) \in U-f(A)

Hence, f(y_{0}) \in U-B

Hence, f(y_{0}) \in U-f(A)

Hence, f(y_{0}) \in (f(A))^{'}

Hence, y_{0} \in f^{-1}(B)^{'}. Hence, f^{-1}(B^{'}) \subseteq f^{-1}(B)^{'}

Reversing the arguments proves the other subset inequality.

Hence, f^{-1}(B^{'}) = f^{-1}(B)^{'}. QED.

More Problems :

A) Two mappings f: X \rightarrow Y and g: X \rightarrow Y are said to be equal (and we write them as f=g) if f(x) = g(x) for every x in X. Let f, g, and h be any three mappings of a non-empty set X into itself, and now prove that the multiplication of mappings is associative in the sense that (fg)h = f(gh).

Solution A:

Let f: X \rightarrow X, g: X \rightarrow X, and h: X \rightarrow X be any three mappings of X into itself. Let x_{0} \in X and let h(x_{0}) = x_{1} \in X. Now, we know that ((fg)h)(x)= (fg)(h(x)). So that now we want to find (fg)(x_{1}) = f(g(x_{1})) = f(x_{2}) assuming g(x_{1}) \in x_{2} \in X.

Now, on the other hand, (f(gh))(x) means (f)((gh)(x)) = f(g(h(x_{0})) = f(g(x_{1}))=f(x_{2}) just as in LHS. QED.

B) Let X be a non-empty set. The identity mapping i_{X} on X is the mapping of X onto itlsef defined by i_{X}(x)=x for every x. Then, i_{X} sends each element of the set X to itself; that is, leaves fixed each element of X. Prove that fi_{X}= i_{X}f=f for any mapping f of X into itself. If f is one-to-one onto, so that its inverse f^{-1} exists, show that ff^{-1} = f^{-1}f=i_{X}. Prove further that f^{-1} is the only mapping of X into itself which has this property; that is, show that if g is a mapping of X into itself such that fg=gf=i_{X}, then g=f^{-1}. Hint: g=gi_{X}=g(ff^{-1})=(gf)f^{-1} = i_{X}f^{-1}=f^{-1}, or

g=i_{X}g=(f^{-1}f)g=f^{-1}(fg) = f^{-1}i_{X}=f^{-1}

B(i) TPT: fi_{X}=i_{X}f=f for any mapping f of X into itself. Proof: Consider x_{0}\in X and such that f(x_{0}) = x_{1}. Hence, fi_{X}(x_{0}) = f(i_{X}(x_{0}))=f(x_{0}) = x_{1} \in X = f(x_{0}). Now, on the other (i_{X}f)(x_{0}) = i_{X}(f(x_{0}))=i_{X}(x_{1})= x_{1} also. QED.

B(ii): Let f be one-to-one onto such that f: X \rightarrow X. Hence, f^{-1} exists. Also, f^{-1}: X \rightarrow X. Let f(x_{0}) = x_{1} \in X. Hence, by definition and because f^{-1} is also one-to-one and onto, f^{-1}(x_{1})=x_{0}. Hence, clearly, ff^{-1} = f^{-1}f=i_{X}. QED.

B(iii) : Prove that such a f^{-1} is unique.

Solution to B(iii): Let there be another function g such that gf=fg=i_{X}. Also, we have ff^{-1}=f^{-1}f=i_{X}. Use the hint ! ๐Ÿ™‚ QED.

Question C:

Let X and Y be non-empty sets and f a mapping of X into Y. Prove the following: (i) f is one-to-one if and only if there exists a mapping g of Y into X such that gf=i_{X} (ii) f is onto if and only if there exists a mapping h of Y into X such that fh=i_{X}.

Solution C(i) : Given f: X \rightarrow Y such that if x_{0} \neq x_{1}, then f(x_{0}) \neq f(x_{1}). Now, we want a mapping g: Y \rightarrow X such that gf=i_{X}. Let us construct a g such that g(y_{0})=x_{0} and g(y_{1}) = x_{1}. Then, (gf)(x_{0}) = g(f(x_{0}))=g(y_{0})=x_{0}. Similarly, gf(x_{1})=x_{1}. Here, we have assumed that f(x_{0})=y_{0} and f(x_{1})=y_{1}. So, knowing f to be one-to-one, we can explicitly construct a mapping g such that g: Y \rightarrow X and gf=i_{X}. QED. On the other hand, let it be given that X and Y are two non-empty sets, that f: X \rightarrow Y and g: Y \rightarrow X such that gf=i_{X}. That is, if some x^{'} \in X, then we have (gf)(x^{'}) = i_{X}(x^{'})=x^{'}. That is, g(f(x^{'})) = x^{'}. This forces, if f(x^{'}) = y^{'}, then g(y^{'})=x^{'}. Now, if there be an element x^{''} \neq x^{'}, it will force f(x^{''})=y^{''} \neq x^{'}. Hence, different inputs give rise to different outputs and so f is one-to-one. QED.

Solution C(ii) : Given f: X \rightarrow Y and f is onto, that is, f(X) = Y. We want to show a function h: Y \rightarrow X such that fh=i_{X}. Since f(X)=Y, with X as domain, Y as codomain equal to range, f is one-to-one, onto. So h=f^{-1}. QED.

Question D:

Let X be a non-empty set and f a mapping of X into itself. Show f is one-to-one onto if and only there exists a mapping g of X into itself such that gf=fg=i_{X}. If there exists a mapping g with the property, then there is one and only one such mapping. Why?

Solution D: From previous question, C we are done.

Question E:

Let X be a non-empty set, and let f and g be one-to-one mappings of X onto itself. Show that fg is also a one-to-one mapping of X onto itself and that (fg)^{-1}=g^{-1}f^{-1}.

HW. Hint: consider the action of the functions on each element.

Question F:

Let X and Y be non-empty sets and f a mapping of X into Y. If A and B are, respectively, subsets of X and Y, prove the following:

(a) ff^{-1}(B) \subseteq B, and ff^{-1}(B)=B is true for all B if and only if f is onto.

(b) A \subseteq f^{-1}f(A), and A = f^{-1}f(A) is true for all A if and only if f is one-to-one.

(c) f(A_{1} \bigcap A_{2}) = f(A_{1}) \bigcap f(A_{2}) is true for all A_{1} and A_{2} if and only if f is one-to-one.

(d) f(A)^{'} \subseteq f(A^{'}) is true for all A if and only if f is onto.

(e) If f is onto — so that, f(A)^{'} \subseteq f(A^{'}) is true for all A — then, f(A)^{'}=f(A^{'}) is true for all A if and only if f is also one-to-one.

Solution Fa: Put B=Y, so that f is onto. To prove the other subset relationship, simply reverse the arguments.

Solution Fb:

We need to apply the definition that different inputs give rise to different outputs.


๐Ÿ˜ฆ I hope to blog later)


Solution Fc:

It certainly implies that A_{1} \bigcap A_{2} \neq \phi.


(I hope to blog later).

Solution Fd:

Given that f: X \rightarrow Y and A \subseteq X and B \subseteq Y. Then, f(A)^{'} is Y-f(A), that is, Y-B, that is B^{'}, that is, f(B^{'}). Put A=X, then f is onto. Now, f(X)^{'} \subseteq f(X^{'}), that is, Y-f(X) \subseteq f(\phi). This implies Y=f(X). To prove the other subset relationship, simply reverse the arguments. QED.


Nalin Pithwa.

What is Topology about? Hocking and Young’s views

Reference: Topology by Hocking and Young, Dover Publications Inc., NY.

Topology may be considered as an abstract study of the limit point concept. As such, it stems in part from a recognition of the fact that many important mathematical topics depend entirely upon the properties of limit points. The very definition of a continuous function is an example of this dependence. Another example is the meaning of the connectedness of a geometric figure. To exaggerate, one might view topology as the complement of modern algebra in that together they cover the two fundamental types of operations found in mathematics.

In applying the unifying principle of abstraction, we study concrete examples and try to isolate the basic properties upon which the interesting phenomena depend. In the final analysis, of course, the determination of the “correct” properties to be abstracted is largely an experimental process. For instance, although the limit of a sequence of real numbers is a widely used idea, experience has shown that a more basic concept if that of a limit point of a set of real numbers.


The real number p is a limit point of a set X of real numbers provided that for every positive number \epsilon, there is an element x of the set X such that 0 < |p-x|< \epsilon.

As an example, let X consists of all real numbers of the two forms \frac{1}{n} and \frac{n-1}{n}, where n is an integer greater than 2. Then, 0 and 1 are the only limit points of X. Thus, the limit point of a set need not belong to the set. On the other hand, every real number is a limit point of the set of all rational numbers, indicating that a set may have limit points belonging to itself.

Some terminology is needed before we pursue this abstraction further. Let S be any set of elements. These may be such mathematical entities as points in the Euclidean plane, curves in a given class, infinite sequences of real numbers, elements of an algebraic group, etc., but in general, we take S to be an abstract undefined set. To reflect the geometric content of topology, we refer to the elements of S by the generic name point. We may now name our fundamental structure.


The set S hasย  a topology (or is topologized) provided that, for every point p in S and every subset X of S, the question, “Is p a limit point of X?” can be answered.

This definition is extremely generally as to be almost useless in practice. There is nothing in it to impose certain desirable properties upon the limit point relation (to be discussed in detail later in the text), and also nothing in it indicates whereby the pertinent question can be answered. An economical method of accomplishing the latter is to adopt some rule or test whose application will answer the question in every case. For the set of real numbers, Definition 1-1 serves this purpose and hence, defines a topology for the real numbers. [The use of the word topology here differs from its use as the name of a subject. Loosely speaking, topology (the subject) is the study of topologies. (as in definition 1-2)].

A set S may be assigned different topologies but there are two extremes. For the first, we always answer the question in Definition 1-2 in the affirmative; that is, every point is a limit point of every subset. This yields a worthless topology: there are simply too many limit points!! For the other extreme, we assume that the answer is always “no,” that is, no point is a limit point of any set. The resulting topology is calledย the discrete topology for S.ย The very fact that it is dignified with a name would indicate that this extreme is not quite so useless as the first.

Those factors that dictate the choice of a topology for a given set S should become more apparent as we progress. In many cases, a “natural” topology exists, a topology agreeing with our intuitive idea of what a limit point should be. Definition 1-1 furnishes such a topology for the real numbers, for instance. In general, however, we require only a structure within the set S which will define limit point in a simple manner and in such a way that certain basic relations concerning limit points are maintained. To illustrate this latter requirement, it is intuitively evident that if p is a limit point of a subset X and X is contained in another subset Y, then we would want p to be also a limit point of Y. There are many such structures one may impose upon a set and we will develop the more commonly used topologies (in this chapter in the text). Before doing this, however, we continue our preliminary discussion with a few general remarks upon the aims and tools of topology.

The study of topologized sets (or any other abstract system) involves two broad and interrelated questions. The first of these concerns the investigation and classification of the various concrete realizations, or models, which we may encounter. This entails the recognition of equivalent model, as is done for isomorphic groups or congruent geometric figures, for example. In turn, this equivalence of models is usually defined in terms of a reversible transformation of one model onto another. This equivalence transformation is so chosen as to leave invariant the fundamental properties of the models. As examples, we have the rigid motions in geometry, the isomorphisms in group theory, etc.

One of the first to perceive the importance of these underlying transformations was Felix Klein. In his famous Erlanger Program (1870), he characterized the various geometries in terms of these basic transformations. For instance, we may define the Euclidean geometry as the study of those properties of geometric figures that are invariant under the group of rigid motions. (For example, Dihedral groups).

The second broad question in studying an abstract system such as our topologized sets involves consideration of transformations more general than the one-to-one equivalence transformations. The requirement that the transformation be one-to-one and reversible is dropped and we retain only the requirement that the basic structure is to be preserved. The homomorphisms in group theory illustrate this situation. In topology, the corresponding transformations are those that preserve limit points. Such a transformation is said to be continuous and is a true generalization of the continuous functions used in analysis. It follows that the second aspect of topology finds many applications in function theory.


Nalin Pithwa.

What is Topology about? A nice accessible beginning viewpoint

Reference: Intuitive Concepts in Elementary Topology by B H Arnold, Dover Publications, Inc. NY.ย 

What is Topology?

It is surprising that a fairly satisfactory description of topology can be obtained by changing “geometry” to “topology” , “geometric” to “topological” .

Let us back track a bit —- Euclidean geometry is the study of certain properties of figures in a plane or in space. Not all properties of a figure are of interest — only the geometric properties. For example, the colour of a triangle is not its geometric properties. But length of sides of a triangles, the measures of its angles, its area are certainly geometric properties. So, which properties are geometric ? Answer: Two figures are said to be congruent if and only if one of them can be placed upon the other so that the two figures exactly coincide.

In the above definition of congruence: the emphasis is on the phrase “can be placed upon.” Let us examine the phrase more closely. How do we “place” a figure? How can we move it? What are we allowed to do to it on the way? In geometry, the movements we are allowed are the rigid motions, (translations, rotations, and reflections) in which the distance between any two points of the figure is not changed. Thus, the geometric properties are those that are invariant under rigid motions.

In topology, the movements we are allowed might be called the elastic motions. We imagine that our figures are made of perfectly elastic rubber and in moving a figure, we can stretch, twist, pull and bend it at pleasure. We are even allowed to cut such a rubber figure and tie in a knot, provided that we later sew up the cut exactly as it was before; that is, so that points which were close together before we cut the figure are close together after the cut is sewed up. However, we must be careful that distinct points in a figure remain distinct; we are not allowed to force the two different points to coalesce into just one point. Two figures are said to be topologically equivalent if one figure can be made to coincide with the other by an elastic motion. The topological properties of a figure are those which are also enjoyed by all topologically equivalent figures. Thus, to a topologist, a coffee cup and a dough nut are the same ! ๐Ÿ™‚

Certainly, any topological property of a figure is also a geometric property of that figure, but many geometric properties are not topological properties. The topological properties of a figure can be only the most basic and fundamental of its geometric properties. In topology, when we do elastic transformations, the properties of the figures based on “metric” are lost. That is, lengths, areas, measures of angles are not preserved. So what is preserved? Let us leave this question for some time and play with our elementary view of topology as rubber sheet geometry.

In fact, it might first appear at first glance that no property is a topological one — that, any property of a figure could be changed by an elastic motion ! ๐Ÿ™‚ Fortunately, this is not the case. For instance, a circle C divides the points of a plane into 3 sets — the points inside the circle, the points on the circle and the points outside the circle. Try to visualize this…squeeze…smash the circle…whatever is in the interior will still be in the interior, whatever is on the circle will still be on the circle and whatever is outside it will remain outside it ! ๐Ÿ™‚ So, this is a topological property of a circle ! ๐Ÿ™‚


Nalin Pithwa


What is Topology about? Paul Alexandroff’s view(s)

Reference: Elementary Concept of Topology by Paul Alexandroff (Translated by Alan E. Farley). Dover Publications, Inc. NY.

Prof. David Hilbert’s views via the preface to this little booklet: (June 1962, Gottingen).

Few branches of geometry have developed so rapidly and successfully in recent times as topology, and rarely has an initially unpromising branch of a theory turned out to be of such fundamental importance for such a great range of completely different fields as topology. Indeed, today in nearly all branches of analysis and in its far reaching applications, topological methods are used and topological questions asked.

Such a wide range of applications naturally requires that the conceptual structure be of such precision that the common core of the supeficially different questions may be recognized. It is not surprising that such an analysis of fundamental geometrical concepts must rob them to a large extent of their immediate intuitiveness —- so much the more, when in the application to other fields, as in the geometry of our surrounding space, an extension to arbitrary dimensions becomes necessary.

While I have attempted in my Anschauliche Geometrie to consider spatial perception, here it will be shown how many of these concepts may be extended and sharpened and thus, how the foundation may be given for a new, self-contained theory of a much extended concept of space. Nevertheless, the fact that again and again vital intuition has been the driving force, even in the case of all of these theories, forms a glowing example of the harmony between intuition and thought.

Thus, the following book is to be greeted as a welcome complement to my Anschauliche Geometrie on the side of topological systematization; may it win new friends for the science of geometry.


I. The specific attraction and in a large part the significance of topology lies in the fact that its most important questions and theorems have an immediate intuitive content and thus teach us in a direct way about space, which appears as the place in which continuous processes occur. As confirmation of this view, I would like to begin by adding a few examples to the many known ones:

i) One need only think of the simplest fixed-point theorem or of the well-known topological properties of closed surfaces such as are described, for instance, in Hilbert and Cohn-Vossen’s Anschauliche Geometrie, chapter 6. Published in English under the title Geometry and the Imagination.

2)ย The Jordan Curve Theorem:

A simple closed curve (that is, the topological image of a circle) lying in the plane divides the plane into precisely two regions and forms their common boundary.

3.ย The question which naturally arises now is:ย What can one say about a closed Jordan curve theorem in three-dimensional space?

The decomposition of the plane by this closed curve amounts to the fact that there are pairs of points which have the property that every polygonal path which connects them (or, which is “bounded” by them) necessarily has points in common with the curve. Such pairs of points are said to be separated by the curve or “linked” with it.

In three-dimensional space, there are certainly no pairs of points which are separated by our Jordan curve, but there are closed polygons which are linked with it in the natural sense that every piece of surface which is bounded by the polygon necessarily has points in common with the curve. Here the portion of the surface spanned by the polygon need not be simply connected but may be chosen entirely arbitrarily.

The Jordan curve theorem may also be generalized in another way for three-dimensional space : in space, there are not only closed curves, but also closed surfaces, and every such surface divides the space into two regions —- exactly as a closed curve did in the plane.

Supported by analogy, the reader can probably imagine what the relationships are in four-dimensional space: for every closed curve, there exists a closed surface linked with it; for every closed three-dimensional manifold a pair of points linked with it. These are special cases of the Alexander duality theorem.

((PS: In one dimension, a manifold may be a straight line, in two dimensions a plane, or the surface of a cube, a balloon, or a doughnut. The defining feature of a manifold is that, from the vantage point of any spot on such an object, the immediate vicinity looks like perfectly regular and normal Euclidean space. Think of yourself shrunk to the size of a pinpoint, sitting on the surface of a doughnut. Look around you, and it seems that you’re sitting on a flat disk. Go down one dimension and sit on a curve, and the stretch nearby looks like a straight line. Should you be perched on a three-dimensional manifold, however esoteric, your immediate neighborhood would look like the interior of a ball. In other words, how the object appears from afar may be quite different from the ,way it appears to your nearsighted eye.

By 1950, topologists were having a field day with manifolds, redefining every object in sight topologically. The diversity and sheer number of manifolds is such that today, although all two-dimensional objects have been defined topologically, not all three- and four-dimensional objects-of which there is literally an infinite assortment- have been so precisely described. Manifolds turn up in a wide variety of physical problems, including some in cosmology, where they are often very hard to cope with. The notoriously difficult three-body problem proposed by King Oskar II of Sweden and Norway in 1885 for a mathematical competition in which Poincar6 took part, which entails predicting the orbits of any three heavenly bodies–such as the sun, moon, and earth-is one in which manifolds figure largely.

This has been a Clay Millennium Problem and has been resolved by Grigory Perelman.))

4.ย Perhaps, the above examples leave the reader with the impression that in topology nothing at all but obvious things are proved !! ๐Ÿ˜ฆย 

This impression will fade quickly as we go on. However, be that as it may, even these “obvious” things are to be taken much more seriously : one can easily give examples of propositions which sound as “obvious” as the Jordan curve theorem, but which may be proved false. Who would believe, for example, that in a plane there are three (four, firve….in fact, infinitely many!) simply connected bounded regions which all have the same boundary; or that one can find in three-dimensional space a simple Jordan arc (that is, a topological image of a polygonal line) such that there are circles outside of this arc that cannot possibly be contracted to a point without meeting it ? There are also closed surfaces of genus zero which possess an analogous property. In other words, one can construct a topological image of a sphere and an ordinary circle in its interior in such a way that the circle may not be contracted to a point wholly inside the surface.

5.ย All of these phenomena were wholly unsuspected at the beginning of the 20th century; the development of set theoretic methodsย  in topology first led to their discovery and; consequently, to a substantial extension of our idea of space. However, let me at once issue the emphatic warning that the most important problems of set theoretic topology are in no way confined to the exhibition of, so to speak, “pathological” geometrical structures; on the contrary, they are concerned with something quite positive. I would formulate the basic problem of set theoretic topology as follows:

To determine which set theoretic structures have a connection with the intuitively given material of elementary polyhedral topology and hence, deserve to be considered as geometrical figures —even if very general ones.

Obviously implicit in the formulation of this question is the problem of a systematic investigation of structures of the required type, particularly with reference to those of their properties which actually enable us to recognize the above mentioned connection and so bring about the geometrization of the most general set theoretic topological concepts.

PS: The purpose of sharing or blogging this is just to revise it for myself and hopefully, some readers will also benefit. In particular, these are my own study notes. Especially, Prof Paul Halmos used to say “I write what I talk to myself. I think by writing”…


Nalin Pithwa.