how to prove it - ch4, sec4.3(More About Relations)

This section introduces another notation for Relation. It is motivated by the fact that in mathematics we often express a relationsip between two objects x and y by putting some symbol between them, e.g. x < y, x = y etc.
Imitating these notations, if R is a relation from A to B, $x \in A$ and $y \in B$, mathematicians sometimes write xRy to mean $(x,y) \in R$

Another way to think about relations is to draw pictures of them with two ovals representing A and B with dots in them for each element, and for each pair $(x,y) \in R$ draw an arrow from dot representing x to dot representing y.

If R is a relation from A to A, then it is sometimes also called a relation on A(or a binary relation on A). For example identity relation(=) is a binary relation. Binary relations can be represented with directed graphs.

Suppose R is a (binary)relation on A then

- R is reflexive on A if $\forall x \in A (x,x) \in R$

- R is symmetric if $\forall x \in A \forall y \in A ((x,y) \in R \rightarrow (y,x) \in R)$

- R is transitive if $\forall x \in A \forall y \in A \forall z \in A ((x,y) \in R \land (y,z) \in R \rightarrow (x,z) \in R)$


Moreover, what follows is that

- R is reflexive iff $i_A \subseteq R$, where $i_A$ is the identity relation on A

- R is symmetric iff $R^{-1}$ = R

- R is transitive iff $R \circ R \subseteq R$


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

Ex-4
(a) {(a,c), (b,d), (c,c), (d,a), (d,b)}
reflexive: no
symmetric: no
transitive: no

(b) {(a,b), (a,d), (b,a), (b,d)}
reflexive: no
symmetric: no
transitive: yes

(c) {(a,a), (b,b), (b,d), (c,c), (d,d), (d,b)}
reflexive: yes
symmetric: yes
transitive: yes

(d) {(a,b), (a,c), (a,d), (b,d), (c,d)}
reflexive: no
symmetric: no
transitive: yes


Ex-5: {(a,y), (a,z), (b,x), (c,y), (c,z)}


Ex-6: $D_r \circ D_s$ = {$(x,z) \in R X R | \exists y \in R (|x - y| < r \land |y - z| < s)$}

Since |a + b| < |a| + |b|

so |(x-y) + (y-z)| < |x-y| + |y-z| < r + s
=> |x - z| < r + s

Hence, $D_r \circ D_s$ = {$(x,z) \in R X R | |x - z| < r + s$}


Ex-7: ($\rightarrow$) Suppose R is reflexive. Let x be an arbitrary element of A s.t. $(x,x) \in i_A$. It follows from our assumption that $(x,x) \in R$. Since x is arbitrary, so $i_A \subseteq R$
($\leftarrow$) Suppose $i_A \subseteq R$. Let x be an arbitrary element of A, then $(x,x) \in i_A$. It follows from our assumption that $(x,x) \in R$. Since x is arbitrary, so R is reflexive.


Ex-8: ($\rightarrow$) Suppose R is transitive. Let x, z be arbitrary elements of A s.t. $(x,z) \in R \circ R$. Then, there exists a $y \in A$ s.t. $(x, y) \in R$ and $(y,z) \in R$. It follows from our assumption that $(x,z) \in R$. Since x and z are arbitrary, so $R \circ R \subseteq R$

($\leftarrow$) Suppose $R \circ R \subseteq R$. Let x,y,z be arbitrary elements of A s.t. $(x,y) \in R$ and $(y,z) \in R$. Then $(x,z) \in R \circ R$. It follows from our assumption that $(x,z) \in R$. Since x,z are arbitrary, so R is transitive


Ex-9:
(a) Let x be arbitrary elements of A and z be an arbitrary element of B s.t. $(x,z) \in R \circ i_A$
So, $(x,z) \in R \circ i_A$ iff
$\exists y \in A ((x,y) \in i_A \land (y,z) \in R)$

Since $(x,y) \in i_A$ iff x = y

