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 $\varnothing$ = $\varnothing$ X A = $\varnothing$

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. $AX(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. $AX(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)}
= $\varnothing$

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

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 $\varnothing$ = $\varnothing$ X A = $\varnothing$


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

Let p be arbitrary element of $AX(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 AXB$. Thus $(x,y)\in \left(AXB\right)\cup \left(AXC\right)$

Case#2: $y\in C$
Then $(x,y)\in AXC$. Thus $(x,y)\in \left(AXB\right)\cup \left(AXC\right)$

Since p is arbitrary, we can conclude that $AX(B\cup C)\subseteq \left(AXB\right)\cup \left(AXC\right)$

Now, Let p be arbitrary element of $\left(AXB\right)\cup \left(AXC\right)$. Then either $p\in \left(AXB\right)$ or $p\in \left(AXC\right)$. Let us consider both the cases

Case#1: $p\in \left(AXB\right)$
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 AX(B\cup C)$

Case#2: $p\in \left(AXC\right)$
By similar argument as above, $(x,y)\in AX(B\cup C)$

Since p is arbitrary, we can conclude that $\left(AXB\right)\cup \left(AXC\right)\subseteq AX(B\cup C)$

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

-- Prove that $\left(AXB\right)\cap \left(CXD\right)=(A\cap C)X(B\cap D)$ --

Let p be an arbitrary element of $\left(AXB\right)\cap \left(CXD\right)$. Then $p\in \left(AXB\right)$ and $p\in \left(CXD\right)$. 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 $\left(AXB\right)\cap \left(CXD\right)\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 \left(AXB\right)$ and $(x,y)\in \left(CXD\right)$. Thus $p\in \left(AXB\right)\cap \left(CXD\right)$. Since p is arbitrary, so $(A\cap C)X(B\cap D)\subseteq \left(AXB\right)\cap \left(CXD\right)$

Hence $\left(AXB\right)\cap \left(CXD\right)=(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\backslash C$. So $y\in B$ and $y\notin C$. Since $x\in A$ and $y\in B$, so $p\in \left(AXB\right)$. Since $y\notin C$, so $p\notin \left(AXC\right)$. Hence $p\in \left(AXB\right)\backslash \left(AXC\right)$. Since p is arbitrary, so $(AXB\backslash C)\subseteq \left(AXB\right)\backslash \left(AXC\right)$

Now let p be an arbitrary element of $\left(AXB\right)\backslash \left(AXC\right)$. Then $p\in \left(AXB\right)$ and $p\notin \left(AXC\right)$. It follows that there exist x and y s.t. p = (x,y). Since $p\in \left(AXB\right)$, so $x\in A$ and $y\in B$. Since $p\notin \left(AXC\right)$, 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 AX(B\backslash C)$. Since p is arbitrary, so $\left(AXB\right)\backslash \left(AXC\right)\subseteq (AXB\backslash C)$

Thus $(AXB\backslash C)=\left(AXB\right)\backslash \left(AXC\right)$


Ex-9 Let p be an arbitrary element of $\left(AXB\right)\backslash \left(CXD\right)$. Then $p\in \left(AXB\right)$ and $p\notin \left(CXD\right)$. Thus there exist x and y s.t. p = (x,y). Since $p\in \left(AXB\right)$, so $x\in A$ and $y\in B$. Since $p\notin \left(CXD\right)$, 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\backslash C)XB$. Thus $p\in \left[AX\right(B\backslash D\left)\right]\cup \left[\right(A\backslash C\left)XB\right]$

Case#2: $y\notin D$
Since $x\in A$ and $y\in B$ and $y\notin D$, so $p\in AX(B\backslash D)$. Thus $p\in \left[AX\right(B\backslash D\left)\right]\cup \left[\right(A\backslash C\left)XB\right]$

Since p is arbitrary, $\left(AXB\right)\backslash \left(CXD\right)\subseteq \left[AX\right(B\backslash D\left)\right]\cup \left[\right(A\backslash C\left)XB\right]$

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

Case#1: $p\in AX(B\backslash 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 \left(AXB\right)$. Also since $y\notin D$, so $p\notin \left(CXD\right)$. Thus $p\in \left(AXB\right)\backslash \left(CXD\right)$

Case#2: $p\in (A\backslash C)XB$
we can use similar argument as above case to prove that $p\in \left(AXB\right)\backslash \left(CXD\right)$

Now since p is arbitrary, so $\left[AX\right(B\backslash D\left)\right]\cup \left[\right(A\backslash C\left)XB\right]\subseteq \left(AXB\right)\backslash \left(CXD\right)$

Thus $\left(AXB\right)\backslash \left(CXD\right)$ = $\left[AX\right(B\backslash D\left)\right]\cup \left[\right(A\backslash C\left)XB\right]$


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 \left(CXD\right)$. 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}\left(A_{i}X{B}_i\right)$. 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}\left(A_{i}X{B}_i\right)\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.