Chapter  4, Relations
Section  4.5  Closures
Summary
 Reflexive Closure: Suppose $R$ is a relation on a set $A$. Then the reflexive closure of $R$ is the smallest set $S \subseteq A \times A$
such that $R \subseteq S$ and $S$ is reflexive, if there is such a smallest set. In other words, a relation $S \subseteq A \times A$ is the reflexive
closure of $R$ if it has the following three properties:
 $R \subseteq S$.
 $S$ is reflexive.
 For every relation $T \subseteq A \times A$,if $R \subseteq T$ and $T$ is reflexive, then $S \subseteq T$.
 Strict Partial Order and Strict Total Order: Suppose $R$ is a relation on $A$. Then $R$ is said to be irreflexive if $\forall x \in A((x, x) \notin R)$.
$R$ is called a strict partial order if it is irreflexive and transitive. It is called a strict total order if it is a strict partial order, and in addition it
satisfies the following requirement, called trichotomy:
$\forall x \in A \forall y \in A(xRy \lor yRx \lor x = y)$.  Symmetric Closure: Suppose $R$ is a relation on $A$. The symmetric closure of $R$ is the smallest set $S \subseteq A \times A$ such that $R \subseteq S$
and $S$ is symmetric, if there is such a smallest set. In other words, a relation $S \subseteq A \times A$ is the symmetric closure of R if it has the following properties:
 $R \subseteq S$.
 $S$ is symmetric.
 For every relation $T \subseteq A \times A$,if $R \subseteq T$ and $T$ is symmetric, then $S \subseteq T$.
 Transitive Closure: The transitive closure of $R$ is the smallest set $S \subseteq A \times A$ such that $R \subseteq S$ and $S$ is transitive, if there is such a
smallest set. In other words, a relation $S \subseteq A \times A$ is the transitive closure of $R$ if it has the following properties:
 $R \subseteq S$.
 $S$ is transitive.
 For every relation $T \subseteq A \times A$,if $R \subseteq T$ and $T$ is transitive, then $S \subseteq T$.
 Suppose $R$ is a relation on $A$ and suppose:
 $S$ is Reflexive closure of $R$. Then $S$ is the smallest element of the family of sets $\mathcal F = \{ T \subseteq A \times A \, \vert \, R \subseteq T \text{ and } T \text{ is reflexive } \}$. Since we know the smallest element of a family of sets $\mathcal F$ is $\cap \mathcal F$, $S = \cap \mathcal F$.
 $S$ is Symmetric closure of $R$. Then $S$ is the smallest element of the family of sets $\mathcal F = \{ T \subseteq A \times A \, \vert \, R \subseteq T \text{ and } T \text{ is symmetric } \}$. Since we know the smallest element of a family of sets $\mathcal F$ is $\cap \mathcal F$, $S = \cap \mathcal F$.
 $S$ is Transitive closure of $R$. Then $S$ is the smallest element of the family of sets $\mathcal F = \{ T \subseteq A \times A \, \vert \, R \subseteq T \text{ and } T \text{ is transitive } \}$. Since we know the smallest element of a family of sets $\mathcal F$ is $\cap \mathcal F$, $S = \cap \mathcal F$.
 Since all the family of sets mentioned above, contains the element $A \times A$(because $R \subseteq A \times A \land A \times A$ is reflexive, symmetric and transitive), $\mathcal F \ne \phi$. Thus $\cap \mathcal F$ is defined. So we can conclude that reflexive, symmetric and transitive closures exist for every relation. Also since a set has a smallest element, it can have only one such element. Thus reflective, symmetric, and transitive closures are unique.
 Reflexive closure of a relation $R$ on $A$ is $S = R \cup i_A$.
 Symmetric closure of a relation $R$ on $A$ is $S = R \cup R^{1}$.
Soln1
(a)
Reflexive Closure:
$S = \{ (a,a), (b,b), (c,c), (a,b), (b,c), (c,b) \}$.
Symmetric Closure:
$S = \{ (a,a), (a,b), (b,a), (b,c), (c,b) \}$.
Transitive Closure:
$S = \{ (a,a), (a,b), (b,c), (a,c), (c,b), (c,c), (b,b) \}$.
(b)
Reflexive Closure:
$S = \{(x,y) \in R \times R \, \vert \, x < y \text{ or } x = y \}$.
which is equivalent to,
$S = \{(x,y) \in R \times R \, \vert \, x \le y \}$.
Symmetric Closure:
$S = \{(x,y) \in R \times R \, \vert \, x < y \text{ or } x > y\}$.
Transitive Closure:
As we can see, $R$ is alreast a transitive closure:
$S = \{(x,y) \in R \times R \, \vert \, x < y \}$.
(c)
Reflexive Closure:
Since $D_r$ is defined for positive number $r$, thus $r \ne 0$, so $(x,x) \notin D_r$, Thus including it,
$S = \{(x,y) \in R \times R \, \vert \, \vert x  y \vert < r \text{ or } x = y \}$.
Symmetric Closure:
As we can see $R$ is already symmetric,
$S = \{(x,y) \in R \times R \, \vert \, \vert x  y \vert < r \}$.
Transitive Closure:
$S = R \times R$.
Soln2 Similar to Soln1(a).
Soln3
(a) Suppose $R$ is asymmetric relation. Suppose $x,y$ are arbitrary elements of $A$ such that $xRy$. Thus $yRx$ is false. Or we can also say that $xRy \land yRx$ is false, or $\lnot (xRy \land yRx)$. Thus we can also say $(xRy \land yRx) \to x = y$. Since $x$ and $y$ are arbitrary, we can conclude that $\forall x \forall y((xRy \land yRx) \to x = y)$. Thus $R$ is antisymmetric.
(b) Suppose $R$ is strict partial order. Suppose $x$ and $y$ are arbitrary elements of $A$ such that $xRy$. We will prove by contradiction that $(y,x) \notin R$. Suppose $yRx$. Since $xRy \land yRx$ and $R$ is transitive, it follows $xRx$. This contradicts with the given that $R$ is strict partial order, and $(x,x) \notin R$. Thus if $xRy$ then $(y,x) \notin R$. Thus we can conclude that $R$ is asymmetric.
Soln4
(a)
Suppose $R$ is strict partial order.
Reflexive: Since $S$ is reflexive closure of $R$, it follows that $i_A \subseteq S$. Thus $S$ is reflexive.
Transitive: Suppose $x,y,z \in S$ such that $(x,y) \in S \land (y,z) \in S$. Since $S = R \cup i_A$, $(x,y) \in R \cup i_A$ and $(y,z) \in R \cup i_A$. Thus we have $(x,y) \in R \lor (x,y) \in i_A$ and $(y,z) \in R \lor (y,z) \in i_A$. Thus we have following possible cases:

