Sunday, June 6, 2010

how to prove it - ch4, sec4.5(Closures)

This section talks about various closures for a relation, R. There always exists a set, S that has all the ordered pairs from R + just the pairs that are needed to make R a reflexive/symmetric/transitive relation. Such a set is called reflexive/symmetric/transitive closure of R.

Here are the formal defintions..

Reflexive Closure: Suppose R is a relation on a set A. Then the reflexive closure of R is the smallest set $S \subseteq A X A$ s.t. $R \subseteq S$ and S is reflexive, if there is such a smallest set. In other words, a relation $S \subseteq A X A$ is the reflexive closure of R if it has the following three properties:

1. $R \subseteq S$
2. S is reflexive
3. For every relation $T \subseteq A X A$, if $R \subseteq T$ and T is reflexive, then $S \subseteq T$

Or, S is the smallest set from the familiy of sets $F$ = {$T \subseteq A X A | R \subseteq T \land T-is-reflexive$}, that is $\cap F$.

definitions of symmetric and transitive closure are similar.

Strict Partial/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 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 (x R y \cup y R x \cup x = y)$

Note: Sometimes, for proofs, it is useful to know that
if S is reflexive closure of R then S = $R \cup i_A$, where $i_A$ is the identity relation on A
if S is symmetric closure of R then S = $R \cup R^{-1}$

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

Ex-1: (a) Reflexive closure is obtained by just adding {$(x,x) \in A X A | x \in A$} to R if not already
R = {(a,a), (b,b), (c,c), (a,b), (b,c), (c,b)}

Symmetric closure is obtained by just adding {$(x,y) \in A X A | (y,x) \in R$} to R if not already
R = {(a,a), (a,b), (b,a), (b,c), (c,b)}

Transitive closure is obtained by just adding {$(x,z) \in A X A | \exists ((x,y) \in R \land (y,z) \in R)$} to R if not already
R = {(a,a),(a,b),(b,c),(a,c),(c,b),(b,b),(c,c)}

(b) Reflexive Closure = {$(x,y) \in R X R | x \leq y$}
Symmetric Closure = {$(x,y) \in R X R | x < y \lor x > y$}
Transitive Closure = R itself is transitive

(c) Reflexive Closure = $D_r$ is already reflexive
Symmetric Closure = $D_r$ is already symmetric
Transitive Closure = R X R

Ex-2:
(a) R = {(a,c),(b,d),(c,c),(d,a),(d,b)}
Reflexive Closure = {(a,a),(b,b),(c,c),(d,d),(a,c),(b,d),(d,a),(d,b)}
Symmetric Closure = {(a,c),(c,a),(b,d),(d,b),(c,c),(d,a),(a,d)}
Transitive Closure = {(a,c),(b,d),(d,a),(b,a),(c,c),(d,b),(d,c),(b,c)}

(b),(c),(d) are pretty similar

Ex-3:
(a) Suppose R is asymmetric. Let x,y be arbitrary elements of A s.t. $(x,y) \in R$ and $(y,x) \in R$. Since, R is asymmetric so its not possible unless x = y. Since x,y are arbitrary so R is antisymmetric.

(b) Suppose R is a strict partial order on A, so its irreflexive and transitive. Let x,y be arbitrary elements of A s.t. $(x,y) \in R$. We'll prove by contradiction that $(y,x) \notin R$. Assume $(y,x) \in R$. Since $(x,y) \in R$ and $(y,x) \in R$ and R is transitive, so $(x,x) \in R$. But, this is not possible because R is irreflexive. Hence our assumption is never true. Thus $(y,x) \notin R$. Hence $(x,y) \in R \rightarrow (y,x) \notin R$. Since x,y are arbitrary so R is asymmetric and hence antisymmetric.

Ex-4:
(a) Suppose R is a strict partial order on A and S is reflexive closure of R.

Since S is reflexive closure of R, so its reflexive by definition.

Since S is reflexive closure of R, so S = $R \cup i_A$.
Let x,y be arbitrary elements of A s.t. $(x,y) \in S$ and $(y,x) \in S$. Then either $(x,y) \in R$ or (x = y) and either $(y,x) \in R$ of (x = y). Let us consider all the possible cases

