How to Prove It - Solutions

Summary

• Equivalence Relation: Suppose $R$ is a relation on a set $A$. Then $R$ is called an equivalence relation on $A$ if it is reflexive, symmetric, and transitive.
• Suppose $A$ is a set and $\mathcal F \subseteq \mathcal P(A)$. We will say that $\mathcal F$ is pairwise disjoint if every pair of distinct elements of $\mathcal F$ are disjoint, or in other words $\forall X \in \mathcal F \forall Y \in \mathcal F(X \ne Y \to X \cap Y = \phi)$. $\mathcal F$ is called a partition of $A$ if it has the following properties:
  • $\cup \mathcal F$ = A.
  • $\mathcal F$ is pairwise disjoint.
  • $\forall X \in \mathcal F(X \ne \phi)$.
• Suppose $R$ is an equivalence relation on a set $A$, and $x \in A$. Then the equivalence class of $x$ with respect to $R$ is the set:
  • $[x]_R = \{ y \in A \, \vert \, yRx \}$. If $R$ is clear from context, then we can use $[x]$ instead of $[x]_R$. The set of all equivalence classes of elements of $A$ is called $A$ modulo $R$, and is denoted $A \, / \, R$. Thus,
  • $A \, / \, R = \{ [x]_R \, \vert \, x \in A \} = \{ X \subseteq A \, \vert \, \exists x \in A(X = [x]_R) \}$.
• Suppose $R$ is an equivalence relation on a set $A$. Then $A \, / \, R$ is a partition of $A$. This is proved using following lemmas:
  • For every $x \in A, x \in [x]$.
  • For every $x \in A$ and $y \in A$, $y \in [x]$ iff $[y] = [x]$.
• Suppose $A$ is a set and $\mathcal F$ is a partition of $A$. Then there is an equivalence relation $R$ on $A$ such that $A \, / \, R = \mathcal F$. It uses the following lemma:
  • Suppose $A$ is a set and $\mathcal F$ is a partition of $A$. Let $R = \cup X \in \mathcal F (X \times X)$. Then $R$ is an equivalence relation on $A$.

Soln1

$\{ \{1\}, \{2\}, \{3\} \}$,
$\{ \{1\}, \{2,3\} \}$,
$\{ \{1,2\}, \{3\} \}$,
$\{ \{1,3\}, \{2\} \}$,
$\{ \{1,2,3\} \}$.

Soln2

For $\mathcal F = \{ \{1\}, \{2\}, \{3\} \}$, $R = \{ (1,1), (2,2), (3,3) \}$
For $\mathcal F = \{ \{1\}, \{2,3\} \}$, $R = \{ (1,1), (2,2), (3,3), (2,3), (3,2) \}$
For $\mathcal F = \{ \{1,2\}, \{3\} \}$, $R = \{ (1,1), (2,2), (1,2), (2,2), (3,3) \}$
For $\mathcal F = \{ \{1,3\}, \{2\} \}$, $R = \{ (1,1), (3,3), (1,3), (3,1), (2,2) \}$
For $\mathcal F = \{ \{1,2,3\} \}$, $R = \{ (1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2), (1,3), (3,1) \}$.

Soln3

(a) Yes it is a equivalence relation. Equivalence classes = $\{ X \subseteq W, X \ne \phi \, \vert \, \text{ if }x \in X \text{ and } w \in W \text{ and}, (w \text{ and } x \text{ both starts with same letter}), \text{ then } w \in X\}$.

(b) It is not an equivalence relation.

(c) This is an equivalence relation. Equivalence classes = $\{ X \subseteq W, X \ne \phi \, \vert \, \text{ if }x \in X \text{ and } w \in W \text{ and}, (w \text{ and } x \text{ both contains same number of letters }), \text{ then } w \in X\}$.

Soln4

(a) It is not a equivalence relation.

(b) It is an equivalence relation. To find equivalence classes, we know that :

1. Difference of two rational numbers is always rational.
2. If we have two real numbers such that one is irrational and other number is rational, then their difference will be irrational.
3. If we have two irrational numbers then either their difference can be rational or irrational.

From the first two points, the equivalence class is all rational numbers: $\{ x \in Q \}$.

Now, from the third point which I got wrong earlier(Thanks William for pointing out. Check his comment for a better desciption), the equivalance classes in this case should be: $\, \{ [x]_S \; \vert \; x \text{ is irrational } \} \,$, where $\, S \,$ is the given relation.

(c) It is an equivalence relation. Its equivalnce classes are: $\{[x] \, \vert \, x \in \mathbb{R} \}$, where $[x] = \{... x \times {10}^{-3}, x \times {10}^{-2}, x \times {10}^{-1}, x \times {10}^{0}, x \times {10}^{1}, x \times {10}^{2}, x \times {10}^{3}, ...\}$ or equivalently $\, \{ x \times {10}^z \; \vert \; z \in \mathbb{Z} \} \,$

Thanks William for pointing out. Earlier I got this wrong: $[x] = \{... x^{-3}, x^{-2}, x^{-1}, x^{0}, x^{1}, x^{2}, x^{3}, ...\}$.

Soln5

We are given that $\mathcal F = \{ P_d \, \vert \, d \in D \}$.

• $\cup \mathcal F = P$:

($\to$). Suppose $x \in \cup \mathcal F$. Thus there exist atleast one set $P_d$, where $d \in D$, such that $x \in P_d$. Thus $x$ is a person must be be born on day $d$. It follows that $x \in P$. Thus $\cup \mathcal F \subseteq P$.

($\leftarrow$). Suppose $x \in P$. Thus $x$ must/will be born on some day $d$. Thus $x \in P_d$. It follows that $x \in cup \mathcal F$. Thus $P \subseteq \cup \mathcal F$.

• $P_{d_1} \cap P_{d_2} = \phi$, where $d_1 \ne d_2$.

Suppose $P_{d_1} \cap P_{d_2} \ne \phi$. Thus there must exist atleast one person who is born on $d_1$ and on $d_2$. But this is not possible for a person to take birth on two different dates. Thus it contradicts the assumption $P_{d_1} \cap P_{d_2} \ne \phi$. Thus $P_{d_1} \cap P_{d_2} = \phi$.

• $\forall X \in \mathcal F(X \ne \phi)$.

Suppose $P_d \in \mathcal F$. We can assume here that there is atleast one person born on every day. Thus atleast one person is born on $P_d$, $P_d \ne \phi$. Thus $\forall X \in \mathcal F(X \ne \phi)$.

Now see that $[x]_B = \{ y \, \vert \, x \text{ and } y \text{ are born on same day } \} = \{ y \, \vert \, x \text{ and } y \text{ are born on some day } d \} = P_d$.

Thus $P \, \ \, B$ satisfies all the conditions of a partition.

Soln6

Suppose $x \in T$. Since all the angles of $x$ are equal to itself, $(x,x) \in S $. Thus$ S $$ is reflexive.

Suppose $(x,y) \in S$. Thus all angles of $x$ are equal to $y$. Or we can also say that all angles of $y$ are equal to $x$, or $(y,x) \in S$. Thus $S$ is symmetric.

