# 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

# Dihedral groups explained by I N Herstein

Reference: Abstract Algebra, Third Edition, I N Herstein

First consider the following: Let S be the plane, that is, $S= \{ (x,y): x, y \in R\}$ and consider $f, g \in A(S)$ defined by $f(x,y)=(-x,y)$ and $g(x,y)=(-y,x)$; f is the reflection about the y-axis and g is the rotation through 90 degrees in a counterclockwise direction about the origin. We then define $G = \{ f^{i}g^{j}: i=0,1; j=0,1,2,3\}$, and let * in G be the product of elements in A(S). Clearly, $f^{2}=g^{4}=$ identity mapping;

$(f*g)(x,y)=(fg)(x,y)=f(g(x,y))=f(-y,x)=(y,x)$ and $(g*f)(x,y)=g(f(x,y))=g(-x,y)=(-y,-x)$

So $g*f=f*g$.

It is a good exercise to verify that $g*f=f*g^{-1}$ and G is a non-abelian group of order 8. This group is called the dihedral group of order 8. [Try to find a formula for $(f^{i}g^{j})*(f^{s}g^{t})=f^{a}g^{b}$ that expresses a, b in terms of i, j, s and t.

II) Let S be as in above example and f the mapping in above example. Let $n>2$ and let h be the rotation of the plane about the origin through an angle of $2\pi/n$ in the counterclockwise direction. We then define $G=\{ f^{k}h^{j}: k=0,1 ; j=0,1,2, \ldots, n-1\}$ and define the product * in G via the usual product of mappings. One can verify that $f^{2}=h^{n}=$ identity mapping and $fh=h^{-1}f$. These relations allow us to show that (with some effort) G is a non-abelian group of order 2n. G is called the dihedral group of order 2n.

More later,

Nalin Pithwa

# Equivalence relations and partitions: some core basic theorems

Suppose R is an equivalence relation on a set S. For each a in S, let [a] denote the set of elements of S to which a is related under R, that is, $[a] = \{ x: (a,x) \in R\}$

We call [a] the equivalence class of a in S under R. The collection of all such equivalence classes is denoted by S/R, that is, $S/R = \{ [a]: a \in S\}$. It is called the quotient set of S by R.

The fundamental property of an equivalence relation and its quotient set is contained in the following theorem:

Theorem I:

Let R be an equivalence relation on a set S. Then, the quotient set S/R is a partition of S. Specifically,

(i) For each $a \in S$, we have $a \in [a]$.

(ii) $[a]=[b]$ if and only if $(a,b) \in R$.

(iii) If $[a] \neq [b]$, then [a] and [b] are disjoint.

Proof of (i):

Since R is reflexive, $(a,a) \in R$ for every $a \in S$ and therefore $a \in [a]$.

Proof of (ii):

Assume: $(a,b) \in R$.

we want to show that $[a] = [b]$. That is, we got to prove, (i) $[b] \subseteq [a]$ and (ii) $[a] \subseteq [b]$.

Let $x \in [b]$; then, $(b,x) \in R$. But, by hypothesis $(a,b) \in R$ and so, by transitivity, $(a,x) \in R$. Accordingly, $x \in [a]$. Thus, $[b] \subseteq [a]$.

To prove that $[a] \subseteq [b]$, we observe that $(a,b) \in R$ implies, by symmetry, that $(b,a) \in R$. Then, by a similar argument, we obtain $[a] \subseteq [b]$. Consequently, $[a]=[b]$.

Now, assume $[a] = [b]$.

Then by part (i) of this proof that for each $a \in S$, we have $a \in [a]$. So, also, here $b \in [b]=[a]$; hence, $(a,b) \in R$.

Proof of (iii):

Here, we prove the equivalent contrapositive of the statement (iii), that is:

If $[a] \bigcap [b] \neq \emptyset$ then $[a] = [b]$.

if $[a] \bigcap [b] \neq \emptyset$ then there exists an element $x \in A$ with $x \in [a] \bigcap [b]$. Hence, $(a,x) \in R$ and $(b,x) \in R$. By symmetry, $(x,b) \in R$, and, by transitivity, $(a,b) \in R$. Consequently, by proof (ii), $[a] = [b]$.

The converse of the above theorem is also true. That is,

Theorem II:

Suppose $P = \{ A_{i}\}$ is a partition of set S. Then, there is an equivalence relation $\sim$ on S such that the set $S/\sim$ of equivalence classes is the same as the partition $P = \{ A_{i}\}$.

Specifically, for $a, b \in S$, the equivalence $\sim$ in Theorem I is defined by $a \sim b$ if a and b belong to the same cell in P.