Case#1: $(x,y) \in R$ and $(y,x) \in R$
not possible as R is strict partial order and hence antisymmetric

Case#2: x = y
Then x = y

Since x,y are arbitrary so S is antisymmetric

Let x,y,z be arbitrary elements of A s.t. $(x,y) \in S$ and $(y,z) \in S$. Then either $(x,y) \in R$ or (x = y) and $(y,z) \in R$ or (y = z). Let us consider all the cases
Case#1: $(x,y) \in R$ and $(y,z) \in R$
Since R is transitive, so $(x,z) \in R$ and then $(x,z) \in S$

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

Case#3: (x = y) and $(y,z) \in R$
Then $(x,z) \in S$

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

Thus $(x,z) \in S$. Since x,y,z are arbitrary so S is transitive

Hence S is partial order on A

(b) Suppose R is total order. Let x,y be arbitrary elements of A. consider following cases

Case#1: x = y
Then $(x,y) \in i_A$, and hence $(x,y) \in S$

Case#2: x $\neq$ y
Then either $(x,y) \in R$ or $(y,x) \in R$. Thus either $(x,y) \in S$ or $(y,x) \in S$.

Since x,y are arbitrary so S is total order

Ex-5:
(a) Clearly S = $R \setminus i_A$ is a subset of (A X A) and $S \subseteq R$. Let x,y be arbitrary elements of A s.t. $(x,y) \in S$. Then $(x,y) \in R$ and $(x,y) \notin i_A$. Since $(x,y) \notin i_A$. So $x \neq y$. Since x,y are arbitrary so S is irreflexive. Thus S is an element of the family of sets {$T \subseteq A X A | T \subseteq$ R and T-is-irreflexive}
Let T be an arbitrary element of {$T \subseteq A X A | T \subseteq$ R and T-is-irreflexive}. Let x,y be arbitrary elements of A s.t. $(x,y) \in T$. Since $T \subseteq R$, so $(x,y) \in R$. Since T is irreflexive, so $x \neq y$ and hence $(x,y) \notin i_A$. Thus $(x,y) \in R \setminus i_A$. Hence $(x,y) \in S$. Since x,y are arbitrary so $T \subseteq S$. Since T is arbitrary, so S is the largest element.

(b) We proved that S is irreflexive in part(a). Let x,y,z be arbitrary elements of A s.t. $(x,y) \in S$ and $(y,z) \in S$. It follows that $(x,y) \in R$ and $(y,z) \in R$ and $x \neq y \neq z$, so $(x,z) \in R$ and $(x,z) \notin i_A$, and hence $(x,z) \in S$. Since x,y,z are arbitrary so S is transitive. Since S is irreflexive and transitive so S is strict partial order.

Ex-6:
(a) R consists of (parent,child) only, while S consists of (parent,child), (grandparent,child),(great-grandparent,child),...
(b) $R \subseteq S \circ S^{-1}$ and $S \circ S^{-1}$ is reflexive, symmetric and transitive

Ex-7:
(a) ($\rightarrow$) Suppose R is reflexive. clearly R satisfies all 3 properties of reflexive closure of R as R is reflexive, $R \subseteq R$ and R is the smallest of all the reflexive relations of which R is a subset. Thus R is reflexive closure of itself.
($\leftarrow$) Suppose R is its own reflexive closure. Then by definition of reflexive closure, R is reflexive.

(b) Theorem: R is symmetric iff R is its own symmetric closure.
Proof: ($\rightarrow$) Suppose R is symmetric. clearly R satisfies all 3 properties of symmetric closure of R as R is symmetric, $R \subseteq R$ and R is the smallest of all the symmetric relations of which R is a subset. Thus R is symmetric closure of itself.
($\leftarrow$) Suppose R is its own symmetric closure. Then by definition of symmetric closure, R is symmetric

Theorem: R is transitive iff R is its own transitive closure.
Proof: this is also true and proof is very similar to the last theorem

Ex-8: We will prove that
Dom(S) = Ran(S)
Ran(S) = Dom(R) $\cup$ Ran(R)
Dom(R) $\cup$ Ran(R) = Dom(S)

