how to prove it - ch2, sec2.3(More On Sets) ex

So far we've learnt 3 ways to represent sets.
- By listing all elements e.g. {1,2,3,4} represents a set that contains 1,2,3 and 4
- By using ellipsis, e.g. {1,2,3,4,...} represents set of all positive integers
- By using elementhood test as in {x | P(x)}, e.g. {x | $x^2 = 9$} represents set {-3,3}. And if we want to be more precise and S is the universe of discourse then we say {$x \in S | P(x)$}

This section introduces another way called "index set" or "index family" which is to write
{$x_i | i \in I$} where $x_i$ is some function of i.
For example {$n^2 | n \in N$} represents set of square of all natural numbers.
Note that set of square of all natural numbers can also be represented by

{$x | \exists i \in N (i^2 = x)$}

This means ($x \in \{n^2 | n \in N\}$) $\equiv$ ($\exists n \in N (x = n^2)$)

In general, ($x \in \{x_i | i \in I\}$) $\equiv$ ($\exists i \in I (x = x_i)$)

Family Of Set A set, all of whose elements are sets.
For example, Power Set of a set S is the set of all the subsets of S, i.e. {A | A $\subseteq$ S}.
So an element x belonging to power set of S means $x \subseteq S$

Intersection of all the sets in a family of set F is denoted by $\cap F$ = {$x | \forall A \in F (x \in A)$}

Union of all the sets in a family of set F is denoted by $\cup F$ = {$x | \exists A \in F (x \in A)$}

Alternatively
A family F of sets $A_i$ can be convenienty defined as {$A_i | i \in I$}.

There exists, additional notations for intersection/union of family based on above definition.

$\cap F$ = ${\cap}_{i \in I}A_i$ = {$x | \forall i \in I (x \in A_i)$}

and

$\cup F$ = ${\cup}_{i \in I}A_i$ = {$x | \exists i \in I (x \in A_i)$}




======================================================================================
$P(A)$ in all of these exercises represents Power Set of A and $F$ represents famility of set.

Ex-1(a) $F \subseteq P(A)$
= $\forall x (x \in F \rightarrow x \in P(A))
= $\forall x (x \in F \rightarrow x \subseteq A)$
= $\forall x [x \in F \rightarrow (\forall y (y \in x \rightarrow y \in A))]

Ex-1(b) $A \subseteq \{2n+1 | n \in N\}$
= $\forall x [x \in A \rightarrow x \in \{2n+1 | n \in N\}]$
= $\forall x [x \in A \rightarrow \exists n \in N (2n+1 = x)]$