So, $(x,x) \in i_A \land (x,z) \in R$ iff
$(x,z) \in R$

Since x,z are arbitrary, so $R \circ i_A = R$

(b) Let x be an arbitrary elements of A and z be an arbitrary element of B s.t. $(x,z) \in i_B circ R$
So $(x,z) \in i_B \circ R$ iff
$\exists y \in B ((x,y) \in R \land (y,z) \in i_B)$

Since $(y,z) \in i_B$ iff y = z

So, $(x,z) \in R \land (z,z) \in i_B$ iff
$(x,z) \in R$

Since x,z are arbitrary, so $i_B \circ R = R$


Ex-10:
Let x be an arbitrary element of A s.t. $(x,x) \in i_D$. Then $x \in D$, so $x \in Dom(S)$. Then there exists a $y \in A$ s.t. $(x,y) \in S$. Then $(y,x) \in S^{-1}$. So $(x,x) \in S^{-1} \circ S$. Since x is arbitrary, so $i_D \subseteq S^{-1} \circ S$

Let x be an arbitrary element of A s.t. $(x,x) \in i_R$. Then $x \in R$, so $x \in Ran(S)$. Then there exists a $y \in A$ s.t. $(y,x) \in S$. Then $(x,y) \in S^{-1}$. So $(x,x) \in S \circ S^{-1}$. Since x is arbitrary, so $i_R \subseteq S \circ S^{-1}$


Ex-11: Suppose R is reflexive. Let x,z be elements of A s.t. $(x,z) \in R$. It follows from our assumption that $(x,x) \in R$ and $(z,z) \in R$. Since $(x,x) \in R$ and $(x,z) \in R$, so $(x,z) \in R \circ R$. Since x,z are arbitrary, so $R \subseteq R \circ R$


Ex-12:
(a) Suppose R is reflexive. Let x be an arbitrary element of A. It follows from our assumption that $(x,x) \in R$. Then $(x,x) \in R^{-1}$ also. Since x is arbitrary, so If R is reflexive then $R^{-1}$ is also reflexive

(b) Suppose R is symmetric. Let x,y be arbitrary elements of A s.t. $(x,y) \in R$. It follows from our assumption that $(y,x) \in R$ also. Then $(x,y) \in R^{-1}$ and $(y,x) \in R^{-1}$ as well. Since x, y are arbitrary, so If R is symmetric then so is $R^{-1}$

(c) Suppose R is transitive. Let x,y,z be arbitrary elements of A s.t. $(x,y) \in R$ and $(y,z) \in R$. It follows from our assumption that $(x,z) \in R$ also. Since $(x,y) \in R$, so $(y,x) \in R^{-1}$. Since $(y,z) \in R$, so $(z,y) \in R^{-1}$. And since $(x,z) \in R$, so $(z,x) \in R^{-1}$. Since x,y,z are arbitrary, so If R is transitive then so is $R^{-1}


Ex-13:
(a) Its true. Suppose R1 and R2 are reflexive. Let x be an arbitrary element of A. It follows from our assumption that $(x,x) \in R1$. Then $(x,x) \in R1 \cup R2$ also. Since x is arbitrary, so If R1 and R2 are reflexive then $R1 \cup R2$ is reflexive too.

(b) Its true. Suppose R1 and R2 are symmetric. Let x,y be arbitrary elements of A s.t. $(x,y) \in R1 \cup R2$. Then $(x,y) \in R1$ or $(x,y) \in R2$. Let us consider both the cases
Case#1: $(x,y) \in R1$
Since R1 is symmetric, so $(y,x) \in R1$. Then $(y,x) \in R1 \cup R2$

Case#2: $(x,y) \in R2$
Since R2 is symmetric, so $(y,x) \in R2$. Then $(y,x) \in R1 \cup R2$

Therefore $(y,x) \in R1 \cup R2$. Since x, y are arbitrary, so If R1 and R2 are symmetric then so is $R1 \cup R2$

(c) Its false. Here is the counterexample.
A = $R$