Case 1: $(x,y) \in R$ and $(y,z) \in i_A$:
Since $(y,z) \in i_A$, $y = z$. Since $(x,y) \in R$ and $y = z$, it follows $(x,z) \in R$. Or we can also say $(x,z) \in S$. 
Case 2: $(x,y) \in i_A$ and $(y,z) \in R$: Since $(x,y) \in i_A$, $x = y$. Since $(y,z) \in R$ and $y = x$, it follows $(x,z) \in R$. Or we can also say $(x,z) \in S$.

Case 3: $(x,y) \in R$ and $(y,z) \in R$:
Since $R$ is transitive, it follows that $(x,z) \in R$. Or we can also say $(x,z) \in S$. 
Case 4: $(x,y) \in i_A$ and $(y,z) \in i_A$:
Thus $x = y = z$. Since $x = z$, it follows $(x,z) \in i_A$. Or we can also say $(x,z) \in S$.
Thus from all the cases, $(x,z) \in S$. Since $x,y,z$ are arbitrary, we can conlude that $S$ is arbitrary.
Antisymmetric: Suppose $x,y \in A$ such that $(x,y) \in S \land (y,x) \in S$. Thus $(x,y) \in R \cup i_A$ and $(y,x) \in R \cup i_A$. Thus we have following cases:

Case 1: $(x,y) \in R$ and $(y,x) \in i_A$:
Since $x = y$. But since $(x,y) \in R$, $(x,y) \notin R$. Thus this cases is not possible. 
Case 2: $(x,y) \in i_A$ and $(y,x) \in R$: Since $x = y$. But since $(x,y) \in R$, $(x,y) \notin R$. Thus this cases is not possible.

Case 3: $(x,y) \in R$ and $(y,x) \in R$:
Since $R$ is transitive, it follows $(x,x) \in R$. But since $R$ is irreflexive, $(x,x) \notin R$. Thus this case is also not possible. 
Case 4: $(x,y) \in i_A$ and $(y,x) \in i_A$:
Thus $x = y$.
Thus from all the cases, if $(x,y) \in S \land (y,x) \in S$, then $x = y$. Thus $S$ is antisymmetric.
(b)
Suppose $x,y \in A$. Since $R$ is strict partial order we have following cases:

Case 1: $x = y$. Thus $(x,y) \in i_A$. Since $i_A \subseteq S$, $(x,y) \in S$. Thus $(x,y) \in S \lor (y,x) \in S$.

Case 2: $x R y$. Thus $(x,y) \in S$. Or we can also say $(x,y) \in S \lor (y,x) \in S$.