Ex-1(c) $\{n^2+n+1 | n \in N\} \subseteq \{2n+1 | n \in N\}$
= $\forall x [x \in \{n^2+n+1 | n \in N\} \rightarrow x \in \{2n+1 | n \in N\}$
= $\forall x [\exists n \in N (n^2+n+1 = x) \rightarrow \exists n \in N (2n+1 = x)]$

Ex-1(d) $\lnot [P({\cup}_{i \in I}A_i) \subseteq {\cup}_{i \in I} P(A_i)]$
= $\lnot [\forall x (x \in P({\cup}_{i \in I}A_i) \rightarrow x \in {\cup}_{i \in I} P(A_i)]$
= $\exists x \lnot[(x \in P({\cup}_{i \in I}A_i) \rightarrow x \in {\cup}_{i \in I} P(A_i)]$
= $\exists x \lnot[x \notin P({\cup}_{i \in I}A_i) \lor x \in {\cup}_{i \in I} P(A_i)]$
= $\exists x [x \in P({\cup}_{i \in I}A_i) \land x \notin {\cup}_{i \in I} P(A_i)]$
= $\exists x [x \subseteq ({\cup}_{i \in I}A_i) \land \lnot (\exists i \in I (x \in P(A_i)))]$
= $\exists x [\forall y (y \in x \rightarrow y \in ({\cup}_{i \in I}A_i)) \land \lnot (\exists i \in I (x \subseteq A_i))]$
= $\exists x [\forall y (y \in x \rightarrow \exists i \in I (y \in A_i)) \land \forall i \in I \lnot (x \subseteq A_i)]$
= $\exists x [\forall y (y \in x \rightarrow \exists i \in I (y \in A_i)) \land \forall i \in I \exists y (y \in x \land y \notin A_i)]$


Ex-2(a) $x \in \cup F \setminus \cup G$
= $x \in \cup F \land x \notin \cup G$
= $\exists A \in F (x \in A) \land \lnot \exists A \in G (x \in A)$
= $\exists A \in F (x \in A) \land \forall A \in G (x \notin A)$

Ex-2(b) $\{x \in B | x \notin C \} \in P(A)$
= $\{x \in B | x \notin C \} \subseteq A$
= $\forall y [y \in \{x \in B | x \notin C \} \rightarrow y \in A]$
= $\forall y [y \in B \land y \notin C \rightarrow y \in A]$

Ex-2(c) $x \in {\cap}_{i \in I}(A_i \cup B_i)$
= $\forall i \in I [x \in (A_i \cup B_i)]$
= $\forall i \in I [x \in A_i \lor x \in B_i]$

Ex-2(d) $x \in ({\cap}_{i \in I}A_i) \cup ({\cap}_{i \in I}B_i)$
= $x \in ({\cap}_{i \in I}A_i) \lor x \in ({\cap}_{i \in I}B_i)$
= $\forall i \in I (x \in A_i) \lor \forall i \in I (x \in B_i)$


Ex-3 $P(\{\emptyset\}) = \{\emptyset, \{\emptyset\}\}$


Ex-4
$\cap F$ = {red, blue}
$\cup F$ = {red, green, blue, orange, purple}


Ex-5
$\cap F$ = $\emptyset$ , Mathematicians would say that $\cap F$ is undefined for this case
$\cup F$ = {3, 7, 12, 5, 16, 23}


Ex-6 I = {2, 3, 4, 5} and for each $i \in I$ $A_i$ = {i, i+1, i-1, 2i}
(a) Find all $A_i$
$A_2$ = {2, 3, 1, 4}
$A_3$ = {3, 4, 2, 6}
$A_4$ = {4, 5, 3, 8}
$A_5$ = {5, 6, 4, 10}

(b)
${\cap}_{i \in I}A_i$ = {4}
${\cup}_{i \in I}A_i$ = {1, 2, 3, 4, 5, 6, 8, 10}


Ex-7 trivial, passed


Ex-8 I = {2, 3} ; for all $i \in I$ $A_i$ = {i, 2i} and $B_i$ = {i, i+1}
(a)
$A_2$ = {2, 4}
$A_3$ = {3, 6}

$B_2$ = {2, 3}
$B_3$ = {3, 4}

(b)
Find ${\cap}_{i \in I}(A_i \cup B_i)$

$(A_2 \cup B_2)$ = {2, 3, 4}
$(A_3 \cup B_3)$ = {3, 4, 6}

${\cap}_{i \in I}(A_i \cup B_i)$ = {3, 4}


Find, $({\cap}_{i \in I}A_i) \cup ({\cap}_{i \in I}B_i)$
= {} $\cup$ {3}
= {3}

(c) They are not equivalent.


Ex-9 I = {1,2}; $A_i$ = {i, 2i}; $B_i$ = {3i, 4i}

$A_1$ = {1,2}
$A_2$ = {2,4}

$B_1$ = {3,4}
$B_2$ = {6,8}

$A_1 \cap B_1$ = { }
$A_2 \cap B_2$ = { }
So, ${\cup}_{i \in I}(A_i \cap B_i)$ = { } .............result-a

${\cup}_{i \in I}A_i$ = {1,2,4}
${\cup}_{i \in I}B_i$ = {3,4,6,8}
So,
$({\cup}_{i \in I}A_i) \cap ({\cup}_{i \in I}B_i)$ = {4} ............result-b

clearly result-a and result-b are not same.


Ex-10 $x \in P(A \cap B)$
= $x \subseteq (A \cap B)$
= $\forall y [y \in x \rightarrow y \in (A \cap B)]$
= $\forall y [y \in x \rightarrow (y \in A \land y \in B)]$
= $\forall y [y \notin x \lor (y \in A \land y \in B)]$
= $\forall y [(y \notin x \lor y \in A) \land (y \notin x \lor y \in B)]$
= $\forall y [(y \in x \rightarrow y \in A) \land (y \in x \rightarrow y \in B)]$
= $[\forall y (y \in x \rightarrow y \in A)] \land [\forall y (y \in x \rightarrow y \in A)]$
= $(x \subseteq A) \land (x \subseteq B)$
= $x \in P(A) \land x \in P(B)$


Ex-11 A = {1} and B = {2}
$P(A \cup B)$
= $P(\{1,2\})$
= {$\emptyset$, {1}, {2}, {1,2}}

$P(A) \cup P(B)$
= $P(\{1\}) \cup P(\{2\})$
= {$\emptyset$, {1}} $\cup$ {$\emptyset$, {2}}
= {$\emptyset$, {1}, {2}}

clearly the two are not equal.


Ex-12(a) LHS
= $x \in {\cup}_{i \in I}(A_i \cup B_i)$
= $\exists i \in I [x \in (A_i \cup B_i)]$
= $\exists i \in I [x \in A_i \lor x \in B_i]$
= $\exists i \in I (x \in A_i) \lor \exists i \in I (x \in B_i)$
= $(x \in {\cup}_{i \in I}A_i) \lor (x \in {\cup}_{i \in I}B_i)$
= $x \in [({\cup}_{i \in I}A_i) \cup ({\cup}_{i \in I}B_i)]$
= RHS

Ex-12(b) LHS
$x \in (\cap F)\cap(\cap G)$
= $x \in (\cap F) \land x \in (\cap G)$
= $[\forall A \in F (x \in A)] \land [\forall A \in G (x \in A)]$

RHS
$x \in \cap (F \cup G)$
= $\forall A \in (F \cup G) (x \in A)$
= $\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 \in F \rightarrow x \in A) \land (A \in G \rightarrow x \in A)]$
= $[\forall A \in F (x \in A)] \land [\forall A \in G (x \in A)]$

clearly both sides are equal

Ex-12(c) LHS
= $x \in {\cap}_{i \in I}(A_i \setminus B_i)$
= $\forall i \in I (x \in A_i \setminus B_i)$
= $\forall i \in I (x \in A_i \land x \notin B_i)$
= $[\forall i \in I (x \in A_i))] \land [\forall i \in I (x \notin B_i))]$
= $(x \in {\cap}_{i \in I}A_i) \land [\forall i \in I \lnot (x \in B_i)]$
= $(x \in {\cap}_{i \in I}A_i) \land \lnot [\exists i \in I (x \in B_i)]$
= $(x \in {\cap}_{i \in I}A_i) \land \lnot (x \in {\cap}_{i \in I}B_i)$
= $x \in ({\cap}_{i \in I}A_i) \setminus ({\cap}_{i \in I}B_i)$
= RHS