Thus, we see that there is a one-one correspondence between the equivalence relations on a set S and the partitions of S.

Proof of Theorem II:

Let $a, b \in S$, define $a \sim b$ if a and b belong to the same cell $A_{k}$ in P. We need to show that $\sim$ is reflexive, symmetric and transitive.

(i) Let $a \in S$. Since P is a partition there exists some $A_{k}$ in P such that $a \in A_{k}$. Hence, $a \sim a$. Thus, $\sim$ is reflexive.

(ii) Symmetry follows from the fact that if $a, b \in A_{k}$, then $b, a \in A_{k}$.

(iii) Suppose $a \sim b$ and $b \sim c$. Then, $a, b \in A_{i}$ and $b, c \in A_{j}$. Therefore, $b \in A_{i} \bigcap A_{j}$. Since P is a partition, $A_{i} = A_{j}$. Thus, $a, c \in A_{i}$ and so $a \sim c$. Thus, $\sim$ is transitive.

Accordingly, $\sim$ is an equivalence relation on S.

Furthermore,

$[a] = \{ x: a \sim x\}$.

Thus, the equivalence classes under $\sim$ are the same as the cells in the partition P.

More later,

Nalin Pithwa.

# Some foundation mathematics

Well-Ordering Principle:

Every non-empty set S of non-negative integers contains a least element; that is, there is some integer a in S such that $a \leq b$ for all b’s belonging to S.

Because this principle plays a role in many proofs related to foundations of mathematics, let us use it to show that the set of positive integers has what is known as the Archimedean property.

Archimedean property:

If a and b are any positive integers, then there exists a positive integer n such that $na \geq b$.

Proof:

Assume that the statement of the theorem is not true so that for some a and b, we have $na for every positive integer n. Then, the set $S = \{ b-na : n \in Z^{+}\}$ consists entirely of positive integers. By the Well-Ordering Principle, S will possess a least element, say, $b-ma$. Notice that $b- (m+1)a$ also lies in S; because S contains all integers of this form. Further, we also have $b-(m+1)a=(b-ma)-a contrary to the choice of $b-ma$ as the smallest integer in S. This contradiction arose out of original assumption that the Archimedean property did not hold; hence, the proof. QED.

First Principle of Finite Induction:

Let S be a set of positive integers with the following properties:

a) the integer 1 belongs to S.

b) Whenever the integer k is in S, the next integer $k+1$ is also in S.

Then, S is the set of all positive integers.

Second Principle of Finite Induction:

Let S be a set of positive integers with the following properties:

a) the integer 1 belongs to S.

b) If k is a positive integer such that $1,2,\ldots k$ belong to S, then $(k+1)$ must also be in S.

Then, S is the set of all positive integers.

So, in lighter vein, we assume a set of positive integers is given just as Kronecker had observed: “God created the natural numbers, all the rest is man-made.”

More later,

Nalin Pithwa.

# Precursor to Algebra: Herstein shows a way!

Reference: Abstract Algebra, 3rd edition, I. N. Herstein, Prentice Hall International Edition.

Problems:

1. Let S be a set having an operation * which assigns an element a*b of S for any $a,b \in S$. Let us assume that the following two rules hold:

i) If a, b are any objects in S, then $a*b = a$

ii) If a, b are any objects in S, then $a*b=b*a$

Show that S can have at most one object.

II. Let S be the set of all integers $0, \pm 1, \pm 2, \pm 3, \ldots, \pm n, \ldots$. For a, b in S, define * by $a*b=a-b$. Verify the following:

(i) $a*b \neq b*a$ unless $a=b$.

(ii) $(a*b)*c \neq a*(b*c)$ in general. Under what conditions on a, b, c is $(a*b)*c=a*(b*c)$?

(iii) the integer 0 has the property that $a*0=a$ for every a in S.

(iv) For a in S, $a*a=0$.

III) Let S consist oif f the two objects $\square$ and $\triangle$. We define the operation * on S by subjecting $\square$ and $\triangle$ to the following conditions:

i) $\square * \triangle = \triangle = \triangle * \square$i

ii) $\square * \square =\square$

iii) $\triangle * \triangle=\square$

of verify by explicit calculations that if a, b, c are any elements of S (that is, a, b and c can be any of $\square$ or $\triangle$ then

i) $a*b$ is in S

ii) $(a*b)*c=a*(b*c)$

iii) $a*b=b*a$

iv) There is a particular a in S such that $la=latex a*b=b*a=b$ for all b in S.

,v) Given b in S, then $b*b=a$ where a is the parituclar element in part “iv” above.

Cheers,

Nalin Pithwa