Monday, May 31, 2010

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

Saturday, May 29, 2010

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)$

Thursday, May 27, 2010

how to prove it - ch4, sec4.1(Ordered Pairs and Cartisian Product)

As the title suggests, this section is about orderderd pairs(pairs where ordering is important) and cartisian product of sets.

Cartisian product of two sets A and B is defined as
A X B = {(a,b) | a $\in$ A and b $\in$ B}
where (a,b) is the ordered pair. Often a is called the first and b is called the second coordinate of the ordered pair.

One important property we might want to notice is that
A X $\emptyset$ = $\emptyset$ X A = $\emptyset$

Now, for any statement P(x,y), where x and y are free variables and x ranges over a set A and y ranges over a set B. Then
Truth set(T) of P(x,y) would be defined as {(a,b) | P(a,b)}

clearly if some (a,b) $\in$ T, then P(a,b)

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

Ex-1(a) {(x,y) | x is a parent of y}

Ex-1(b) {(x,y) | someone lives in x and attends y}

Ex-2(a) {(x,y) | x lives in y} for example {(himanshu,bangalore), ...}

Ex-2(b) {(x,y) | population of x is y} for example
{(bangalore, 1 mn), ...}

Ex-3(a) {(x,y) | y = $x^2 - x - 2$} for example {(0,-2), (1,-2),...}

Ex-3(b) {(x,y) | y < x} for example {(1,0), (2,1), (2,0), ...}

Ex-3(c) {(x,y) | either y = $x^2 - x - 2$ or y = 3x-2 } for example {(0,-2), (1,1), ...}

Ex-3(d) {(x,y) | y < x and either y = $x^2 - x - 2$ or y = 3x-2 }


Ex-4
1. $A X (B \cap C)$
= {1,2,3} X {4}
= {(1,4), (2,4), (3,4)}

(A X B) $\cap$ (A X C)
= {(1,1), (2,1), (3,1), (1,4), (2,4), (3,4)} $\cap$ {(1,3), (2,3), (3,3), (1,4), (2,4), (3,4)}
= {(1,4), (2,4), (3,4)}

2. $A X (B \cup C)$
= {1,2,3} X {1,3,4}
= {(1,1), (2,1), (3,1), (1,3), (2,3), (3,3), (1,4), (2,4), (3,4)}

(A X B) $\cup$ (A X C)
= {(1,1), (2,1), (3,1), (1,4), (2,4), (3,4)} $\cup$ {(1,3), (2,3), (3,3), (1,4), (2,4), (3,4)}
= {(1,1), (2,1), (3,1), (1,3), (2,3), (3,3), (1,4), (2,4), (3,4)}

3. (A X B) $\cap$ (C X D)
= {(1,1), (2,1), (3,1), (1,4), (2,4), (3,4)} $\cap$ {(3,5), (4,5)}
= $\emptyset$

$(A \cap C) X (B \cap D)$
= {3} X $\emptyset$
= $\emptyset$

4. (A X B) $\cup$ (C X D)
= {(1,1), (2,1), (3,1), (1,4), (2,4), (3,4)} $\cap$ {(3,5), (4,5)}
= {(1,1), (2,1), (3,1), (1,4), (2,4), (3,4), (3,5), (4,5)}

$(A \cup C) X (B \cup D)$
= {1,2,3,4} X {1,4,5}
= {(1,1), (2,1), (3,1), (4,1), (1,4), (2,4), (3,4), (4,4), (1,5), (2,5), (3,5), (4,5)}

5. A X $\emptyset$ = $\emptyset$ X A = $\emptyset$


Ex-5
-- Prove $A X (B \cup C)$ = (A X B) $\cup$ (A X C). --

Let p be arbitrary element of $A X (B \cup C)$. It follows that there exist x and y s.t. p = (x,y) and $x \in A$ and $y \in B \cup C$. Since $y \in B \cup C$, so either $y \in B$ or $y \in C$. Let us consider both the cases.

Case#1: $y \in B$
Then $(x,y) \in A X B$. Thus $(x,y) \in (A X B) \cup (A X C)$

Case#2: $y \in C$
Then $(x,y) \in A X C$. Thus $(x,y) \in (A X B) \cup (A X C)$

Since p is arbitrary, we can conclude that $A X (B \cup C) \subseteq (A X B) \cup (A X C)$

Now, Let p be arbitrary element of $(A X B) \cup (A X C)$. Then either $p \in (A X B)$ or $p \in (A X C)$. Let us consider both the cases

Case#1: $p \in (A X B)$
There exist $x \in A$ and $y \in B$ s.t. p = (x,y). clearly $y \in (B \cup C)$ also, so $(x,y) \in A X (B \cup C)$

Case#2: $p \in (A X C)$
By similar argument as above, $(x,y) \in A X (B \cup C)$

Since p is arbitrary, we can conclude that $(A X B) \cup (A X C) \subseteq A X (B \cup C)$

Thus $A X (B \cup C)$ = (A X B) $\cup$ (A X C)

-- Prove that $(A X B) \cap (C X D) = (A \cap C) X (B \cap D)$ --

Let p be an arbitrary element of $(A X B) \cap (C X D)$. Then $p \in (A X B)$ and $p \in (C X D)$. So there exists x and y s.t. p = (x,y) and $x \in A$ and $y \in B$ and $x \in C$ and $y \in D$. So $x \in (A \cap C)$ and $y \in (B \cap D)$. Hence $p \in (A \cap C) X (B \cap D)$. Since p is arbitrary, so $(A X B) \cap (C X D) \subseteq (A \cap C) X (B \cap D)$

Let p be an arbitrary element of $(A \cap C) X (B \cap D)$. It follows there exist x and y s.t. p = (x,y) and $x \in (A \cap C)$ and $y \in (B \cap D)$. So $x \in A$ and $x \in C$ and $y \in B$ and $y \in D$. So $(x,y) \in (A X B)$ and $(x,y) \in (C X D)$. Thus $p \in (A X B) \cap (C X D)$. Since p is arbitrary, so $(A \cap C) X (B \cap D) \subseteq (A X B) \cap (C X D)$

Hence $(A X B) \cap (C X D) = (A \cap C) X (B \cap D)$


Ex-6 Flaw is that all the cases are not considered. Here is the list of cases that is left out in the proof.

$x \in A$ and $y \in D$
$x \in C$ and $y \in B$


Ex-7 m * n


Ex-8 It is true. Here is the proof.

Let p be an arbitrary element of (A X B\C). It follows there exist x and y s.t. p = (x,y) and $x \in A$ and $y \in B \setminus C$. So $y \in B$ and $y \notin C$. Since $x \in A$ and $y \in B$, so $p \in (A X B)$. Since $y \notin C$, so $p \notin (A X C)$. Hence $p \in (A X B) \setminus (A X C)$. Since p is arbitrary, so $(A X B\C) \subseteq (A X B) \setminus (A X C)$

Now let p be an arbitrary element of $(A X B) \setminus (A X C)$. Then $p \in (A X B)$ and $p \notin (A X C)$. It follows that there exist x and y s.t. p = (x,y). Since $p \in (A X B)$, so $x \in A$ and $y \in B$. Since $p \notin (A X C)$, so either $x \notin A$ or $y \notin C$.. but we already saw that $x \in A$, so $y \notin C$. Since $x \in A$, $y \in B$ and $y \notin C$. So $p \in A X (B \setminus C)$. Since p is arbitrary, so $(A X B) \setminus (A X C) \subseteq (A X B\C)$

Thus $(A X B\C) = (A X B) \setminus (A X C)$


Ex-9 Let p be an arbitrary element of $(A X B) \setminus (C X D)$. Then $p \in (A X B)$ and $p \notin (C X D)$. Thus there exist x and y s.t. p = (x,y). Since $p \in (A X B)$, so $x \in A$ and $y \in B$. Since $p \notin (C X D)$, so either $x \notin C$ or $y \notin D$. Let us consider both the cases.

Case#1: $x \notin C$
Since $x \in A$ and $y \in B$ and $x \notin C$, so $p \in (A \setminus C) X B$. Thus $p \in [A X (B \setminus D)] \cup [(A \setminus C) X B]$

Case#2: $y \notin D$
Since $x \in A$ and $y \in B$ and $y \notin D$, so $p \in A X (B \setminus D)$. Thus $p \in [A X (B \setminus D)] \cup [(A \setminus C) X B]$

Since p is arbitrary, $(A X B) \setminus (C X D) \subseteq [A X (B \setminus D)] \cup [(A \setminus C) X B]$

Again, Let p be an arbitrary element of $[A X (B \setminus D)] \cup [(A \setminus C) X B]$. Then either $p \in A X (B \setminus D)$ or $p \in (A \setminus C) X B$. Let us consider both the cases.

Case#1: $p \in A X (B \setminus D)$
Then there exist x and y s.t. p = (x,y) and $x \in A$ and $y \in B$ and $y \notin D$. Since $x \in A$ and $y \in B$, so $p \in (A X B)$. Also since $y \notin D$, so $p \notin (C X D)$. Thus $p \in (A X B) \setminus (C X D)$

Case#2: $p \in (A \setminus C) X B$
we can use similar argument as above case to prove that $p \in (A X B) \setminus (C X D)$

Now since p is arbitrary, so $[A X (B \setminus D)] \cup [(A \setminus C) X B] \subseteq (A X B) \setminus (C X D)$

Thus $(A X B) \setminus (C X D)$ = $[A X (B \setminus D)] \cup [(A \setminus C) X B]$


Ex-10 Suppose (A X B) and (C X D) are disjoint. Let (x,y) be an arbitrary ordered pair of (A X B), it follows that $(x,y) \notin (C X D)$. So either $x \notin C$ or $y \notin D$. Since x,y are arbitrary, Thus either A and C are disjoint or B and D are disjoint.


