## 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)\equivx \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.