how to prove it - ch4, sec4.6(Equivalence Relations)

Equivalence Relation: A relation which is reflexive, symmetric and transitive.

It turns out that every equivalence relation on a set A determines a partitions of A, whose elements are the equivalence classes for the equivalence relation. Let us define them precisely.

Partition on A: A subset $F$ of power set of A, $P(A)$, is called a partition on A if it has following three properties.

- $\cup F$ = A
- $F$ is pairwise disjoint, that means $\forall X \in F \forall Y \in F (X \neq Y \rightarrow X \cap Y = \emptyset)$. Simply speaking, every two different elements of $F$ are disjoint
- $\forall X \in F (X \neq \emptyset)$

Equivalence Classes: Suppose R is an equivalence relation on A, and $x \in A$. Then the equivalence class of x with respect to R is the set
$[x]_R$ = {$y \in A$ | yRx }
If R is clear from the context, then we just write $[x]$. The set of all equivalence classes of elements of A is called A modulo R, and is denoted by A/R.
A/R = {[$x]_R | x \in A$} = {$X \subseteq A | \exists x (X = [x]_R)$}

There are some interesting theorems proved. I'll note them down here for the reference purposes.

Theorem: Suppose R is an equivalence relation on A, then A/R is a partition of A

it can be proved using following lemmas.
lemma1: For every $x \in A$, $x \in [x]$
lemma2: For every $x \in A$ and $y \in A$, $y \in [x]$ iff [y] = [x]. That is, all the equivalence classes are disjoint

Theorem: Suppose A is a set and $F$ is a partition of A. Then there is an equivalence relation R on A s.t. A/R = $F$
and it happens to be R = $\cup_{X \in F}(X x X)$


=================================================================================

Ex-1: {{1}, {2}, {3}}
{{1,2}, {3}}
{{1}, {2,3}}
{{1,3}, 2}
{{1,2,3}}


Ex-2: {(1,1),(2,2),(3,3)}
{(1,1),(2,2),(3,3),(1,2),(2,1)}
{(1,1),(2,2),(3,3),(2,3),(3,2)}
{(1,1),(2,2),(3,3),(1,3),(3,1)}
{(1,1),(2,2),(3,3),(1,2),(2,3),(1,3),(2,1),(3,2),(3,1)}


Ex-3:
(a) Yes, it is equivalence relation. The equivalence classes are sets of all the words that start with a, sets of all the words that start with b,...

(b) It is not an equivalence relation as its not transitive. For example $(ab,bc) \in S$ and $(bc,cd) \in S$ but $(ab,cd) \notin S$

(c) Yes, it is equivalence relation. words of same length would fall into same equivalence class.


Ex-4:
(a) Its not equivalence relation as its not symmetric. For example $(5,3) \in R$ but $(3,5) \notin R$

(b) Yes, its an equivalence relation. Equivalence classes would be, set of all the real numbers such that their difference is any rational number.

(c) Yes, its an equivalence relation. Let us see example of an equivalence class..
[1] = {..., $\frac{1}{10000}$, $\frac{1}{1000}$, $\frac{1}{100}$, $\frac{1}{10}$, 1, 10, 100, 1000, 10000, ...}

In general for any real number x, the equivalence class would look like
[x] = {..., $\frac{x}{10000}$, $\frac{x}{1000}$, $\frac{x}{100}$, $\frac{x}{10}$, x, x*10, x*100, x*1000, x*10000, ...}


Ex-5: P = set of all people
B = {$(p,q) \in P x P$ | p and q have same birthday }
$P_d$ = {$p \in P$ | p has birthday on day d}

by definition of equivalence classes
P/B = {$X \subseteq P | \exists x (X = [x])$}

Now $P_d$ would be a equivalence class if there exists a person p s.t. [p] = $P_d$ i.e. there is atleast one person who was born on day d. So, if we make the assumption that for all the days there is atleast one person who was born on that day then P/B = {$P_d | d \in D$}.


Ex-6: Clearly the relation is reflexive as one triangle is similar to itself. Its symmetric because if a triangle x is similar to y, then y is similar to x also. Its also transitive because if x and y are similar triangles, y and z are similar triangles then clearly x and z are also similar triangles. Thus similarity relation is equivalence relation on set of triangles.


Ex-7: Proof for R is symmetric:
Let x,y be arbitrary elements of A s.t. $(x,y) \in R$. Then we can choose a $X \in F$ s.t. $(x,y) \in X x X$, that is $x \in X$ and $y \in X$. Thus $(y,x) \in X x X$, and so $(y,x) \in R$. Since x,y are arbitrary so R is symmetric

Proof for R is transitive:
Let x,y,z be arbitrary element of A s.t. $(x,y) \in R$ and $(y,z) \in R$. Then we can choose $X_1 \in F$ s.t. $(x,y) \in X_1 x X_1$ and $X_2 \in F$ s.t. $(y,z) \in X_2 x X_2$. Thus $x \in X_1$ and $y \in X_1$, $y \in X_2$ and $z \in X_2$. Since $F$ is a partition, so pairwise disjoint. Since $y \in X_1$ and $y \in X_2$, so $X_1 = X_2$. Thus $z \in X_1$, hence $(x,z) \in X_1 x X_1$ and hence $(x,z) \in R$. Since x,y,z are arbitrary so R is transitive