Case 3: $y R x$. Thus $(y,x) \in S$. Or we can also say $(x,y) \in S \lor (y,x) \in S$.
Thus from all the cases, we have $(x,y) \in S \lor (y,x) \in S$. Since $x,y$ are arbitrary, it follows that $S$ is total order.
Soln5
(a)
To prove that $S$ is the largest element of $\mathcal F = \{ T \subseteq A \times A \, \vert \, T \subseteq R \text{ and } T \text{ is irreflexive } \}$. We need to prove that $S \in \mathcal F$ and $\forall T \in \mathcal F (T \subseteq \mathcal S)$.
Suppose $x,y \in A$ such that $(x,y) \in S$. Thus $(x,y) \in R \land (x,y) \notin i_A$. Thus if $(x,y) \in S$ then $(x,y) \in R$. Thus $S \subseteq R$. Also since $(x,y) \notin i_A$, it follows that $x \ne y$. Thus if $(x,y) \in S$, then $x \ne y$. It follows that $S$ is irreflexive. Also $S = R \setminus i_A$, it follows that $S \subseteq A \times A$. Since $S \subseteq A \times A$ and $S \subseteq R$ and $S$ is irreflexive, it follows that $S \in \mathcal F$.
Suppose $T \in \mathcal F$. Suppose $x,y \in A$ such that $(x,y) \in T$. Since $R \subseteq T$, it follows that $(x,y) \in R$. Also since $T$ is irreflexive, it follows that $x \ne y$. Thus $(x,y) \notin i_A$. Since $(x,y) \in R \land (x,y) \notin i_A$, it follows that $(x,y) \in R \setminus i_A$. Thus $(x,y) \in S$. Since $x,y$ are arbitrary, it follows that $T \subseteq S$. Since $T$ is arbitrary, it follows that $\forall T \in \mathcal F(T \subseteq S)$.
Thus $S \in \mathcal F$ and $\forall T \in \mathcal F(T \subseteq S)$, it follows that $S$ is the largest element of $\mathcal F$.
(b)
Suppose $R$ is partial order on $A$.
Suppose $x \in A$. Since $R$ is partial order, $(x,x) \in R$. Also $(x,x) \in i_A$. Thus $(x,x) \notin R \setminus i_A$, or $(x,x) \notin S$. Thus $S$ is irreflexive.
Suppose $x,y,z \in A$ such that $(x,y) \in S \land (y,z) \in S$. Since $S = R \setminus i_A$, it follows $(x,y) \in R \land (y,z) \in R \land x \ne y \land y \ne z$. Since $R$ is transitive, it follows that $(x,z) \in R$. We will prove by contradiction that $x \ne z$. Suppose $x = z$, then since $(x,y) \in R$, it follows $(z,y) \in R$. Also we have $(y,z) \in R$ and since $R$ is antisymmetric, it follows that $y = z$. But since $(y,z) \in S$, $y \ne z$. Thus $x = z$ leads to contradiction. Thus $x \ne z$, or $(x,z) \notin i_A$. Since $(x,z) \in R \land (x,z) \notin i_A$, it follows that $(x,z) \in S$. Since $x,y,z$ are arbitrary, it follows that $S$ is transitive.
Thus $S$ is irreflexive and transitive, it follows that $S$ is strict partial order.
Soln6
(a) $S = \{ (p,q) \, \vert \, p \text{ is ancestor of } q \}$.
(b) We know that $S^{1} = \{(p,q) \, \vert \, q is ancestor of p \}$.
Thus $S \circ S^{1} = \{ (p,r) \, \vert \,$ There exists a $q$ such that $(p,q) \in S^{1}$ and $(q,r) \in S \}$.
It is equivalent to:
$S \circ S^{1} = \{ (p,r) \, \vert \,$ There exists a $q$ such that $q$ is the ancestor of $p$ and $q$ is the ancestor of $r \}$.
It is equivalent to:
$S \circ S^{1} = \{ (p,r) \, \vert \,$ There exists a $q$ such that $p$ and $r$ have a ancestor $q \}$.
It is equivalent to:
$S \circ S^{1} = \{ (p,r) \, \vert \, p$ and $r$ have a common ancestor $\}$.
Soln7
(a)
($\to$)Suppose $S = R$ and $R$ is reflexive. Thus:
 $R \subseteq S$.
 $S$ is reflexive.
 Suppose $T \in A \times A$ is a set such that $R \subseteq T$ and $T$ is reflexive. Since $S = R$, thus $S \subseteq T$.
Thus $S$ is reflexive closure of $R$. Since $S = R$, $R$ is reflexive closure of $R$.
($\leftarrow$)Suppose $S = R$ and $S$ is reflexive closure of $R$. Since $S$ is reflexive closure of $R$, it follows that $i_A \subseteq S$, or $i_A \subseteq R$. It follows that $R$ is reflexive.
(b)
($\to$)Suppose $S = R$ and $R$ is symmetric. Thus:
 $R \subseteq S$.
 $S$ is symmetric.
 Suppose $T \in A \times A$ is a set such that $R \subseteq T$ and $T$ is symmetric. Since $S = R$, thus $S \subseteq T$.
Thus $S$ is reflexive closure of $R$. Since $S = R$, $R$ is symmetric closure of $R$.
($\leftarrow$)Suppose $S = R$ such that $S$ is symmetric closure of $R$. Since $S$ is symmetric closure of $R$, it follows that $S$ is symmetric. Thus $R$ is symmetric.
Similarly it can be proved for transitive that $R$ is transitive iff $R$ is transitive closure of $R$.
Soln8
Suppose $S$ is symmetric closure of $R$. Thus $S$ is symmetric. Suppose $x \in Dom(S)$. Thus there exist an element $y$ such that $(x,y) \in S$. Since $S$ is symmetric, it follows that $(y,x) \in S$. Thus $x \in Ran(S)$. Since $x$ is arbitrary, it follows that $Dom(S) = Ran(S)$.
Now to prove $Dom(S) = Dom(R) \cup Ran(R)$:
($\to$)Suppose $x \in Dom(S)$. Thus there exist an element $y$ such that $(x,y) \in S$. We will prove by contradiction that $(x,y) \in R \lor (y,x) \in R$. Suppose $\lnot ((x,y) \in R \lor (y,x) \in R)$. Thus $(x,y) \notin R \land (y,x) \notin R$. Now consider a set $T = S  \{ (x,y), (y,x) \}$ thus making $T \subseteq S$. Since $S$ was symmetric, and we removed $(x,y),(y,x)$ from $S$, it follows that $T$ is also symmetric. Since $T$ contains all the elements of $S$ except $(x,y)$ and $(y,x)$ and since $(x,y) \notin R \land (y,x) \notin R$, it follows that $R \subseteq T$. Since $T$ is symmetric, and $R \subseteq T$ and $T \subseteq S$, it follows that $S$ is not the smallest element such that $R \subseteq S$ and $S$ is symmetric. But it contradicts with the given that $S$ is symmetric closure. Thus our assumption $\lnot ((x,y) \in R \lor (y,x) \in R)$ is wrong. It follows that $(x,y) \in R \lor (y,x) \in R$. It follows that $x \in Dom(R) \cup Ran(R)$. Since $x$ is arbitrary, it follows that $Dom(S) \subseteq Dom(R) \cup Ran(R)$.
($\leftarrow$)Suppose $x \in Dom(R) \cup Ran(R)$. Thus there exist an element $y$ such that either $(x,y) \in R$ or $(y,x) \in R$. Thus we have following possible cases:

Case 1: $xRy$. Since $xRy$, and $R \subseteq S$, it follows $(x,y) \in S$. Thus $x \in Dom(S)$.

Case 2: $yRx$. Since $yRx$, and $R \subseteq S$, it follows $(y,x) \in S$. Since $S$ is symmetric, it follows that $(x,y) \in S$. Thus $x \in Dom(S)$.
Thus from both cases, if $x \in Dom(R) \cup Ran(R)$, then $x \in Dom(S)$. Since $x$ is arbitrary, $Dom(R) \cup Ran(R) \subseteq Dom(S)$.
Thus we have $Dom(S) \subseteq Dom(R) \cup Ran(R)$ and $Dom(R) \cup Ran(R) \subseteq Dom(S)$, it follows that $Dom(S) = Dom(R) \cup Ran(R)$.
Finally putting all together we have $Dom(S) = Ran(S) = Dom(R) \cup Ran(R)$.
Soln9
Let $T = \{ (x, y) \in S \, \vert \, x \in Dom(R) \text{ and } y \in Ran(R) \}$.
Suppose $(x,y) \in R$. Since $R \subseteq S$, it follows $(x,y) \in S$. Also since $(x,y) \in R$, it follows $x \in Dom(R)$ and $y \in Ran(R)$. Thus $(x,y) \in T$. Since $(x,y)$ is arbitrary, it follows that $R \subseteq T$.
Suppose that $(x,y) \in T \land (y,z) \in T$. It follows that $(x,y) \in S \land (y,z) \in S$. Since $S$ is transitive, it follows $(x,z) \in S$. Since $(x,y) \in T$, it follows $x \in Dom(R)$. Similarly since $(y,z) \in T$, it follows $z \in Ran(R)$. Thus we have $(x,z) \in S$ and $x \in Dom(R)$ and $y \in Ran(R)$, it follows that $(x,z) \in T$. Thus $T$ is transitive.
Also note that by the definition of $T$, $T \subseteq S$. Also since $S$ is transitive closure of $R$ and $R \subseteq T$ and $T$ is transitive,
it follows that(by the definition of transitive closure), $S \subseteq T$.
Since $S \subseteq T$ and $T \subseteq S$, it follows thar $T = S$.
Suppose $x \in Dom(T)$. It follows that $x \in Dom(R)$. Thus $Dom(T) \subseteq Dom(R)$. Suppose $x \in Dom(R)$. Since $R \subseteq T$, it follows that $x \in Dom(T)$. Thus $Dom(R) \subseteq Dom(T)$. Since $Dom(T) \subseteq Dom(R)$ and $Dom(R) \subseteq Dom(T)$, it follows that $Dom(R) = Dom(T)$.
Suppose $y \in Ran(T)$. It follows that $y \in Ran(R)$. Thus $Ran(T) \subseteq Ran(R)$. Suppose $y \in Ran(R)$. Since $R \subseteq T$, it follows that $y \in Ran(T)$. Thus $Ran(R) \subseteq Ran(T)$. Since $Ran(T) \subseteq Ran(R)$ and $Ran(R) \subseteq Ran(T)$, it follows that $Ran(R) = Ran(T)$.
Soln10
(a)
Since $R$ is the relation on $A$. Clearly $R \subseteq A \times A$. Suppose $(x,y) \in A \times A$. Then $(y,x) \in A \times A$. Thus $A \times A \in \mathcal F$. It follows $\mathcal F \ne \phi$.
(b)
Suppose $S = \cap \mathcal F$.
Suppose $(x,y) \in R$. Suppose $T$ is an arbitrary element in $\mathcal F$. It follows $R \subset T$. Thus $(x,y) \in T$. Since $T$ is arbitrary, it follows $\forall T \in \mathcal F((x,y) \in T)$. Thus $(x,y) \in \cap \mathcal F$. Since $(x,y)$ is arbitrary, it follows $R \subseteq \cap \mathcal F$.
Suppose $(x,y) \in \cap \mathcal F$. Suppose $T$ is an arbitrary element in $\mathcal F$. Since $(x,y)$ belongs to all the elements of $\cap \mathcal F$, it follows that $(x,y) \in T$. Since $T$ is symmetric, it follows that $(y,x) \in T$. Since $T$ is arbitrary, it follows $\forall T \in \mathcal F((y,x) \in T)$. Thus $(y,x) \in \cap \mathcal F$. Thus $\cap \mathcal F$ is symmetric.
Suppose $T \subseteq A \times A$ such that $R \subseteq T$ and $T$ is symmetric. It follows that $T \in \mathcal F$. Suppose $(x,y) \in \cap \mathcal F$, thus $\forall X \in \mathcal F((x,y) \in X)$. Since $T \in \mathcal F$, it follows that $(x,y) \in T$. Thus $\cap \mathcal F \subseteq T$.
Thus from all the above points, we can conclude that $S = \cap \mathcal F$ is symmetric closure of $R$.
Soln11
(a)
We know that reflexive closure of $R = \cap \mathcal F$, where $\mathcal F = \{ T \subseteq A \times A \, \vert \, R \subseteq T \text{ and } T \text{ is reflexive } \}$.
Suppose $S_1 = \cap \mathcal F_1$ and $S_2 = \cap \mathcal F_2$.
Suppose $T_2 \in \mathcal F_2$ is an arbitrary element. Thus $R_2 \subseteq T_2$ and $T_2$ is reflexive. Since $R_1 \subseteq R_2$, it follows $R_1 \subseteq T_2$ and T_2 is reflexive. Since $S_1$ is reflexive closure of $R_1$, it follows by the definition of reflexive closure that $S_1 \subseteq T_2$. Since $T_2$ is arbitrary, it follows $\forall T_2 \in \mathcal F_2 (S_1 \in T_2)$, or $S_1 \subseteq \cap \mathcal F_2$. Thus $S_1 \subseteq S_2$.
(b)
 Symmetric
