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.