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

Relation: Suppose A and B are sets. Then a set $R \subseteq A X B$ is called a relation from A to B.

If x ranges over A and y ranges over B, then clearly the truth set of any statement P(x,y) will also be a relation from A to B. However, a thing to notice is that definition of relation does not require such an statement, any subset of (A X B) is a relation.

Let us see some more definitions, given that R is a relation from A to B and S is a relation from B to C.

Domain of R
Dom(R) = {$a \in A | \exists b \in B ((a,b) \in R))$}

Range of R
Ran(R) = {$b \in B | \exists a \in A ((a,b) \in R))$}

Inverse of R
$R^{-1}$ = {$(b,a) \in (B X A) | (a,b) \in R$}

Composition of Relation S and R
$S \circ R$ = {$(a,c) \in (A X C) | \exists b \in B ((a,b) \in R \land (b,c) \in S)$}
Note that, in general composition is not commutative i.e. $S \circ R \neq R \circ S$

Some Properties:
$(R^{-1})^{-1}$ = R
Dom($R^{-1}$) = Ran(R)
Ran($R^{-1}$) = Dom(R)
$T \circ (S \circ R)$ = $(T \circ S) \circ R$
$(S \circ R)^{-1}$ = $R^{-1} \circ S^{-1}$


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

Ex-1
(a) Domain is the set of all the persons who are parent of someone. Range is the set of all the persons.

(b) Domain is the set of all real numbers. Range is the set of all positive real numbers.


Ex-2
(a) Domain and Range both are set of all the people who have a brother.

(b) Domain is set of all the real numbers. Range is set of all the real numbers less than 1.


Ex-3
(a) $L^{-1} \circ L$ = {$(s,t) \in (S X S) | \exists r \in R ((s,r) \in L \land (r,t) \in L^{-1})$}
= {$(s,t) \in (S X S)$ | s and t share the same dorm room}

(b) $E \circ (L^{-1} \circ L)$ = {$(s,c) \in (S X C)$ | s is a student who shares the dorm room with another student who is enrolled in course c}


Ex-4
(a) $S \circ R$ = {(1,5), (1,6), (1,4), (2,4), (3,6)}

(b) $S \circ S^{-1}$ = {(5,5), (5,6), (6,5), (6,6), (4,4)}


Ex-5
(a) $S^{-1}$ = {(7,4), (8,4), (6,5)}
$S^{-1} \circ R$ = {(1,4), (3,5), (3,4)}

(b) $R^{-1}$ = {(7,1), (6,3), (7,3)}
$R^{-1} \circ S$ = {(4,1), (5,3)}


Ex-6
(a) Clearly Dom(R) and Ran($R^{-1}$), both are a subset of A. Let a be an arbitrary element of Dom(R).
$a \in Dom(R)$ iff $\exists b \in B ((a,b) \in R))$
iff $\exists b \in B ((b,a) \in R^{-1})$
iff $a \in Ran(R^{-1})$

Since a is arbitrary so, Ran($R^{-1}$) = Dom(R)

(b) Dom(R) = Dom($(R^{-1})^{-1}$) = Ran($R^{-1}$)

(c) Suppose an arbitrary ordered pair $(a,d) \in (T \circ S) \circ R$. Then there exists $b \in B$ s.t. $(a,b) \in R$ and $(b,d) \in T \circ S$. Since $(b,d) \in T \circ S$, so there exists a $c \in C$ s.t. $(b,c) \in S$ and $(c,d) \in T$. Now that we have $(a,b) \in R$ and $(b,c) \in S$, so $(a,c) \in S \circ R$. Also since $(c,d) \in T$, so $(a,d) \in T \circ (S \circ R)$.

(d) Clearly $S \circ R$ is a relationship from A to C, so $(S \circ R)^{-1}$ is a relationship from C to A. Suppose an arbitrary ordered pair $(c,a) \in (S \circ R)^{-1}$ where $c \in C$ and $a \in A$.

$(c,a) \in (S \circ R)^{-1}$ iff
$(a,c) \in (S \circ R)$ iff
$\exists b ((a,b) \in R \land (b,c) \in S)$ iff
$\exists b ((b,a) \in R^{-1} \land (c,b) \in S^{-1})$ iff
$(c,a) \in (S^{-1} \circ R^{-1})$