Suppose $(x,y) \in S \land (y,z) \in S$. Thus all angles of $x$ are equal to $y$. Also all angles of $y$ are equal to $z$. Thus all angles of $x$ are equal to $z$. Thus $(x,z) \in S$. We can conclude that $S$ is transitive.

Thus $S$ is reflexive, symmetric and transitive, we can conclude that $S$ is equivalence relation.

Soln7

To complete the proof, we need to prove that $R$ is symmetric and transitive.

Suppose $(x,y) \in R$. Since $R = \cup_{X \in \mathcal F}(X \times X)$, it follows that there exist an $X$ such that $(x,y) \in X \times X$. Thus $x \in X$ and $y \in X$. Thus $(y,x) \in X \times X$. It follows that $(y,x) \in \cup_{X \in \mathcal F}(X \times X)$. Thus $(y,x) \in R$. We can conclude that $R$ is symmetric.

Suppose $(x,y) \in R \land (y,x) \in R$. Thus $(x,y) \in X$ and $(y,z) \in Y$ for some $X \in \mathcal F$ and $Y \in \mathcal F$. Thus $x \in X$ and $x \in Y$. Since $\mathcal F$ is a partition of $A$, it follows that $X \cap Y = \phi$. Thus only if $X = Y$, then $x \in X$ and $x \in Y$ is possible. Thus $z \in X \times X$. It follows that $(x,z) \in \cup_{X \in \mathcal F}(X \times X)$. Thus $S$ is transitive.

Soln8

Suppose $A \, / \, R = A \, / \, S$.

