Tuesday, May 11, 2010

how to prove it - ch3, sec3.4(Proofs Involving Conjunctions and Biconditionals) ex

Proof strategies for conjunctions and biconditionals introduced in this sections are pretty trivial. Here they are...

To prove a goal of the form $P \land Q$: simply prove P and Q separately

To prove a goal of the form $P \leftrightarrow Q$: simply prove $P \rightarrow Q$ and $Q \rightarrow P$ separately

To use a given of the form $P \land Q$ assume as if P and Q are both given. To use a given of the form $P \leftrightarrow Q$ assume as if $P \rightarrow Q$ and $Q \rightarrow P$ are both given.

Some times when proving $P \leftrightarrow Q$, steps to prove $P \rightarrow Q$ and $Q \rightarrow P$ are same except the order is reversed. In those cases, to keep the proof concise, we can go direct $P \leftrightarrow R \leftrightarrow Q$ where R is a common form that comes while proving $P \rightarrow Q$ and $Q \rightarrow P$

Other Notes:
This is Set specific. A = B can be proved by either proving $\forall (x \in A \leftrightarrow x \in B)$ or by proving $(A \subseteq B) \land (B \subseteq A)$ where A and B are sets.

Another thing when proofs involve even/odd numbers, we can use following definitions for even/odd.
An integer x is even if $\exists k \in Z (x = 2k)$
An integer x is odd if $\exists k \in Z (x = 2k + 1)$


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

Ex-1
($\rightarrow$)Suppose $\forall x (P(x) \land Q(x))$ is true. Let y be arbitrary, so P(y) is true. Since y is arbitrary, we can conclude $\forall x P(x)$ is true. By using similar argument we can prove that $\forall x Q(x)$ is also true. Hence $\forall x P(x) \land \forall x Q(x)$ is true.
($\leftarrow$)Suppose $\forall x P(x) \land \forall x Q(x)$ is true. Let y be arbitrary, it follows that P(y) is true and Q(y) is true as well, so $P(y) \land Q(y)$ is true. Since y is arbitrary, we can conclude $\forall x (P(x) \land Q(x))$ is true.


Ex-2
Suppose $A \subseteq B$, $A \subseteq C$ and let x be an arbitrary element of A. Since $A \subseteq B$, therefore $x \in B$. Also since $A \subseteq C$, therefore $x \in C$ also. So $x \in B \land x \in C$ and therefore $x \in B \cap C$. Since x is arbitrary, we can conclude $A \subseteq B \cap C$. Thus if $A \subseteq B$ and $A \subseteq C$ then $A \subseteq B \cap C$


Ex-3 Let C be an arbitrary set and x be an arbitrary element of $C \setminus B$. It follows that $x \in C$ and $x \notin B$. Since $A \subseteq B$, it means every element of A is an element of B also or in other words(the contrapositive) a element that is not in B is not in A also. Since $x \notin B$, therefore $x \notin A$. Since $x \in C$ and $x \notin A$, therefore $x \in C \setminus A$. Since x is arbitrary, we can conclude $C \setminus B \subseteq C \setminus A$


Ex-4 Suppose $A \subseteq B$ and $\lnot (A \subseteq C)$. Since $\lnot (A \subseteq C)$, there exists atleast one x s.t. x is in A but not in C. Since $A \subseteq B$, x should be in B also. So x is in B but not in C, Thus $\lnot (B \subseteq C)$.


Ex-5 Suppose $A \subseteq B \setminus C$ and A is non-empty. Let $a$ be an element of A. It follows that $a \in B \setminus C$, that is $a \in B$ and $a \notin C$. We've found an element that is in B but not in C, so $\lnot (B \subseteq C)$.


Ex-6
Let x be an arbitrary element of $A \setminus (B \cap C)$. It follows
$x \in A \setminus (B \cap C)$ iff
$x \in A \land \lnot x \in (B \cap C)$ iff
$x \in A \land \lnot (x \in B \land x \in C)$ iff
$x \in A \land (x \notin B \lor x \notin C)$ iff
$(x \in A \land x \notin B) \lor (x \in A \land x \notin C)$ iff
$(x \in A \setminus B) \lor (x \in A \setminus C)$ iff
$x \in (A \setminus B) \cup (A \setminus C)$
Since x is arbitrary, we can conclude $A \setminus (B \cap C)$ = $(A \setminus B) \cup (A \setminus C)$