Since (c,a) is arbitrary, clearly $(S \circ R)^{-1}$ = $S^{-1} \circ R^{-1}$


Ex-7 I came up with F = $E \circ E$, then looked the answer in the book which is $E \circ E \subseteq F$, which makes more sense and two friends don't necessarily have to have a common enemy.


Ex-8
(a) Let a be an arbitrary element of Dom($S \circ R$). Then there exists a $c \in C$ s.t. $(a,c) \in S \circ R$. Then there exists a $b \in B$ s.t. $(a,b) \in R$ and $(b,c) \in S$. Since $(a,b) \in R$, so $a \in Dom(R)$. Since a is arbitrary, so Dom($S \circ R$) $\subseteq$ Dom(R).

(b) Suppose $Ran(R) \subseteq Dom(S)$. And $a \in A$ is an arbitrary element of Dom(R). Then there exists a $b \in B$ s.t. $(a,b) \in R$. So $b \in Ran(R)$. It follows from our assumption that $b \in Dom(S)$. Then there exists a $c \in C$ s.t. $(b,c) \in S$. Since $(a,b) \in R$ and $(b,c) \in S$, so $(a,c) \in S \circ R$. And hence $a \in Dom(S \circ R)$. Since a is arbitrary, so $Dom(R) \subseteq Dom(S \circ R)$. In part(a) of this exercise we also proved that $Dom(S \circ R) \subseteq Dom(R)$. Thus If $Ran(R) \subseteq Dom(S)$ then $Dom(S \circ R) = Dom(R)$

(c)
Theorem#1: $Ran(S \circ R) \subseteq Ran(S)$
Proof: Let $c \in C$ be an arbitrary element of $Ran(S \circ R)$. Then there exists $a \in A$ s.t. $(a,c) \in (S \circ R)$. Then there exists $b \in B$ s.t. $(a,b) \in R$ and $(b,c) \in S$. So, $c \in Ran(S)$. Since c is arbitrary so $Ran(S \circ R) \subseteq Ran(S)$

Theorem#2: If $Dom(S) \subseteq Ran(R)$ then $Ran(S \circ R)$ = $Ran(S)$
Proof: Let $c \in C$ be an arbitrary element of Ran(S). Then there exists $b \in B$ s.t. $(b,c) \in S$. So $b \in Dom(S)$. It follows from our assumption that $b \in Ran(R)$. Then there exists $a \in A$ s.t. $(a,b) \in R$. Since $(a,b) \in R$ and $(b,c) \in S$, so $(a,c) \in (S \circ R)$. So $c \in Ran(S \circ R)$. Since c is arbitrary, so $Ran(S) \subseteq Ran(S \circ R)$. In theorem#1 we proved the opposite, so we can conclude that If $Dom(S) \subseteq Ran(R)$ then $Ran(S \circ R)$ = $Ran(S)$


Ex-9
(a) Its true, here is the proof. Let (a,b) be an arbitrary element of R. Then $a \in Dom(R)$ and $b \in Ran(R)$. Then $(a,b) \in Dom(R) X Ran(R)$. Since a and b are arbitrary, so $R \subseteq Dom(R) X Ran(R)$

(b) Its true, here is the proof. Suppose $R \subseteq S$. Let (b,a) be an arbitrary element of $R^{-1}$. Then $(a,b) \in R$. It follows from our assumption that $(a,b) \in S$, so $(b,a) \in S^{-1}$. Since (b,a) is arbitrary so, If $R \subseteq S$ then $R^{-1} \subseteq S^{-1}$.

(c) Its true, here is the proof. Let (a,b) be an arbitrary element of $(R \cup S)^{-1}$
$(a,b) \in (R \cup S)^{-1}$ iff
$(b,a) \in (R \cup S)$ iff
$(b,a) \in R \lor (b,a) \in S$ iff
$(a,b) \in R^{-1} \lor (a,b) \in S^{-1}$ iff
$(a,b) \in R^{-1} \cup S^{-1}$

Since (a,b) is arbitrary, so $(R \cup S)^{-1}$ = $ R^{-1} \cup S^{-1}$