and that will establish that Dom(S) = Ran(S) = Dom(R) $\cup$ Ran(R)

Proof for Dom(S) = Ran(S):
Let x be arbitrary element of A s.t.
$x \in Dom(S)$ iff
$\exists y \in A ((x,y) \in S)$ iff ...(since S is symmetric,so..)
$\exists y \in A ((y,x) \in S)$ iff
$x \in Ran(S)$

Thus Dom(S) = Ran(S)

Proof for Ran(S) = Dom(R) $\cup$ Ran(R):
($\rightarrow$) Let y be an arbitrary element of Ran(S). Then we can chose a $x \in A$ s.t. $(x,y) \in S$. Since S is symmetric closure of R, so S = $R \cup R^{-1}$. It follows that either $(x,y) \in R$ or $(x,y) \in R^{-1}$. Thus x is either in Dom(R) or in Ran(R). Since x is arbitrary so $Ran(S) \subseteq Dom(R) \cup Ran(R)$
($\leftarrow$) Let y be an arbitrary element of $Dom(R) \cup Ran(R)$. Let us consider the two cases
Case#1: $y \in Dom(R)$
Then, we can choose a $x \in A$ s.t. $(y,x) \in R$. Since $R \subseteq S$, so $(y,x) \in S$. Since S is symmetric, so $(x,y) \in S$. Thus $y \in Ran(S)$

Case#2: $y \in Ran(R)$
Then, we can choose a $x \in A$ s.t. $(x,y) \in R$. Since $R \subseteq S$, so $(x,y) \in S$. Thus $y \in Ran(S)$

Since y is arbitrary, so $Dom(R) \cup Ran(R) \subseteq Ran(S)$

Thus Ran(S) = Dom(R) $\cup$ Ran(R)

Proof for Dom(R) $\cup$ Ran(R) = Dom(S)
This proof is very similar to the one shown above

Ex-9: Let T = {$(x,y) \in S | x \in Dom(R) \land y \in Ran(R)$}
Let (a,b) be an arbitrary ordered pair in R. Since $R \subseteq S$, so $(a,b) \in S$. And, clearly $a \in Dom(R)$ and $b \in Ran(R)$. So $(a,b) \in T$. Since a,b are arbitrary so $R \subseteq T$.
Let a,b,c be arbitrary s.t. $(a,b) \in T$ and $(b,c) \in T$. Then $(a,b) \in S$ and $(b,c) \in S$ and $a \in Dom(R)$ and $b \in Ran(R)$ and $b \in Dom(R)$ and $c \in Ran(R)$. Since S is transitive, so $(a,c) \in S$.. And since $a \in Dom(R)$ and $c \in Ran(R)$, so $(a,c) \in T$. Since a,b,c are arbitrary so T is transitive.
But, since S is transitive closure of R so $S \subseteq T$.

Proof for Dom(S) = Dom(R):
Its clear that $Dom(R) \subseteq Dom(S)$ since $R \subseteq S$. Let x be an arbitrary element of Dom(S), then we can choose a y s.t. $(x,y) \in S$. Since $S \subseteq T$, so $(x,y) \in T$. So $x \in Dom(R)$. Since x is arbitrary, so $Dom(S) \subseteq Dom(R)$. Thus Dom(S) = Dom(R)

proof for Ran(S) = Ran(R) is similar

Ex-10:
(a) Consider (A X A), clearly $R \subseteq (A X A)$ and $(A X A) \subseteq (A X A)$. So $(A X A) \in F$. Hence $F \neq \emptyset$
(b) Suppose S = $\cap F$.
Let T be an arbitrary element of $F$. Then $R \subseteq T$. Since T is arbitrary, so $R \subseteq \cap F$. Hence $R \subseteq S$.

Let (x,y) be an arbitrary element of $\cap F$. Then for any arbitrary $T \in F$, $(x,y) \in T$. Since T is symmetric, so $(y,x) \in T$ also. Since T is arbitrary, so $(y,x) \in \cap F$. Since x,y are arbitrary so $\cap F$ or S is symmetric.

Let Q be an arbitrary symmetric relation on A s.t. $R \subseteq Q$. Then $Q \in F$. Thus $\cap F \subseteq Q$. Hence $S \subseteq Q$.