Ex-7
($\rightarrow$)Suppose A and B are arbitrary sets, let x be an arbitrary element of $P(A \cap B)$. It follows that $x \subseteq (A \cap B)$. Let y be an arbitrary element of x, then $y \in (A \cap B)$ and therefore $y \in A$ and $y \in B$. Since y is arbitrary so $x \subseteq A$ and also $x \subseteq B$, therefore $x \in P(A)$ and $x \in P(B)$. Thus, $x \in P(A) \cap P(B)$.
($\leftarrow$)Suppose A and B are arbitrary sets, let x be an arbitrary element of $P(A) \land P(B)$. It follows that $x \in P(A) \land x \in P(B)$, therefore $x \subseteq A$ and $x \subseteq B$. Let y be an arbitrary element of x, then $y \in A$ and $y \in B$. So, $y \in A \cap B$. Since y is arbitrary, we conclude $x \subseteq (A \cap B)$. Thus, $x \in P(A \cap B)$.


Ex-8
($\rightarrow$)Suppose $A \subseteq B$. Let x be an arbitrary element of $P(A)$, Since $x \in P(A)$ it follows $x \subseteq A$. Since $A \subseteq B$, so $x \subseteq B$ also. Therefore $x \in P(B)$. Since x is arbitrary, we can conclude $P(A) \subseteq P(B)$.
($\leftarrow$)Suppose $P(A) \subseteq P(B)$. Let x be an arbitrary element of A, so there should exist atleast one set y in $P(A)$ s.t. $x \in y$. Since $P(A) \subseteq P(B)$, so $y \in P(B)$. It means $y \subseteq B$ and $x \in y$, therefore $x \in B$ also. Since x is arbitrary, we can conclude $A \subseteq B$.


Ex-9 Suppose x and y are odd integers. So there exists a $k_1 \in Z$ s.t. $x = 2k_1 + 1$ and a $k_2 \in Z$ s.t. $y = 2k_2 + 1$. On multiplying both we get $xy = 2(2k_1k_2 + k_1 + k_2) + 1$. Since $(2k_1k_2 + k_1 + k_2) \in Z$, therefore xy is odd.


Ex-10 Let n be an arbitrary integer.
($\rightarrow$)We want to prove that If $n^3$ is even then so is n. We'll prove the contrapositive that is, If n is odd then $n^3$ is also odd. Suppose n is odd, then there exists a $k \in Z$ s.t. $n = 2k + 1$. So $n^3 = (2k + 1)^3$ and then $n^3 = 8k^3 + 1 + 6k(2k + 1)$, then $n^3 = 8k^3 + 12k^2 + 6k + 1$, then $n^3 = 2(4k^3 + 6k^2 + 3k) + 1$. Since $(4k^3 + 6k^2 + 3k) \in Z$, so $n^3$ is odd.
($\leftarrow$)Suppose n is even, then there exists a $k \in Z$ s.t. $n = 2k$, so $n^3 = 2(4k^3)$. Since $4k^3 \in Z$, so $n^3$ is even.


Ex-11
(a) The flaw is in chosing the same k for both m and n.
(b) It is incorrect. A counterexample is n = 5, m = 2.


Ex-12 Suppose x is an arbitrary real number.
($\rightarrow$) Suppose, for a particular real number y, (x + y = xy)
=> y = $\frac{x}{x-1}$
it is defined only when $(x-1) \neq 0$, that is $x \neq 1$. Since x is arbitrary, we can conclude that $\forall x \in R \exists y \in R ((x + y = xy) \rightarrow (x \neq 1))$

($\leftarrow$) Suppose, $x \neq 1$, Let us take a real number y = $\frac{x}{x-1}$. It is defined because $x \neq 1$ and hence $(x-1) \neq 0$.
Now check (x + y)
= $x + \frac{x}{x-1}$
= $\frac{x(x-1) + x}{x-1}$
= $\frac{x^2}{x-1}$
= xy
Since x is arbitrary, we can conclude that $\forall x \in R \exists y \in R ((x \neq 1) \rightarrow (x + y = xy))$


Ex-13 Let z = 1, and now prove
$\forall x \in R^+ [\exists y \in R (y - x = \frac {y}{x}) \leftrightarrow x \neq 1]$

Suppose x be arbitrary positive real number and then we need to prove following
$\exists y \in R (y - x = \frac {y}{x}) \leftrightarrow x \neq 1$

