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.