Thus S is symmetric closure of R

Ex-11:
(a) Suppose $R_1 \subseteq R_2$. Let $S_1$ and $S_2$ be reflexive closures of $R_1$ and $R_2$ respectively, so $S_1 = R_1 \cup i_A$ and $S_2 = R_2 \cup i_A$.. Let (x,y) be an arbitrary ordered pair in $S_1$. Then either $(x,y) \in R_1$ or (x = y). It follows that either $(x,y) \in R_2$ or (x = y). Then $(x,y) \in S_2$. Since x,y are arbitrary so $S_1 \subseteq S_2$

(b) Theorem: Suppose $R_1 \subseteq R_2$. Let $S_1$ and $S_2$ be symmetric closures of $R_1$ and $R_2$ respectively, then $S_1 \subseteq S_2$.
Proof: Let (x,y) be arbitrary ordered pair of $S_1$. Then $(x,y) \in R_1 \cup R_1^{-1}$. Let us consider two possible cases
Case#1: $(x,y) \in R_1$
Then $(x,y) \in R_2$, and then $(x,y) \in S_2$

Case#2: $(x,y) \in R_1^{-1}$
Then $(y,x) \in R_1$, then $(y,x) \in S_2$. Since $S_2$ is symmetric, so $(x,y) \in S_2$

Thus $(x,y) \in S_2$. Since x,y are arbitrary so $S_1 \subseteq S_2$

Theorem: Suppose $R_1 \subseteq R_2$. Let $S_1$ and $S_2$ be transitive closures of $R_1$ and $R_2$ respectively, then $S_1 \subseteq S_2$.
Proof: Let (x,y) be an arbitrary ordered pair in $S_1$. Then either $(x,y) \in R_1$ or we can choose a $z \in A$ s.t. $(x,z) \in R_1$ and $(z,y) \in R_1$. Let us consider both the cases
Case#1: $(x,y) \in R_1$
Then $(x,y) \in R_2$, so $(x,y) \in S_2$

Case#2: we can choose $z \in A$ s.t. $(x,z) \in R_1$ and $(z,y) \in R_1$
Then $(x,z) \in R_2$ and $(z,y) \in R_2$. Then $(x,z) \in S_2$ and $(y,z) \in S_2$. Since $S_2$ is symmetric, so $(x,y) \in S_2$

Thus $(x,y) \in S_2$. Since x,y are arbitrary so $S_1 \subseteq S_2$

Ex-12: Since $R = R_1 \cup R_2$, so $R_1 \subseteq R$ and also $R_2 \subseteq R$
(a) ($\rightarrow$) Using the results from Ex-11, $S_1 \subseteq S$ and $S_2 \subseteq S$. Thus $S_1 \cup S_2 \subseteq S$.
($\leftarrow$) Let (x,y) be an ordered pair in S, Then $(x,y) \in R \cup i_A$. So $(x,y) \in R_1 \cup R_2 \cup i_A$. Let us consider all 3 cases
Case#1: $(x,y) \in R_1$
Then $(x,y) \in S_1$, so $(x,y) \in S_1 \cup S_2$

Case#2: $(x,y) \in R_2$
Then $(x,y) \in S_2$, so $(x,y) \in S_1 \cup S_2$

Case#3: $(x,y) \in i_A$
Then (x = y), then $(x,y) \in S_1$ because $S_1$ is reflexive, hence $(x,y) \in S_1 \cup S_2$

Thus $(x,y) \in S_1 \cup S_2$. Since x,y are arbitrary so $S \subseteq S_1 \cup S_2$.

Hence $S_1 \cup S_2 = S$

(b) ($\rightarrow$) Using the results from Ex-11, $S_1 \subseteq S$ and $S_2 \subseteq S$. Thus $S_1 \cup S_2 \subseteq S$.
($\leftarrow$) Let (x,y) be an arbitrary ordered pair in S. Then $(x,y) \in R \cup R^{-1}$. Let us consider both the cases
Case#1: $(x,y) \in R$
Then either $(x,y) \in R_1$ or $(x,y) \in R_2$. Then either $(x,y) \in S_1$ or $(x,y) \in S_2$. So $(x,y) \in S_1 \cup S_2$