Ex-13

(a)
$B_3 = A_{1,3} \cup A_{2,3}$
$B_3 = \{1,3,4\} \cup \{2,3,5\}$
$B_3 = \{1,2,3,4,5\}$

$B_4 = A_{1,4} \cup A_{2,4}$
$B_4 = \{1,4,5\} \cup \{2,4,6\}$
$B_4 = \{1,2,4,5,6\}$

(b) ${\cap}_{j \in J}B_j$
= $B_3 \cap B_4$
= $\{1,2,3,4,5\} \cap \{1,2,4,5,6\}$
= $\{1,2,4,5\}

(c) Let $C_i$ = ${\cap}_{j \in J}A_{i,j}$ = $A_{i,3} \cap A_{i,4}$

$C_1 = $A_{1,3} \cap A_{1,4}$
= $\{1,3,4\} \cap \{1,4,5\}$
= $\{1,4\}$

$C_2 = $A_{2,3} \cap A_{2,4}$
= $\{2,3,5\} \cap \{2,4,6\}$
= $\{2\}$

${\cup}_{i \in I}({\cap}_{j \in J}A_{i,j})$
= ${\cup}_{i \in I}C_i$
= $C_1 \cup C_2$
= $\{1,4\} \cup \{2\}$
= $\{1,2,4\}$

clearly ${\cap}_{j \in J}({\cup}_{i \in I}A_{i,j})$ and ${\cup}_{i \in I}({\cap}_{j \in J}A_{i,j})$ are not equal.

(d)
$x \in {\cap}_{j \in J}({\cup}_{i \in I}A_{i,j})$
= $\forall j \in J (x \in {\cup}_{i \in I}A_{i,j})$
= $\forall j \in J \exists i \in I (x \in A_{i,j})$

$x \in {\cup}_{i \in I}({\cap}_{j \in J}A_{i,j})$
= $\exists i \in I (x \in {\cap}_{j \in J}A_{i,j})$
= $\exists i \in I \forall j \in J (x \in A_{i,j})$

clearly, they are not equivalent.

Ex-14
(a) $x \in \cup F$ means
$\exists A (A \in F \land x \in A)$
For $F = \emptyset$, above is not possible because there is no A
and hence, for any x $x \notin \cup F$ if $F = \emptyset$
$\therefore \cup \emptyset = \emptyset$

(b)
$x \in \cap F$ means
$\forall A (A \in F \rightarrow x \in A)$
For $F = \emptyset$, above is definitely true because there is no A to check for
and hence, for any x $x \in \cap \emptyset$ is always true
$\therefore \cap \emptyset = U$, where $U$ is the universe of discourse

However, for the reasons specified in the book it is too confusing(because $U$ will be context dependant) and mathematicians consider $\cap \emptyset$ undefined.


Ex-15

(a) Let us take a look at the two possiblities..

1. R belongs to the class of sets where set is an element of itself Then R is an element of itself, BUT elements of R are the sets which are not element of themselves. So, we have a contradiction here and its not possible.

2. R belongs to the class of sets where set is not element of itself Then R is not an element of itself, BUT R is the set of ALL such sets which are not element of themselves. So, we have a contracition here and its not possible.

Hence, R can not exist.

(b) This means a set can never be an element of itself. And hence, a universe of discourse of ALL the sets is meaningless.