We know that symmetric closure of $R = \cap \mathcal F$, where $\mathcal F = \{ T \subseteq A \times A \, \vert \, R \subseteq T \text{ and } T \text{ is symmetric } \}$.
Suppose $S_1 = \cap \mathcal F_1$ and $S_2 = \cap \mathcal F_2$.
Suppose $T_2 \in \mathcal F_2$ is an arbitrary element. Thus $R_2 \subseteq T_2$ and $T_2$ is symmetric. Since $R_1 \subseteq R_2$, it follows $R_1 \subseteq T_2$ and T_2 is symmetric. Since $S_1$ is symmetric closure of $R_1$, it follows by the definition of symmetric closure that $S_1 \subseteq T_2$. Since $T_2$ is arbitrary, it follows $\forall T_2 \in \mathcal F_2 (S_1 \in T_2)$, or $S_1 \subseteq \cap \mathcal F_2$. Thus $S_1 \subseteq S_2$.
 Transitive:
We know that transitive closure of $R = \cap \mathcal F$, where $\mathcal F = \{ T \subseteq A \times A \, \vert \, R \subseteq T \text{ and } T \text{ is transitive } \}$.
Suppose $S_1 = \cap \mathcal F_1$ and $S_2 = \cap \mathcal F_2$.
Suppose $T_2 \in \mathcal F_2$ is an arbitrary element. Thus $R_2 \subseteq T_2$ and $T_2$ is transitive. Since $R_1 \subseteq R_2$, it follows $R_1 \subseteq T_2$ and T_2 is transitive. Since $S_1$ is transitive closure of $R_1$, it follows by the definition of transitive closure that $S_1 \subseteq T_2$. Since $T_2$ is arbitrary, it follows $\forall T_2 \in \mathcal F_2 (S_1 \in T_2)$, or $S_1 \subseteq \cap \mathcal F_2$. Thus $S_1 \subseteq S_2$.
Soln12
(a)
 ($\to$), Proof of $S_1 \cup S_2 \subseteq S$:
Since $R_1 \cup R_2 = R$, it follows $R_1 \subseteq R$ and $R_2 \subseteq R$. Thus using Soln11(a), $S_1 \subseteq S$ and $S_2 \subseteq S$. It follows that $S_1 \cup S_2 \subseteq S$.
 ($\to$), Proof of $S \subseteq S_1 \cup S_2$:
We will first prove:
 $R \subseteq S_1 \cup S_2$.
 $S_1 \cup S_2$ is reflexive.
Suppose $(x,y) \in R$, or $(x,y) \in R_1 \cup R_2$. We have following cases:
Case 1: $(x,y) \in S_1$: Since $R_1 \subseteq S_1$, it follows that $(x,y) \in S_1$, or we may also say $(x,y) \in S_1 \cup S_2$.
Case 2: $(x,y) \in S_2$: Since $R_2 \subseteq S_2$, it follows that $(x,y) \in S_2$, or we may also say $(x,y) \in S_1 \cup S_2$.
Since $(x,y)$ is arbitrary, and from all possible cases we can conclude that $R \subseteq S_1 \cup S_2$.
Suppose $x \in A$. Since $S_1$ is reflexive, it follows that $(x,x) \in S_1$. Thus we can also say that $(x,x) \in S_1 \cup S_2$. Thus $S_1 \cup S_2$ is reflexive.
Since $R \subseteq S_1 \cup S_2$ and $S_1 \cup S_2$ is reflexive, and $S$ is the reflexive closure of $R$, then by using the definition of reflexive closure, $S \subseteq S_1 \cup S_2$.
Since $S_1 \cup S_2 \subseteq S$ and $S \subseteq S_1 \cup S_2$, we can conclude that $S = S_1 \cup S_2$.
(b)
 ($\to$), Proof of $S_1 \cup S_2 \subseteq S$:
Since $R_1 \cup R_2 = R$, it follows $R_1 \subseteq R$ and $R_2 \subseteq R$. Thus using Soln11(b), $S_1 \subseteq S$ and $S_2 \subseteq S$. It follows that $S_1 \cup S_2 \subseteq S$.
 ($\to$), Proof of $S \subseteq S_1 \cup S_2$:
We will first prove:
 $R \subseteq S_1 \cup S_2$.
 $S_1 \cup S_2$ is symmetric.