Ex-8: ($\rightarrow$) Suppose A/R = A/S. Let (x,y) be an arbitrary ordered pair in R. Then $x \in [x]_R$ and $y \in [y]_R$. Since A/R = A/S, so $[x]_R \in A/S$ and $[y]_R \in S$. Thus $(x,y) \in A/S$. Since (x,y) is arbitrary so $R \subseteq S$
($\leftarrow$) Using a similar argument as above, we can prove that $S \subseteq R$
Thus R = S


Ex-9: ($\rightarrow$) Let (x,y) be an arbitrary element of S. Then we can choose an $X \in F$ s.t. $(x,y) \in X x X$. Since $F$ = A/R, so X is an equivalence class of R on A. Thus X = $[x]_R$ = $[y]_R$, hence $(x,y) \in R$.
($\leftarrow$) Let (x,y) be an arbitrary element of R. Then we can choose an $X \in A/R$ s.t. $x \in X$ and $y \in X$. Since $F$ = A/R and $(x,y) \in X x X$, so $(x,y) \in \cup_{X \in F}(X x X)$. Thus $(x,y) \in S$. Since (x,y) is arbitrary so $R \subseteq S$

Thus S = R


Ex-10:
(a) Proof for $C_m$ is reflexive:
Let x be an arbitrary real number. since (x - x = 0*m), so $(x,x) \in C_m$. Since x is arbitrary, so $C_m$ is reflexive.

Proof for $C_m$ is symmetric:
Let x and y be arbitrary real numbers s.t. $(x,y) \in C_m$. Then we can choose a $k \in Z$ s.t. (x - y = km). Then (y - x = -km). Since $-k \in Z$, so $(y,x) \in C_m$. Since x,y are arbitrary so $C_m$ is symmetric

(b) For $C_2$:
Let us see an example.. [1] = {....-7,-5,-3,-1,1,3,5,7,.....} = {$n \in Z$ | |n|%2 = 1}
Now you can see that $C_2$ has two equivalence classes which are

{$n \in Z$ | |n|%2 = 1}, basically all odd integers
{$n \in Z$ | |n|%2 = 0}, all even integers

For $C_3$:
It has 3 equivalence classes
{$n \in Z$ | n % 3 = 0 }, all integers divisible by 3
{$n \in Z$ | |n| % 3 = 1 }
{$n \in Z$ | |n| % 3 = 2 }

Its easy to see that $C_m$ will have m equivalence classes


Ex-11: Since n is integer, so either its even or its odd. Let us consider both the cases
Case#1: n is even
Then, we can choose a $k \in Z$ s.t. n = 2k. Then $n^2$ = $(2k)^2$ = $4k^2$. Then $n^2 - 0$ is divisible by 4. So $n \equiv 0$ (mod 4)

Case#2: n is odd
Then, we can choose a $k \in Z$ s.t. n = (2k + 1). then $n^2$ = $(2k+1)^2$ = $4k^2 + 4k + 1$. Then $n^2 - 1$ = $4(k^2 + k)$, which is clearly divisible by 4. So $n \equiv 1$ (mod 4)

Thus if n is an integer then either $n \equiv 0$ (mod 4) or $n \equiv 1$ (mod 4)


Ex-12: Suppose $a \equiv c$ (mod m) and $b \equiv d$ (mod m). clearly we can choose some $k,l \in Z$ s.t.
a - c = km ...(i) and
b - d = lm ...(ii)

adding eq (i) and (ii) we get
a + b - c - d = (k+l)m
=> (a+b) - (c+d) = (k+l)m

Since $k+l \in Z$, so clearly $(a+b) \equiv (c+d)$ (mod m)

From eq (i), a = km + c ...(iii)
From eq (ii),b = lm + d ...(iv)

On multiplying eq (iii) and (iv) we get
ab = (km + c)(lm + d)
=> ab = kl$m^2$ + clm + cd + kdm
=> ab - cd = (klm + kd + cl)m

Since (klm + kd + cl) is integer, so $ab \equiv cd$ (mod m)


Ex-13:
(a) Let x be an arbitrary element of B. clearly $(x,x) \in B x B$. Since $B \subseteq A$, so $x \in A$ hence $(x,x) \in R$. So $(x,x) \in R \cap B x B$. Thus $(x,x) \in S$. Since x is arbitrary so S is reflexive on B.
Let x,y be arbitrary elements of B s.t. $(x,y) \in S$. Then $(x,y) \in R$. Since R is equivalence relation, hence symmetric and so $(y,x) \in R$. Also $(y,x) \in B x B$. Thus $(y,x) \in R \cap B x B$. So $(y,x) \in S$. Since x,y are arbitrary so S is symmetric.
Let x,y,z be arbitrary elements of B s.t. $(x,y) \in S$ and $(y,z) \in S$. So $(x,y) \in R$ and $(y,z) \in R$, hence $(x,z) \in R$. Also $(x,z) \in B x B$. Thus $(x,z) \in R \cap B x B$. So $(x,z) \in S$. Since x,y,z are arbitrary so S is transitive.
Thus S is equivalence relation on B.