R1 = {(0,1), (1,2), (0,2)} //Its transitive
R2 = {(2,3), (3,4), (2,4)} //Its transitive

$R1 \cup R2$ = {(0,1), (1,2), (0,2), (2,3), (3,4), (2,4)}
Its not transitive as $(0,2) \in R1 \cup R2$ and $(2,3) \in R1 \cup R2$ but $(0,3) \notin R1 \cup R2$


Ex-14:
(a) Its true. Suppose R1 and R2 are reflexive. Let x be an arbitrary element of A. It follows from our assumption that $(x,x) \in R1$ and $(x,x) \in R2$. So $(x,x) \in R1 \cap R2$. Since x is arbitrary, so If R1 and R2 are reflexive then so is $R1 \cap R2$

(b) Its true. Suppose R1 and R2 are symmetric. Let x,y be arbitrary elements of A s.t. $(x,y) \in R1 \cap R$. Then $(x,y) \in R1$ and $(x,y) \in R2$. Then $(y,x) \in R1$ and $(y,x) \in R2$. So $(y,x) \in R1 \cap R2$. Since x,y are arbitrary so If R1 and R2 are symmetric then so is $R1 \cap R2$

(c) Its true. Suppose R1 and R2 are transitive. Let x,y,z be arbitrary elements of A s.t. $(x,y) \in R1 \cap R2$ and $(y,z) \in R1 \cap R2$. So $(x,y) \in R1$ and $(y,z) \in R1$, thus $(x,z) \in R1$. Also $(x,y) \in R2$ and $(y,z) \in R2$, thus $(x,z) \in R2$. Therefore $(x,z) \in R1 \cap R2$. Since x,y,z are arbitrary so If R1 and R2 are transitive then so is $R1 \cap R2$


Ex-15:
(a) Its false. Here is the counterexample.
A = {0,1}
R1 = {(0,0), (1,1), (0,1)}
R2 = {(0,0), (1,1)}

$R1 \setminus R2$ = {(0,1)}
clearly, its not reflexive

(b) Its true. Suppose R1 and R2 are symmetric. Let x,y be arbitrary elements of A s.t. $(x,y) \in R1 \setminus R2$. Then $(x,y) \in R1$ and $(x,y) \notin R2$. Since $(x,y) \in R1$, it follows from our assumption that $(y,x) \in R1$. Since $(x,y) \notin R2$, it follows from our assumption that $(y,x) \notin R2$. So $(y,x) \in R1 \setminus R2$. Since x,y are arbitrary, so if R1 and R2 are symmetric then so is $R1 \setminus R2$

(c) Its false, here is the counterexample

R1 = {(0,1), (1,2), (0,2)}
R2 = {(0,2)}

$R1 \setminus R2$ = {(0,1), (1,2)}
clearly its not transitive


Ex-16: Suppose R and S are reflexive relations on A. Let x be an arbitrary element of A. It follows from our assumption that $(x,x) \in R$ and $(x,x) \in S$. Thus $(x,x) \in R \circ S$. Since x is arbitrary, so If R and S are reflexive then so is $R \circ S$


Ex-17: Suppose R and S are symmetric relations on A.
($\rightarrow$) Suppose $R \circ S$ is symmetric.
Let x,z be arbitrary elements of A s.t. $(x,z) \in R \circ S$. Since $R \circ S$ is symmetric, so $(z,x) \in R \circ S$. Then there exists a $y \in A$ s.t. $(z,y) \in S$ and $(y,x) \in R$. Since R is symmetric, so $(x,y) \in R$. Also since S is symmetric, so $(y,z) \in S$. Since $(x,y) \in R$ and $(y,z) \in S$, so $(x,z) \in S \circ R$. Since x,z are arbitrary, so $R \circ S \subseteq S \circ R$
Again let x,z be arbitrary elements of A s.t. $(x,z) \in S \circ R$. Then there exists a $y \in A$ s.t. $(x,y) \in R$ and $(y,z) \in S$. Since R is symmetric, so $(y,x) \in R$. Since S is symmetric, so $(z,y) \in S$. Since $(y,x) \in R$ and $(z,y) \in S$, so $(z,x) \in R \circ S$. Since $R \circ S$ is symmetric, so $(x,z) \in R \circ S$. Since x,z are arbitrary, so $S \circ R \subseteq R \circ S$.
Hence If $R \circ S$ is symmetric then $R \circ S$ = $S \circ R$