($\rightarrow$) $\exists y \in R (y - x = \frac {y}{x}) \rightarrow x \neq 1$
we prove the contrapositive
which is , $x = 1 \rightarrow \forall y \in R (y - x \neq \frac {y}{x})
Suppose, x = 1 and y be arbitrary real number. clearly $y-1 \neq y$. So, that establishes first half of the biconditional statement.

($\leftarrow$) $x \neq 1 \rightarrow \exists y \in R (y - x = \frac {y}{x})$
clearly, given that $x \neq 1$, then you can choose real number $y = \frac{x^2}{x-1}$ for which $y - x = \frac {y}{x}$. So, that establishes second half of the biconditional statement.

Ex-14 Let x be an arbitrary element of $\cup \{A \setminus B | A \in F \}$. It follows that there exists a set $a \in F$ s.t. $x \in a \setminus B$. Moreover, $\lnot (a \subseteq B)$ is true otherwise $a \setminus B$ will be empty. Since $\lnot (a \subseteq B)$, so $a \notin P(B)$. Since $a \in F$ and $a \notin P(B)$, so $a \in F \setminus P(B)$ and hence $x \in \cup (F \setminus P(B))$. Since x is arbitrary, we can conclude $\cup \{A \setminus B | A \in F \} \subseteq \cup (F \setminus P(B))$


Ex-15
given: every element of $F$ is disjoint from some element of $G$
goal: $\cup F$ and $\cap G$ are disjoint $\equiv$ $\forall x \in \cup F (\forall y \in \cap G x \neq y)$

Formal Proof:
Let x be an arbitrary element of $\cup F$, so there exists a set $f \in F$ s.t. $x \in f$. Let y be an arbitrary element of $\cap G$, so y is in every set in $G$. Since every element of $F$ is disjoint from some element of $G$, so there exists a $g \in G$ s.t. $f$ and $g$ are disjoint. But $y \in g$ also as y is in every set in $G$ and since $x \in f$ and $f$ and $g$ are disjoint, therefore $x \neq y$. Since x and y are arbitrary, we can conclude that $\cup F$ and $\cap G$ are disjoint.


Ex-16 We will prove that $A \subseteq \cup P(A)$ and also $\cup P(A) \subseteq A$.
Let us prove $A \subseteq \cup P(A)$. Let x be an arbitrary element of A. Since $A \in P(A)$, so by definition of $\cup P(A)$, x should be an element of $\cup P(A)$ also. Since x is arbitrary, $A \subseteq P(A)$.
Let us prove $\cup P(A) \subseteq A$. Let x be an arbitrary element of $\cup P(A)$, so there exists an $a \in P(A)$ s.t. $x \in a$. Since $a \in P(A)$, therefore $a \subseteq A$ and hence $x \in A$ also. Since x is arbitrary we can conclude that $\cup P(A) \subseteq A$.
Thus $A = P(A)$.


Ex-17
(a) Let x be an arbitrary element of $\cup (F \cap G)$. It follows, there exists a set $A \in (F \cap G)$ s.t. $x \in A$. Since $A \in (F \cap G)$, so $A \in F$ and hence $x \in \cup F$ also. By similar argument $x \in \cup G$ also. Since $x \in \cup F$ and $x \in \cup G$, therefore $x \in (\cup F) \cap (\cup G)$. Since x is arbitrary, we can conclude $\cup (F \cap G) \subseteq (\cup F) \cap (\cup G)$

(b) The flaw is in the fact that we are chosing the same A in both families.

(c) $F$ = { {1},{2} } and $G$ = { {2}, {1,2} }
$F \cap G$ = { {2} }
$\cup (F \cap G)$ = { 2 }... (i)

$\cup F$ = { 1,2 }
$\cup G$ = { 1,2 }
$(\cup F) \cap (\cup G)$ = { 1,2 }... (ii)

clearly (i) and (ii) are not same.

Note: How I found it?
I realized for $x \in (\cup F) \cap (\cup G)$, $x \in (\cup F) \land x \in (\cup G)$ and hence there exist particular $f \in F$ and $g \in G$ s.t. $x \in f$ and $x \in g$. Note that $f$ and $g$ could be *different* sets.
However for $x \in \cup (F \cap G)$, there exist a particular $a \in (F \cap G)$ s.t. $x \in a$. Note that for this case the *same* set $a$ has to be in both the families.