(b) Let x be an arbitrary element of B. Let y be arbitrary element of $[x]_S$. Then
$y \in [x]_S$ iff
$(y,x) \in S$ iff
$(y,x) \in R \land (y,x) \in B x B$ iff
$y \in [x]_R \land y \in B$ iff
$y \in [x]_R \cap B$

Since y is arbitrary, so $[x]_S$ = $[x]_R \cap B$


Ex-14:
(a) Let X be an arbitrary set from $P(A)$. $X \triangle X$ = $(X \setminus X) \cup (X \setminus X)$ = $\emptyset$. Since $\emptyset \subseteq B$, so $(X,X) \in R$. Since X is arbitrary, so R is reflexive on $P(A)$
Let (X,Y) be an arbitrary ordered pair in $P(A) x P(A)$ s.t. $(X,Y) \in R$. Then $X \triangle Y \subseteq B$, then $(X \setminus Y) \cup (Y \setminus X) \subseteq B$, then $(Y \setminus X) \cup (X \setminus Y) \subseteq B$, then $(Y,X) \subseteq B$. Thus $(Y,X) \in R$. Since (X,Y) is arbitrary so R is symmetric.
Let (X,Y) and (Y,Z) be two arbitrary ordered pairs in $P(A) x P(A)$ s.t. $(X,Y) \in R$ and $(Y,Z) \in R$. Then $X \triangle Y \subseteq B$ and $Y \triangle Z \subseteq B$. Then
$(X \setminus Y) \cup (Y \setminus X) \subseteq B$ ...(i) and
$(Y \setminus Z) \cup (Z \setminus Y) \subseteq B$ ...(ii)

We will prove that $X \triangle Z \subseteq B$. Let x be an arbitrary element of $X \triangle Z$. Then either $x \in X \setminus Z$ or $x \in Z \setminus X$. Let us consider both the cases
Case#1: $x \in X \setminus Z$
Then $x \in X$ and $x \in Z$. Now either $x \in Y$ or $x \notin Y$, so either $x \in Y \setminus Z$ or $x \in X \setminus Y$. It follows from eq(i) and eq(ii) that $x \in B$.

case#2: $x \in Z \setminus X$
By a similar argument as above, $x \in B$.

Since x is arbitrary, so $X \setminus Z \subseteq B$

Since X,Y,Z are arbitrary so R is transitive on $P(A)$

Since R is reflexive, symmetric and transitive so R is equivalence relation on $P(A)$

(b) We will prove it by contradiction. Suppose X be arbitrary element of $P(A)$. Assume Y,Z be two different arbitrary elements of $[X]_R$. s.t. $Y \cap B = \emptyset$ and $Z \cap B = \emptyset$.
Since $Y \in [X]_R$, so $(Y,X) \in R$.
Since $Z \in [X]_R$, so $(Z,X) \in R$. Since R is equivalence relation and hence symmetric, so $(X,Z) \in R$. Since $(Y,X) \in R$ and $(X,Z) \in R$ and R is transitive, so $(Y,Z) \in R$.
Then, $Y \triangle Z \subseteq B$
Since Y and Z are different, so $Y \triangle Z$ has to be non-empty. Then we can choose some $x \in Y \triangle Z$. Since $Y \triangle Z \subseteq B$, so $x \in B$. Since $x \in Y \triangle Z$, so either $x \in Y \setminus Z$ or $x \in Z \setminus Y$. Let us consider both the cases

Case#1: $x \in Y \setminus Z$
Then $x \in Y$ and $x \notin Z$. Now since $Y \cap B = \emptyset$, so $x \notin B$. And that is a contradiction, hence this case is not possible.

Case#2: $x \in Z \setminus Y$
Then $x \in Z$ and $x \notin Y$. Now since $Z \cap B = \emptyset$, so $x \notin B$. And that is a contradiction. hence this case is not possible.

Since none of the cases are possible, so such x can not exist and hence $Y \triangle Z = \emptyset$. Then $Y = Z$.

Since X is arbitrary so, for every $X \in P(A)$ there is exactly one $Y \in [X]_R$ such that $Y \cap B = \emptyset$


Ex-15: First, we will prove that $\cup (F \cup G)$ = $A \cup B$.
($\rightarrow$) Let x be an arbitrary element of $\cup (F \cup G)$. Then we can choose some $X \in F \cup G$ s.t. $x \in X$. Now either $X \in F$ or $X \in G$. Let us choose both the cases.
Case#1: $X \in F$
Then $x \in \cup F$, then $x \in A$. Thus $x \in A \cup B$

