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.


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


By contradiction:

Assume that the statement of the theorem is not true so that for some a and b, we have na <b 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<b-ma 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.


  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 * \squarei

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.


Nalin Pithwa


Set Theory for Real Analysis: Part I:

Reference: Introductory Real Analysis by Kolmogorov and Fomin:

(Available at, for example, Amazon India: http://www.amazon.in/Introductory-Analysis-Dover-Books-Mathematics/dp/0486612260/ref=sr_1_1?s=books&ie=UTF8&qid=1499886166&sr=1-1&keywords=Introductory+real+analysis)

Functions and mappings. Images and preimages.

Theorem 1: The preimage of the union of two sets is the union of the preimages of the sets: f^{-1}(A \bigcup B) = f^{-1}(A)\bigcup f^{-1}(B).

Theorem 2:The  preimages of the intersection of two sets is the intersection of the preimages of the sets: f^{-1}(A \bigcap B)=f^{-1}(A) \bigcap f^{-1}(B).

Theorem 3: The images of the union of two sets equals the union of the images of the sets: f(A \bigcup B)=f(A) \bigcup (B).

Remark 1: Surprisingly enough, the image of the intersection of the two sets does not necessarily equal the intersection of the images of the sets. For example, suppose the mapping f projects the xy-plane onto the x-axis, carrying the point (x,y) into the (x,0). Then, the segments 0\leq x\leq 1, y=0 and 0\leq x \leq 1, y=1 do not intersect, although their images coincide.

Remark 2Theorems 1-3 (above) continue to hold for unions and intersections of of an arbitrary number (finite or infinite) of sets A_{\alpha}:




Decomposition of a set into classes. Equivalence relation. 

(NP: This is, of course, well-known so I will not dwell on it too much nor reproduce too much from the mentioned text). Just for quick review purposes:

A relation R on a set M is called an equivalence relation (on M) if it satisfies the following three conditions:

  1. Reflexivity: aRa, for every a \in M.
  2. Symmetry: If aRb, then bRa.
  3. Transitivity: If aRb and bRc, then aRc.

Theorem 4: A set M can be partitioned into classes by a relation R (acting as a criterion for assigning two elements to the same class) if and only if R is an equivalence relation on M.

Remark: Because of theorem 4, one often talks about the decomposition of M into equivalence classes.

Exercises 1:

Problem 1: Prove that if A \bigcup B=A and A \bigcap B=A, then A=B.

Problem 2: Show that in general (A-B)\bigcup B \neq A

Problem 3: Let A = \{ 2,4, \ldots, 2n, \ldots\} and B= \{ 3,6, \ldots, 3n, \ldots\}. Find A \bigcap B and A-B.

Problem 4: Prove that

(a) (A-B)\bigcap C=(A \bigcap C)-(B \bigcap C)

(b) A \triangle B =(A \bigcup B)-(A \bigcap B)

Problem 5: Prove that \bigcup_{\alpha}A_{\alpha}-\bigcup_{\alpha}B_{\alpha} \subset \bigcup_{\alpha}(A_{\alpha}-B_{\alpha}).

Problem 6: Let A_{\alpha} be the set of all positive integers divisible by n. Find the sets (a) \bigcup_{n=2}^{\infty}A_{\alpha} (b) \bigcap_{n=2}^{\infty}A_{\alpha}.

Problem 7: Find

(a) \bigcup_{n=1}^{\infty}[a+\frac{1}{n},b-\frac{1}{n}] (b) \bigcap_{n=1}^{\infty}(a-\frac{1}{n},b+\frac{1}{n})

Problem 8: Let A_{\alpha} be the set of points lying on the curve y=\frac{1}{x^{\alpha}} where (0<x<\infty). What is \bigcap_{\alpha \geq 1}A_{\alpha}?

Problem 9: Let y=f(x)= [x] for all real x, where [x] is the fractional part of x. Prove that every closed interval of length 1 has the same image under f. What is the image? is f one-to-one? What is the pre-image of the interval \frac{1}{4} \leq y \leq \frac{3}{4}? Partition the real line into classes of points with the same image.

Problem 10: Given a set M, let \Re be the set of all ordered pairs on the form (a,a) with a\in M, and let aRb iff (a,b) \in \Re. Interpret the relation R.

Problem 11: Give an example of a binary relation which is:

a) Reflexive and symmetric, but not transitive.

b) Reflexive but neither symmetric nor transitive.

c) Symmetric, but neither reflexive nor transitive.

d) Transitive, but neither reflexive not symmetric.













BIG Math Network Blog:

I hope to start writing this blog regularly, if not frequently, but, firstly, I hope the following blog helps many of my readers too:


BIG Math Network: Connecting Mathematical Scientists in Business, Industry, Government and Academia

(I just came across today from an AMS Blog.)

(Thanks to Evelyn J. Lamb)

— shared here by Nalin Pithwa.

Misteaks of mathematicians


(As remembered by Prof Walter Rudin in his autobiography, “The Way I Remember it”.)

Mathematicians are human. Humans make mistakes. Therefore…

This is no cause for alarm. I have no figures to back this up, but compared to the flood of published papers, the number of serious errors in the literature must be tiny. Most are probably caught by referees. And, if there is a serious error in a paper that is important enough to be studied by a significant number of interested mathematicians, that error will be discovered. Even better, the one who made it won’t be able to argue his way out of it.

There is an amusing article by Geoffrey K. Pullum in Natural Language and Linguistic Theory 5, 1987, 303-309, which compares this social aspect of mathematics with what happens in linguistics. It describes the story of Rourke’s claim to have proved the Poincare conjecture. (The article was sent to me by Catherine, my linguist daughter.)

My first encounter with this sort of thing started with the letter on the following page (typed a bit later after two paragraphs):

Needless to say, I was totally amazed. Here was Dieudonne, a world class mathematician and one of the founders of Bourbaki, not telling me, a young upstart, “you are wrong, because here is what I proved a few years ago” but asking me, instead to tell him what he had done wrong! Actually, it took me a while to find the error, and if I had not proved earlier (in J. Math. Mech. 7, 1958, 103-116) that convolution-factorization is always possible in L^{1} I would have accepted his conclusion with no hesitation, not because he was famous, but because his argument was simple, and, perfectly correct, as far as it went.

He proved, correctly, that every convolution of non-negative functions coincides almost everywhere with one that is lower semicontinuous. But (and this is what he ignored) that function may have +\infty among its values.


Evanston, Illinois.

58, Rue de Verneuil, Paris 7e (France).

Paris, December 17

 Dear Professor Rudin:

In the last issue of the Bulletin AMS, I see that you announce in abstract 7311, p.382, that in the algebra L^{1}(R^{n}), any element is the convolution of two elements of that algebra. I am rather amazed at the statement, for a few years ago I had made a simple remark which seemed to me to disprove your theorem (Compositio Mathematica, 12 (1954) p.17, footnote 3). I reproduce the proof for your convenience.

Suppose f, g are in L^{1} and greater than or equal to zero, and for each n consider the usual “truncated” functions f_{n}=\inf(f,n) and g_{n}=\inf(g,n); f(resp. g) is the limit of the increasing sequence (f_{n}) (resp. g_{n}), hence, by the usual Lebesgue convergence theorem, h=f*g is a.e. the limit of

h_{n}=f_{n}*g_{n}, which is obviously an increasing sequence. Moreover, f_{n} and g_{n} are both in L^{2}, hence it is well known that h_{n} can be taken continuous and bounded. It follows that h is a.e. equal to a Baire function of the first class. However, it is well-known that there are integrable functions which do not have that property, and therefore they cannot be convolutions.

I am unable to find any flaw in that argument, and if you can do so, I would very much appreciate if you can tell me where I am wrong.

Sincerely yours

J. Dieudonne

His argument proves that there are non-negative functions h in

L^{1} that are not representable as h=f*g with f \geq 0 and g \geq 0. (I had also observed this). In the general real-valued case, if h=f*g, each of f and g is a difference of two non negative functions, so that f*g breaks into four convolutions of the type considered by Dieudonne. Of these, two are greater than or equal to zero, two are less than or equal to zero, and one may therefore run into the problem of subtracting \infty from \infty (which is at least as much as of a no-no as is dividing 0 by 0). Hence, one can no longer conclude that h coincides almost everywhere with a function of Baire class one, that is, with a real-valued function which is everywhere the pointwise limit of a sequence of continuous ones.

Dieudonne had fallen into the “without loss of generality” trap by restricting himself to f \geq 0 and g \geq 0, and tacitly assuming that the general case would follow.

Here is his  reply to my explanation.

Paris, January 12, 1952.

Dear Professor Rudin:

Thank you for pointing out my error; as, it is of a very common type, I suppose I should have been able to detect it myself, but you know how hard it is to see one’s own mistakes, when you have once become convinced that some result must be true!!

Your proof is very ingenious; I hope you will be able to generalize that result to arbitrary locally compact abelian groups, but I suppose this would require a somewhat different type of proof.

With my congratulations for your nice result and my best thanks, I am

Sincerely yours