Ex-18
($\rightarrow$)
given:
goal: If $(\cup F) \cap (\cup G) \subseteq \cup (F \cap G)$ then $\forall A \in F \forall B \in G (A \cap B \subseteq \cup (F \cap G))$

Assume the hypotheses

given: $(\cup F) \cap (\cup G) \subseteq \cup (F \cap G)$
goal: $\forall A \in F \forall B \in G (A \cap B \subseteq \cup (F \cap G))$

Let A be an arbitrary element of $F$ and B be an arbitrary element of $G$.

given: $(\cup F) \cap (\cup G) \subseteq \cup (F \cap G)$
goal: $A \cap B \subseteq \cup (F \cap G)$ $\equiv$ $\forall x (x \in (A \cap B) \rightarrow x \in \cup (F \cap G))$

Let x be arbitrary

given: $(\cup F) \cap (\cup G) \subseteq \cup (F \cap G)$
goal: $x \in (A \cap B) \rightarrow x \in \cup (F \cap G)$

Assume the hypotheses

given: $(\cup F) \cap (\cup G) \subseteq \cup (F \cap G)$ , $x \in (A \cap B)$
goal: $x \in \cup (F \cap G)$

Formal Proof:
Suppose $(\cup F) \cap (\cup G) \subseteq \cup (F \cap G)$. Let A be an arbitrary element of $F$ and B be an arbitrary element of $G$ and x be an arbitrary element of $A \cap B$. It follows $x \in A$ and $x \in B$. Since $x \in A$ and $A \in F$, so $x \in \cup F$. Similarly, $x \in \cup G$. So $x \in (\cup F) \cap (\cup G)$. Since $(\cup F) \cap (\cup G) \subseteq \cup (F \cap G)$, hence $x \in \cup (F \cap G)$. Since x is arbitrary, we can conclude that $A \cap B \subseteq \cup (F \cap G)$. And since A and B are arbitrary, therefore $\forall A \in F \forall B \in G (A \cap B \subseteq \cup (F \cap G))$

($\leftarrow$)
Suppose $\forall A \in F \forall B \in G (A \cap B \subseteq \cup (F \cap G))$. Let x be an arbitrary element of $(\cup F) \cap (\cup G)$. Then $x \in \cup F$, it follows that there exists a set $f \in F$ s.t. $x \in f$. Similarly there exists a set $g \in G$ s.t. $x \in g$. So $x \in f \cap g$. Since $\forall A \in F \forall B \in G (A \cap B \subseteq \cup (F \cap G))$, so $(f \cap g) \subseteq \cup (F \cap G)$ and hence $x \in \cup (F \cap G)$. Since x is arbitrary, we conclude that $(\cup F) \cap (\cup G) \subseteq \cup (F \cap G)$


Ex-19
($\rightarrow$)We will prove it by contradiction. Suppose $\cup F$ and $\cup G$ are disjoint. Let A be an arbitrary element of $F$ and B be an arbitrary element of $G$ and A and B are not disjoint. Then, there exists a x s.t. $x \in A$ and $x \in B$. Since $x \in A$ and $A \in F$, so $x \in \cup F$ and similarly $x \in \cup G$ also. This means $\cup F$ and $\cup G$ have a common element x and hence not disjoint and that contradicts our assumption. Hence A and B have to be disjoint. Since A and B are arbitrary, we conclude that for all $A \in F$ and $B \in G$, A and B are disjoint.
($\leftarrow$)We will prove it by contradiction. Suppose for all $A \in F$ and $B \in G$, A and B are disjoint. Assume $\cup F$ and $\cup G$ are not disjoint, then there exists a x s.t. $x \in \cup F$ and $x \in \cup G$. It follows there exist $A \in F$ and $B \in G$ s.t. $x \in A$ as well as $x \in B$ but this contradicts our earlier assumption. Hence $\cup F$ and $\cup G$ are disjoint.


Ex-20
(a) Suppose x be an arbitrary element of $(\cup F) \setminus (\cup G)$. It follows that $x \in \cup F$ and $x \notin \cup G$. Since $x \in \cup F$, therefore there exists $A \in F$ s.t. $x \in A$. Since $x \notin \cup G$, x can not be an element of any set in $G$. Since $x \in A$, so $A \notin G$. Since $A \in F$ and $A \notin G$, so $A \in F \setminus G$. Since $x \in A$ and $A \in F \setminus G$, therefore $x \in \cup (F \setminus G)$. Since x is arbitrary, we can conclude $(\cup F) \setminus (\cup G) \subseteq \cup (F \setminus G)$