Case#2: $X \in G$
Then $x \in \cup G$, then $x \in B$. Thus $x \in A \cup B$

Since $x \in A \cup B$ and x is arbitrary, so $\cup (F \cup G) \subseteq A \cup B$

($\leftarrow$) Let x be an arbitrary element of $A \cup B$. Let us consider both the cases
Case#1: $x \in A$
Then $x \in \cup F$. Then we can choose $X \in F$ s.t. $x \in X$. Since $X \in F$, so $X \in F \cup G$. Thus $x \in \cup (F \cup G)$

Case#2: $x \in B$
Then $x \in \cup G$. Then we can choose $X \in G$ s.t. $x \in X$. Since $X \in G$, so $X \in F \cup G$. Thus $x \in \cup (F \cup G)$

Since $x \in \cup (F \cup G)$ and x is arbitrary, so $A \cup B \subseteq \cup (F \cup G)$

Thus, $\cup (F \cup G)$ = $A \cup B$

Second, we will prove that $F \cup G$ is pairwise disjoint
Let X,Y be two arbitrary elements of $F \cup G$ s.t. $X \neq Y$. Let us consider following exhaustive set of cases
Case#1: $X \in F$ and $Y \in F$
Since F is a partition, so $X \cap Y = \emptyset$

Case#2: $X \in G$ and $Y \in G$
Since G is a partition, so $X \cap Y = \emptyset$

Case#3: $X \in F$ and $Y \in G$
Then $X \in P(A)$ and $Y \in P(B)$, so $X \subseteq A$ and $Y \subseteq B$. Since A and B are disjoint, so $X \cap Y = \emptyset$

Case#3: $X \in G$ and $Y \in F$
Then $X \in P(B)$ and $Y \in P(A)$, so $X \subseteq B$ and $Y \subseteq A$. Since A and B are disjoint, so $X \cap Y = \emptyset$

Thus X and Y are disjoint. Since X and Y are arbitrary, so $F \cup G$ is pairwise disjoint

Third, we will prove that every element in $F \cup G$ is non-empty.
Let X be an arbitrary element of $F \cup G$. Then either $X \in F$ or $X \in G$. Since F and G both are partitions so in any of the two cases $X \neq \emptyset$. Since X is arbitrary so every element in $F \cup G$ is non-empty

Hence, $F \cup G$ is a partition of $A \cup B$


Ex-16:
(a) First, we prove that $R \cup S$ is reflexive on $A \cup B$
Let x be an arbitrary element of $A \cup B$. Then either $x \in A$ or $x \in B$. Then either $(x,x) \in R$ or $(x,x) \in S$. Then $(x,x) \in R \cup S$. Since x is arbitrary, so $R \cup S$ is reflexive on $A \cup B$

Second, we prove that $R \cup S$ is symmetric on $A \cup B$
Let (x,y) be an arbitrary ordered pair in $R \cup S$. Then either $(x,y) \in R$ or $(x,y) \in S$. Then either$(y,x) \in R$ or $(y,x) \in S$. Then $(y,x) \in R \cup S$. Since (x,y) is arbitrary so $R \cup S$ is symmetric on $A \cup B$

Third, we prove that $R \cup S$ is transitive on $A \cup B$
Let (x,y) and (y,z) be arbitrary elements of $R \cup S$. Then, following cases are possible.
Case#1: $(x,y) \in R$ and $(y,z) \in R$
Then $(x,z) \in R$

Case#2: $(x,y) \in S$ and $(y,z) \in S$
Then $(x,z) \in S$

Case#3: $(x,y) \in R$ and $(y,z) \in S$
Then $x \in A$ and $y \in A$, $y \in B$ and $z \in B$. Since A and B are disjoint, y can't be element of both and hence this case is not possible

Case#4: $(x,y) \in S$ and $(y,z) \in R$
Then $x \in B$ and $y \in B$, $y \in A$ and $z \in A$. Since A and B are disjoint, y can't be element of both and hence this case is not possible

Thus either $(x,z) \in R$ or $(x,z) \in S$. Thus $(x,z) \in R \cup S$. Since (x,y) and (y,z) are arbitrary so $R \cup S$ is transitive

Hence $R \cup S$ is an equivalence relation on $A \cup B$

(b) First, we prove that for all $x \in A$, $[x]_{R \cup S}$ = $[x]_R$.
Suppose x is arbitrary element of A.
($\rightarrow$) Let y be an arbitrary element of $[x]_{R \cup S}$. Then $(y,x) \in R \cup S$. Then either $(y,x) \in R$ or $(y,x) \in S$. Since $x \in A$, so $(y,x) \notin S$. Thus $(y,x) \in R$. Hence $y \in [x]_R$. Since y is arbitrary so $[x]_{R \cup S} \subseteq [x]_R$
($\leftarrow$) Let y be an arbitrary element of $[x]_R$. Then $(y,x) \in R$, then $(y,x) \in R \cup S$. So $y \in [x]_{R \cup S}$. Since y is arbitrary, so $[x]_R \subseteq [x]_{R \cup S}$