Ex-10
($\rightarrow$) Suppose $S \circ R = \emptyset$. Let arbitrary $b \in B$ be an element of Ran(R). Then there exists $a \in A$ s.t. $(a,b) \in R$. It follows from our assumption that either $b \notin Dom(S)$ or for all $c \in C$, $c \notin Ran(S)$. clearly some $c \in C$ has to be in Ran(S) as S is the relation from B to C, therefore $b \notin Dom(S)$. Since b is arbitrary, so If $S \circ R = \emptyset$ then Ran(R) and Dom(S) are disjoint.

($\leftarrow$) Suppose Ran(R) and Dom(S) are disjoint. We will prove by contradiction that $S \circ R = \emptyset$. Assume $a \in A$, $c \in C$ s.t. (a,c) be an arbitrary element of $S \circ R$. Then there exists a $b \in B$ s.t. $(a,b) \in R$ and $(b,c) \in S$. Since $(a,b) \in R$, so $b \in Ran(R)$. Since $(b,c) \in S$, so $b \in Dom(S)$. So, b is both in Ran(R) and Dom(S) but this is contradictory to our first assumption that Ran(R) and Dom(S) are disjoint. So $S \circ R = \emptyset$.


Ex-11
(a) Let $a \in A$, $c \in C$ be s.t. $(a,c) \in (S \circ R) \setminus (T \circ R)$. Then $(a,c) \in S \circ R$ and $(a,c) \notin T \circ R$. Since $(a,c) \in S \circ R$, so there exists a $b \in B$ s.t. $(a,b) \in R$ and $(b,c) \in S$. Since $(a,c) \notin T \circ R$, so clearly $(b,c) \notin T$. Now that $(b,c) \in S$ and $(b,c) \notin T$, so $(b,c) \in S \setminus T$. Also since $(a,b) \in R$, therefore $(a,c) \in (S \setminus T) \circ R$. Since (a,c) is arbitrary, so $(S \circ R) \setminus (T \circ R) \subseteq (S \setminus T) \circ R$

(b) The proof seems to be correct.

(c) Proof given in part(b) of the exercise is correct.


Ex-12
(a) Its true, here is the proof. Suppose $S \subseteq T$. Let $a \in A$, $c \in C$ be s.t. $(a,c) \in S \circ R$. Then we can chose a $b \in B$ s.t. $(a,b) \in R$ and $(b,c) \in S$. It follows from our assumption that $(b,c) \in T$ as well. Thus $(a,c) \in T \circ R$. Since a,c are arbitrary, so If $S \subseteq T$ then $S \circ R \subseteq T \circ R$

(b) Its true, here is the proof. Let $a \in A$, $c \in C$ be s.t. $(a,c) \in (S \cap T) \circ R$. Then we can chose a $b \in B$ s.t. $(a,b) \in R$ and $(b,c) \in S$ and $(b,c) \in T$. Clearly, $(a,c) \in S \circ R$ and $(a,c) \in T \circ R$. Thus $(a,c) \in (S \circ R) \cap (T \circ R)$. Since a,c are arbitrary, therefore $(S \cap T) \circ R \subseteq (S \circ R) \cap (T \circ R)$

(c) Its false, here is the counter example.
R = {((2,3), (2,5)}
S = {(3,4)}
T = {(5,4)}

$S \circ R$ = {(2,4)}
$T \circ R$ = {(2,4)}

$(S \circ R) \cap (T \circ R)$ = {(2,4)}

$S \cap T$ = $\emptyset$

$(S \cap T) \circ R$ = $\emptyset$

(d) Its true, here is the proof. Let $a \in A$, $c \in C$ be s.t. $(a,c) \in (S \cup T) \circ R$. Then we can chose a $b \in B$ s.t. $(a,b) \in R$ and $(b,c) \in (S \cup T)$. Since $(b,c) \in (S \cup T)$, so either $(b,c) \in S$ or $(b,c) \in T$. Let us consider both the cases

Case#1: $(b,c) \in S$
Then $(a,c) \in S \circ R$. Thus $(a,c) \in (S \circ R) \cup (T \circ R)$

Case#2: $(b,c) \in T$
Then $(a,c) \in T \circ R$. Thus $(a,c) \in (S \circ R) \cup (T \circ R)$

Since a,c are arbitrary, therefore $(S \cup T) \circ R \subseteq (S \circ R) \cup (T \circ R)$