Suppose $(x,y) \in R$, or $(x,y) \in R_1 \cup R_2$. We have following cases:
Case 1: $(x,y) \in S_1$: Since $R_1 \subseteq S_1$, it follows that $(x,y) \in S_1$, or we may also say $(x,y) \in S_1 \cup S_2$.
Case 2: $(x,y) \in S_2$: Since $R_2 \subseteq S_2$, it follows that $(x,y) \in S_2$, or we may also say $(x,y) \in S_1 \cup S_2$.
Since $(x,y)$ is arbitrary, and from all possible cases we can conclude that $R \subseteq S_1 \cup S_2$.
Suppose $x,y \in A$ such that $(x,y) \in S_1 \cup S_2$. Thus $(x,y) \in S_1 \lor (x,y) \in S_2$. Since $S_1$ and $S_2$ are symmetric, it follows that $(y,x) \in S_1 \lor (y,x) \in S_2$, or $(x,y) \in S_1 \cup S_2$. Thus $S_1 \cup S_2$ is symmetric.
Since $R \subseteq S_1 \cup S_2$ and $S_1 \cup S_2$ is symmetric, and $S$ is the symmetric closure of $R$, then by using the definition of symmetric closure, $S \subseteq S_1 \cup S_2$.
Since $S_1 \cup S_2 \subseteq S$ and $S \subseteq S_1 \cup S_2$, we can conclude that $S = S_1 \cup S_2$.
(c)
Proof of $S_1 \cup S_2 \subseteq S$:
Since $R_1 \cup R_2 = R$, it follows $R_1 \subseteq R$ and $R_2 \subseteq R$. Thus using Soln11(b), $S_1 \subseteq S$ and $S_2 \subseteq S$. It follows that $S_1 \cup S_2 \subseteq S$.
Counter example for $S \ne S_1 \cup S_2$:
Suppose:
$A = \{1, 2, 3, 4 \}$.
$R_1 = \{ (1,2), (2,2), (2,3) \}$.
$R_2 = \{ (4,2), (2,4) \}$
$R = R_1 \cup R_2 = \{ (1,2), (2,2), (2,3), (4,2), (2,4) \}$.
Transitive closure for $R_1$ is:
$S_1 = \{ (1,2), (2, 2), (2,3), (1,3) \}$.
Transitive closure for $R_2$ is:
$S_2 = \{ (2,2), (4,2), (2,4), (4,4) \}$.
And $S_1 \cup S_2 = \{ (1,2), (2, 2), (2,3), (1,3), (4,2), (2,4), (4,4) \}$.
Transitive closure for $R$ is : $S = \{ (1,2), (2,2), (2,3), (4,2), (2,4), (1,3), (4,4), (1,4), (4,3) \}$.
Clearly $S \ne S_1 \cup S_2$.
Soln13
For all the parts there is one common part that I shall prove here.
We have $S_i$ is reflexive/symmetric/transitive closure of $R_i$, where $i \in \{1,2\}$.
Suppose $(x,y) \in R_1 \cap R_2$. It follows $(x,y) \in R_1 \land (x,y) \in R_2$. Since $R_1 \subseteq S_1$ and $R_2 \subseteq S_2$, it follows that $(x,y) \in S_1 \cap S_ 2$. Thus $R_1 \cap R_2 \subseteq S_1 \cap S_2$.
(a)
We know that $S_1 = R_1 \cup i_A$ and $S_2 = R_2 \cup i_A$.
And $S = (R_1 \cap R_2) \cup i_A$,
Suppose that $(x,y) \in S_1 \cap S_2$. Thus $(x,y) \in R_1 \cup i_A$ and $(x,y) \in R_2 \cup i_A$. iff
$((x,y) \in R_1 \lor (x,y) \in i_A) \land ((x,y) \in R_2 \lor (x,y) \in i_A)$ iff
$((x,y) \in R_1 \land (x,y) \in R_2) \lor (x,y) \in i_A$ iff
$((x,y) \in R_1 \cap R_2) \lor (x,y) \in i_A$ iff
$(x,y) \in (R_1 \cap R_2) \cup i_A$ iff
$(x,y) \in S$.
Thus $(S_1 \cap S_2) = S$.
(b)
Suppose $(x,y) \in S_1 \cap S_2$. It follows that $(x,y) \in S_1$ and $(x,y) \in S_2$. Since $S_1$ and $S_2$ are symmetric, it follows that $(y,x) \in S_1 \land (y,x) \in S_2$. Thus $(y,x) \in S_1 \cap S_2$. Thus $S_1 \cap S_2$ is symmetric.
Since $S$ is symmetric closure of $R_1 \cap R_2$, and $R_1 \cap R_2 \subseteq S_1 \cap S_2$, and $S_1 \cap S_2$ is symmetric, then by the definition of symmetric closure, it follows that $S \subseteq S_1 \cap S_2$.
Counter example to show: $S_1 \cap S_2 \nsubseteq S$:
Suppose $A = \{1,2\}, R_1 = \{(1,2)\}, R_2 = \{(2,1)\}$.
Thus $R_1 \cap R_2 = \phi$.
Symmetric closure of $R_1$ is:
$S_1 = \{(1,2), (2,1) \}$.
Symmetric closure of $R_2$ is:
$S_2 = \{(1,2), (2,1) \}$.
Symmetric closure of $R_1 \cap R_2$ is:
$S = \{ \phi \}$.
And $S_1 \cap S_2 = \{(1,2), (2,1) \}$.
Thus $S_1 \cap S_2 \nsubseteq S$.
(c)
Suppose $(x,y) \in S_1 \cap S_2$ and $(y,z) \in S_1 \cap S_2$. It follows that $(x,y) \in S_1$ and $(y,z) \in S_2$. Since $S_1$ and $S_2$ are transitive, it follows that $(x,z) \in S_1$ and $(x,z) \in S_2$. Thus $(x,z) \in S_1 \cap S_2$. Thus $S_1 \cap S_2$ is symmetric.
Since $S$ is transitive closure of $R_1 \cap R_2$, and $R_1 \cap R_2 \subseteq S_1 \cap S_2$, and $S_1 \cap S_2$ is transitive, then by the definition of transitive closure, it follows that $S \subseteq S_1 \cap S_2$.
Counter example to show: $S_1 \cap S_2 \nsubseteq S$:
Suppose:
$A = \{1, 2, 3 \}$.
$R_1 = \{ (1,2), (2,3) \}$.
$R_2 = \{ (1,3) \}$
$R = R_1 \cap R_2 = \phi$.
Transitive closure for $R_1$ is:
$S_1 = \{ (1,2), (2,3), (1,3) \}$.
Transitive closure for $R_2$ is:
$S_2 = \{ (1,3) \}$.
Transitive closure for $R$ is : $S = \{ \phi \}$.
And $S_1 \cap S_2 = \{ (1,3) \}$.
Clearly $S_1 \cap S_2 \nsubseteq S$.
Soln14
Suppose:
$A = \{1, 2, 3, a, b, c \}$.
$R_1 = \{ (1,2), (2,3), (a,b), (b,c) \}$.
$R_2 = \{ (2,3), (a,c), (c,b) \}$.
Thus, $R_1 \setminus R_2 = \{ (1,2), (a,b), (b,c) \}$.
Transitive closure of $R_1$ is:
$S_1 = \{ (1,2), (2,3), (1,3), (a,b), (b,c), (a,c) \}$.
Transitive closure of $R_2$ is:
$S_2 = \{ (2,3), (a,c), (c,b), (a,b) \}$.
Transitive closure of $R = R_1 \setminus R_2$ is:
$S = \{ (1,2), (a,b), (b,c), (a,c) \}$.
And $S_1 \setminus S_2 = \{ (1,2), (1,3), (b,c) \}$.
Thus $S \nsubseteq S_1 \setminus S_2$ and $S_1 \setminus S_2 \nsubseteq S$.
Soln15
We will prove that $S = R \cup R^{1} \cup i_A$ is the symmetric reflexive closure of $R$.