Hence $[x]_{R \cup S}$ = $[x]_R$.

By using a similar argument, we can prove that for all $y \in B$, $[y]_{R \cup S}$ = $[y]_R$

(c) ($\rightarrow$) Let X be an arbitrary element of $(A \cup B)/(R \cup S)$. Then we can choose some $x \in A \cup B$ s.t. X = $[x]_{R \cup S}$. Then using the result of part(b), either $x \in A$ and $X = [x]_R$ or $x \in B$ and $X = [x]_S$. Then either $X \in A/R$ or $X \in B/S$. Thus $X \in (A/R) \cup (B/S)$. Since X is arbitrary, so $(A \cup B)/(R \cup S) \subseteq (A/R) \cup (B/S)$

($\leftarrow$) Let X be an arbitrary element of $(A/R) \cup (B/S)$. Then either $X \in (A/R)$ or $X \in (B/S)$. Then either we can choose some $x \in A$ s.t.$X = [x]_R$ or we can choose some $x \in B$ s.t. $[x]_S$. Using results of part(b), It follows from both the cases that $X = [x]_{R \cup S}$ whether $x \in A$ or $x \in B$. Thus $X \in (A \cup B)/(R \cup S)$. Since X is arbitrary, so $(A/R) \cup (B/S) \subseteq (A \cup B)/(R \cup S)$

Thus, $(A \cup B)/(R \cup S)$ = $(A/R) \cup (B/S)$

Ex-17: First, we prove that $\cup (F.G)$ = A.
($\rightarrow$) Let x be an arbitrary element of $\cup (F.G)$. Then we can choose some $Z \in F.G$ s.t. $x \in Z$. Since $Z \in F.G$, then we can choose some $X \in F$ and $Y \in Z$ s.t. Z = $X \cap Y$. Then $x \in X$ and $x \in Y$. Then $x \in \cup F$ and $x \in \cup G$. Since $\cup F$ = $\cup G$ = A, so $x \in A$. Since x is arbitrary, so $\cup (F.G) \subseteq A$
($\leftarrow$) Let x be an arbitrary element of A. Since A = $\cup F$ = $\cup G$, so $x \in \cup F$ and $x \in \cup G$. Then we can choose some $X \in F$ and $Y \in G$ s.t. $x \in X$ and $x \in G$. Then $x \in X \cap Y$. Let Z = $X \cap Y$, so $x \in Z$. Then $x \in \cup (F.G)$. Since x is arbitrary so $A \subseteq \cup (F.G)$.

Thus $\cup (F.G)$ = A


Ex-18: Basically for every element X in $F$ and for every element Y in $G$, create $X \cap Y$. Ignore $\emptyset$ and rest are all elements of $F.G$.
So potentially, $F.G$ = {$R^{-} \cap Z$, $R^{-} \cap (R \setminus Z)$, $R^{+} \cap Z$, $R^{+} \cap (R \setminus Z)$, {0}$\cap Z$, {0} $\cap (R \setminus Z)$}
= {$Z^{-}$, $R^{-} \setminus Z$, $Z^{+}$, $R^{+} \setminus Z$, {0}, $\emptyset$}

remove all empty sets, we get

$F.G$ = {$Z^{-}$, $R^{-} \setminus Z$, $Z^{+}$, $R^{+} \setminus Z$, {0}}


Ex-19:
(a) First, we prove the T is reflexive.
Let x be an arbitrary element of A. Then $(x,x) \in R$ and $(x,x) \in S$. Then $(x,x) \in R \cap S$. Then $(x,x) \in T$. Since x is arbitrary, so T is reflexive on A.

Second, we prove that T is symmetric.
Let (x,y) be an arbitrary element of T. Then $(x,y) \in R$ and $(x,y) \in S$. Since R,S are symmetric so $(y,x) \in R$ and $(y,x) \in S$. Then $(y,x) \in R \cap S$. Thus $(y,x) \in T$. Since (x,y) is arbitrary so T is symmetric on A

Third, we prove that T is transitive.
Let (x,y) and (y,z) be two arbitrary elements of T. Then $(x,y) \in R$ and $(y,z) \in R$, $(x,y) \in S$ and $(y,z) \in S$. Since R,S are transitive so $(x,z) \in R$ and $(x,z) \in S$. Then $(x,z) \in R \cap S$. Thus $(x,z) \in T$. Since (x,y) and (y,z) are arbitrary so T is transitive on A.

Hence T is an equivalence relation on A.

(b) Let x be an arbitrary element of A. Let y be an arbitrary element of $[x]_T$.
so $y \in [x]_T$ iff
$(y,x) \in T$ iff
$(y,x) \in R \cap S$ iff
$(y,x) \in R \land (y,x) \in S$ iff
$y \in [x]_R \land y \in [x]_S$ iff
$y \in [x]_R \cap [x]_S$