(b) The flaw is in the statement, "Since $x \in A$ and $A \notin G$, $x \notin \cup G$". On the contrary, Since A is a particular set in $G$ and there *can* be another set $B \in G$ s.t. $x \in B$ and in that case $x \in \cup G$.

(c)
($\rightarrow$)
given:
goal: If $\cup(F \setminus G) \subseteq (\cup F) \setminus (\cup G)$ then $\forall A \in (F \setminus G) \forall B \in G (A \cap B = \emptyset)$

Assume the hypotheses

given: $\cup(F \setminus G) \subseteq (\cup F) \setminus (\cup G)$
goal: $\forall A \in (F \setminus G) \forall B \in G (A \cap B = \emptyset)$

Let A be an arbitrary element of $F \setminus G$ and B be an arbitrary element of $G$.

given: $\cup(F \setminus G) \subseteq (\cup F) \setminus (\cup G)$
goal: $A \cap B = \emptyset$ $\equiv$ $\forall x (x \notin A) \lor (x \notin B)$

Let x be arbitrary

given: $\cup(F \setminus G) \subseteq (\cup F) \setminus (\cup G)$
gaol: $(x \notin A) \lor (x \notin B)$ $\equiv$ $x \in A \rightarrow x \notin B$

Assume the hypotheses

given: $\cup(F \setminus G) \subseteq (\cup F) \setminus (\cup G)$ , $x \in A$
goal: $x \notin B$

Formal Proof:
Suppose $\cup(F \setminus G) \subseteq (\cup F) \setminus (\cup G)$. Let A be an arbitrary element of $F \setminus G$ and B be an arbitrary element of $G$ and x be an arbitrary element of A. Since $x \in A$ and $A \in (F \setminus G)$, therefore $x \in \cup(F \setminus G)$. Since $\cup(F \setminus G) \subseteq (\cup F) \setminus (\cup G)$, therefore $x \in (\cup F) \setminus (\cup G)$, therefore $x \notin (\cup G)$. It means x is not an element of any element in $G$. Hence x can not be element of B or $x \notin B$. Thus $x \in A \rightarrow x \notin B$, therefore $x \notin A \lor x \notin B$, therefore $\lnot (x \in A \land x \in B)$, therefore $x \notin (A \cap B)$. Since x is arbitrary, we can conclude $A \cap B = \emptyset$

($\leftarrow$)
given:
goal: If $\forall A \in (F \setminus G) \forall B \in G (A \cap B = \emptyset)$ then $\cup(F \setminus G) \subseteq (\cup F) \setminus (\cup G)$

Assume the hypotheses

given: $\forall A \in (F \setminus G) \forall B \in G (A \cap B = \emptyset)$
goal:
$\cup(F \setminus G) \subseteq (\cup F) \setminus (\cup G)$
$\equiv$ $\forall x (x \in \cup(F \setminus G) \rightarrow x \in (\cup F) \setminus (\cup G))$

Let x be arbitrary

given: $\forall A \in (F \setminus G) \forall B \in G (A \cap B = \emptyset)$
goal: $x \in \cup(F \setminus G) \rightarrow x \in (\cup F) \setminus (\cup G)$

Assume the hypotheses

given: $\forall A \in (F \setminus G) \forall B \in G (A \cap B = \emptyset)$ , $x \in \cup(F \setminus G)$
goal: $x \in (\cup F) \setminus (\cup G)$

Formal Proof:
Suppose $\forall A \in (F \setminus G) \forall B \in G (A \cap B = \emptyset)$. Let x be an arbitrary element of $\cup(F \setminus G)$. It follows that there exists a set $y \in F \setminus G$ s.t. $x \in y$.
Since $y \in F \setminus G$, so $y \in F$. Also $x \in y$, hence $x \in \cup F$.
Since $y \in F \setminus G$, so y is disjoint from every set in $G$ because of our assumpion made in the starting of the proof and hence x can not belong to any set in $G$. Thus, $x \notin \cup G$.
As we've proven that $x \in \cup F$ and $x \notin \cup G$, so $x \in (\cup F) \setminus (\cup G)$. Since x is arbitrary, we can conclude $\cup(F \setminus G) \subseteq (\cup F) \setminus (\cup G)$