Ex-11
(a) Let (x,y) be an ordered pair in $\cup_{i \in I}(A_i X B_i)$. Then there exists a particular $k \in I$ s.t. $(x,y) \in A_k X B_k$. It follows that $x \in A_k$ and $y \in B_k$. Since $x \in A_k$, so $x \in \cup_{i \in I}A_i$. Also since $y \in B_k$, so $y \in \cup_{i \in I}B_i$. So $(x,y) \in \cup_{i \in I}A_i X \cup_{i \in I}B_i$. Since x,y is arbitrary, so $\cup_{i \in I}(A_i X B_i) \subseteq \cup_{i \in I}A_i X \cup_{i \in I}B_i$

(b) Let (x,y) be an arbitrary ordered pair in $\cup_{p \in P}C_p$. Then there exists a particular ordered pair (l,m) in P s.t. $(x,y) \in C_{(l,m)}$. Since $C_{(l,m)} = A_l X B_m$, So $(x,y) \in A_l X B_m$. Then $x \in A_l$ and $y \in B_m$. Since $x \in A_l$, so $x \in \cup_{i \in I}A_i$. Also since $y \in B_m$, so $y \in \cup_{i \in I}B_i$. Thus $(x,y) \in \cup_{i \in I}A_i X \cup_{i \in I}B_i$. Since (x,y) is arbitrary, so $\cup_{p \in P}C_p \subseteq \cup_{i \in I}A_i X \cup_{i \in I}B_i$

Again, Let (x,y) be and arbitrary ordered pair in $\cup_{i \in I}A_i X \cup_{i \in I}B_i$. Then $x \in \cup_{i \in I}A_i$ and $y \in \cup_{i \in I}B_i$. Since $x \in \cup_{i \in I}A_i$, so there exists a particular $l \in I$ s.t. $x \in A_l$ and similarly there exists a particular $m \in I$ s.t. $y \in B_m$. So $(x,y) \in A_l X B_m$. Then $(x,y) \in C_{(l,m)}$. So $(x,y) \in \cup_{p \in P}C_p$. Since (x,y) is arbitrary, so $\cup_{i \in I}A_i X \cup_{i \in I}B_i \subseteq \cup_{p \in P}C_p$.

Thus $\cup_{p \in P}C_p$ = $\cup_{i \in I}A_i X \cup_{i \in I}B_i$


Ex-12 The proof and the theorem, both are incorrect. It starts with assuming elements in A and B. It is nowhere given that A and B, both are non-empty set.

Sunday, May 23, 2010

how to prove it - ch3, sec3.7(More Proofs) ex

Ex-1 Existence: Try A = $\cup F$

Let x be an arbitrary element of $F$. It follows that $x \subseteq \cup F$, and hence $x \in P(\cup F)$. Since x is arbitrary, so $F \subseteq P(\cup F)$. clearly $A = \cup F$, satisfies the property that $F \subseteq P(A)$

Now let us see if $\forall B (F \subseteq P(B) \rightarrow A \subseteq B)$.
Let B be an arbitrary set s.t. $F \subseteq P(B)$. Suppose x is an arbitrary element of $\cup F$, then there exists a set $D \in F$ s.t. $x \in D$. Since $F \subseteq P(B)$, so $D \in P(B)$ also. Thus $D \subseteq B$, hence $x \in B$ also. Since x is arbitrary, therefore $\cup F \subseteq B$, clearly $A = \cup F$, satisfies the property that $\forall B (F \subseteq P(B) \rightarrow A \subseteq B)$

Uniqueness: Let there exists another such set D. Then $F \subseteq P(D)$ and $\forall B (F \subseteq P(B) \rightarrow D \subseteq B)$. We can chose B = $\cup F$. Since $F \subseteq P(\cup F)$, so $D \subseteq \cup F$. Since $F \subseteq P(D)$ and $D \subseteq \cup F$, it follows that $D = \cup F = A$


Ex-2 Let x be arbitrary s.t.
$x \in P(A \setminus B) \setminus (P(A) \setminus P(B))$ iff
$x \in P(A \setminus B) \land \lnot x \in (P(A) \setminus P(B))$ iff
$x \in P(A \setminus B) \land \lnot (x \in P(A) \land \lnot x \in P(B))$ iff
$x \in P(A \setminus B) \land (x \notin P(A) \lor x \in P(B))$ iff
$x \subseteq (A \setminus B) \land (\lnot x \subseteq A \lor x \subseteq B)$

clearly $x \subseteq (A \setminus B)$ and either $\lnot x \subseteq A$ or $x \subseteq B$. Since $x \subseteq (A \setminus B)$, so $x \subseteq A$ and $\lnot x \subseteq B$. Clearly there is only one such x possible and that is $\emptyset$.

Hence $P(A \setminus B) \setminus (P(A) \setminus P(B))$ = {$\emptyset$}


Ex-3 We will prove that (a) $\rightarrow$ (b) $\rightarrow$ (c) $\rightarrow$ (a)

Proof for (a) $\rightarrow$ (b):
Suppose $(A \triangle C) \cap (B \triangle C)$ = $\emptyset$. Let x be an arbitrary element of $A \cap B$. We will prove by contradiction that $x \in C$. Assume $x \notin C$, Then $x \in (A \setminus C)$ and hence $x \in (A \triangle C)$. By similar argument $x \in (B \triangle C)$, so $x \in (A \triangle C) \cap (B \triangle C)$. This is a contradiction and hence $x \in C$. Since x is arbitrary, we can conclude that $A \cap B \subseteq C$.
Now, let x be an arbitrary element of C. Again we will prove by contradiction that $x \in A \cup B$. Assume $x \notin A \cup B$, then $x \notin A$ and $x \notin B$. Clearly $x \in (C \setminus A)$, so $x \in (A \triangle C)$. By similar argument $x \in (B \triangle C)$. So $x \in (A \triangle C) \cap (B \triangle C)$, which is a contradiction and hence $x \in A \cup B$. Since x is arbitrary, we can conclude that $A \cap B \subseteq C \subseteq A \cup B$

Proof for (b) $\rightarrow (c):
Suppose $A \cap B \subseteq C \subseteq A \cup B$. Let x be an arbitrary element of $A \triangle C$. So either $x \in A \setminus C$ or $x \in C \setminus A$. Let us consider both the cases

Case#1: $x \in A \setminus C$
Then $x \in A$ and $x \notin C$. Since $A \cap B \subseteq C$, so $x \notin B$. Thus $x \in A \setminus B$, therefore $x \in A \triangle B$

Case#2: $x \in C \setminus A$
Thus $x \in C$ and $x \notin A$. Since $C \subseteq A \cup B$, so $x \in B$. Thus $x \in B \setminus A$, therefore $x \in A \triangle B$

From both the cases, $x \in A \triangle B$. Since x is arbitrary, we can conclude that $A \triangle C \subseteq A \triangle B$

Proof for (c) $\rightarrow (a):
Suppose $A \triangle C \subseteq A \triangle B$. Let x be an arbitrary element of $(A \triangle C) \cap (B \triangle C)$. So $x \in (A \triangle C)$ and $x \in (B \triangle C)$. Since $x \in (A \triangle C)$, it follows that either $x \in A \setminus C$ or $x \in C \setminus A$. Let us consider both the cases

Case#1: $x \in A \setminus C$
Then $x \in A$ and $x \notin C$. Since $x \in (A \triangle C)$, therefore $x \in (A \triangle B)$. Since $x \in (A \triangle B)$ and $x \in A$, so $x \notin B$. It means $x \notin B$ and $x \notin C$, hence $x \notin (B \triangle C)$ and this is a contradiction, so this case is not possible.

Case#2: $x \in C \setminus A$
Then $x \in C$ and $x \notin A$. Since $x \in (A \triangle C)$, therefore $x \in (A \triangle B)$. Since $x \notin A$ and $x \in (A \triangle B)$, so $x \in B$. Since $x \in B$ and $x \in C$, so $x \notin (B \triangle C)$ and this is a contradiction, so this case is not possible.

Since none of the above cases are possible, it means such an x can not exist. Hence $(A \triangle C) \cap (B \triangle C)$ = $\emptyset$


Ex-4
given: $P(\cup_{i \in I}A_i) \subseteq \cup_{i \in I}P(A_i)$
goal: $\exists i \in I (\forall j \in I (A_j \subseteq A_i))$

Let us analyze the goal a little bit. Let us say for a particular $k \in I$, for all $j \in I$, $A_j \subseteq A_k$. Then clearly, $(\cup i \in I A_i) \subseteq A_k$

Formal Proof:
Suppose $P(\cup_{i \in I}A_i) \subseteq \cup_{i \in I}P(A_i)$. Let x be arbitrary element of $P(\cup_{i \in I}A_i)$, Then
$x \in P(\cup_{i \in I}A_i) \rightarrow x \in \cup_{i \in I}P(A_i)$ iff
$x \subseteq (\cup_{i \in I}A_i) \rightarrow \exists i \in I (x \in P(A_i))$ iff

Let us chose a particular $k \in I$ for the conclusion in the above statement. Then

$x \subseteq (\cup_{i \in I}A_i) \rightarrow (x \in P(A_k))$ iff
$x \subseteq (\cup_{i \in I}A_i) \rightarrow x \subseteq A_k$

Thus $(\cup i \in I A_i) \subseteq A_k$.