Case#2: $(x,y) \in R^{-1}$
Then $(x,y) \in (R_1 \cup R_2)^{-1}$, so $(x,y) \in R_1^{-1} \cup R_2^{-1}$. Then either $(x,y) \in R_1^{-1}$ or $(x,y) \in R_2^{-1}$. Then either $(y,x) \in R_1$ or $(y,x) \in R_2$. Then either $(y,x) \in S_1$ or $(y,x) \in S_2$. Since $S_1$ and $S_2$ are symmetric, so either $(x,y) \in S_1$ or $(x,y) \in S_2$. Thus $(x,y) \in S_1 \cup S_2$

Thus $(x,y) \in S_1 \cup S_2$. Since x,y are arbitrary so $S \subseteq S_1 \cup S_2$.

Hence $S_1 \cup S_2 = S$

(c) Using the results from Ex-11, $S_1 \subseteq S$ and $S_2 \subseteq S$. Thus $S_1 \cup S_2 \subseteq S$.

Ex-13:
(a) $S_1 \cap S_2$
= $(R_1 \cup i_A) \cap (R_2 \cup i_A)$
= $[R_1 \cap (R_2 \cup i_A)] \cup [i_A \cap (R_2 \cup i_A)]$
= $[(R_1 \cap R_2) \cup (R_1 \cap i_A)] \cup [(i_A \cap R_2) \cup (i_A \cap i_A)]$
= $R \cup (R_1 \cap i_A) \cup (R_2 \cap i_A) \cup i_A$
= $(R \cup i_A) \cup (R_1 \cap i_A) \cup (R_2 \cap i_A)$
= $S \cup (R_1 \cap i_A) \cup (R_2 \cap i_A)$

Clearly, $S \subseteq S_1 \cap S_2$

(b) $S_1 \cap S_2$
= $(R_1 \cup R_1^{-1}) \cap (R_2 \cup R_2^{-1})$
= $[R_1 \cap (R_2 \cup R_2^{-1})] \cup [R_1^{-1} \cap (R_2 \cup R_2^{-1})]$
= $[(R_1 \cap R_2) \cup (R_1 \cap R_2^{-1})] \cup [(R_1^{-1} \cap R_2) \cup (R_1^{-1} \cap R_2^{-1})]$
= $[R \cup (R_1 \cap R_2^{-1})] \cup [(R_1^{-1} \cap R_2) \cup R^{-1}]$
= $(R \cup R^{-1}) \cup (R_1 \cap R_2^{-1}) \cup (R_1^{-1} \cap R_2)$
= $S \cup (R_1 \cap R_2^{-1}) \cup (R_1^{-1} \cap R_2)$

clearly, $S \subseteq S_1 \cap S_2$

(c) Using the result from Ex-14(c) in section-4.3, $S_1 \cap S_2$ is transitive. Since $R_1 \cap R_2 \subseteq S_1 \cap S_2$, so by definition of transitive closure $S \subseteq S_1 \cap S_2$.

Ex-14: TODO

Ex-15: We will prove that $R \cup R^{-1} \cup i_A$ is the reflexive symmetric closure of R, which always exists.
its clear that $R \subseteq R \cup R^{-1} \cup i_A$.

Since $R \cup i_A$ is reflexive closure of R, so $R \cup i_A$ is reflexive and hence $R \cup i_A \cup R^{-1}$ is also reflexive. Using a similar argument, since $R \cup R^{-1}$ is symmetric closure of R and hence symmetric. Thus $R \cup R^{-1} \cup i_A$ is also symmetric.

Let T be an arbitrary relation on A s.t. $R \subseteq T$ and T is reflexive as well as symmetric on A. Let (x,y) be an arbitrary ordered pair in $R \cup R^{-1} \cup i_A$. Then let us consider following cases

Case#1: $(x,y) \in R$
Then $(x,y) \in T$

Case#2: $(x,y) \in R^{-1}$
Then $(y,x) \in R$. Then $(y,x) \in T$. Since T is symmetric, so $(x,y) \in T$

Case#3: $(x,y) \in i_A$
Then (x = y). Since T is reflexive, so $(x,y) \in T$