Since y is arbitrary, so $[x]_T$ = $[x]_R \cap [x]_S$

(c) Let X be an arbitrary element of $P(A)$.
Then $X \in A/T$ iff
$\exists x \in A (X = [x]_T)$ iff (using part(b) result)
$\exists x \in A (X = [x]_R \cap [x]_S)$ iff
$X \in (A/R).(A/S)$

Since X is arbitrary so (A/T) = (A/R).(A/S)


Ex-20: First, we prove that $\cup (F \otimes G)$ = $A x B$
($\rightarrow$) Let p be an arbitrary element of $\cup (F \otimes G)$. Then we can choose some $Z \in F \otimes G$ s.t. $p \in Z$. Since $Z \in F \otimes G$, so we can choose some $X \in F$ and $Y \in G$ s.t. Z = $X x Y$. Thus $p \in X x Y$. Since $X \in F$, so $X \in P(A)$ and hence $X \subseteq A$. By a similar argument $Y \subseteq B$. Thus $p \in A x B$. Since p was arbitrary, so $F \otimes G \subseteq A x B$
($\leftarrow$) Let (x,y) be an arbitrary element of $A x B$. Then, $x \in A$ and $y \in B$. Then $x \in \cup F$ and $y \in \cup G$. Then we can choose some $X \in F$ s.t. $x \in X$ and we can choose some $Y \in G$ s.t. $y \in Y$. Thus $(x,y) \in X x Y$. So $(x,y) \in \cup (F \otimes G)$. Since (x,y) is arbitrary so $A x B \subseteq \cup (F \otimes G)$

Thus $\cup (F \otimes G)$ = $A x B$

Second, we prove that $F \otimes G$ pairwise disjoint.
Suppose Z and W be two arbitrary elements of $F \otimes G$ s.t. $Z \neq W$. Then we can choose some $X_1 \in F$, $X_2 \in F$, $Y_1 \in G$, $Y_2 \in G$ s.t. $Z = X_1 x Y_1$ and $W = X_2 x Y_2$. Since $Z \neq W$, so either $X_1 \neq X_2$ or $Y_1 \neq Y_2$. Let us consider both the cases
Case#1: $X_1 \neq X_2$
Since $F$ is a partition, so $X_1 \cap X_2 = \emptyset$. Then it follows that $Z \cap W = \emptyset$

Case#2: $Y_1 \neq Y_2$
Since $G$ is a partition, so $Y_1 \cap Y_2 = \emptyset$. Then it follows that $Z \cap W = \emptyset$

Thus Z and W are disjoint. Since Z and W are arbitrary, so $F \otimes G$ is pairwise disjoint

Third, we prove that every element of $F \otimes G$ is non-empty
Let Z be an arbitrary element of $F \otimes G$. Then we can choose some $X \in F$ and $Y \in G$ s.t. $Z = X x Y$. Since $F$ and $G$ are partitions, so $X \neq \emptyset$ and $Y \neq \emptyset$. Thus $X x Y \neq \emptyset$. So $Z \neq \emptyset$. Since Z is arbitrary, so every element of $F \otimes G$ is non-empty

Hence $F \otimes Z$ is a partition of $A x B$