($\leftarrow$) Suppose $R \circ S$ = $S \circ R$. Let x,z be arbitrary elements of A s.t. $(x,z) \in R \circ S$. It follows from our assumption that $(x,z) \in S \circ R$. Then there exists a $y \in A$ s.t. $(x,y) \in R$ and $(y,z) \in S$. Since R is symmetric, so $(y,x) \in R$. Since S is symmetric, so $(z,y) \in S$. Thus $(z,x) \in R \circ S$. Since x and z are arbitrary, so If $R \circ S$ = $S \circ R$ then $R \circ S$ is symmetric


Ex-18: Suppose R and S are transitive relations on A, $S \circ R \subseteq R \circ S$. Let x,y,z be arbitrary elements of A s.t. $(x,y) \in R \circ S$ and $(y,z) \in R \circ S$.
Since $(x,y) \in R \circ S$, so there exists a $v \in A$ s.t.
$(x,v) \in S$ ...(i) and
$(v,y) \in R$ ...(ii)

Also since $(y,z) \in R \circ S$, so there exists a $w \in A$ s.t.
$(y,w) \in S$ ...(iii) and
$(w,z) \in R$ ...(iv)

From (ii) and (iii)
$(v,w) \in S \circ R$

Since $S \circ R \subseteq R \circ S$, so $(v,w) \in R \circ S$. Then there exists a $m \in A$ s.t.
$(v,m) \in S$ ...(v) and
$(m,w) \in R$ ...(vi)

Since R is transitive, so from (iv) and (vi), $(m,z) \in R$ ...(vii)
Since S is transitive, so from (v) and (i), $(x,m) \in S$ ... (viii)

From (vii) and (viii) $(x,z) \in R \circ S$.

Since x and z are arbitrary, so If R, S are transitive and $S \circ R \subseteq R \circ S$ then $R \circ S$ is transitive.


Ex-19:
(a) If $(X,Y) \in S$ and $(Y,Z) \in S$ then by definition there exist $x \in X$, $y1 \in Y$ s.t. xRy1 and there exist $y2 \in Y$ and $z \in Z$ s.t. y2Rz, where y1 and y2 may or may not be equal. given proof assumes them to be equal which is not right and that is the flaw in the proof

(b) Given theorem is incorrect, here is the counterexample.
A = {0,1,2,3}

R = {(0,1),(2,3)}

$P(A)$ = {{0}, {1,2}, {3}, ...}

({0},{1,2}) $\in S$ because $(0,1) \in R$
({1,2),{3}) $\in S$ because $(2,3) \in R$
but ({0},{3}) $\notin S$ because $(0,3) \notin R$


Ex-20: Suppose R is transitive. Let X,Y,Z be arbitrary elements of B s.t. $(X,Y) \in S$ and $(Y,Z) \in S$. Let x be an arbitrary element of X, z be an arbitrary element of Z and we can chose a $y \in Y$(we can chose because B contains non-empty subsets of A only, so Y should have atleast one element). Then $(x,y) \in R$ and $(y,z) \in R$. Since R is transitive, so $(x,z) \in R$. Thus $(X,Z) \in S$. Since X,Y,Z are arbitrary so we can conclude that If R is transitive then S is also transitive


Ex-21:
(a) Its true. Suppose R is reflexive. Let X be an arbitrary element of $P(A)$. Let x be an arbitrary element of X. Since $X \in P(A)$, so $X \subseteq A$, then It follows from our assumption that $(x,x) \in R$. So, for every x in X, we have same x in X s.t. $(x,x) \in R$. So $(X,X) \in S$. Since X is arbitrary, so If R is reflexive then S is also reflexive.