(d)
$F$ = { {1}, {1,2} }
$G$ = { {1} }
$F \setminus G$ = { {1,2} }
$\cup (F \setminus G)$ = {1,2) ...(i)

$\cup F$ = {1,2}
$\cup G$ = {1}
$(\cup F) \setminus (\cup G)$ = {2} ...(ii)

clearly (i) and (ii) are not same.


Ex-21 We will prove the contrapositive, which says If for all $A \in F$ there exists some $B \in G$ s.t. $A \subseteq B$ then $\cup F \subseteq \cup G$. Suppose for all $A \in F$ there exists some $B \in G$ s.t. $A \subseteq B$. Let x be an arbitrary element of $\cup F$. It follows that there exists some $A \in F$ s.t. $x \in A$. But, there has to exist a $B \in G$ s.t. $A \subseteq B$. Then $x \in B$. So we have $x \in B$ and $B \in G$, therefore $x \in \cup B$. Since x is arbitrary, we can conclude $\cup F \subseteq \cup G$


Ex-22
(a) Following strategies have been used...
To prove a goal of the form $\forall x P(x)$
To prove a goal of the form $P \rightarrow Q$
To use a given of the form $P \land Q$

(b) Let x be an arbitrary element of $B \setminus (\cup_{i \in I}A_i)$. Then
$x \in B \setminus (\cup_{i \in I}A_i)$ iff
$x \in B \land \lnot (x \in (\cup_{i \in I}A_i))$ iff
$x \in B \land \lnot (\exists i \in I (x \in A_i))$ iff
$x \in B \land (\forall i \in I (x \notin A_i))$ iff
$\forall i \in I (x \in B) \land (x \notin A_i)$ iff
$\forall i \in I (x \in B \setminus A_i)$ iff
$x \in \cap_{i \in I}(B \setminus A_i)$

Since x is arbitrary, we can conclude $B \setminus (\cup_{i \in I}A_i)$ = $\cap_{i \in I}(B \setminus A_i)$

(c)
The theorem is, $B \setminus (\cap_{i \in I}A_i)$ = $\cup_{i \in I}(B \setminus A_i)$

Let x be an arbitrary element of $B \setminus (\cap_{i \in I}A_i)$. Then
$x \in B \setminus (\cap_{i \in I}A_i)$ iff
$x \in B \land \lnot (x \in (\cap_{i \in I}A_i))$ iff
$x \in B \land \lnot (\forall i \in I (x \in A_i))$ iff
$x \in B \land (\exists i \in I (x \notin A_i))$ iff
$\exists i \in I (x \in B \land x \notin A_i)$ iff
$\exists i \in I (x \in B \setminus A_i)$ iff
$x \in \cup_{i \in I}(B \setminus A_i)$

Since x is arbitrary, we can conclude $B \setminus (\cap_{i \in I}A_i)$ = $\cup_{i \in I}(B \setminus A_i)$


Ex-23
(a) Let x be an arbitrary element of $\cup_{i \in I}(A_i \setminus B_i)$. Then there exists $i \in I$ s.t. $x \in A_i \setminus B_i$, that is $x \in A_i$ and $x \notin B_i$. Since $i \in I$ and $x \in A_i$, so $x \in \cup_{i \in I}A_i$. Since $i \in I$ and $x \notin B_i$, so $x \notin \cap_{i \in I}B_i$. Thus $x \in (\cup_{i \in I}A_i) \setminus (\cap_{i \in I}B_i)$. Since x is arbitrary, we can conclude that $\cup_{i \in I}(A_i \setminus B_i) \subseteq (\cup_{i \in I}A_i) \setminus (\cap_{i \in I}B_i)$

Another method(WRONG):
Let x be an arbitrary element of $\cup_{i \in I}(A_i \setminus B_i)$. Then
$x \in \cup_{i \in I}(A_i \setminus B_i)$
=> $\exists i \in I (x \in A_i \setminus B_i)$
=> $\exists i \in I (x \in A_i \land x \notin B_i)$
=> $(\exists i \in I (x \in A_i)) \land (\exists i \in I (x \notin B_i))$ (justify this step)
=> $(x \in \cup_{i \in I}A_i) \land \lnot (\forall i \in I (x \in B_i))$
=> $(x \in \cup_{i \in I}A_i) \land \lnot (x \in \cap_{i \in I}B_i)$
=> $x \in (\cup_{i \in I}A_i) \setminus (\cap_{i \in I}B_i)$