$R \subseteq S$: Since $S = R \cup R^{1} \cup i_A$, it is clear that $R \subseteq S$.

$S$ is reflexive: Suppose $x \in A$. Thus $(x,x) \in i_A$. It follows that $(x,x) \in R \cup R^{1} \cup i_A$. Thus $S$ is reflexive.

$S$ is symmetric: Suppose $(x,y) \in S$. Thus $(x,y) \in R \lor (x,y) \in R^{1}$. Thus $(y,x) \in R \lor (y,x) \in R^{1}$. Thus we can also say that $(y,x) \in R \cup R^{1} \cup i_A$. Thus $S$ is symmetric.

Suppose $T \subseteq A \times A$ such that $R \subseteq T$ and $T$ is symmetric and reflexive. Suppose $(x,y) \in S$. Thus $(x,y) \in R \cup R^{1} \cup i_A$. Thus we have following cases:

Case 1: $(x,y) \in R$:
Since $R \subseteq T$, it follows that $(x,y) \in T$. 
Case 2: $(x,y) \in R^{1}$: Thus $(y,x) \in R$. Since $R \subseteq T$, it follows that $(y,x) \in T$. Since $T$ is symmetric, it follows $(x,y) \in T$.

Case 3: $(x,y) \in i_A$: Thus $x = y$. Since $T$ is reflexive, it follows that $(x,x) \in T$, or $(x,y) \in T$.

Thus if $(x,y) \in S$, then $(x,y) \in T$, it follows that $S \subseteq T$. Thus $S$ is the smallest set of all such sets like $T$.
Thus we proved that such set $S$ exists.
Soln16
Since $S$ is reflexive closure of $R$, it follows that $S = R \cup i_A$.
(a) Suppose $(x,y) \in S$. Then $(x,y) \in R \lor (x,y) \in i_A$. Thus we have following cases:

Case 1: $(x,y) \in R$:
Since $R$ is symmetric, $(y,x)$ \in R. Since $R \subseteq S$, it follows $(y,x) \in S$. 
Case 2: $(x,y) \in i_A$: Thus $x = y$. Since $S$ is reflexive, it follows $(x,y) \in S$.
Thus from both cases, $S$ is symmetric.
(b) Suppose $(x,y) \in S \land (y,z) \in S$. Thus we have following possible cases:

Case 1: $(x,y) \in R \land (y,z) \in i_A$.
Thus $y = z$. It follows $(x,z) \in R$. Since $R \subseteq S$, it follows $(x,z) \in S$. 
Case 2: $(x,y) \in R \land (y,z) \in R$. Since $R$ is transitive, it follows that $(x,z) \in R$. Since $R \subseteq S$, it follows that $(x,z) \in S$.