J. Dieudonne

The factorization theorem was indeed extended, even further than he had hoped. When Paul Cohen saw my rather complicated proof about L^{1}(\Re^{n}) (the case n=1 was much easier) he said: “Aha, approximate identities” and quickly produced a very general factorization theorem in Banach algebras with approximate left identities (Duke Math. J. 26, 1959, 199-205). Ed Hewitt (Math. Scand. 15, 1964, 147-155) extended Cohen’s proof so as to include convolution operators on L^{p} (1 \leq p < \infty). Every h in L^{p} is f*g with f in L^{1}, g in L^{p}.

In my next story, I was the one who goofed, but it ended well. This concerned the open unit ball B in the n-dimensional complex space C^{n}. A one-to-one holomorphic map from B onto B will be called an automorphism of B. (When n=1, B is the unit disc in C, and its automorphisms are the familiar Moebius transformations that send z to e^{i\theta}\frac{(z-\alpha)}{(1-\overline{\alpha} z)} ). The automorphisms of B are also explicitly known for all n.

Can a space X of complex valued functions on B(or on the boundary of B)  Moebius-invariant (or \mathcal{M} invariant) spaces of certain types (Duke Math. J. 43, 10976, 841-861) but the following was not answered:

Which closed subalgebras of C(B) are \mathcal{M}- invariant?

Here, C(B) is the algebra of all complex valued continuous (possibly unbounded) functions on B, with the topology of uniform convergence on compact sets, and with pointwise addition and multiplication.

The five obvious possibilities are: \{ 0 \}, the constants, the holomorphic functions on B, those whose complex conjugates are holomorphic and C(B) itself. The answer (Ann. Inst. Fourier 23, 1983, 19-41) is:

Theorem. There are no others.

I believe that this is the most difficult theorem that I ever proved. It was new even for n=1. I started with a proof of the one-dimensional case, and then used that to derive the same conclusion in n dimensions. Fairly soon after I submitted the paper, Malgrange, who was an editor of Annales Fourier, wrote that the referee did not understand how I passed from 1 to n. When I looked at it, I couldn’t understand it either! What I had written simply made no sense, and there seemed to be no way to repair it. I had to go back and instead of first dealing with the one-variable case I had to do the whole thing in n variables from the start. Fortunately, it worked. But it took a whole summer.

When I sent the corrected (much longer) version to Malgrange, I wrote that I should like to  thank the referee in the corrected paper, but only if I could mention his or her name. I saw no virtue in anonymous thanks. The referee agreed to this; it turned out to be my friend Jean-Pierre Rosay.

A few years later, we (i.e., the Madison Mathematics Department) wanted to invite Rosay for a whole year’s visit. I had a so-called Vilas Professorship which provided research funds for worthy projects. So I sent a request to the appropriate committee; to strengthen the case, I mentioned that not only I but several of my colleagues (Ahern, Forelli, Nagel, Wainger among them) would find him very stimulating. My letter was returned by no other than Irv Shain, the Chancellor, saying that Vilas Professorships were only for the benefit of those who  had one and for no one else’s, and that I should write a different letter, explaining how Rosay’s presence would benefit me. I did that, and as a clincher enclosed a reprint of the paper in which I thanked him. That did it.

Soon after he arrived, he and I started  to work on several questions about holomorphic maps. This resulted in a long paper. (Trans. AMS 310, 1988, 47-86), the first of several that we wrote together. Our collaboration went so well that I suggested that we ought to try to  keep him. We succeeded in this, and it could well be that my role in getting him to stay here was one of thei best things I ever did for the Department.

I know of only one totally absurd paper that was published in a respectable journal, namely the one by Nikola Pandeski in Math., Annalen 287, 1990, 185-192. In one variable, the “corona theorem” asserts that the open unit disc U is dense in the maximal ideal space of the Banach algebra of all bounded holomorphic functions in U. Its original proof, by Lennart Carleson (Annals of Math. 76, 1963, 547-559) involved a great deal of difficult “hard” analysis. A much simpler one was later found by Tom Wolff. But the n-variable analogue, which Pandeski claimed to have proved, is still wide open.

This paper appeared during a several complex variables conference in Oberwolfach. I heard that it caused great hilarity because nothing in it makes sense. For example, the proof starts by covering a sphere with a finite disjoint collection of small balls! I have heard several explanations about how this absurdity got into print, none of them convincing. I was quite annoyed about the whole affair because Pandeski attributed several absolutely false assertions to me, and because Granert, the editor who  had (mis)handled this paper refused to publish my protest.


Never mind. To err is human …

Nalin Pithwa