Ex-5
(a) Let x be an arbitrary element s.t.
$x \in \cup_{X \in F}(\cup_{i \in X}A_i)$ iff
$\exists X \in F (x \in \cup_{i \in X}A_i)$ iff
$\exists X \in F (\exists i \in X x \in A_i)$ iff
$\exists X [X \in F \land \exists i (i \in X \land x \in A_i)$ iff
$\exists X \exists i (X \in F \land i \in X \land x \in A_i)$ iff
$\exists i \exists X (X \in F \land i \in X \land x \in A_i)$ iff
$\exists i (\exists X (X \in F \land i \in X)) \land x \in A_i$ iff
$\exists i (i \in \cup F) \land x \in A_i$ iff
$\exists i (i \in I) \land x \in A_i$ iff
$x \in \cup_{i \in I}A_i$

Therefore $\cup_{i \in I}A_i$ = $\cup_{X \in F}(\cup_{i \in X}A_i)$

(b) Let x be an arbitrary element s.t.
$x \in \cap_{X \in F}(\cap_{i \in X}A_i)$ iff
$\forall X [X \in F \rightarrow (x \in \cap_{i \in X}A_i)]$ iff
$\forall X [X \in F \rightarrow (\forall i (i \in X \rightarrow x \in A_i))]$ iff
$\forall X \forall i [X \in F \rightarrow (i \in X \rightarrow x \in A_i)]$ iff
$\forall i \forall X [X \in F \rightarrow (i \in X \rightarrow x \in A_i)]$ iff
$\forall i ([\forall X (X \in F \rightarrow i \in X)] \rightarrow x \in A_i)$ iff
$\forall i (i \in \cap F \rightarrow x \in A_i)$ iff
$\forall i \in J (x \in A_i)$ iff
$x \in \cap_{i \in J}A_i$

Therefore $\cap_{i \in J}A_i$ = $\cap_{X \in F}(\cap_{i \in X}A_i)$

(c) Suppose x be an arbitrary element of $\cup_{i \in J}A_i$. It follows that there is a particular $k \in J$ s.t. $x \in A_k$. Since J = $\cap F$, so for any arbitrary $X \in F$, $k \in X$. Since $k \in X$ and $x \in A_k$, so $x \in \cup_{i \in X}A_i$. Since X is arbitrary, so $x \in \cap_{X \in F}(\cup_{i \in X}A_i)$. Since x is arbitrary, we can conclude that $\cup_{i \in J}A_i \subseteq \cap_{X \in F}(\cup_{i \in X}A_i)$

Now, let x be an arbitrary element of $\cap_{X \in F}(\cup_{i \in X}A_i)$. Let X be an arbitrary element of $F$. Then $x \in \cup_{i \in X}A_i$, it follows there exists a particular $k \in X$ s.t. $x \in A_k$. Since $k \in X$ and X is arbitrary element of $F$, so $k \in \cap F$. Since J = $\cap F$, so $k \in J$. Since $k \in J$ and $x \in A_k$, therefore $x \in \cup_{i \in J}A_i$. Since x is arbitrary, we can conclude that $\cap_{X \in F}(\cup_{i \in X}A_i) \subseteq \cup_{i \in J}A_i$

Hence, $\cup_{i \in J}A_i$ = $\cap_{X \in F}(\cup_{i \in X}A_i)$

(d) We will prove that $\cap_{i \in J}A_i \subseteq \cup_{X \in F}(\cap_{i \in X}A_i)$.

Suppose x is an arbitrary element of $\cap_{i \in J}A_i$. So for any arbitrary $i \in \cap F$, $x \in A_i$. Since $i \in \cap F$, so for any arbitrary $X \in F$, $i \in X$. Since $i \in X$ and $x \in A_i$, therefore $x \in \cap_{i \in X}A_i$. Since X is arbitrary, so $x \in \cap_{X \in F}(\cap_{i \in X}A_i)$, hence clearly $x \in \cup_{X \in F}(\cap_{i \in X}A_i)$. Since x is arbitrary, therefore $\cap_{i \in J}A_i \subseteq \cup_{X \in F}(\cap_{i \in X}A_i)$

However, $\lnot [\cup_{X \in F}(\cap_{i \in X}A_i) \subseteq \cap_{i \in J}A_i]$. Here is the counter example

$F$ = { {1}, {2} }
$A_1$ = {2}
$A_2$ = {3}
J = $\cap F$ = $\emptyset$

$\cup_{X \in F}(\cap_{i \in X}A_i)$ = {2,3}
$\cap_{i \in J}A_i$ = $\emptyset$


Ex-6 Analysis:
We need to prove that $\forall \epsilon > 0 \exists \delta > 0 \forall x (0 < |x-2| < \delta \rightarrow |\frac{3x^2 - 12}{x-2} - 12| < \epsilon)$

Given arbitrary $\epsilon > 0$, we want to find out a $\delta > 0$ s.t.
$0 < |x-2| < \delta \rightarrow |\frac{3x^2 - 12}{x-2} - 12| < \epsilon$

Let us solve for, $|\frac{3x^2 - 12}{x-2} - 12| < \epsilon$
=> $|\frac{3x^2 - 12 -12 x + 24}{x-2}| < \epsilon$
=> $|\frac{3(x-2)^2}{x-2}| < \epsilon$

Since $|x-2| > 0$, so $(x - 2) \neq 0$, so

=> $|3(x-2)| < \epsilon$
=> $|x - 2| < \frac{\epsilon}{3}$

So, $\delta = \frac{\epsilon}{3}$ satisfies the condition.

Formal Proof:
Suppose $\epsilon$ is an arbitrary positive real number and $\delta = \frac{\epsilon}{3}$. Suppose $0 < |x-2| < \delta$.

So, $|\frac{3x^2 - 12}{x-2} - 12|$
= $|\frac{3(x-2)^2}{x-2}|$
= $|3(x-2)|$ (Since $|x-2| > 0$, so $(x-2) \neq 0$)
< $3 \delta$ = $3 \frac{\epsilon}{3}$ = $\epsilon$

clearly, $\forall \epsilon > 0 \exists \delta > 0 \forall x (0 < |x-2| < \delta \rightarrow |\frac{3x^2 - 12}{x-2} - 12| < \epsilon)$.


Ex-7
Suppose $\lim_{x \to c}f(x) = L$. It follows that for every $\epsilon > 0$ there exists $\delta > 0$ s.t. if $0 < |x-c| < \delta$ then $|f(x) - L| < \epsilon$. We can chose $\epsilon = L$ because $L > 0$. Thus If $0 < |x-c| < \delta$ then $|f(x) - L| < L$. For the two cases where

Case#1: |f(x)-L| = f(x) - L
Then, f(x)-L > 0, so f(x) > L, and so f(x) > 0

Case#2: |f(x)-L| = L - f(x)
So, $L - f(x) < L$
Then, f(x) > 0

Thus, There exists $\delta > 0$ s.t. If $0 < |x-c| < \delta$ then f(x) > 0


Ex-8 Suppose $\lim_{x \to c}f(x) = L$.
Let $\epsilon$ be an arbitrary positive number. It follows that $\frac{\epsilon}{7}$ is also a positive number. So there exists $\delta > 0$ s.t. If $0 < |x-c| < \delta$ then $|f(x)-L| < \frac{\epsilon}{7}$. So clearly, for the same $\delta$, If $0 < |x-c| < \delta$ then $|7f(x) - 7L| < \epsilon$. Hence $\lim_{x \to c}7f(x) = 7L$


Ex-9
The proof and theorem, both are correct.

Strategies Used:

Since goal is of the form of "there exist irrantional numbers a and b s.t. ...", so we start with thinking about finding such particular values for a and b. Since, its already known that $\sqrt{2}$, so author applies the nice trick to come up with a implicit given that either $\sqrt{2}^\sqrt{2}$ is rational or irrational and then applies the cases.

Theory of the DOM by Douglas Crockford [My notes]

I just watched the Theory of the DOM video lecture series by Douglas Crockford of Yahoo. Here are the links to all 3 of them

part-1
part-2
part-3

Mr Crockford very nicely tells the history to explain us why/how we got to today's state of browsers, dom and javascript. That aside, I want to note down some of the (theory)things that I want to really really remember from it.


How a typical browser works




You type the URL -> Fetch engine brings the data(or html content from the server) and puts it in cache -> Parse engine parses the html contenct and builds a tree -> Flow engine calculates the position and size of various elements and either augments the same tree or creates a new structure -> Paint engine displays it on the screen



typically, when events(such as Fetch engine downloaded a referenced image) happen,(optionally) a script(js) is executed and then Flow-Paint cycle is repeated

The DOM example



This is IE DOM and not W3C dom. W3C mandates that even the whitespaces between different html elements should be captured in the DOM. Also, notice, though there is no <head> tag in the html, still a head node is introduced in the dom by the browser.

Pointers - what all pointers are maintained for a node by the browser



so, following properties on a node object are available.

node.firstChild
node.lastChild
node.nextSibling
node.previousSibling
node.parent

Retrieving Nodes
Primary ways to get handle to nodes in DOM are

document.getElementById(id)
document.getElementsByName(name)
document.getElementsByTag(tagname)

document.element gives handle to <html> node
document.body gives handle to <body> node

Then, on any node, node.childNodes gives an array of all the children

Once you get a node, you can set/get various properties in it(such as style, class etc).

Creating Node
You can create new nodes by using following

document.createElement(tagname)
document.createTextNode(text)
node.cloneNode() : clones a node
node.cloneNode(true) : clones a node and its descendants as well

These newly created notes are not attached to the DOM by default, but you'll explicitly have to attach them using one of following ways
node.appendChild(new)
node.insertBefore(new, sibling)
node.insertAfter(new, sibling)
node.replaceChild(new, old)
old.parentNode.replaceChild(new, old)

When you remove a node, its important that you remove all the event handlers associated with it. It is essential because IE6 has a memory leak in garbage collection in that it can not collect cyclically referenced objects even though they are garbage. It is fixed in IE7 though.

There is one more non-standard way. However, almost all good browsers support it. A property called "innerHtml" gives you a handle to the browser html parser, to it you can pass html text and the parser can parse it and attach to the dom.

Events
The browser has an event-driven single threaded, asynchronous programming model. Events are targeted to particular nodes and cause invocation of event-handler functions.
There are mouse events(such as click, double click, mousedown, mousemove, mouseout, mouseover, mouseup) and input events(such as blur, focus, change, keydown, keypress, keyup, reset and submit).

There are 3 ways to associate event-handlers with nodes.

classic: node["on" + type] = function; [works on almost all browsers]
microsoft: node.attachEvent("on" + type, function); [IE only]
w3c: node.addEventListener(type, function, true for trickling/false for bubbling)

Event Handler:
The handler takes an optional event object. But, IE choses not to pass it and use global event object instead. So following boiler-plate code is needed..
 function(e) {
e = e || event; //in case of IE, e is undefined and global event is used
var target = e.target || e.srcElement; //some browsers have target while some have srcElement prop
...
}

Trickling and Bubbling
There are two different event dispatch model used by different browsers.
In Trickling model, even is first passed to document root, then to its child and then to its child untill the node where event occured is reached. Any node in the chain may stop the event propagation. Its best to avoid it.
In Bubbling mode, its exactly opposite of trickling, event is first passed to the node where it occured and then to its parent... all the way upto document root.

Let say, you want to cancel bubbling. That is you want to stop propagation of event once the original node handled it. Following is the way
 //two ways
e.cancelBubble = true; //works almost on all browsers
//w3c way
if (e.stopPropagation) {
e.stopPropagation();

//note that you need to write both or else use a js platform lib
}

An event handler can also prevent the browser default action associated with the event(such as submitting a form) with following code..
 //three ways, you need to do all of them
e.returnValue = false; //works on almost all browsers
//w3c way
if(e.preventDefault) {
e.preventDefault();
}
return false;


Additional JS functions provided by browsers
alert(text), confirm(text), prompt(text,default) - they are blocking calls and must be avoided in case of AJAX application
setTimeout(func, msec) and setInterval(func, msec)

every window/frame/iframs has its own global window(aka self, top, parent) reference

Refs for Inter-window communication
frames[] : child frames and iframes
name : text name of window
opener : reference to open
parent : reference to parent
self/window : reference to this window
top : reference to outermost
open() : open a new window

In general, For security reasons, A script can refer another window if
document.domain === otherwindow.document.domain , also called the same origin policy

Browser Detection
In general its good to avoid navigator.userAgent as not all browsers are honest, instead one is encouraged to feature based detection.

In the end, crockford highly recommends that one should use one of the js platform library such as YUI(or jquery) and they take care of cross browser issues.

Things to Avoid
document.all
collections get such as document.forms, document.anchors etc
document.write
use of language attribute in script tag
trickling model of event dispatching

Friday, May 21, 2010

how to prove it - ch3, sec3.6(Existence and Uniqueness Proofs) ex

This section is about proving statements of the form of $\exists ! x P(x)$, which means there exists *only* one x s.t. P(x) is true. It starts out with describing that all of the following statements are equivalent.

$\exists ! x P(x)$
$\exists x (P(x) \land \forall y (P(y) \rightarrow y = x))$
$\exists x (P(x) \land \lnot \exists y (P(y) \land y \neq x))$
$\exists x \forall y (P(y) \leftrightarrow y = x)$
$\exists x P(x) \land \forall y \forall z (P(y) \land P(z) \rightarrow y = z)$

To Prove a goal of the form $\exists ! x P(x)$

Strategy#1:
Use $\exists x P(x) \land \forall y \forall z (P(y) \land P(z) \rightarrow y = z)$. That is prove two goals, $\exists x P(x)$ and $\forall y \forall z (P(y) \land P(z) \rightarrow y = z)$.
$\exists x P(x)$ proves that there exists such an x. It is labeled as existence proof.
$\forall y \forall z (P(y) \land P(z) \rightarrow y = z$ proves that such an x is unique. It is labeled as uniqueness proof.

So, form of the final proof looks like following.

Existence: [Proof of $\exists x P(x)$ goes here]
Uniqueness: [Proof of $\forall y \forall z (P(y) \land P(z) \rightarrow y = z$ goes here]

Strategy#2:
Use $\exists x (P(x) \land \forall y (P(y) \rightarrow y = x))$.

In general, however, we can use any of the formulas listed in the starting of this post.


To Use a given of the form $\exists ! x P(x)$
In general, again we can use any one of the statements listed but very usually $\exists x P(x) \land \forall y \forall z (P(y) \land P(z) \rightarrow y = z)$ is used. It means we can assume that $\exists x P(x)$ and $\forall y \forall z (P(y) \land P(z) \rightarrow y = z)$. $\exists x P(x)$ can probably be used by chosing an object named $x_0$ s.t. $P(x_0)$.


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

Ex-1
[Existence]
Let us try y = $\frac{x}{x^2 + 1}$, $x^2 + 1$ has got to be non-zero for any real x
$x^2y$
= $x^2 * \frac{x}{x^2 + 1}$
= $\frac{x^3}{x^2 + 1}$

$x - y$
= $x - \frac{x}{x^2 + 1}$
= $\frac{x^3 + x - x}{x^2 + 1}$
= $\frac{x^3}{x^2 + 1}$

clearly $x^2y = x - y$ for y = $\frac{x}{x^2 + 1}$

[Uniqueness]
To see that above solution is unique, suppose $x^2z = x - z$
Then, $x^2z + z = x$
=> $z(x^2 + 1) = x$
=> $z = \frac{x}{x^2 + 1} = y$


Ex-2 To see that it exists, try x = 4 and y be arbitrary real number.

LHS = xy + x - 4
= 4y + 4 - 4
= 4y = RHS

To prove it is unique, let say there exists another real number z s.t. (zy + z - 4 = 4y)
Then, z(y + 1) = 4y + 4
=> z = $\frac{4y + 4}{y + 1} = \frac{4(y + 1)}{(y + 1)}$
which is clearly not defined if y+1 = 0 else z = 4 = x.

Ex-3
To see that it exists, try y = $\frac{x^2}{x - 1}$ , its defined since $x - 1 \neq 0$

$\frac{y}{x}$
= $\frac{x^2}{x(x - 1)}$
= $\frac{x}{x - 1}$

y - x
= $\frac{x^2}{x - 1} - x$
= $\frac{x^2 - x^2 + x}{x - 1}$
= $\frac{x}{x - 1}$

clearly $\frac{y}{x} = y - x$

To see that its unique. Let say there exists another real number z s.t.$\frac{z}{x} = z - x$
=> $z = xz - x^2$
=> $xz - z = x^2$
=> z = $\frac{x^2}{x - 1}$ = y


Ex-4
To see that it exists, try y = $\frac{1}{x}$

For any real number z,

zy = $\frac{z}{x}$

To see that it is unique, Let say there exists another real number w s.t. for all real number z
$zw = \frac{z}{x}$
=> $z(w - \frac{1}{x}) = 0$

Since z can be any real number, so

$w - \frac{1}{x} = 0$
=> w = $\frac{1}{x}$ = y


Ex-5
(a) Let x be an arbitrary element of $\cup ! F$. Then there exists exactly one set A s.t. $A \in F$ and $x \in A$. So by definition of $\cup F$, x is an element of $\cup F$ also. Since x is arbitrary, we can conclude that $\cup ! F \subseteq \cup F$

(b)
($\rightarrow$)
Suppose $\cup ! F = \cup F$. Let A and B are two different arbitrary set in $F$. We'll prove by contradiction that A and B are disjoint. Let x be an element s.t. $x \in A$ and $x \in B$. By definition of $\cup F$, $x \in \cup F$. Since $\cup F = \cup ! F$, so $x \in \cup ! F$. It means there is only one set in $F$ to which x belongs. So either A = B or such an x can not exist. Since A and B are different, so x can not exist and hence A and B are disjoint. Since A and B are arbitrary, we can conclude that $F$ is pairwise disjoint.

($\leftarrow$)
Suppose $F$ is pairwise disjoint.

we've already proven in (a) that $\cup ! F \subseteq \cup F$

Now we'll prove that, for this case, $\cup F \subseteq \cup ! F$ also and that will establish $\cup ! F = \cup F$. Let x be an arbitrary element of $\cup F$. So there exists atleast one set A s.t. $A \in F$ and $x \in A$. Since $F$ is pairwise disjoint, so there can not exist another set in $F$ such that x belongs to it and hence there is only one set A s.t. $A \in F$ and $x \in A$. Thus $x \in \cup ! F$. Since x is arbitrary, we can conclude that $\cup F \subseteq \cup ! F$.
Hence $\cup ! F = \cup F$


Ex-6
(a) To prove the existence, try A = $\emptyset$ as $\emptyset \subset U$ and hence $\emptyset \in P(U)$. For any set $B \in P(U)$, $\emptyset \cup B = B$.
To prove the uniqueness, let say there exists another set $C \in P(U)$ s.t. $\forall B \in P(U) (C \cup B = B)$. We can put $B = \emptyset$ in this equation to get $C \cup \emptyset = \emptyset$ and hence C = $\emptyset$ = A.

(b) To prove the existence, try $A = U$. For any $B \in P(U)$, $B \subseteq U$ and so $U \cup B = U$.

To prove the uniqueness, let say there is another set $C \in P(U)$ s.t. $\forall B \in P(U) (C \cup B = C)$. We can put $B = U \setminus C$ in this equation to get $C \cup U \setminus C = C$, therefore $U = C$ and hence $C = U = A$


Ex-7
(a) To prove the existence, try A = $U$. For any $B \in P(U)$, $B \subseteq U$ and hence $U \cap B = B$
To prove the uniqueness, assume there is another set $C \in P(U)$ s.t. $\forall B \in P(U) (C \cap B = B)$. We can put B = $U$ in this equation, then $C \cap U = U$. Thus $C = U = A$

(b) To prove the existence, try A = $\emptyset$. For any set $B \in P(U)$, clearly $\emptyset \cap B = \emptyset$
To prove the uniqueness, assume there is another set $C \in P(U)$ s.t. $\forall B \in P(U) (C \cap B = C)$. We can put $B = \emptyset$ in this equation, then $C \cap \emptyset = C$. Hence $C = \emptyset = A$


Ex-8
(a) To prove the existence of such a set B for every set A, choose B = $U \setminus A$. Clearly for any set $C \in P(U)$
$C \cap B$ = $C \cap U \setminus A$ = all the elements that are in C and not in A = $C \setminus A$

To prove the uniquencess, assume there exists another set D for every set A s.t. $\forall C \in P(U) (C \setminus A = C \cap D)$. We can put C = $U$ in this equation, then $U \setminus A = U \cap D$ and therefore $D = U \setminus A = B$

(b)
To prove the existence of such a set B for every set A, choose B = $U \setminus A$. For any set $C \in P(U)$
$C \setminus (U \setminus A)$ = all elements that are in C and they're either not in $U$ or they are in A, since $U$ is the universe of discourse and there is nothing that is not in $U$. So it means, all elements that are in C and also in A = $C \cap A$

To prove the uniqueness, assume there exists another set D for every set A s.t. $\forall C \in P(U) (C \cap A = C \setminus D)$. We can put C = $U$ in this equation, then $U \cap A = U \setminus D$. So $A = U \setminus D$ and therefore $D = U \setminus A = B$


Ex-9
(a) Existence: Try X = $\emptyset$. For any set,
$A \triangle \emptyset$
= $A \setminus \emptyset \cup \emptyset \setminus A$
= $A \cup \emptyset$
= A

Uniqueness: Let say there exists another set B s.t. $\forall A (A \triangle B = A)$. We can put A = $\emptyset$ in this equation, Then
$\emptyset \triangle B = \emptyset$
=> $\emptyset \setminus B \cup B \setminus \emptyset = \emptyset$
=> $\emptyset \cup B = \emptyset$
=> $B = \emptyset = X$

(b) Here we want to prove, For every set A there exists a unique set B s.t. $A \triangle B = \emptyset$
Existence: Try B = A. Clearly $A \triangle A$
= $A \setminus A \cup A \setminus A$
= $\emptyset \cup \emptyset$
= $\emptyset$

Uniqueness: Let say, For every set A there exists another such set C. Then for a particular set A we can chose a particular set C s.t. $A \triangle C = \emptyset$
Then, $A \setminus C \cup C \setminus A = \emptyset$
=> clearly $A \setminus C = \emptyset$ and $C \setminus A = \emptyset$
=> $C = A = B$

(c) Existence: Try C = $A \triangle B$

$A \triangle C$
= $A \triangle (A \triangle B)$
= $(A \triangle A) \triangle B$
= $\emptyset \triangle B$
= B

Uniquenses: Let say there exists another such set D, Then
$A \triangle D = B$

For both sides, let us take their symmetric difference with A. Then

$A \triangle (A \triangle D) = A \triangle B$
=> $(A \triangle A) \triangle D = A \triangle B$
=> $\emptyset \triangle D = A \triangle B$
=> D = $A \triangle B$ = C

(d) Existence: Try B = A.
For any $C \subseteq A$,
$B \triangle C$
= $A \triangle C$
= $A \setminus C \cup C \setminus A$

Since $C \subseteq A$, therefore $C \setminus A = \emptyset$. So

$B \triangle C$
= $A \setminus C \cup C \setminus A$
= $A \setminus C \cup \emptyset$
= $A \setminus C$

Uniqueness: Let say there exists another such set D. Then
$\forall C (C \subseteq A \rightarrow D \triangle C = A \setminus C)$

we can chose C to be $\emptyset$, Then

$D \triangle \emptyset = A \setminus \emptyset$
=> $D = A = B$


Ex-10
Proof provided by Stavros Mekesis, original link: https://www.dropbox.com/s/fg8hes2nnwrm7ac/velleman.pdf

First we prove that $A \neq \emptyset$ and then we prove that A can not have more than 1 element and that establishes that A has only 1 element.

Proof for $A \neq \emptyset$:
We use proof by contradiction. Suppose $A = \emptyset$.
For $F = \emptyset$ in particular, $\cup F = \emptyset = A$ but clearly $A \notin \emptyset$. So $A \neq \emptyset$

Proof for A not having more than 1 element:
Again we use proof by contradiction. Suppose A has more than 1 elements. Consider an element $x \in A$ and $A \backslash {x} \neq \emptyset$ as A has more than 1 elements by assumption.
Now consider the particular family of sets $F$ = {{x},A\{x}}$
clearly, $\cup F = A$, but $A \notin F$. So A can not have more than 1 elements.


Ex-11
Existence: Try A = $\cup F$, such an A exists because its given that for any family of set $G \subseteq F$, $\cup G \in F$ so clearly $\cup F$ should also be in $F$.
For any set $B \in F$, clearly $B \in \cup F$

Uniqueness: Let say there exists another set $C \in F$ s.t. $\forall B \in F (B \subseteq C)$. We can chose B = $\cup F$, then $\cup F \subseteq C$. So C = $\cup F$ = A


Ex-12
(a) $\exists x (P(x) \land \exists y (P(y) \land (y \neq x) \land \forall z (P(z) \rightarrow (z = x \lor z = y))))$

(b) Strategy would be to first find two values x and y s.t. $x \neq y$ and P(x) and P(y). Next, one needs to prove that $\forall z (P(z) \rightarrow (z = x \lor z = y))$

(c) First we need to find two such values, clearly for x = 0 and for x = 1, $x^3 = x^2$. Now let us say there is another value z s.t. $z^3 = z^2$.
Then $z^3 = z^2$
=> $z^3 - z^2 = 0$
=> $z^2(z - 1) = 0$
=> either z = 0 or (z - 1) = 0
=> either z = 0 or z = 1

Sunday, May 16, 2010

how to prove it - ch3, sec3.5(Proofs Involving Disjunctions) ex

To use a given of the form $P \lor Q$
Strategy#1:
In this case the proof can be broken into cases. So, form of the final proof looks like following
Case 1. P is true
[Proof of goal goes here]
Case 2. Q is true
[Proof of goal goes here]
Since we know $P \lor Q$, these cases cover all the possibilities. Therefore the goal must be true.

However, this is a general technique, you may find it useful to break proof into cases even if the cases are not directly suggested by a given of the form $P \lor Q$. Any proof can be broken into cases at any time, as long as the cases exhaust all of the possibilities. For example, if we're proving something about integers. We can assume the cases like "x is even, x is odd" or "x < 0, x = 0, x > 0".

Strategy#2:
If you are also given $\lnot P$ or if you can prove P to be false, then use this given to conclude that Q is true... viceversa is also true.

To prove a goal of the form $P \lor Q$

Strategy#1: In the place where we write "proof of the goal", we need to prove only one of P or Q.

Strategy#2: Since $P \lor Q$ = $\lnot P \rightarrow Q$ = $\lnot Q \rightarrow P$, we can apply the strategies of proofs involving conditionals. This suggests a rule of inference called disjunctive syllogism .

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

Ex-1
Let x be an arbitrary element of $A \cap (B \cup C)$. Then $x \in A$ and $x \in (B \cup C)$. Let us consider the two cases.
Case1: $x \in B$
Since $x \in A$ and $x \in B$, so $x \in (A \cap B)$. Thus clearly $x \in (A \cap B) \cup C$

Case2: $x \in C$, clearly $x \in (A \cap B) \cup C$

Since x is arbitrary, we can conclude $ A \cap (B \cup C) \subseteq (A \cap B) \cup C$


Ex-2
Let x be an arbitrary element of $(A \cup B) \setminus C$. It follows that $x \in (A \cup B)$ and $x \notin C$. Let us consider the two exhaustive cases

Case1: $x \in A$
clearly $x \in A \cup (B \setminus C)$

Case2: $x \in B$
Since $x \notin C$ and $x \in B$, so clearly $x \in (B \setminus C)$. Thus $x \in A \cup (B \setminus C)$

Since x is arbitrary, we can conclude $(A \cup B) \setminus C \subseteq A \cup (B \setminus C)$


Ex-3
Let x be arbitrary. Then
$x \in A \setminus (A \setminus B)$ iff
$x \in A \land \lnot (x \in (A \setminus B))$ iff
$x \in A \land \lnot (x \in A \land x \notin B)$ iff
$x \in A \land (x \notin A \lor x \in B)$ iff
$(x \in A \land x \notin A) \lor (x \in A \land x \in B)$ iff
$x \in A \land x \in B$ iff
$x \in (A \cap B)$

Since x is arbitrary, we can conclude that $A \setminus (A \setminus B)$ = $A \cap B$


Ex-4
Let x be an arbitrary element of A. Let us consider 2 exhaustive cases

Case1: $x \in C$
Then, $x \in A \cap C$. Since $A \cap C \subseteq B \cap C$, therefore $x \in B \cap C$ and hence $x \in B$.

Case2: $x \notin C$
Then, $x \in A \cup C$. Since $A \cup C \subseteq B \cup C$, therefore $x \in B \cup C$. Since $x \notin C$ ,therefore $x \in B$.

Since x is arbitrary, we can conclude $A \subseteq B$


Ex-5
Suppose $A \triangle B \subseteq A$. Let x be an arbitrary element of B. We will prove by contradiction that $x \in A$. Assume $x \notin A$. Since $x \in B$ and $x \notin A$, therefore $x \in B \setminus A$, and then $x \in (A \setminus B) \cup (B \setminus A)$. Thus $x \in A \triangle B$. Since $A \triangle B \subseteq A$, so $x \in A$ should be true and that contradicts our assumption of $x \notin A$. So the assumption is wrong and $x \in A$. Since x is arbitrary, we can conclude $B \subseteq A$


Ex-6
($\rightarrow$) Suppose $A \cup C \subseteq B \cup C$. Let x be an arbitrary element $A \setminus C$. It follows that $x \in A$ and $x \notin C$ and hence $x \in A \cup C$. Since $A \cup C \subseteq B \cup C$, so $x \in B \cup C$. Since $x \notin C$, therefore $x \in B$. Since x is arbitrary, we can conclude $A \setminus C \subseteq B \setminus C$

($\leftarrow$) Suppose $A \setminus C \subseteq B \setminus C$. Let x be arbitrary element of $A \cup C$. Let us consider the two exhaustive cases

Case1: $x \in C$
clearly $x \in (B \cup C)$ also

Case2: $x \notin C$
Since $x \in A \cup C$ and $x \notin C$, it follows that $x \in A$ and hence $x \in A \setminus C$. Since $A \setminus C \subseteq B \setminus C$, therefore $x \in B \setminus C$ and hence $x \in B$ and therefore $x \in (B \cup C)$

Since x is arbitrary, we can conclude $A \cup C \subseteq B \cup C$


Ex-7
Suppose x be an arbitrary element of $P(A) \cup P(B)$. Let us consider the two exhaustive cases

Case1: $x \in P(A)$
then, $x \subseteq A$. And then $x \subseteq (A \cup B)$, so $x \in P(A \cup B)$

Case2: $x \in P(B)$
then, $x \subseteq B$. And then $x \subseteq (A \cup B)$, so $x \in P(A \cup B)$

Since x is arbitrary, we can conclude $P(A) \cup P(B) \subseteq P(A \cup B)$


Ex-8
given:
goal: If $P(A) \cup P(B) = P(A \cup B)$ then $A \subseteq B$ or $B \subseteq A$

Assume the hypotheses

given: $P(A) \cup P(B) = P(A \cup B)$
goal: $A \subseteq B$ or $B \subseteq A$ $\equiv$ If A is not subset of B then $B \subseteq A$

Assume the hypotheses again

given: $P(A) \cup P(B) = P(A \cup B)$ , $\lnot (A \subseteq B)$
goal: $B \subseteq A$

Formal Proof:
Suppose $P(A) \cup P(B) = P(A \cup B)$ and $\lnot (A \subseteq B)$. Since $\lnot (A \subseteq B)$, so we can chose a y s.t. $y \in A$ and $y \notin B$.

Now, We will prove by contradiction that $B \subseteq A$. Let us assume that $\lnot (B \subseteq A)$. Then we can chose a x s.t. $x \in B$ and $x \notin A$. Let us call C to be the set {x,y}. Clearly C is neither a subset of A nor that of B but $C \subseteq A \cup B$. However $P(A) \cup P(B) = P(A \cup B)$ means, $P(A \cup B) \rightarrow P(A) \cup P(B)$ and that means for any arbitrary set D, if $D \subseteq A \cup B$ then either $D \subseteq A$ or $D \subseteq B$. Since $C \subseteq A \cup B$, so C should either be a subset of A or that of B but both of these are already false and this is a contradiction. Therefore $\lnot (B \subseteq A)$ is false and it means $B \subseteq A$.


Ex-9
$y + \frac{1}{x}$ = $1 + \frac{y}{x}$ iff
$\frac{xy + 1}{x}$ = $\frac{x + y}{x}$ iff
$xy + 1$ = $x + y$ iff
$xy - x - y + 1 = 0$ iff
$x(y-1) -(y - 1) = 0$ iff
$(x - 1)(y - 1) = 0$ iff
$(x - 1) = 0$ or $(y - 1) = 0$ iff
$x = 1$ or $y = 1$


Ex-10
Suppose |x - 3| > 3. Let us consider the two exhaustive cases

Case1: (x - 3) $\geq$ 0
Since |x - 3| > 3, so (x - 3) > 3, then x > 6. On multiplying both sides with x we get $x^2$ > $6x$

Case2: (x - 3) < 0
Since |x - 3| > 3, so -(x - 3) > 3
=> (x - 3) < -3
=> x < 0

therefore $x^2$ > 0 but $6x$ < 0
so clearly $x^2$ > $6x$


Ex-11
($\rightarrow$)
Suppose |2x - 6| > x. Let us consider the two cases

Case1: (2x - 6) $\geq$ 0
Then (2x - 6) > x
=> x - 6 > 0
=> x > 6
=> x - 4 > 2 , so (x - 4) is positive and hence |x - 4| = (x - 4)
=> |x - 4| > 2

Case2: (2x - 6) < 0
Then -(2x - 6) > x
=> 2x - 6 < -x
=> 3x < 6
=> x < 2
=> x - 4 < -2 , so (x - 4) is negative and hence |x - 4| = -(x - 4)
=> -(x - 4) > 2
=> |x - 4| > 2

($\leftarrow$)
Suppose |x - 4| > 2. Let us consider the two cases

Case1: (x - 4) $\geq$ 0
Then (x - 4) > 2
=> x > 6
=> x + x > 6 + x
=> 2x > 6 + x
=> 2x - 6 > x

Also since (x - 4) $\geq$ 0
=> x $\geq$ 4
=> x > 0

Since 2x - 6 > x and x > 0, so 2x - 6 > 0 and so |2x - 6| = (2x - 6)
hence |2x - 6| > x

Case2: (x - 4) < 0
Then -(x - 4) > 2
=> (x - 4) < -2
=> x < 2 ...(i)

=> 2x < 4
=> 2x - 6 < -2 and so 2x - 6 is negative and hence |2x - 6| = -(2x - 6)

Again x < 2
=> 3x < 6
=> 3x - 6 < 0
=> 2x - 6 < -x
=> -(2x - 6) > x
=> |2x - 6| > x


Ex-12

(a)
($\rightarrow$)
Suppose |a| $\leq$ b. Let us consider the two cases

Case1: a $\geq$ 0
then a $\leq$ b

Case2: a < 0
then -a $\leq$ b
=> a $\geq$ -b

So either a $\leq$ b or a $\geq$ -b and hence -b $\leq$ a $\leq$ b

($\leftarrow$)
Suppose -b $\leq$ a $\leq$ b. Let us consider the two cases

Case1: a $\geq$ 0
So , |a| = a
=> -b $\leq$ |a| $\leq$ b
=> |a| $\leq$ b

Case2: a < 0
So, |a| = -a
Since -b $\leq$ a $\leq$ b
=> b $\geq$ -a $\geq$ -b
=> b $\geq$ |a| $\geq$ -b
=> b $\geq$ |a|
=> |a| $\leq$ b

(b)
Above we proved |a| $\leq$ b iff -b $\leq$ a $\leq$ b

For any real number x
|x| = |x|

we could also say
|x| $\leq$ |x|

Let say a = x and b = |x|

Since -b $\leq$ a $\leq$ b
so -|x| $\leq$ x $\leq$ |x|

(c)
Let us consider following set of exhaustive cases

Case1: x $\geq$ 0 and y $\geq$ 0
Then |x| = x, |y| = y. Since (x + y) is also positive
So, |x + y| = x + y
=> |x + y| = |x| + |y|

Case2: x < 0 and y < 0
Then |x| = -x, |y| = -y. Since (x + y) is also negative
So, |x + y| = -(x + y)
=> |x + y| = -x + (-y)
=> |x + y| = |x| + |y|

Case3: x $\geq$ 0 , y < 0 , (x + y) $\geq$ 0
Then |x| = x, |y| = -y and |x + y| = (x + y)
=> |x + y| = |x| - |y|

Since |x| - |y| < |x| + |y|
So |x + y| < |x| + |y|

Case4: x $\geq$ 0 , y < 0 , (x + y) < 0
Then |x| = x, |y| = -y and |x + y| = -(x + y)
=> |x + y| = -|x| + |y|

Since -|x| + |y| < |x| + |y|
So |x + y| < |x| + |y|

Case5: x < 0, y $\geq$ 0 , (x + y) $\geq$ 0
Then |x| = -x, |y| = y and |x + y| = (x + y)
=> |x + y| = -|x| + |y|
=> |x + y| < |x| + |y|

Case6: x < 0, y $\geq$ 0 , (x + y) < 0
Then |x| = -x, |y| = y and |x + y| = -(x + y) = -x - y
=> |x + y| = |x| - |y|
=> |x + y| < |x| + |y|


Since above set of cases is exhaustive, hence |x + y| $\leq$ |x| + |y|


Ex-13
Let us consider two exhaustive cases.

Case1: x is even
Then there exists an integer k s.t. x = 2k
=> $x^2$ = $4k^2$
=> $x^2 + x$ = $4k^2 + 2k$
=> $x^2 + x$ = $2k(2k + 1)$

Since k(k+1) is an integer, thus $x^2 + x$ is even

Case2: x is odd
Then there exists an integer k s.t. x = 2k + 1
=> $x^2$ = $(2k + 1)^2$
=> $x^2$ = $4k^2 + 1 + 4k$
=> $x^2 + x$ = $(4k^2 + 1 + 4k) + (2k + 1)$
=> $x^2 + x$ = $4k^2 + 6k + 2$
=> $x^2 + x$ = $2(2k^2 + 3k + 1)$

Since $(2k^2 + 3k + 1)$ is an integer, thus $x^2 + x$ is even


Ex-14
Let us consider two exhaustive cases

Case1: x is even
Then there exists an integer k s.t. x = 2k
=> $x^4$ = $16k^4$
=> $x^4$ = $8(2k^4)$

Clearly $x^4$ is divisible by 8. Thus remainder, when $x^4$ is divided by 8, is 0

Case2: x is odd
Then there exists an integer k s.t. x = 2k + 1
=> $x^4$ = $(2k + 1)^4$
=> $x^4$ = $(4k^2 + 1 + 4k)^2$
=> $x^4$ = $16k^4 + 1 + 16k^2 + 2(4k^2 + 4k + 16k^3)$
=> $x^4$ = $16k^4 + 1 + 24k^2 + 8k + 32k^3$
=> $x^4$ = $8(2k^4 + 4k^3 + 3k^2 + k) + 1$

Clearly, remainder, when $x^4$ is divided by 8, is 1

Thus, when $x^4$ is divided by 8, remainder is either 0 or 1


Ex-15
(a)
Let x be an arbitrary element of $\cup (F \cup G)$

$x \in \cup (F \cup G)$ iff
there exists a set A s.t.
$x \in A \land A \in (F \cup G)$ iff
$x \in A \land (A \in F \lor A \in G)$ iff
$(x \in A \land A \in F) \lor (x \in A \land A \in G)$ iff
$x \in \cup F \lor x \in \cup G$ iff
$x \in (\cup F) \cup (\cup G)$

Since x is arbitrary, we can conclude that $\cup (F \cup G)$ = $(\cup F) \cup (\cup G)$

(b)
My conjecture is $\cap (F \cup G)$ = $(\cap F) \cap (\cap G)$

Proof:
Let x be an arbitrary element of $\cap (F \cup G)$

So $x \in \cap (F \cup G)$
=> $\forall A (A \in F \cup G \rightarrow x \in A)$
=> $\forall A (A \in F \lor A \in G \rightarrow x \in A)$
=> $\forall A (\lnot (A \in F \lor A \in G) \lor x \in A)$
=> $\forall A ((A \notin F \land A \notin G) \lor x \in A)$
=> $\forall A ((A \notin F \lor x \in A) \land (A \notin G \lor x \in A))$
=> $[\forall A (A \notin F \lor x \in A)] \land [\forall A (A \notin G \lor x \in A)]$
=> $[\forall A (A \in F \rightarrow x \in A)] \land [\forall A (A \in G \rightarrow x \in A)]$
=> $(x \in \cap F) \land (x \in \cap G)$
=> $x \in (\cap F) \cap (\cap G)$

Since x is arbitrary, so $\cap (F \cup G)$ = $(\cap F) \cap (\cap G)$


Ex-16
(a)
($\rightarrow$)
Let x be an arbitrary element of $B \cup (\cup F)$. Let us consider the two cases

Case1: $x \in B$
It follows that $x \in \cup \{B\}$. And also $x \in \cup (F \cup \{B\})$

Case2: $x \in \cup F$
Then, there exists a set $A \in F$ s.t. $x \in A$, since $A \in F \cup \{B\}$ also. So $x \in \cup (F \cup \{B\})$

Since x is arbitrary, clearly $B \cup (\cup F) \subseteq \cup (F \cup \{B\})$

($\leftarrow$)
Let x be an arbitrary element of $\cup (F \cup \{B\})$. Then there exists a set $A \in (F \cup \{B\})$ s.t. $x \in A$. Let us consider the two cases

Case1: $A \in F$
Then $x \in \cup F$ and therefore $x \in B \cup (\cup F)$

Case2: $A \in \{B\}$
It means A = B, so $x \in B$ and hence $x \in B \cup (\cup F)$

Since x is arbitrary, we conclude that $\cup (F \cup \{B\}) \subseteq B \cup (\cup F)$

Thus, $B \cup (\cup F)$ = $\cup (F \cup \{B\})$

(b)
($\rightarrow$)
Let x be an arbitrary element of $B \cup (\cap F)$. Let us consider the two cases

Case1: $x \in B$
Then for any set A, $x \in B \cup A$. Thus for all $A \in F$, $x \in B \cup A$ and therefore $x \in \cap_{A \in F}(B \cup A)$

Case2: $x \in \cap F$
Then for all $A \in F$, $x \in A$. So $x \in B \cup A$ also and therefore $x \in \cap_{A \in F}(B \cup A)$

Since x is arbitrary, we conclude that $B \cup (\cap F) \subseteq \cap_{A \in F}(B \cup A)$

($\leftarrow$)
Let x be an arbitrary element of $\cap_{A \in F}(B \cup A)$. Then for any $A \in F$, $x \in B \cup A$. Let us consider the two cases

Case1: $x \in B$
Then $x \in B \cup (\cap F)$ also.

Case2: $x \in A$
Since A any set in $F$. So $x \in \cap F$ and therefore $x \in B \cup (\cap F)$

Since x is arbitrary, we conclude that $\cap_{A \in F}(B \cup A) \subseteq B \cup (\cap F)$

Thus, $B \cup (\cap F)$ = $\cap_{A \in F}(B \cup A)$

(c)
My conjecture: $B \cap (\cap F)$ = $\cap (F \cap \{B\})$

Proof:
Let x be an arbitrary element.

$x \in B \cap (\cap F)$ iff
$x \in B \land x \in \cap F$ iff
$x \in B \land \forall A \in F (x \in A)$ iff
$[\forall A \in \{B\} (x \in A)] \land [\forall A \in F (x \in A)]$ iff
$\forall A \in (F \cap \{B\}) (x \in A)$ iff
$x \in \cap (F \cap \{B\})$

Since x is arbitrary, we can conclude $B \cap (\cap F)$ = $\cap (F \cap \{B\})$


Ex-17
Let x be an arbitrary element of $\cap H$. So for all sets $C \in H$, $x \in C$. Let A be an arbitrary element of $F$ and B be an arbitrary element of $G$. Since $A \cup B \in H$, so $x \in A \cup B$. Let us consider the two cases

Case1: $x \in A$
Since A is arbitrary, so $x \in \cap F$, Thus $x \in (\cap F) \cup (\cap G)$

Case2: $x \in B$
Since B is arbitrary, so $x \in \cap G$, Thus $x \in (\cap F) \cup (\cap G)$

Since x is arbitrary, we can conclude $\cap H \subseteq (\cap F) \cup (\cap G)$


Ex-18
Let x be arbitrary element of $A \triangle B$

$x \in A \triangle B$ iff
$x \in (A \cup B) \setminus (A \cap B)$ iff
$x \in (A \cup B) \land \lnot (x \in A \cap B)$ iff
$(x \in A \lor x \in B) \land \lnot (x \in A \land x \in B)$ iff
$(x \notin B \rightarrow x \in A) \land (x \notin A \lor x \notin B)$ iff
$(x \notin B \rightarrow x \in A) \land (x \in A \rightarrow x \notin B)$ iff
$x \in A \leftrightarrow x \notin B$

Thus $\forall x (x \in A \triangle B \leftrightarrow (x \in A \leftrightarrow x \notin B))$


Ex-19
($\rightarrow$)
Suppose $A \triangle B$ and C are disjoint.

Let x be an arbitrary element of $A \cap C$. It follows that $x \in A$ and $x \in C$. Since $A \triangle B$ and C are disjoint and $x \in C$, so $x \notin A \triangle B$. By definition of $A \triangle B$, either $x \notin A \cup B$ or $x \in A \cap B$. Since $x \in A$ so $x \notin A \cup B$ can not be true and hence $x \in A \cap B$. Thus $x \in B$. Since $x \in C$ and $x \in B$, so $x \in B \cap C$. Since x is arbitrary, we can conclude $A \cap C \subseteq B \cap C$

By exactly similar argument as above we can prove that $B \cap C \subseteq A \cap C$. Thus $A \cap C$ = $B \cap C$

($\leftarrow$)
Suppose $A \cap C$ = $B \cap C$. Let x be an arbitrary element of $A \triangle B$. By definition of $A \triangle B$, $x \in A \setminus B$ or $x \in B \setminus A$. We will prove by contradiction that $x \notin C$. Let us assume that $x \in C$. Now consider the two cases

Case1: $x \in A \setminus B$
It follows that $x \in A$ and $x \notin B$. Since $x \in C$ also, so $x \in A \cap C$. Since $A \cap C$ = $B \cap C$, so $x \in B \cap C$ and hence $x \in B$ but that contradicts our assumption for this case. Thus $x \notin C$

Case2: $x \in B \setminus A$
It follows that $x \in B$ and $x \notin A$. Since $x \in C$ also, so $x \in B \cap C$. Since $B \cap C$ = $A \cap C$, so $x \in A \cap C$ and hence $x \in A$ but that contradicts our assumption for this case. Thus $x \notin C$.

Since above cases are the exhaustive set, so $x \notin C$. Since x is arbitrary, we can conclude that $A \triangle B$ and C are disjoint.


Ex-20
($\rightarrow$)
Suppose $A \triangle B \subseteq C$. Let x be an arbitrary element of $A \cup C$. It follows that $x \in A$ or $x \in C$. Let us consider both the cases

Case1: $x \in A$
We'll prove by contradiction that $x \in B \cup C$. Assume $x \notin B \cup C$, therefore $x \notin B$ and $x \notin C$. Since $x \in A$ and $x \notin B$,
so $x \in A \setminus B$
=> $x \in A \triangle B$

Since $A \triangle B \subseteq C$
therefore $x \in C$, but this contradicts our assumption and hence $x \in B \cup C$.

Case2: $x \in C$
so definitely $x \in B \cup C$

Since x is arbitrary, we conclude that $A \cup C \subseteq B \cup C$

By using an exactly similar argument we can prove that $B \cup C \subseteq A \cup C$ also. Thus $A \cup C$ = $B \cup C$

($\leftarrow$)
Suppose $A \cup C$ = $B \cup C$. Let x be an arbitrary element of $A \triangle B$. Then, either $x \in A \setminus B$ or $x \in B \setminus A$. let us consider both the cases

Case1: $x \in A \setminus B$
Then $x \in A$ and $x \notin B$. Since $x \in A$, so $x \in A \cup C$ also. And since $A \cup C$ = $B \cup C$, so $x \in B \cup C$. Since $x \notin B$, so $x \in C$

Case2: $x \in B \setminus A$
Then $x \in B$ and $x \notin A$. Since $x \in B$, so $x \in B \cup C$ also. And since $B \cup C$ = $A \cup C$, so $x \in A \cup C$. Since $x \notin A$, so $x \in C$

From above cases, we can conclude that $x \in C$. Since x is arbitrary, so $A \triangle B \subseteq C$


Ex-21
($\rightarrow$)
Suppose $C \subseteq A \triangle B$.

Let x be an arbitrary element of C, then $x \in A \triangle B$. Thus $x \in A \cup B$ and $x \notin A \cap B$. So $x \in A \cup B$. Since x is arbitrary, so $C \subseteq A \cup B$

Let x be an arbitrary element of $x \in A \cap B \cap C$. Then $x \in A$ and $x \in B$ and $x \in C$. Since $C \subseteq A \triangle B$, so $x \in A \triangle B$ and then $x \in A \setminus B$ or $x \in B \setminus A$. Let us consider both the cases

Case1: $x \in A \setminus B$
Then $x \in A$ and $x \notin B$. But we already said that $x \in B$. This is a contradiction and such x can not exist

Case2: $x \in B \setminus A$
Then $x \in B$ and $x \notin A$. But we already said that $x \in A$. This is a contradiction and such x can not exist

Hence a x s.t. $x \in A \cap B \cap C$ can not exist and hence $A \cap B \cap C = \emptyset$

So if $C \subseteq A \triangle B$ then $C \subseteq A \cup B$ and $A \cap B \cap C = \emptyset$

($\leftarrow$)
Suppose $C \subseteq A \cup B$ and $A \cap B \cap C = \emptyset$. Let x be an arbitrary element of C. So $x \in A \cup B$ and hence $x \in A$ or $x \in B$. Let us consider both the cases

Case1: $x \in A$
Since $x \in C$ and $x \in A$, then $x \notin B$ as $A \cap B \cap C = \emptyset$. Since $x \in A$ and $x \notin B$, so $x \in A \setminus B$ and hence $x \in A \triangle B$. Since x is arbitrary, we can conclude that $C \subseteq A \triangle B$

Case2: $x \in B$
Since $x \in C$ and $x \in B$, then $x \notin A$ as $A \cap B \cap C = \emptyset$. Since $x \in B$ and $x \notin A$, so $x \in B \setminus A$ and hence $x \in A \triangle B$. Since x is arbitrary, we can conclude that $C \subseteq A \triangle B$


Ex-22
(a)
Let x be an arbitrary element of $A \setminus C$. Then $x \in A$ and $x \notin C$. Let us consider two cases

Case1: $x \in B$
Then $x \in B \setminus C$, so $x \in (A \setminus B) \cup (B \setminus C)$

Case2: $x \notin B$
Then $x \in A \setminus B$, so $x \in (A \setminus B) \cup (B \setminus C)$

From two cases above, its clear that $x \in (A \setminus B) \cup (B \setminus C)$. Since x is arbitrary, so $A \setminus C \subseteq (A \setminus B) \cup (B \setminus C)$

(b)
Let x be an arbitrary element of $A \triangle C$. Let us consider the two cases

Case1: $x \in B$
Since $x \in A \triangle C$, so $x \in A \setminus C$ or $x \in C \setminus A$. Let us consider these cases further
Case-a: $x \in A \setminus C$
Then $x \in A$ and $x \notin C$. Since $x \in B$ and $x \notin C$, so $x \in B \setminus C$ and hence $x \in B \triangle C$
Case-b: $x \in C \setminus A$
Then $x \in C$ and $x \notin A$. Since $x \in B$ and $x \notin A$, so $x \in B \setminus A$ and hence $x \in A \triangle B$

So $x \in (A \triangle B)$ or $x \in (B \triangle C)$. Thus $x \in (A \triangle B) \cup (B \triangle C)$

Case2: $x \notin B$
Since $x \in A \triangle C$, so $x \in A \setminus C$ or $x \in C \setminus A$. Let us consider these cases further
Case-a: $x \in A \setminus C$
Then $x \in A$ and $x \notin C$. Since $x \notin B$ and $x \in A$, so $x \in A \setminus B$ and hence $x \in A \triangle B$
Case-b: $x \in C \setminus A$
Then $x \in C$ and $x \notin A$. Since $x \notin B$ and $x \in C$, so $x \in C \setminus B$ and hence $x \in B \triangle C$

So $x \in (A \triangle B)$ or $x \in (B \triangle C)$. Thus $x \in (A \triangle B) \cup (B \triangle C)$

Since x is arbitrary, so $A \triangle C \subseteq (A \triangle B) \cup (B \triangle C)$


Ex-23
(a)
Let x be an arbitrary element of $(A \cup B) \triangle C$. It follows that either $x \in (A \cup B) \setminus C$ or $x \in C \setminus (A \cup B)$. Let us consider both the cases

Case1: $x \in (A \cup B) \setminus C$
Then $x \in (A \cup B)$ and $x \notin C$. So, either $x \in A \setminus C$ or $x \in B \setminus C$. Thus $x \in A \triangle C$ or $x \in B \triangle C$. Hence $x \in (A \triangle C) \cup (B \triangle C)$

Case2: $x \in C \setminus (A \cup B)$
Then $x \in C$ and $x \notin (A \cup B)$. Since $x \notin (A \cup B)$, so $x \notin A$ and $x \notin B$. Hence $x \in C \setminus A$ and $x \in C \setminus B$. And therefore $x \in (A \triangle C)$ and $x \in (B \triangle C)$. So $x \in (A \triangle C)$ or $x \in (B \triangle C)$ also. Thus $x \in (A \triangle C) \cup (B \triangle C)$

Since x is arbitrary, we can conclude that $(A \cup B) \triangle C \subseteq (A \triangle C) \cup (B \triangle C)$

(b)
A = {3}
B = {4}
C = {3,4}


Ex-24
(a)
Let x be an arbitrary element of $(A \triangle C) \cap (B \triangle C)$. So $x \in A \triangle C$ and $x \in B \triangle C$. $x \in A \triangle C$ means either $x \in A \setminus C$ or $x \in C \setminus A$. Similarly $x \in B \triangle C$ means $x \in B \setminus C$ or $x \in C \setminus B$. So following 4 cases are possible.

Case1: $x \in A \setminus C$ and $x \in B \setminus C$
Then $x \in A$ and $x \in B$ and $x \notin C$. Thus $x \in A \cap B$ and $x \notin C$. So $x \in (A \cap B) \setminus C$. Hence $x \in (A \cap B) \triangle C$

Case2: $x \in A \setminus C$ and $x \in C \setminus B$
This case is not possible as $x \in A \setminus C$ suggests that $x \notin C$ while $x \in C \setminus B$ suggests $x \in C$

Case3: $x \in C \setminus A$ and $x \in B \setminus C$
This case is also not possible for the same reason as above

Case4: $x \in C \setminus A$ and $x \in C \setminus B$
Then $x \in C$ and $x \notin A$ and $x \notin B$. Since $x \notin A$ and $x \notin B$, so $x \notin A \cup B$ and then $x \notin A \cap B$ also. Thus $x \in C \setminus (A \cap B)$. Hence $x \in (A \cap B) \triangle C$

From above cases, it is clear that $x \in (A \cap B) \triangle C$. Since x is arbitrary, so we can conclude that $(A \triangle C) \cap (B \triangle C) \subseteq (A \cap B) \triangle C$

(b)
Here is the counterexample
A = {3}
B = {4}
C = {3,4}

$(A \cap B) \triangle C$ = {3,4}
$(A \triangle C) \cap (B \triangle C)$ = $\emptyset$


Ex-25
$(A \setminus B) \triangle C$ is not a subset of $(A \triangle C) \setminus (B \triangle C)$ and here is the counterexample
A = {1}
B = {2}
C = {3}

$(A \setminus B) \triangle C$ = {1,3}
$(A \triangle C) \setminus (B \triangle C)$ = {1}

and $(A \triangle C) \setminus (B \triangle C) \subseteq (A \setminus B) \triangle C$, here is the proof
Let x be an arbitrary element of $(A \triangle C) \setminus (B \triangle C)$. It follows that $x \in A \triangle C$ and $x \notin B \triangle C$.
$x \in A \triangle C$ means $x \in A \setminus C$ or $x \in C \setminus A$
$x \notin B \triangle C$ means $x \notin B \cup C$ or $x \in B \cap C$

So there are 4 cases to consider

Case1: $x \in A \setminus C$ and $x \notin B \cup C$
It means $x \in A$ and $x \notin C$ and $x \notin B$. So $x \in (A \setminus B) \setminus C$, thus $x \in (A \setminus B) \triangle C$

Case2: $x \in A \setminus C$ and $x \in B \cap C$
This case is not possible as $x \in A \setminus C$ suggests that $x \notin C$ while $x \in B \cap C$ suggests $x \in C$

Case3: $x \in C \setminus A$ and $x \notin B \cup C$
This case is also not possible for the same reason as above

Case4: $x \in C \setminus A$ and $x \in B \cap C$
It means $x \in C$ and $x \notin A$ and $x \in B$. Since $x \notin A$, so $x \notin A\setminus B$ should also be true. Since $x \in C$ and $x \notin A \setminus B$, therefore $x \in C \setminus (A \setminus B)$. Thus $x \in (A \setminus B) \triangle C$

From above cases, its clear that $x \in (A \setminus B) \triangle C$. Since x is arbitrary, we can conclude that $(A \triangle C) \setminus (B \triangle C) \subseteq (A \setminus B) \triangle C$

Ex-26
The theorem given is correct. However the proof presented is not correct, as it actually proves that (x > 0) OR (x < 6) wherease what we want to prove is that (x > 0) AND (x < 6). It can be fixed as follows.
In Case1, the assumption is that (x - 3 $\geq$ 0), so (x $\geq$ 3). And its concluded that (x < 6). So, from this case, we can conclude that (x $\geq$ 3) AND (x < 6)
Similarly from Case2, we can conclude that (x > 0) AND (x < 3)

Now, we can conclude that (0 < x < 6) (TODO: justify it)


Ex-27
The theorem as well as the proof given is correct.

Strategies:
Initial theorem is in the form $P \land Q \rightarrow R$

So, First strategy is to suppose that P and Q are true. Then we use existential instantiation on P that is $\lnot (A \subseteq B)$. Later we get $x \notin A$ or $x \in B$, that is $x \in A \rightarrow x \in B$, since $x \in A$ is known already so $x \in B$ is established through that.


Ex-28
The theorem as well as the proof given are correct.

Notice that, even thought there is no explicit given of the form $P \lor Q$, but since x being real can be divided in to 2 exhaustive cases $x = 0$ and $x \neq 0$, therefore the strategy of taking cases is used


Ex-29
Suppose $\forall x P(x) \rightarrow \exists x Q(x)$
=> $\lnot (\forall x P(x)) \lor (\exists x Q(x))$
=> $(\exists x \lnot P(x)) \lor (\exists x Q(x))$
=> $\exists x (\lnot P(x) \lor Q(x))$
=> $\exists x (P(x) \rightarrow Q(x))$

Thus if $\forall x P(x) \rightarrow \exists x Q(x)$ then $\exists x (P(x) \rightarrow Q(x))$


Ex-30
The theorem is incorrect. Here is the counterexample, A = {1,2} ; B = {0,1}; C = {2,3}

The flaw is in both cases. For example Case1 means $x \in A$ and $x \in B$, not $x \in A \rightarrow x \in B$. Same is the problem with the other one. (convincing enough??)


Ex-31
Prove that $\exists x (P(x) \rightarrow \forall x P(x))$.
TODO, no idea how to prove this. Is the given statement even correct?