Case 3: $(x,y) \in i_A \land (y,z) \in R$. Thus $x = y$. It follows $(x,z) \in R$. Since $R \subseteq S$, it follows $(x,z) \in S$.

Case 4: $(x,y) \in i_A \land (y,z) \in i_A$. Thus $x = y = z$. Since $S$ is reflexive, it follows that $(x,z) \in S$.
Thus from both cases, $S$ is transitive.
Soln17
Suppose $R$ is symmetric. Suppose $(x,y) \in R$. Since $R$ is symmetric, it follows $(y,x) \in R$. Since $R \subseteq S$, it follows $(y,x) \in S$. Thus $(x,y) \in S^{1}$. Thus $R \subseteq S^{1}$.
Suppose $(x,y) \in S^{1} \land (y,z) \in S^{1}$. It follows that $(y,x) \in S \land (z,y) \in S$. Since $S$ is transitive, it follows that $(z,x) \in S$. Thus $(x,z) \in S^{1}$. Thus $S^{1}$ is transitive.
Since $R \subseteq S^{1}$ and $S^{1}$ is transitive and $S$ is transitive closure of $R$, it follows from the definition of transitive closure that $S \subseteq S^{1}$. Thus if $(x,y) \in S$, then $(x,y) \in S^{1}$. Since $(x,y) \in S^{1}$, it follows that $(y,x) \in S$. Thus $S$ is symmetric.
Soln18
Let $Q$ be the symmetric closure of $R$, and let $S$ be the transitive closure of $Q$. Also, let $Q'$ be the transitive closure of $R$, and let $S'$ be the symmetric closure of $Q'$.
(a)
Since $S$ is transitive closure of $Q$. It follows that $Q \subseteq S$. Since $Q$ is symmetric closure of $R$. It follows that $Q$ is symmetric and $R \subseteq Q$. Using Soln17, since $Q$ is symmetric, $S$ is symmetric. Also since $Q \subseteq S$ and $R \subseteq Q$, it follows that $R \subseteq S$. Thus $S$ is transitive and symmetric and $R \subseteq S$.
Now suppose $T \subseteq A \times A$ such that $T$ is transitive and symmetric, and $R \subseteq T$. Since $T$ is symmetric and $R \subseteq T$, and $Q$ is the symmetric closure of $R$, it follows(using definition of symmetric closure) that $Q \subseteq T$. Since $T$ is transitive and $Q \subseteq T$, and $S$ is the transitive closure of $Q$, it follows(using definition of transitive closure) that $S \subseteq T$. Thus $S$ is the smallest of the sets like $T$. It follows that $S$ is symmetric transitive closure of $R$.
(b)
Suppose $Q$ is symmetric closure of $R$, $R \subseteq Q$.
We know from Soln11, that if $R_1 \subseteq R_2$, and $S_1$ and $S_2$ are transitive closure of $R_1$ and $R_2$ respectively, then $S_1 \subseteq S_2$.
Now since $Q'$ is transitive closure of $R$ and $S$ is transitive closure of $Q$, and $R \subseteq Q$, it follows that $Q' \subseteq S$. Since $S$ is symmetric, and $Q' \subseteq S$, and $S'$ is symmetric closure of $Q'$, it follows by the definition of symmetric closure that $S' \subseteq S$.
(c) False. The problem will be because the symmetric closure of a transitive set is may not be transitive. For eg: $R = \{(1,2)\}$. Clearly $\{(1,2)\}$ is transitive but symmetric closure of $R$ is $\{(1,2),(2,1)\}$. Clearly this is not transitive.
Counter Example:
Suppose:
$A = \{1,2\}$.
$R = \{(1,2)\}$
Thus,
Symmetric closure of $R$ is:
$Q = \{(1,2),(2,1)\}$.
Transitive closure of $Q$ is:
$S = \{(1,2),(2,1),(1,1)\}$.
But, if we do first transitive then symmetric,
Transitive closure of $R$ is:
$Q' = \{(1,2)\}$.
Thus symmetric closure of $Q'$:
$S' = \{(1,2),(2,1)\}$.
Clearly, $S' \ne S$.
Soln19
Proof and theorem both are not correct. The proof does not take into account that affter adding elements to $R$ to make it transitive, it may no longer be antisymmetric.
Counter example: $A = \{(1,2,3\}$, R = { (1,1), (2,2), (3,3), (1,2), (2,3), (3,1) } $$
Clearly $R$ is antisymmetric and reflexive.
Transitive closure of $R$:
$S = \{ (1,1), (2,2), (3,3), (1,2), (2,3), (3,1), (1,3), (3,2), (2,1) \}$.
Clearly $S$ is not antisymmetric. Thus $S$ is not partial order on $A$.
Soln20
(a) We shall give two examples of minimal elements:
$M_1 = \{ (San Francisco, Chicago), (Chicago, Dallas), (Dallas, New York), (New York, Washington DC), (Washington DC, San Francisco) \}$.
$M_2 = \{ (San Francisco, Washington DC), (Washington DC, New York), (New York, Dallas), (Dallas, Chicago), (Chicago, San Francisco) \}$.
These both are minimal elements since for both of them following statement holds:
There does not exist any other set, say $X$ in $\mathcal F$ such that apart from itself such that our set, say $M_1 \subseteq X$.
(b) Since smallest set in $\mathcal F$ should be the subset of all other sets. Since $M_1$ and $M_2$ are sets in $\mathcal F$ and $M_1 \cap M_2 = \phi$, it follows that there is no smallest set in $\mathcal F$.