Equivalence relations and partitions: some core basic theorems

Posted on by Nalin Pithwa

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

Posted on by Nalin Pithwa

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:

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!

Posted on by Nalin Pithwa

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

Cheers,

Nalin Pithwa

 

Set Theory for Real Analysis: Part I:

Posted on by Nalin Pithwa

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 2: Theorems 1-3 (above) continue to hold for unions and intersections of of an arbitrary number (finite or infinite) of sets A_{\alpha}:

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

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

f(\bigcup_{\alpha}A_{\alpha})=\bigcup_{\alpha}f(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:

Posted on by Nalin Pithwa

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

https://bigmathnetwork.wordpress.com/

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.