Ex-21: $F \otimes F$ = $(F x F) \setminus \{\emptyset\}$
So $F \otimes F$ = {$R^{-} x R^{-}, R^{-} x R^{+}, R^{-} x \{0\}, R^{+} x R^{-}, R^{+} x R^{+}, R^{+} x \{0\}, \{0\} x R^{-}, \{0\} x R^{+}, \{(0,0\}$}

Let us describe them in terms of xy-plane(in turn in terms of 4 quadrants of the plane).
$R^{-} x R^{-}$ is 3rd(bottom left) quadrant
$R^{-} x R^{+}$ is 2nd(top left) quadrant
$R^{-} x \{0\}$ is negative X-axis
$R^{+} x R^{-}$ is 4th(bottom right) quadrant
$R^{+} x R^{+}$ is 1st(top right) quadrant
$R^{+} x \{0\}$ is positive X-axis
$\{0\} x R^{-}$ is negative Y-axis
$\{0\} x R^{+}$ is positive Y-axis
{(0,0)} is origin


Ex-22:
(a) First, we prove that T is reflexive on A x B.
Let (x,y) be an arbitrary element of (A x B). Then $(x,x) \in R$ and $(y,y) \in S$. Then $((x,y),(x,y)) \in T$. Since (x,y) is arbitrary so T is reflexive.

Second, we prove that T is symmetric on A x B.
Let ((x,y),(u,v)) be an arbitrary element of T. Then $(x,u) \in R$ and $(y,v) \in S$. Then $(u,x) \in R$ and $(v,y) \in S$. Thus $((u,v),(x,y)) \in T$. Since ((x,y),(u,v)) is arbitrary so T is symmetric.

Third, we prove that T is transitive on A x B.
Let ((x,y),(u,v)) and ((u,v),(l,m)) be arbitrary elements of T. Then $(x,u) \in R$ and $(u,l) \in R$, $(y,v) \in S$ and $(v,m) \in S$. Then $(x,l) \in R$ and $(y,m) \in S$. Then $((x,y),(l,m)) \in T$. Thus T is transitive.

Hence, T is equivalence relation on A x B.

(b) Suppose $a \in A$ and $b \in B$. Let (x,y) be an arbitrary element of A x B. Then
$(x,y) \in [(a,b)]_T$ iff
$((x,y),(a,b)) \in T$ iff
$(x,a) \in R \land (y,b) \in S$ iff
$x \in [a]_R \land y \in [b]_S$ iff
$(x,y) \in [a]_R x [b]_S$

Since (x,y) is arbitrary, so $[(a,b)]_T$ = $[a]_R x [b]_S$

(c) RHS
= (A/R) $\otimes$ (B/S)
= {$Z \in P(A x B) | \exists a \in A \exists b \in B (Z = [a]_R x [b]_S)$} , now using result of part(b)
= ($Z \in P(A x B) | \exists (a,b) \in (A x B) (Z = [(a,b)]_T)$}
= (A x B)/T
= LHS


Ex-23:
(a) Suppose R is compatible with S. Let T be a relation on A/S, defined as follow
T = {$(X,Y) \in A/S x A/S | \exists x \in X \exists y \in Y (xRy)$}

Let x,y be two arbitrary elements of A. Then
$[x]_S T [y]_T$ iff
$\exists a \in [x]_S \exists b \in [y]_S (aRb)$ iff
$\exists a \in A \exists b \in A (a \in [x]_S) \land (b \in [y]_S) \land (aRb)$ iff
$\exists a \in A \exists b \in A (aSx) \land (bSy) \land (aRb)$ iff (since R is compatible with S)
$xRy$

So T satisfies the given property and hence such a relation exists.

(b) Suppose x,y,a,b are arbitrary elements on S s.t. (xSa) and (ySb). Let (xRy). Then $([x]_S,[y]_S) \in T$. Since (xSa), so $[x]_S = [a]_S$. Since (ySb), so $[y]_S = [b]_S$. Thus $([a]_S,[b]_S) \in T$. Then (aRb). So, If (xRy) then (aRb). Using a similar argument we can prove that If (aRb) then (xRy). Hence (xRy) iff (aRb). Thus R is compatible with S.


Ex-24:
(a) First, we prove that S is reflexive on A.
Let x be an arbitrary element of A. Since R is reflexive, so $(x,x) \in R$. And also $(x,x) \in R^{-1}$. Thus $(x,x) \in R \cap R^{-1}$. So $(x,x) \in S$. Since x is arbitrary, so S is reflexive.

Second, we prove that S is symmetric on A.
Let (x,y) be arbitrary element of S. Then $(x,y) \in R$ and $(x,y) \in R^{-1}$. Then $(y,x) \in R^{-1}$ and $(y,x) \in R$. Then $(y,x) \in R \cap R^{-1}$. Thus $(y,x) \in S$. Since (x,y) is arbitrary so S is symmetric.

Third, we prove that S is transitive on A.
Let (x,y) and (y,z) be arbitrary elements of S. Then $(x,y) \in R$ and $(x,y) \in R^{-1}$, $(y,z) \in R$ and $(y,z) \in R^{-1}$. Since $(x,y) \in R$ and $(y,z) \in R$ and R is transitive, so $(x,z) \in R$. Since $(x,y) \in R^{-1}$ and $(y,z) \in R^{-1}$, so $(y,x) \in R$ and $(z,y) \in R$. Since R is transitive, so $(z,x) \in R$ and hence $(x,z) \in R^{-1}$. So $(x,z) \in R \cap R^{-1}$. Thus $(x,z) \in S$. So S is transitive.

Hence S is equivalence relation on A.

(b) we can use the result from Ex23(a), the statement in question can be proved by just proving that R is compatible with S.
Let x,y,a,b be arbitrary elements of A s.t. (xSa) and (ySb). Let (xRy). Since (xSa), so $x R^{-1} a$ and hence (aRx). Since (aRx) and (xRy) and R is transitive, so (aRy). Since (ySb), so (yRb). Since (aRy) and (yRb) and R is transitive, so (aRb). So, If (xRy) then (aRb). Using a similar argument we can prove that If (aRb) then (xRy). Thus R is compatible with S.

(c) First, we prove that T is reflexive on (A/S).
Let x be an arbitrary element of A. Since R is reflexive, so (xRx). Then $[x]_S T [x]_S$. Since x is arbitrary, so T is reflexive on (A/S).

Second, we prove that T is anti-symmetric on (A/S).
Let x, y be arbitrary elements of A s.t. $[x]_S T [y]_S$ and $[y]_S T [x]_S$. Then (xRy) and (yRx). Then (xRy) and ($x R^{-1}$). Then (xSy). Then, $[x]_S = [y]_S$. Thus, T is anti-symmetric on (A/S).

Third, we prove that T is transitive on (A/S).
Let x,y,z be arbitrary elements of A s.t. $[x]_S T [y]_S$ and $[y]_S T [z]_S$. Then (xRy) and (yRz). Since R is transitive, so (xRz). Then $[x]_S T [z]_S$. Thus T is transitive on (A/S).

Hence, T is partial order on (A/S).


Ex-25:
(a) First, we prove that R is reflexive on A.
Let X be an arbitrary element of A. Its clear that $(X,X) \in R$. Thus R is reflexive.

Second, we prove that R is transitive on A.
Let (X,Y) and (Y,Z) be arbitrary elements of R. Then Y has atleast as many elements as X and Z has atleast as many elements as Y, so Z has atleast as many elements as X. Then $(X,Z) \in R$. Thus R is transitive.

Hence R is preorder on A.

(b) S = $R \cap R^{-1}$ = {$(X,Y) \in$ A x A | X and Y has same number of elements}

Since A = $P(I)$ and I has 100 elements, so no element in A contains more than 100 elements.

A/S = {$\emptyset$,
{elements of A containing 1 element},
{elements of A containing 2 elements},
...,
...,
{elements of A containing 100 elements}}
Clearly, A/S contain 101 elements.

And, if (X R Y) then $[X]_S T [Y]_S$. Then
T = {$([X]_S,[Y]_S)$ | Y has atleast as many elements as X}


Ex-26:
(a) First, we prove that R is reflexive on $P$.
Let $F$ be an arbitrary partition on A. It follows from the definition of "refine" that $F$ refines itself. Then $(F,F) \in R$. Since $F$ is arbitrary, so R is reflexive.

Second, we prove that R is anti-symmetric on $P$.
Let $F$ and $G$ be arbitrary partitions on A s.t. $(F,G) \in R$ and $(G,F) \in R$. So $F$ refines $G$ and $G$ refines $F$. Its not possible unless $F = G$. Thus $F = G$. So, R is anti-symmetric.

Third, we prove that R is transitive on $P$.
Let $F$, $G$ and $H$ be arbitrary partitions on A s.t. $(F,G) \in R$ and $(G,H) \in R$. Let X be arbitrary element of $F$, Y be arbitrary element of $G$ and Z be arbitrary element of $H$. Then $X \subseteq Y$ and $Y \subseteq Z$. Then $X \subseteq Z$. Since X and Z are arbitrary, so $F$ refines $H$. Hence $(F,H) \in R$. Thus R is transitive.

Hence, R is partial order on $P$.

(b) ($\rightarrow$) Suppose $S \subseteq T$. Let $[x]_S$ be an arbitrary element of $F$, that is A/S. Let a be an arbitrary element of $[x]_S$. Then $(a,x) \in S$. Since $S \subseteq T$, so $(a,x) \in T$. Thus $a \in [x]_T$. So $[x]_S \subseteq [x]_T$. Since $[x]_T \in A/T$, so $[x]_T \in G$. Since $[x]_S$ is arbitrary, so $F$ refines $G$.
($\leftarrow$) Suppose (A/S) refines (A/T). Let (x,y) be an arbitrary element of S. clearly, $[x]_S = [y]_S$. Since $[x]_S \in A/S$ and (A/S) refines (A/T), so we can choose some $[z]_T \in A/T$ s.t. $[x]_S \subseteq [z]_T$. So $x \in [z]_T$ and hence $(x,z) \in T$. Since $[x]_S = [y]_S$, so $(y,z) \in T$. Since T is equivalence relation, so its symmetric and transitive, thus it follows from $(x,z) \in T$ and $(y,z) \in T$ that $(x,y) \in T$. Since (x,y) is arbitrary so $S \subseteq T$

Thus $S \subseteq T$ iff (A/S) refines (A/T)

(c) First, we prove that $F.G$ is a lower bound of {$F,G$}.
So we need to prove that $(F.G,F) \in R$ and $(F.G,G) \in R$. Let Z be an arbitrary element of $F.G$, then by its definition we can choose some $X \in F$ and $Y \in G$ s.t. $Z = X \cap Y$. Then $Z \subseteq X$ and $Z \subseteq Y$. That means $F.G$ refines $F$ and $G$ both. Thus $(F.G,F) \in R$ and $(F.G,G) \in R$. Hence $F.G$ is a lower bound of set {$F,G$}

Second, we prove that $F.G$ is largest of all the lower bounds of {$F.G$}.
Let $H$ be an arbitrary lower bound of {$F,G$}. Let Z be an arbitrary element of $H$. It follows that we can choose some $X \in F$ and $Y \in G$ s.t. $Z \subseteq X$ and $Z \subseteq Y$. Then $Z \subseteq X \cap Y$. Since $X \cap Y \in F.G$, so $H$ refines $F.G$. Then $(H,F.G) \in R$. Since $H$ is arbitrary so $F.G$ is largest of all lower bounds of {$F,G$}.

Hence $F.G$ is greatest lower bound of {$F,G$}.