(b) Its false, here is the counterexample.
A = {0,1,2}
R = {(0,1), (1,0)}

$P(A)$ = {{0}, {1}, {1,2}, ...}

X = {0}
Y = {1,2}

({0},{1,2}) $\in S$ because $(0,1) \in R$
({1,2},{0}) $\notin S$ because $(2,0) \notin R$

(c) Its true. Suppose R is transitive. Let X,Y,Z be arbitrary elements of $P(A)$ s.t. $(X,Y) \in S$ and $(Y,Z) \in S$. Let x be arbitrary element of X, then we can chose a $y1 \in Y$ s.t. $(x,y1) \in R$. Since $(Y,Z) \in S$, so we can chose a $z1 \in Z$ s.t. $(y1,z1) \in R$. Since $(x,y1) \in R$ and $(y1,z1) \in R$, it follows from our assumption that $(x,z1) \in R$. Since x is arbitrary, so $(X,Z) \in S$. Since X,Z are arbitrary so If R is transitive then S is also transitive


Ex-22: The proof and theorem, both are incorrect. The flaw is in finding a $y \in A$ s.t. $(x,y) \in R$ because its possible that there is no such y. Here is one example.
A = {1,2,3}

R = {(1,2), (2,1), (1,1), (2,2)}

Notice that although R is symmetric as well as transitive but its not reflexive because it doesn't have (3,3)


Ex-23: Analysis:
given: $F \subseteq P(A)$
goal: R is transitive $\equiv$ If x,y,z are arbitrary elements of A s.t. $(x,y) \in R$ and $(y,z) \in R$ then $(x,z) \in R$

Assume the hypotheses

given: $F \subseteq P(A)$; x,y and z are arbitrary elements of A s.t. $(x,y) \in R$ and $(y,z) \in R$
goal: $(x,z) \in R$ $\equiv$ For every $X \subseteq A \setminus \{x,z\}$, if $X \cup \{x\} \in F$ then $X \cup \{z\} \in F$

Let X be arbitrary subset of $A \setminus \{x,z\}$, Assume the hypotheses

given: $F \subseteq P(A)$; x,y and z are arbitrary elements of A s.t. $(x,y) \in R$ and $(y,z) \in R$; $X \subseteq A \setminus \{x,z\}$; $X \cup \{x\} \in F$
goal: $X \cup \{z\} \in F$


Formal Proof:
Let x,y,z be arbitrary elements of A s.t. $(x,y) \in R$ and $(y,z) \in R$. Let X be an arbitrary subset of $A \setminus \{x,z\}$. Suppose $X \cup \{x\} \in F$. Now let us consider following exhaustive set of cases.

Case#1: $y \notin X$
Since $(x,y) \in R$ and $x \notin X$ and $y \notin X$ and $X \cup \{x\} \in F$, so $X \cup \{y\} \in F$ also. Since $(y,z) \in R$, it follows that $X \cup \{z\} \in F$ also

Case#2: $y \in X$
Consider Y = (X $\cup$ {x})\{y}. Since (Y $\cup$ {y} = X $\cup$ {x}), so (Y $\cup$ {y}) $\in F$. Hence (Y $\cup$ {z}) $\in F$.
So ((X $\cup$ {x})\{y} $\cup$ {z}) \in F$

Then, (X\{y} $\cup$ {x}\{y} $\cup$ {z} $\in F$
then, (X\{y} $\cup$ {x} $\cup$ {z}\{y} $\in F$
then, ((X $\cup$ {z})\{y} $\cup$ {x}) $\in F$
then, ((X $\cup$ {z})\{y} $\cup$ {y}) $\in F$
then (X $\cup$ {z} $\in F)


Thus (X $\cup$ {z} $\in F) and hence $(x,z) \in R$ and so R is transitive