Thus $(x,y) \in T$. Since x,y are arbitrary so $(R \cup R^{-1} \cup i_A) \subseteq T$

Since $R \cup R^{-1} \cup i_A$ satisfies all the properties of reflexive symmetric closure of R, hence it is reflexive symmetric closure of R. So, clearly it exists.

Ex-16:
(a) Suppose R is symmetric. Let (x,y) be an arbitrary ordered pair in S. Then $(x,y) \in R \cup i_A$. So either $(x,y) \in R$ or $(x,y) \in i_A$. It follows that either $(y,x) \in R$ or $(y,x) \in i_A$. Thus $(y,x) \in R \cup i_A$. So $(y,x) \in S$. Since x,y are arbitrary so S is symmetric.

(b) Suppose R is transitive. Let (x,y) and (y,z) be two arbitrary ordered pairs in S. It follows that either $(x,y) \in R$ of $(x,y) \in i_A$ and either $(y,z) \in R$ or $(y,z) \in i_A$. Let us consider this exhaustive set of cases.
Case#1: $(x,y) \in R$ and $(y,z) \in R$
Then $(x,z) \in R$. So $(x,z) \in R \cup i_A$. So $(x,z) \in S$

Case#2: $(x,y) \in R$ and $(y,z) \in i_A$
So (y = z). So, $(x,z) \in R$. Thus $(x,z) \in S$

Case#3: $(x,y) \in i_A$ and $(y,z) \in R$
Then (x = y). Then $(x,z) \in R$. Thus $(x,z) \in S$

Case#4: $(x,y) \in i_A$ and $(y,z) \in i_A$
Then (x = y = z). Thus $(x,z) \in S$

So, $(x,z) \in S$. Since x,y,z are arbitrary so S is transitive

Ex-17: Suppose R is symmetric. Let (x,y) be an arbitrary ordered pair in R. It follows from the assumption that $(y,x) \in R$. Then $(y,x) \in S$ and hence $(x,y) \in S^{-1}$. Since x,y are arbitrary so $R \subseteq S^{-1}$.

Let x,y,z be arbitrary elements of A s.t. $(x,y) \in S^{-1}$ and $(y,z) \in S^{-1}$. So $(y,x) \in S$ and $(z,y) \in S$. Since S is transitive, so $(z,x) \in S$. Thus $(x,z) \in S^{-1}$. Since x,y,z are arbitrary so $S^{-1}$ is transitive.

Since $S^{-1}$ is transitive and $R \subseteq S^{-1}$, so $S \subseteq S^{-1}$. Its only possible when $S = S^{-1}$. Thus S is symmetric.

Ex-18:
(a) Since Q is symmetric closure of R, so Q is symmetric. Since S is transitive closure of Q and Q is symmetric, it follows from Ex-17 result that S is symmetric also. Thus S is symmetric as well as transitive.
Since $R \subseteq Q$ and $Q \subseteq S$, so $R \subseteq S$.
Let T be an arbitrary relation on A s.t. $R \subseteq T$ and T is symmetric as well as transitive. Since T is symmetric, so $Q \subseteq T$. Since $Q \subseteq T$ and T is transitive, so $S \subseteq T$.
So S follows all 3 properties of being symmetric transitive closure of R. Thus S is symmetric transitive closure of R.