The reason this is wrong is that, what we've proven with this method is that
$\cup_{i \in I}(A_i \setminus B_i)$ = $(\cup_{i \in I}A_i) \setminus (\cap_{i \in I}B_i)$
which is not true and that is why one of the steps in above analysis is not justifiable.

(b)
$A_1$ = {1,2} $A_2$ = {3}
$B_1$ = {2} $B_2$ = {5}

$A_1 \setminus B_1$ = {1}
$A_2 \setminus B_2$ = {3}
$\cup_{i \in I}(A_i \setminus B_i)$ = {1,3} ...(i)

$\cup_{i \in I}A_i$ = {1,2,3}
$\cap_{i \in I}B_i$ = $\emptyset$
$(\cup_{i \in I}A_i) \setminus (\cap_{i \in I}B_i)$ = {1,2,3} ...(ii)

clearly (i) and (ii) are not same.


Ex-24
(a) Let x be an arbitrary element of $\cup_{i \in I}(A_i \cap B_i)$. It follows that there exists a $i \in I$ s.t. $x \in A_i$ and $x \in B_i$. Since we have a particular i s.t. $x \in A_i$ and $i \in I$, therefore $x \in \cup_{i \in I}A_i$. By similar argument $x \in \cup_{i \in I}B_i$ as well. Thus $x \in (\cup_{i \in I}A_i) \cap (x \in \cup_{i \in I}B_i)$. Since x is arbitrary, we can conclude that $\cup_{i \in I}(A_i \cap B_i) \subseteq (\cup_{i \in I}A_i) \cap (\cup_{i \in I}B_i)$

(b)
$A_1$ = {1,3} $A_2$ = {4}
$B_1$ = {1} $B_2$ = {3,4}

$A_1 \cap B_1$ = {1}
$A_2 \cap B_2$ = {4}
$\cup_{i \in I}(A_i \cap B_i)$ = {1,4} ...(i)

$\cup_{i \in I}A_i$ = {1,3,4}
$\cup_{i \in I}B_i$ = {1,3,4}
$(\cup_{i \in I}A_i) \cap (\cup_{i \in I}B_i)$ = {1,3,4} ...(ii)

Clearly, (i) and (ii) are not same.


Ex-25
Let us try c = ab. Since a and b are integers, so clearly a|c and b|c as well.

Ex-26
(a)
($\rightarrow$) Suppose 15|n, so there exists $k \in Z$ s.t. n = 15k. So n = 3(5k). Since 5k is an integer so 3|n. Also n = 5(3k) and 3k is an integer, so 5|n. So if 15|n then 3|n and 5|n.
($\leftarrow$) Suppose 3|n and 5|n. So there exist $k \in Z$ s.t.
n = 3k ...(i)
and $l \in Z$ s.t. n = 5l ...(ii)
(sidenote: we want to find a and b s.t. 3a + 5b = 15(or some multiplie of it), on a few tries I came up with a = -5 and b = 6)

multiply (i) with -5, multiply (ii) with 6 and add them both
-5n + 6n = (-15k) + (30l)
=> n = 15(2l - k)
Since (2l - k) is also an integer, so 15|n

(b) It can be proven by finding just one counterexample. n = 30 is one and n = 90, 150 etc are also the counterexamples.

4 comments:

  1. Ex-13: There's no typo.

    Let z = 1.
    [Proof of ∀A ∈ R+[∃y ∈ R(y - x = y/x) ↔ x ≠ z] goes here.]
    Thus ∃z ∈ R∀A ∈ R+[∃y ∈ R(y - x = y/x) ↔ x ≠ z]

    ReplyDelete
  2. @Stavros : thanks, yes makes sense, updating the original post with full proof.

    ReplyDelete
  3. In 26) I found (p-q)/2 as the integer. If n is even, then for 3p = 5q = n, p and q must be even, p-q is even and so (p-q)/2 is an integer. If n is odd, then for 3p = 5q = n, p and q must be odd, so p-q is even (2x+1 - 2y - 1 = 2(x-y), which is always even), so (p-q)/2 is always ok.
    But then, one should prove these separatedly, in order not to clutter the proof...

    ReplyDelete
  4. Hi prove 3 and 6 start with for all set C and for all a,b and c set .... How is it different then every set example or exercise that start with suppose a is a set or suppose a b is a set

    ReplyDelete