($\to$). Suppose $(x,y) \in R$. Since $R$ is equivalence relation, it follows that $y \in [x]_R$ and $[x]_R \in A \, / \, R$. Since $A \, / \, R = A \, / \, S$, it follows that $[x]_R \in A \, / \, S$. Since $S$ is equivalence relation, $x$ must exist in $[x]_S$. Also since $A \, / \, S$ is a partition and $x \in [x]_R$ and $x \in [x]_S$ and $[x]_R \in A \, / \, S$ and $[x]_S \in A \, / \, S$, it follows that $[x]_R = [x[_S$. Since $y \in [x]_R$, it follows $y \in [x]_S$. Thus $(x,y) \in S$. Since $(x,y)$ is arbitrary, it follows that $R \subseteq S$.

($\leftarrow$). Suppose $(x,y) \in S$. Since $S$ is equivalence relation, it follows that $y \in [x]_S$ and $[x]_S \in A \, / \, S$. Since $A \, / \, R = A \, / \, S$, it follows that $[x]_S \in A \, / \, R$. Since $R$ is equivalence relation, $x$ must exist in $[x]_R$. Also since $A \, / \, R$ is a partition and $x \in [x]_R$ and $x \in [x]_S$, it follows that $[x]_R = [x[_S$. Since $y \in [x]_S$, it follows $y \in [x]_R$. Thus $(x,y) \in R$. Since $(x,y)$ is arbitrary, it follows that $S \subseteq R$.

Thus $R \subseteq S$ and $S \subseteq R$, it follows that $R = S$.

Soln9 Since $S$ is an equivalence relation on $\mathcal F$, it follows that $\mathcal F = A \, / \, S$. Since it is given that $\mathcal F = = A \, / \, R$, it follows that $A \, / \, R = A \, / \, S$. Thus by using the result of Soln8, we have $R = S$.

Soln10

(a)

Reflexive:

Suppose $x$ is an integer. Thus $x - x = 0$, or $(x-y) = 0 \times m$. Thus for $k = 0$, $x \equiv x (mod \; m)$. It follows that $(x,x) \in C_m$. Thus $C_m$ is reflexive.

Symmetric:

Suppose $x,y$ are integers such that $(x,y) \in C_m$. Thus $x - y = k \times m$ where $k \in \mathbb Z$. It follows that $-(x-y) = - km$, or $y - x = -k \times m$. Since $k \in \mathbb Z$, it follows $-k \in \mathbb Z$. Thus $(y,x) \in C_m$. It follows that $C_m$ is symmetric.

(b)

Equivalence classes of $C_2$:

$\{..., -3, -1, 1, 3, 5, 7, .... \}$,
$\{..., -2, 0, 2, 4, 6, 8, .... \}$,

Equivalence classes of $C_3$:

$\{...,-2, 1, 4, 7, 10, 13, .... \}$,
$\{...,-1, 2, 5, 8, 11, 14, .... \}$,
$\{...,0, 3, 6, 9, 12, 15, .... \}$,

Clearly there are $m$ equivalence classes of $C_m$.

Soln11

Suppose $n$ is integer, then $n$ is either even or odd. We have following cases:

Case 1: $n$ is even.
Thus $n = 2t$, where $t$ is any integer. It follows that $n^2 = 4t^2$. Thus $4t^2 - 0 = k \times 4$, where $k = t^2$. Thus $4t^2 \equiv 0 (mod \; 4)$, or $n^2 \equiv 0(mod \; 4)$. Thus we can also say $n^2 \equiv 0(mod \; 4) \lor n^2 \equiv 1 (mod \; 4)$.

Case 2: $n$ is odd. Thus $n = 2t + 1$, where $t$ is any natural number. It follows that $n^2 = 4(t^2 + t) + 1$. Thus $4(t^2 + t) + 1 - 1 = k \times 4$, where $k = t^2 + t$. Thus $4(t^2 + t) + 1 \equiv 1 (mod \; 4)$, or $n^2 \equiv 1 (mod \; 4)$. Thus we can also say $n^2 \equiv 0 (mod \; 4) \lor n^2 \equiv 1 (mod \; 4)$.

Thus from both cases, we have $n^2 - 1 \equiv (mod \; 4)$ or $n^2 - 1 \equiv (mod \; 4)$.

Soln12

Suppose $a,b,c,d$ are integers such that $a \equiv c (mod \; m)$ and $b \equiv d(mod \; m)$. Thus we have $a - c = k_1m$ and $b - d = k_2m$. Thus $a = c + k_1m$ and $b = d + k_2m$.

Thus $a + b = c + k_1m + d + k_2m$, which means $a + b = c + d + (k_1 + k_2)m$, or $(a+b) - (c+d) = km$, where $k = k_1 + k_2$. Thus $a+b \equiv (c+d) (mod \; m)$.

Similarly, we have $ab = (c + k_1m)(d + k_2m) = cd + ck_2m + dk_1m + k_1k_2m = cd + (ck_2 + dk_1 + k_1k_1)m$. It follows that $ab - cd = km$ where $k = ck_2 + dk_1 + k_1k_1$. Thus $ab \equiv cd(mod \; m )$.

Soln13

Clearly $S$ is a relation on $B$.

(a)

Suppose $x$ in B. Thus $(x,x) \in B \times B$. Since $B \subseteq A$, and $R$ is reflexive, it follows that $(x,x) \in R$. Thus $(x,x) \in R \cap (B \times B)$. Thus $S$ is reflexive.

Suppose $(x,y) \in S$. Since $S = R \cap (B \times B)$, it follows $(x,y) \in R$ and $(x,y) \in B \times B$. Since $(x,y) \in R$ and $R$ is symmetric, it follows that $(y,x) \in R$. Also since $(x,y) \in B \times B$, it follows $(y,x) \in B \times B$. Thus $(y,x) \in R \land (y,x) \in B \times B$. Thus $(y,x) \in S$. We can conclude that $S$ is symmetric.

Suppose $(x,y) \in S \land (y,z) \in S$. Thus $(x,y) \in R$ and $(y,z) \in R$ and $x,y,z \in B$. Since $R$ is transitive, it follows that $(x,z) \in R$. Also since $x,y,z \in B$, it follows that $(x,z) \in B \times B$. Thus $(x,z) \in R \cap (B \times B)$. Thus $(y,z) \in S$. Thus we can conclude that $S$ is transitive.

Since $S$ is reflexive, symmetric and transitive, it follows that $S$ is equivalence relation.

(b)

Suppose $x \in B$. Since $S$ is an equivalence relation on $B$, it follows that $[x]_S \subseteq B$.

($\to$)Suppose $y \in [x]_S$. It follows that $(y,x) \in S$. Since $S = R \cap (B \times B)$, $(y,x) \in R$, thus, $y \in [x]_R$. Also since $(y,x) \in S$, it follows that $(y,x) \in B \times$, thus, $y \in B$. Thus $y \in [x]_R \cap B$. Since $y$ is arbitrary, it follows that $[x]_S \subseteq [x]_R \cap B$.

($\leftarrow$)Suppose $y \in [x]_R \cap B$. Thus $y \in B$ and $(y,x) \in [x]_R$. Since $x \in B$(given), and $y \in B$, it follows $(y,x) \in B \times B$. Thus we have $(y,x) \in R$ and $(y,x) \in B \times B$, it follows that $(y,x) \in R \cap (B \times B)$. Thus $(y,x) \in S$. It follows that $y \in [x]_S$. Since $y$ is arbitrary, we can conclude that $[x]_R \cap B \subseteq [x]_S$.

Since $[x]_S \subseteq [x]_R \cap B$ and $[x]_R \cap B \subseteq [x]_S$. We can conclude $[x]_S = [x]_R \cap B$.

Soln14

(a)

Suppose $X \in \mathcal P(A)$. Then clearly, $X \triangle X = \phi$. Since $\phi \subseteq B$, it follows that $(X,X) \in R$. Thus $R$ is reflexive.

Suppose $(X,Y) \in R$. Thus $X \triangle Y \subseteq B$. Since $X \triangle Y = Y \triangle X$, it follows $Y \triangle X \subseteq B$. Thus $(Y,X) \in R$. It follows that $R$ is symmetric.

Suppose $(X,Y) \in R \land (Y,Z) \in R$. Suppose $x \in X \triangle Z$. Thus $x \in (X \setminus Z)$ or $x \in Z \setminus X$. Thus we have following possible cases:

• Case 1: $x \in X \setminus Z$ and $x \in Y$. Since $x \in Y \land x \notin Z$, it follows $x \in Y \triangle Z$. Since $(Y,Z) \in R$, it follows $x \in B$.

• Case 2: $x \in X \setminus Z$ and $x \notin Y$.
  Since $x \in X \land x \notin Y$, it follows $x \in X \triangle Y$. Since $(X,Y) \in R$, it follows $x \in B$.

• Case 3: $x \in Z \setminus X$ and $x \in Y$.
  Since $x \in Y \land x \notin X$, it follows $x \in X \triangle Y$. Since $(X,Y) \in R$, it follows $x \in B$.

• Case 4: $x \in Z \setminus X$ and $x \notin Y$.
  Since $x \in Y \land x \notin Z$, it follows $x \in Y \triangle Z$. Since $(Y,Z) \in R$, it follows $x \in B$.

Thus if $x \in X \triangle Z$, then form all the possible cases above $x \in B$. Thus $(X,Z) \subseteq B$. It follows that $(X,Z) \in R$.

Thus $R$ is symmetric.

(b)

Existence:

Suppose $X \in P(A)$. Suppose $Y = X \setminus B$. Clearly $Y \cap B = \phi$ because $Y$ contains only those elements which are in $X$ but not in $B$. Now we will prove that $Y \in [X]_R$. Suppose $x \in X \triangle Y$. Thus we have:

$x \in (X \setminus Y) \lor x \in (Y \setminus X)$ iff.
$(x \in X \land x \notin (X \setminus B)) \lor (x \in (X \setminus B) \land x \notin X)$ iff.
$(x \in X \land \lnot (x \in X \land x \notin B)) \lor ((x \in X \land x \notin B) \land x \notin X)$ iff.
$(x \in X \land (x \notin X \lor x \in B)) \lor (x \in X \land x \notin B \land x \notin X)$ iff.
Since $x \in X \land x \notin X$ is always false.
$x \in X \land (x \notin X \lor x \in B)$ iff.
$(x \in X \land x \notin X) \lor (x \in X \land x \in B)$ iff.
Since $x \in X \land x \notin X$ is always false.
$x \in X \land x \in B$

Thus if $x \in X \triangle Y$, then $x \in B$. Thus if $Y = X \setminus B$, then $X \triangle Y \subseteq B$. And we already prove that for $Y = X \setminus B$, $Y \cap B = \phi$.

Uniqueness:

Suppose $Y, Z \in \mathcal P(A)$, and $Y \in [X]_R$ and $Z \in [X]_R$ and $Y \cap B = Z \cap B = \phi$ such that $Y \ne Z$. First we will prove that $Y$ and $Z$ are not empty. Suppose $Y$ is empty. Thus $X \triangle \phi \subseteq B$. But $X \triangle \phi = X$. Thus $X \subseteq B$. Since $X$ is arbitrary, it follows $\forall X \in \mathcal P(A) (X \subseteq B)$. Since $A \in P(A)$, it follows $A \subseteq B$. But it contradicts with the given that $B \subseteq A$. Thus $Y$ is not empty. Similarly we can show that $Z$ is not empty.

Since $R$ is symmetric and $YRX$, thus $XRY$. Since $R$ is transitive and $ZRX \land XRY$, it follows $ZRY$. Thus $Z \triangle Y \subseteq B$. This is true for $Y = Z$, but that is not that the case since we assumed $Y = Z$. Since $Y$ and $Z$ are not empty, we have following possible cases: Suppose $x \in Z \triangle Y$. Thus either $x \in Z \setminus Y$ or $x \in Y \setminus Z$. Thus we have following cases:

• Case 1: $x \in Z \setminus Y$
  Thus $x \in Z$. Since $x \in Z$ and we have from above that $Z \cap B = \phi$, it follows that $x \notin B$.

• Case 2: $x \in Y \setminus Z$
  Thus $x \in Y$. Since $x \in Y$ and we have from above that $Y \cap B = \phi$, it follows that $x \notin B$.

Thus from both cases if $x \in Y \triangle Z$ then $x \notin B$. Thus $(Y,Z) \notin R$. But it contradicts with $(Y,Z) \in R$. Thus the assumtion that $Y \ne Z$ is wrong. Thus $Y = Z$.

Thus there exist a unique $Y$ such that $Y \in [X]_R$ and $Y \cap B = \phi$.

Soln15

To Prove $\mathcal F \cup \mathcal G$ is a partition of $A \cup B$, we need to prove the following three things:

• $\cup (\mathcal F \cup \mathcal G) = A \cup B$.
• if $X \in (\mathcal F \cup \mathcal G)$ and $Y \in (\mathcal F \cup \mathcal G)$ and $X \ne Y$, then $X \cap Y = \phi$.
• $\forall X \in (\mathcal F \cup \mathcal G)(X \ne \phi )$.

Following are the proofs for each of them:

Proof of $\cup (\mathcal F \cup \mathcal G) = A \cup B$.

($\to$)Suppose $x \in \cup (\mathcal F \cup \mathcal G)$. Thus there exist an $X \in (\mathcal F \cup \mathcal G)$ such that $x \in X$. Since $X \in (\mathcal F \cup \mathcal G)$, it follows that either $X \in \mathcal F$ or $X \in \mathcal G$. Thus we have the following cases:

• Case 1: $X \in \mathcal F$. Since $x \in X$ and $X \in \mathcal F$, it follows that $x \in \cup \mathcal F$. Since $\mathcal F$ is a partition on $A$, $\cup \mathcal F = A$. Thus $x \in A$. Or we can also say $x \in A \cup B$.

• Case 2: $X \in \mathcal G$. Since $x \in X$ and $X \in \mathcal G$, it follows that $x \in \cup \mathcal G$. Since $\mathcal G$ is a partition on $B$, $\cup \mathcal G = B$. Thus $x \in B$. Or we can also say that $x \in A \cup B$.

Thus if $x \in \cup (\mathcal F \cup \mathcal G)$, then $x \in A \cup B$. Thus $\cup (\mathcal F \cup \mathcal G) \subseteq (A \cup B)$.

($\leftarrow$)Suppose $x \in (A \cup B)$. Since $\cup \mathcal F = A$ and $\cup \mathcal G = B$, it follows that either $x \in \cup \mathcal F$ or $x \in \cup \mathcal G$. Thus we can also say $x \in (\cup \mathcal F) \cup (\cup \mathcal G)$, which is equivalent to $x \in \cup (\mathcal F \cup \mathcal G)$. Since $x$ was arbitrary, it follows that $A \cup B \subseteq \cup (\mathcal F \cup \mathcal G)$.

Since $\cup (\mathcal F \cup \mathcal G) \subseteq (A \cup B)$ and $A \cup B \subseteq \cup (\mathcal F \cup \mathcal G)$, it follows that $A \cup B \subseteq = (\mathcal F \cup \mathcal G)$.

Proof of: if $X \in (\mathcal F \cup \mathcal G)$ and $Y \in (\mathcal F \cup \mathcal G)$ and $X \ne Y$, then $X \cap Y = \phi$.

Suppose $X \in (\mathcal F \cup \mathcal G)$ and $Y \in (\mathcal F \cup \mathcal G)$ and $X \ne Y$. Thus we have following possible cases:

• Case 1: $X \in \mathcal F$ and $Y \in \mathcal F$

Since $X \ne Y$ and $\mathcal F$ is a partition on $A$, it follows that $X \cap Y = \phi$.

• Case 2: $X \in \mathcal G$ and $Y \in \mathcal F$

Since $\mathcal G$ is a partition on $B$, it follows that $X \subseteq B$. Similarly since $\mathcal F$ is a partition on $A$, it follows that $Y \subseteq A$. Since $A \cap B = \phi$, it follows that $X \cap Y = \phi$.

• Case 3: $X \in \mathcal G$ and $Y \in \mathcal G$

Since $X \ne Y$ and $\mathcal G$ is a partition on $B$, it follows that $X \cap Y = \phi$.

• Case 4: $X \in \mathcal F$ and $Y \in \mathcal G$

Since $\mathcal F$ is a partition on $A$, it follows that $X \subseteq A$. Similarly since $\mathcal G$ is a partition on $B$, it follows that $Y \subseteq B$. Since $A \cap B = \phi$, it follows that $X \cap Y = \phi$.

Thus from all the cases above $X \cap Y = \phi$.

Proof of $\forall X \in (\mathcal F \cup \mathcal G)(X \ne \phi )$.

Suppose $X \in (\mathcal F \cup \mathcal G)$. Thus either $X \in \mathcal F$ or $X \in \mathcal G$. If $X \in \mathcal F$, then $X \ne \phi$ because $\mathcal F$ is a partition on $A$. Similarly if $X \in \mathcal G$, $X \ne \phi$ since $\mathcal G$ is a partition on $B$.

Soln16

(a) Since $R$ is an equivalence relation on $A$, it follows that $A \, / \, R$ is a partition of $A$. Similarly since $S$ is an equivalence relation on $B$, it follows that $B \, / \, S$ is a partition of $B$. Thus we have $A \, / \, R$ is a partition of $A$ and $B \, / \, S$ is a partition of $B$ and $A \land B$ are disjoint, then from the soln15, it follows that $(A \, / \, R) \cup (B \, / \, S)$ is a partition of $A \cup B$. We know that from theorems in this section that if $A \, / \, R$ is a partition of $A$, then $R$ is an equivalence relation on $A$. Thus, since $(A \, / \, R) \cup (B \, / \, S)$ is a partition on $A \cup B$, it follows that $R \cup S$ is an equivalence relation on $A \cup B$.

(b)

Suppose $x \in A$.

($\to$)Suppose $y \in [x]_{R \cup S}$. Thus $(y,x) \in (R \cup S)$. It follows that $(y,x) \in R$ or $(y,x) \in S$. Since $A \cap B = \phi$ and $x \in A$, it follows that $x \notin B$. Since $S$ is a relation on $B$ and $x \notin B$, it follows that $(y,x) \notin S$. Thus $(y,x) \in R$, or $y \in [x]_R$. Since $y$ is arbitrary, it follows that $[x]_{R \cup S} \subseteq [x]_R$.

($\leftarrow$)Suppose $y \in [x]_R$. Thus $(y,x) \in R$. Since $x \in A$, it follows that $x \in (A \cup B)$. Since $(y,x) \in R$, it follows $y \in A$. Thus $y \in A \cup B$. Thus we can also say that $(y,x) \in (R \cup S)$, where $y,x \in (A \cup B)$. Thus $y \in [x]_{R \cup S}$. Since $y$ is arbitrary, it follows that $[x]_R \subseteq [x]_{R \cup S}$.

Since $[x]_{R \cup S} \subseteq [x]_R$ and $[x]_R \subseteq [x]_{R \cup S}$, it follows that $[x]_R = [x]_{R \cup S}$.

Proof of if $x \in B$, then $[x]_S = [x]_{R \cup S}$ is exactly similar.

(c)

($\to$)Suppose $X \in (A \cup B) \, / \, (R \cup S)$. Suppose $x \in X$. Since $R \cup S$, is an equivalence relation on $A \cup B$, it follows $X = [x]_{R \cup S}$. Since $X \in (A \cup B) \, / \, (R \cup S)$, it follows $X \subseteq (A \cup B)$. Thus $x \in A \cup B$. It follows that either $x \in A$ or $x \in B$. If $x \in A$, then from part(b), $[x]_{R \cup S} = [x]_R$. Similarly if $x \in B$, then from part(b) $[x]_S = [x]_{R \cup S}$. Thus $[x]_{R \cup S} = [x]_R$ or $[x]_{R \cup S} = [x]_S$. Since $X = [x]_{R \cup S}$, it follows that either $X = [x]_R$ or $X = [x]_S$. If $X = [x]_R$, then $X \in (A \, / \, R)$ because $[x]_R \in (A \, / \, R)$. Similarly if $X = [x]_S$, then $X \in (B \, / \, S)$ because $[x]_S \in (B \, / \, S)$. Thus $X \in (A \, / \, R) \cup (B \, / \, S)$. Since $X$ is arbitrary, it follows that $(A \cup B) \, / \, (R \cup S) \subseteq (A \, / \, R) \cup (B \, / \, S)$.

($\leftarrow$)Suppose $X \in (A \, / \, R) \cup (B \, / \, S)$. Suppose $x \in X$. Thus either $X \in (A \, / \, R)$ or $X \in (B \, / \, S)$. If $X \in (A \, / \, R)$, then $X = [x]_R$, then from part(b), $X = [x]_{R \cup S}$. Similarly if $X \in (B \, / \, S)$, then $X = [x]_{R \cup S}$. Thus from both cases $X = [x]_{R \cup S}$. Since $R \cup S$ is equivalence relation on $A \cup B$, it follows that $X \in (A \cup B) \, / \, (R \cup S)$. Thus $(A \, / \, R) \cup (B \, / \, S) \subseteq (A \, / \, R) \cup (B \, / \, S)$.

Thus from both directions, $(A \cup B) \, / \, (R \cup S) = (A \, / \, R) \cup (B \, / \, S)$.

Soln17

Proof of $\cup \mathcal F \cdot \mathcal G = A$.

($\to$)Suppose $x \in \cup \mathcal F \cdot \mathcal G$. Thus there exist an $T$ in $\mathcal F \cdot \mathcal G$ such that $x \in T$. Thus $T \in \mathcal P(A)$. This follows that $T \subseteq A$. Since $x \in T$, $x \in A$. Thus $\cup \mathcal F \cdot \mathcal G \subseteq A$.

($\leftarrow$)Suppose $x \in A$. Since $\mathcal F$ is a partition on $A$, it follows that there exist an $X \in \mathcal F$ such that $x \in X$. Similarly since $\mathcal G$ is a partition on $B$, it follows that there exist a $Y \in \mathcal G$, such that $x \in Y$. Thus $x \in X \land x \in Y$, or $x \in X \cap Y$. If $T = X \cap Y$, then $T \in \mathcal F \cdot \mathcal G$. Since $x \in T$ and $T \in \mathcal F \cdot \mathcal G$, it follows that $x \in \cup (\mathcal F \cdot \mathcal G)$. Thus $A \subseteq (\cup \mathcal F \cdot \mathcal G)$.

Thus from both sides, $\cup \mathcal F \cdot \mathcal G = A$.

Proof of $\mathcal F \cdot \mathcal G$ is pairwise disjoint.

Suppose $T_0 \in \mathcal F \cdot \mathcal G$ and $T_0 \in \mathcal F \cdot \mathcal G$ such that $T_0 \ne T_1$. Thus there exist $X_0 \in \mathcal F$ and $Y_0 \in \mathcal G$ such that $T = X_0 \cap Y_0$. Similarly there must be $X_1 \in \mathcal F$ and $Y_1 \in \mathcal G$ such that $T_1 = X_1 \cap Y_1$. Since $\mathcal F$ is a partition, it follows $X_0 \cap X_1 = \phi$. Similarly $Y_0 \cap Y_1 = \phi$. Suppose $T_0 \cap T_1 \ne \phi$. Thus there exist an $x$ such that $x$ in $T_0 \cap T_1$. Thus $x \in X_0 \cap Y_0$ and $x \in X_1 \cap Y_1$. Thus $x \in X_0 \cap X_1$. Thus $X_0 \cap X_1 \ne \phi$. This is a contradiction thus $T_0 \cap T_1 = \phi$.

Proof of $\forall X \in \mathcal F \cdot \mathcal G (X \ne \phi)$. This is clear from the definition of $\mathcal F \cdot \mathcal G$.

Thus $\mathcal F \cdot \mathcal G$ is a partition of $A$.

Soln18

$\mathcal F \cdot \mathcal G = \{ \mathbb R^- \cap \mathbb Z, \mathbb R^- \cap \mathbb (R \setminus Z), \mathbb R^+ \cap \mathbb Z, \mathbb R^+ \cap \mathbb (R \setminus Z), 0 \cap \mathbb Z, 0 \cap \mathbb (R \setminus Z) \}$.
$\leftrightarrow \mathcal F \cdot \mathcal G = \{ Z^-, (R^- \setminus Z), Z^+, (R^+ \setminus Z), \{0\}, \{0\} \}$.
$\leftrightarrow \mathcal F \cdot \mathcal G = \{ Z^-, (R^- \setminus Z), Z^+, (R^+ \setminus Z), \{0\} \}$.

Soln19

(a)

Proof of $R \cap S$ is reflexive

Suppose $x \in A$. Since $R$ is reflexive, it follows that $(x,x) \in R$. Similarly since $R$ is reflexive, it follows that $(x,x) \in S$. Thus $(x,x) \in R \cap S$. Thus $R \cap S$ is reflexive.

Proof of $R \cap S$ is symmetric

Suppose $(x,y) \in R \cap S$. Thus $(x,y) \in R$ and $(x,y) \in S$. Since $R$ and $S$ are both symmetric, it follows that $(y,x) \in R \cap S$. Thus $R \cap S$ is symmetric.

Proof of $R \cap S$ is transitive

Suppose $(x,y) \in R \cap S$ and $(y,z) \in R \cap S$. Thus $(x,y) \in R \land (y,z) \in S$. Since $R$ is transitive, it follows that $(x,z) \in R$. Similarly since $(x,y) \in S \land (y,z) \in S$ and $S$ is transitive, it follows that $(x,z) \in S$. Thus we have $(x,z) \in R \cap S$. Thus $R \cap S$ is transitive.

Since $R \cap S$ is reflexive, symmetric and transitive, it follows that $R \cap S$ is equivalence relation.

(b)

Suppose $x \in A$.

($\to$)Suppose $y \in [x]_T$. Thus $(y,x) \in (R \cap S)$. Thus $(y,x) \in R$ and $(y,x) \in S$. Since $R$ is equivalence relation on $A$ and $x \in A$ and $(y,x) \in R$, it follows that $y \in [x]_R$. Similarly since $S$ is equivalence relation on $A$ and $x \in A$ and $(y,x) \in S$, it follows that $y \in [x]_S$. Thus $y \in [x]_R \cap [x]_S$. Thus $[x]_T \subseteq [x]_R \cap [x]_S$.

($\leftarrow$)Suppose $y \in [x]_R \cap [x]_S$. Thus $(y,x) \in R$ and $(y,x) \in S$. Thus $(y,x) \in R \cap S$. Since $R \cap S$ is an equivalence relation on $A$ and $x \in A$ and $(y,x) \in R \cap S$, it follows that $y \in [x]_{R \cap S}$, or $y \in [x]_T$. Thus $[x]_R \cap [x]_S \subseteq [x]_T$.

Since $[x]_T \subseteq [x]_R \cap [x]_S$ and $[x]_R \cap [x]_S \subseteq [x]_T$, it follows that $[x]_T = [x]_R \cap [x]_S$.

(c)

Suppose $X \in A \, / \, T$. Thus we have:

$X \in A \, / \, T$. iff
$\exists x \in A (X = [x]_T)$. iff
Since from last part, if $x \in A$ then $[x]_T = [x]_R \cap [x]_S$, we have:
$\exists x \in A (X = [x]_R \cap [x]_S)$. iff
$X \in (A \, / \, R) \land X \in (A \, / \, S)$. iff
$X \in ( A \, / \, R) \cdot ( A \, / \, S)$.

Since $X$ is arbitrary, it follows that $A \, / \, T = (A \, / \, R) \cdot (A \, / \, S)$.

Soln20

Proof of $\cup (\mathcal F \otimes \mathcal G) = A \times B$.

($\to$)Suppose $(x,y) \in \cup (\mathcal F \otimes \mathcal G)$. Thus there exist an element $Z \in \mathcal F \otimes \mathcal G$ such that $(x,y) \in Z$. Since $Z \in P(A) \times P(B)$, it follows that there exist an $X \in \mathcal P(A)$ and $Y \in \mathcal P(B)$ such that $Z = X \times Y$. Since $X \in \mathcal P(A)$, $X \subseteq A$. Similarly since $Y \in \mathcal P(B)$, $Y \subseteq B$. Thus $(x,y) \in A \times B$. Thus $\cup (\mathcal F \otimes \mathcal G) \subseteq A \times B$.

($\leftarrow$)Suppose $(x,y) \in A \times B$. Thus for some set, say, $X \subseteq A$, $x \in X$. Similarly for some set $Y \subseteq B$, $y \in Y$. Thus $(x,y) \in X \times Y$. Thus $(x,y) \in Z$ where $Z \in \mathcal P(A) \times \mathcal P(A)$. Thus $(x,y) \in \cup (\mathcal F \otimes \mathcal G)$. Thus $A \times B \subseteq \cup (\mathcal F \otimes \mathcal G)$.

Proof of $\mathcal F \otimes \mathcal G$ is pairwise disjoint.

Suppose $Z_1 \in \mathcal F \otimes \mathcal G$ and $Z_2 \in \mathcal F \otimes \mathcal G$ and $Z_1 \ne Z_2$. We will prove by contradiction. Suppose $Z_1 \cap Z_2 \ne \phi$. Thus there atleast exist a pair $(x,y)$ such that $(x,y) \in Z_1$ and $(x,y) \in Z_2$. Since $Z_1 \in \mathcal F \otimes \mathcal G$, it follows that for some $X_1 \in \mathcal F$ and $Y_1 \in \mathcal G$, $Z_1 = X_1 \times Y_1$. Similarly since $Z_2 \in \mathcal F \otimes \mathcal G$, it follows that for some $X_2 \in \mathcal F$ and $Y_2 \in \mathcal G$, $Z_2 = X_2 \times Y_2$. Since $(x,y) \in Z_1$ and $Z_1 = X_1 \times Y_1$, it follows that $x \in X_1$ and $y \in Y_1$. Similarly since $(x,y) \in Z_2$, it follows that $x \in X_2$ and $y \in Y_2$. Thus $x \in X_1 \cap X_2$ and $y \in Y_1 \cap Y_2$. Since $X_1 \in \mathcal F$ and $\mathcal F$ is a partition on $A$, ans since $x$ exist in both $X_1$ and $X_2$, it follows that $X_1 = X_2$. Similarly $Y_1 \in \mathcal G$ and $Y_2 \in \mathcal G$, and $\mathcal G$ is a partition on $B$, it follows that $Y_1 = Y_2$. Since $Z_1 = X_1 \times Y_1$ and $Z_2 = X_2 \times Y_2$, it follows that $Z_1 = Z_2$ because $X_1 = X_2$ and $Y_1 = Y_2$. This contradicts with $Z_1 \ne Z_2$. Thus $Z_1 \cap Z_2 = \phi$.

Proof of $\forall Z \in (\mathcal F \otimes \mathcal G)(Z \ne \phi)$.

Suppose $Z \in \mathcal F \otimes \mathcal G$. Thus for some $X \in \mathcal F$ and $Y \in \mathcal G$, $Z = X \times Y$. Since $\mathcal F$ is a partition on $A$, it follows that $X \ne \phi$. Similarly since $\mathcal G$ is a partition on $B$, $Y \ne \phi$. Thus $Z \ne \phi$. Since $Z$ is arbitrary, it follows that $\forall Z \in (\mathcal F \otimes \mathcal G)(Z \ne \phi)$.

Soln21

$\mathcal F \otimes \mathcal F = \{ R^- \times R^-, R^- \times R^+, R^- \times 0, R^+ \times R^-, R^+ \times R^+, R^+ \times 0, 0 \times R^-, 0 \times R^+, \{ 0 \times 0 \} \}$.

$R^- \times R^-$: Bottom left quadrant.
$R^- \times R^+$: Top Right quadrant.
$R^- \times 0$: Negative $x$ axis
$R^+ \times R^-$: Bottom left quadrant.
$R^+ \times R^+$: Top left quadrant.
$R^+ \times 0$: Positive $x$ axis
$0 \times R^-$: Negative $y$ axis
$0 \times R^+$: Positive $y$ axis.
$0 \times 0$: Origin

Soln22

(a)

Reflexive

Suppose $(x,y) \in A \times B$. Thus $x \in A$ and $y \in B$. Since $R$ is equivalence relation on $A$, it follows that $(x,x) \in R$. Similarly since $S$ is equivalence relation on $B$, it follows $(y,y) \in S$. Thus $((x,y),(x,y)) \in T$ because $xRx$ and $yRy$. Thus $T$ is reflexive.

Symmetric

Suppose $((x,y),(x',y')) \in T$. Thus $xRx'$ and $ySy'$. Since $R$ and $S$ are symmetric, it follows that $x'Rx$ and $y'Ry$. Thus $((x',y'),(x,y)) \in T$. Thus $T$ symmetric.

Transitive

Suppose $((x,y),(x',y')) \in T$ and $((x',y'),(x'',y'')) \in T$. Thus $(x,x') \in R$, $(x',x'') \in R$, $(y,y') \in S$, $(y',y'') \\in S$. Since $(x,x') \in R$ and $(x',x'') \in R$, it follows that $(x,x'') \in R$ because $R$ is transitive. Similarly since $(y,y') \in S$ and $(y',y'') \in S$, it follows that $(y,y'') \in S$ because $S$ is transitive. Thus $((x,y),(x'',y'')) \in T$. Thus $T$ is transitive.

(b)

Suppose $a \in A, b \in B$. Suppose $(x,y) \in [(a,b)]_T$. Thus,

$(x,y) \in [(a,b)]_T$. iff
$((x,y),(a,b)) \in T$. iff
$xRa \land ySb$. iff
$x \in [a]_R \land y \in [b]_S$. iff
$(x,y) \in [a]_R \times [b]_S$.

Since $(x,y)$ is arbitrary, it follows that $[(a,b)]_T = [a]_R \times [b]_S$.

(c)

Suppose $Z \in (A \times B)/T$. Thus,

$Z \in (A \times B)/T$. iff
$\exists (x,y) \in A \times B (Z = [(x,y)]_T)$. iff
Using part(b),
$\exists (x,y) \in A \times B (Z = ([x]_R \times [y]_S))$. iff
Since $[x]_R \in A/R$ and $[y]_S \in B/R$ and using the definition of $\mathcal F \otimes \mathcal G$.
$Z \in (A/R) \otimes (B/S)$

Since $Z$ is arbitrary, it follows that $(A \times B)/T = (A/R) \otimes (B/R)$.

Soln23

(a)

For uniqueness proofs, we need to prove two things: Existence and Uniqueness.

We shall prove this using the following strategy: $\exists x (P(x) \land \forall y (P(y) \to y = x) )$. Here $P(x)$ denotes there is a relation $T$ such that $[x]_S T [y]_S \leftrightarrow xRy$.

To understand what it means by compatible:
Suppose $x,y,x',y' \in A$ such that $xSx'$ and $ySy'$. Then if $xRy$ iff $x'Ry'$.

Existence:

Suppose $T = \{ (X,Y) \in A/S \times A/S \, \vert \, \exists x \in X \exists y \in Y (xRy) \}$.

Suppose $R$ is compatible with $S$.

($\to$)Suppose $[x]_S T [y]_S$. Thus by our definition of $T$, $\exists x' \in [x]_S \land y' \in [y]_S (x'Ry')$. Thus $x'Sx \land y'Sy$ and $xRy$. Because $R$ is compatible with $S$ and $x'Rx and y'Ry$ and $x'Ry'$, it follows that $xRy$. Thus $([x]_S T [y]_S) \to xRy$.

($\leftarrow$)Suppose $x,y \in A$ such that $xRy$. Since $S$ is an equivalence relation, we have $x \in [x]_S, y \in [y]_S$. Thus $\exists x \in [x]_S \exists y \in [y]_S (xRy)$. Thus we can also say $[x]_S T [y]_S$. Thus $xRy \to ([x]_S T [y]_S)$.

Thus from both directions we have: $([x]_S T [y]_S) \leftrightarrow xRy$.

Uniqueness:

Suppose that there is some relation $T'$ such that $[x]_S T' [y]_S \to xRy$. Now we will prove that $T' = T$ for proving uniqueness. Suppose $x,y \in A$ such that $[x]_S T' [y]_S$ is true. It follows that $xRy$ must be true. Since $x \in A$ and $y \in A$ and $S$ is a equivalence relation, it follows that $[x]_S \in A/S$ and $[y]_S \in A/S$. Also we know that $x \in [x]_S$ and $y \in [y]_S$. Since $xRy$, thus there atleast exist an element in $[x]_S$ and there exist atleast an element in $[y]_S$ such that $xRy$. Thus we can also say, $\exists x' \in [x]_S \exists y' \in [y]_S (x' R y')$. But this is same as relation $T$. Thus $T' = T$.

Note: Not sure about the correctness of this proof.

(b)

Suppose $x,y,x',y' \in A$ such that $xSx'$ and $ySy'$. Thus $xRy$ iff $[x]_S T [y]_S$. Since $S$ is equivalence relation, $[x]_S =[x′]_S$. Also $[y]_S = [y′]_S$. Thus $xRy$ iff $[x′]_S T [y′]_S$. But $[x′]_S T [y′]_S$, iff $x′Ry′$. Thus $xRy$ iff $x'Ry'$.

Soln24

(a)

Reflexive

Suppose $x$ in $A$. Since $R$ is reflexive, $(x,x) \in R$. Thus $(x,x) \in R^{-1}$. Thus $(x,x) \in R \cap R^{-1}$. Thus $R \cap R^{-1}$ is reflexive.

Symmetric

Suppose $(x,y) \in R \cap R^{-1}$. Thus $(x,y) \in R$ and $(x,y) \in R^{-1}$. Since $R$ and $R^{-1}$ are inverse of each other, and $(x,y) \in R$ and $(x,y) \in R^{-1}$, it follows that $(y,x) \in R^{-1}$ and $(y,x) \in R$. Thus $(y,x) \in R^{-1} \cap R$, or $(y,x) \in R \cap R{-1}$. Thus $R \cap R{-1}$ is symmetric.

Transitive

Suppose $(x,y) \in R \cap R{-1} \land (y,z) \in R^{-1} \cap R$. Thus $(x,y)$ in $R^{-1} \land (y,z) \in R^{-1}$ and $(x,y)$ in $R \land (y,z) \in R$. Since $R$ is transitive, it follows $(x,z)$ in $R$. Since $R$ is transitive, it follows that $R^{-1}$ is also transitive, Thus since $(x,y)$ in $R^{-1} \land (y,z) \in R^{-1}$, it follows $(x,z) \in R^{-1}$. Thus $(x,z) \in R \cap R^{-1}$. Thus $R \cap R^{-1}$ is transitive.

Since $R \cap R^{-1}$ is reflexive, symmetric and transitive, it follows that $R \cap R^{-1}$ is an equivalence relation.

(b)

From Soln23(a), we know that if $R$ is compatible with $S$, then there exist a unique relation $T$ such that $[x]_S T [y]_S$. Thus if we prove that $R$ is compatible with $S$, then such relation exist can be followed from Soln23(a).

Suppose $x,y,x',y' \in A$ such that $xSx'$ and $ySy'$.

($\to$)Suppose $(x,y) \in R$. Since $xSx'$, it follows $x'Sx$. Since $S = R \cap R^{-1}$, it follows that $(x',x) \in R$. Since $(x',x) \in R$ \land $(x,y) \in R$, and $R$ is transitive, it follows that $(x',y) \in R$. Since $ySy'$, it follows $(y,y') \in R$. Since $R$ is transitive, it follows $(x',y') \in R$. Thus $xRy \to x'Ry'$.

($\leftarrow$)Suppose $(x',y') \in R$. Then it can be proved similarly that $x'Ry' \to xRy$.

Thus from both direction we have $xRy \leftrightarrow x'Ry'$. Thus we can conclude that if $xSx' \land ySy'$, then $xRy \leftrightarrow x'Ry'$. Thus $R$ is compatible with $S$.

(c)

To prove $T$ partial order on $A/S$, we need to prove that $T$ is reflexive, transitive and antisymmetric.

Reflexive:/u>

Suppose $X \in A/S$. Since $S$ is equivalence relation, $X \ne \phi$. Suppose $x \in X$. Thus $x = [x]_S$. Since $R$ is reflexive, it follows $xRx$. Thus $[x]_S T [x]_S$. Thus $X$ is reflexive.

Transitive

Suppose $X,Y,Z \in A/S$ such that $XTY \land YTZ$. Suppose $x \in X, y \in Y, z \in Z$. Thus $X = [x]_S, Y = [y]_S, Z = [z]_S$. Since $[x]_S T [y]_S$, it follows $xRy$. Similarly since $[y]_S T [z]_S$ it follows $yRz$. Since $R$ is transitive, it follows $xRz$. Since $xRz$ it follows $[x]_S T [z]_S$. Thus $XTZ$. Thus $T$ is transitive.

Antisymmetric

Suppose $X,Y \in A/S$ such that $XTY \land YTX$. Suppose $x \in X \land y \in Y$. Thus $x \in [x]_S$ and $y \in [y]_S$. Since $[x]_S T [y]_S$, it follows $xRy$. Similarly since $[y]_S T [x]_S$, it follows $yRx$. Since $yRx$, it follows that $xR^{-1}y$. Thus we have $(x,y) \in R$ and $(x,y) \in R^{-1}$. Thus $(x,y) \in R \cap R^{-1}$. Thus $(x,y) \in S$. Since $S$ is an equivalence relation, it follows that $[x]_S = [y]_S$. Thus $X = Y$. Thus $T$ is antisymmetric.

Soln25

(a)

To prove that $R$ is preorder we need to prove that $R$ is reflexive and transitive.

Suppose $X \in A$. Thus $(X,X) \in R$ since $X$ has atleast as many elements as $X$. Thus $R$ is reflexive.

Suppose $X,Y,Z \in A$ such that $(X,Y) \in A \land (Y,Z) \in A$. Thus $Y$ has atleast as many elements as $X$. Also $Z$ has atleast as many elements as $Y$. Thus $Z$ has atleast as many elements as $X$. Thus $(X,Z) \in R$. Thus $R$ is transitive.

Since $R$ is reflexive and transitive, it follows that $R$ is preorder.

(b)

Since $S = R \cap R^{-1}$, it follows that $S = \{ (X,Y) \in A \times A \, \vert \, X and Y contains same number of elements. \}$.

Since $S$ is an equivalence relation as prove in Soln24, $A\S$ is a partition of $A$ on $S$ with every parition containing equal number of elements. Also since $S$ creates a partioton on $A$, no set in the partition is empty. Thus we will have many paritions with each partition containing sets with equal number of elements.

Now consider $T$, which is a partial order on $A/S$. Suppose $[X]_S T [Y]_S$. It follows that $XRY$. Thus $Y$ contains atleast as many elements as $X$. Also since all elements of $[X]_S$ have same number of elements, it follows that all the elements of $[Y]_S$ will have atleast same number of elements as all elements of $[X]_S$. Thus partial order is giving a order to these sets, with initially only those sets having one element followed by the set having two, … and so on.

Suppose $X,Y \in A$. Then either $(X,Y) \in R$ or $(Y,X) \in R$. Thus either $[X]_S T [Y]_S$ or $[Y]_S T [X]_S$. Thus $T$ is a total order.

$A/S$ contains the maximum number of elements that $A$ can have. I am not sure about the number. As I am not sure of the notation $A = \mathcal P(I)$. It seems like $A$ may contain maximum 100 elements. but need to confirm this.

Soln26

(a)

Reflexive:

Suppose $\mathcal F \in P$. Suppose $X \in \mathcal F$. Thus $X \subseteq X$. Thus $(\mathcal F, \mathcal F) \in R$. Thus $R$ is reflexive.

Transitive:

Suppose $\mathcal F, \mathcal G, \mathcal H \in P$ such that $(\mathcal F, \mathcal G) \in R$ and $(\mathcal G, \mathcal H) \in R$. Thus for every set $X \in \mathcal F$, there exist a set $Y \in \mathcal G$ such that $X \subseteq Y$. Similarly for every set $S \in \mathcal G$, there exist a set $T \in \mathcal H$, such that $S \subseteq T$. Thus clearly it follows that for every set $X \in \mathcal F$ there exist a set $Y \in \mathcal H$, such that $X \subseteq Y$. Thus $(\mathcal F, \mathcal H) \in R$. Thus $R$ is transitive.

Antisymmetric:

Suppose $\mathcal F, \mathcal G \in P$ such that $(\mathcal F, \mathcal G) \in R$ and $(\mathcal G, \mathcal F) \in R$. Thus $\forall X \in \mathcal F \forall Y \in \mathcal G(X \subseteq Y)$ and $\forall X \in \mathcal G \forall Y \in \mathcal F(X \subseteq Y)$. This is possible only if $\mathcal F = \mathcal G$. Thus $R$ is antisymmetric.

Since $R$ is reflexive, transitive and antisymmetric, it follows that $R$ is partial order.

(b)

($\to$)Suppose $S \subseteq T$. Suppose $x \in A$. Thus $[x]_S \in \mathcal F$ and $[x]_T \in \mathcal G$. Suppose $y \in [x]_S$. Thus $(y,x) \in S$. Since $S \subseteq T$, it follows $(y,x) \in T$. Thus $(y,x) \in [x]_T$. Since $y$ is arbitrary, it follows that $[x]_S \subseteq [y]_T$. Since $x$ is arbitrary, it follows that $\forall X \in \mathcal F \forall Y \in \mathcal G(X \subseteq Y)$. Thus $\mathcal F$ refines $\mathcal G$.

($\leftarrow$)Suppose $\mathcal F$ refine $\mathcal G$. Suppose $X \in \mathcal F$ is an arbitrary partition in $\mathcal F$. Since $\mathcal F$ refines $\mathcal G$, suppose $Y \in \mathcal G$, such that $X \subseteq Y$. Suppose $y \in Y$. Thus $Y = [y]_T$. Since $X \subseteq Y$, $y \in X$. Thus $X = [y]_S$. Suppose $x \in [y]_T$. Thus $(x,y) \in T$. Since $x \in Y$, it follows $x \in X$. Thus $(x,y) \in S$. Thus if $(x,y) \in T$ then $(x,y) \in S$. Thus $S \subseteq T$.

Thus from both directions, we have $S \subseteq T$, iff $\mathcal F$ refines $\mathcal G$.

(c)

To prove that $\mathcal F \cdot \mathcal G$ is the greatest lower bound of the set $\{ \mathcal F, \mathcal G \}$, if we prove that $\mathcal F \cdot \mathcal G$ is the $R$-smallest element in the set $\{ \mathcal F, \mathcal G \}$, then it will also be the greatest lower bound.

Suppose $Z \in \mathcal F \cdot \mathcal G$. Thus there exist a set $X \in \mathcal F$ and $Y \in \mathcal G$ such that $Z = X \cap Y$. Thus $Z \subseteq X$ and $Z \subseteq Y$. Thus $\mathcal F \cdot \mathcal G$ refines $\mathcal F$ as well as $\mathcal F \cdot \mathcal G$ refines $\mathcal G$. Thus $( \mathcal F \cdot \mathcal G, \mathcal F) \in R$ and $( \mathcal F \cdot \mathcal G, \mathcal G ) \in R$. Thus $\mathcal F \cdot \mathcal G$ is the smallest element of the set $\{ \mathcal F, \mathcal G \}$. Thus $\mathcal F \cdot \mathcal G$ is greatest lower bound of the set $\mathcal F \cdot \mathcal G$.