(b) $Q^{'}$ is transitive closure of R and S is transitive closure of Q, Since $R \subseteq Q$, so from Ex-11 $Q^{'} \subseteq S$. Since $S^{'}$ is symmetric closure of $Q^{'}$ and S is symmetric, so $S^{'} \subseteq S$

(c) No, counterexample is A = {1,2,3} and R = {(1,2),(3,2)}

Ex-19: The proof is wrong as it assumes that even after adding more ordered pairs to R to make it transitive it still stays antisymmetric.
The theorem is also incorrect, here is the counterexample
A = {1,2,3}
R = {(1,1),(2,2),(3,3),(1,2),(2,3),(3,1)}

Then S = {(1,1),(2,2),(3,3),(1,2),(2,3),(3,1), (1,3),(2,1)}. clearly S is not antisymmetric and hence not partial order.

Ex-20:
(a) We can basically make a circular list of all the cities and make pair from them to find the minimal element. One example is {(San Francisco, Chicago), (Chicago, Dallas), (Dallas, New York), (New York, Washington-D.C.), (Washington-D.C.,San Francisco)}
(b) No, because there are multiple minimal elements.

1. In exercise 2-a, your missed (b, b) and (d, d).

2. 6 (a): S = {(p, q) ∈ RxR | q is a descendant of p}
(b): S∘S^{-1} = {(p, p') ∈ RxR | p and p' share a common ancestor}.

3. For exercise 8, it's easier to prove that Dom(S) ⊆ Ran(S), Ran(S) ⊆ Dom(R) ∪ Ran(R), and Dom(R) ∪ Ran(R) ⊆ Dom(S).

4. The proof for the transitive case in 11.b is wrong! It's easier to do something like this:

Let F = {T⊆AxA | R_1⊆T and T is transitive}. Since S_2 is the transitive closure of R_2, R_2⊆S_2, so since R_1⊆R_2, it follows that R_1⊆S_2. But S_2 is a transitive relation, so S_2 ∈ F. Therefore, S_1⊆S_2.

The proof is virtually the same for the reflexive and symmetric cases. You just have to replace the occurrences of "transitive" by "reflexive" or "symmetric" correspondingly.

5. 13 (a):
S1∩S2
= (R1∪iA)∩(R2∪iA)
= (R1∩R2)∪iA [Distributive law]
= R∪iA
= S.

(b):
Since R = R1∩R2 ⊆ S1∩S2 and S1∩S2 is symmetric, S ⊆ S1∩S2.
To see that S1∩S2 ⊈ S, here's a counterexample:

A = {1, 2, 3}
R1 = {(1, 2)}
R2 = {(2, 1), (2, 3)}
S1 = {(1, 2), (2, 1)}
S2 = {(1, 2), (2, 1), (2, 3), (3, 2)}
S1∩S2 = {(1, 2), (2, 1)}
R1∩R2 = ∅
S = ∅

(c):
Since R = R1∩R2 ⊆ S1∩S2 and S1∩S2 is transitive, S ⊆ S1∩S2.
To see that S1∩S2 ⊈ S, here's a counterexample:

A = {1, 2, 3}
R1 = {(1, 3)}
R2 = {(1, 2), (2, 3)}
S1 = {(1, 3)}
S2 = {(1, 2), (1, 3), (2, 3)}
S1∩S2 = {(1, 3)}
R1∩R2 = ∅
S = ∅

6. I can see why you left 14 as "TODO". It was way harder than I thought, but here's how I did it. First, I noticed that no matter what R1 and R2 are, R1\R2 ⊆ R1 is always true, so R ⊆ R1. Therefore, by the result of exercise 11, S ⊆ S1 is also always true. Hence, the first constraint that the relations need to meet is that S2 must "remove" at least one element from S1 that is also in S in the S1\S2 operation, such that S ⊈ S1\S2. Then I noticed if R1\R2 = R1, then S = S1, so S1\S2 ⊆ S1 = S. Thus, R2 needs to remove something from R1, or we'll be forced to arrive at a result where S1\S2 ⊆ S. But what exactly does it need to remove from R1? The next hint comes from the fact that S1\S2 ⊈ S means that there is an element in S1\S2 that is not in S. In other words, after S2 has been subtracted from S1, there needs to be an element that is in S1 but not in S. This means that whatever element R2 removes from R1, it should help us in realizing this goal.

After playing with a few values while keeping these constraints in mind, I arrived at the following example.

A = {a, b, c, u, v, w}
R1 = {(a, b), (b, c), (u, v), (v, w)}
S1 = {(a, b), (b, c), (a, c), (u, v), (v, w), (u, w)}
R2 = {(a, c), (u, v)}
S2 = {(a, c), (u, v)}
R = R1\R2 = {(a, b), (b, c), (v, w)}
S = {(a, b), (b, c), (a, c), (v, w)}

S1\S2 = {(a, b), (b, c), (v, w), (u, w)}

7. Exercise 15 (a): the reasoning to show that S is reflexive and symmetric is incorrect. It is reflexive because iA ⊆ S, and it is symmetric because S is equal to its inverse.