how to prove it - ch3, sec3.5(Proofs Involving Disjunctions) ex

To use a given of the form $P \lor Q$
Strategy#1:
In this case the proof can be broken into cases. So, form of the final proof looks like following
Case 1. P is true
[Proof of goal goes here]
Case 2. Q is true
[Proof of goal goes here]
Since we know $P \lor Q$, these cases cover all the possibilities. Therefore the goal must be true.

However, this is a general technique, you may find it useful to break proof into cases even if the cases are not directly suggested by a given of the form $P \lor Q$. Any proof can be broken into cases at any time, as long as the cases exhaust all of the possibilities. For example, if we're proving something about integers. We can assume the cases like "x is even, x is odd" or "x < 0, x = 0, x > 0".

Strategy#2:
If you are also given $\lnot P$ or if you can prove P to be false, then use this given to conclude that Q is true... viceversa is also true.

To prove a goal of the form $P \lor Q$

Strategy#1: In the place where we write "proof of the goal", we need to prove only one of P or Q.

Strategy#2: Since $P \lor Q$ = $\lnot P \rightarrow Q$ = $\lnot Q \rightarrow P$, we can apply the strategies of proofs involving conditionals. This suggests a rule of inference called disjunctive syllogism .

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

Ex-1
Let x be an arbitrary element of $A \cap (B \cup C)$. Then $x \in A$ and $x \in (B \cup C)$. Let us consider the two cases.
Case1: $x \in B$
Since $x \in A$ and $x \in B$, so $x \in (A \cap B)$. Thus clearly $x \in (A \cap B) \cup C$

Case2: $x \in C$, clearly $x \in (A \cap B) \cup C$

Since x is arbitrary, we can conclude $ A \cap (B \cup C) \subseteq (A \cap B) \cup C$


Ex-2
Let x be an arbitrary element of $(A \cup B) \setminus C$. It follows that $x \in (A \cup B)$ and $x \notin C$. Let us consider the two exhaustive cases

Case1: $x \in A$
clearly $x \in A \cup (B \setminus C)$

Case2: $x \in B$
Since $x \notin C$ and $x \in B$, so clearly $x \in (B \setminus C)$. Thus $x \in A \cup (B \setminus C)$

Since x is arbitrary, we can conclude $(A \cup B) \setminus C \subseteq A \cup (B \setminus C)$


Ex-3
Let x be arbitrary. Then
$x \in A \setminus (A \setminus B)$ iff
$x \in A \land \lnot (x \in (A \setminus B))$ iff
$x \in A \land \lnot (x \in A \land x \notin B)$ iff
$x \in A \land (x \notin A \lor x \in B)$ iff
$(x \in A \land x \notin A) \lor (x \in A \land x \in B)$ iff
$x \in A \land x \in B$ iff
$x \in (A \cap B)$

Since x is arbitrary, we can conclude that $A \setminus (A \setminus B)$ = $A \cap B$


Ex-4
Let x be an arbitrary element of A. Let us consider 2 exhaustive cases

Case1: $x \in C$
Then, $x \in A \cap C$. Since $A \cap C \subseteq B \cap C$, therefore $x \in B \cap C$ and hence $x \in B$.

Case2: $x \notin C$
Then, $x \in A \cup C$. Since $A \cup C \subseteq B \cup C$, therefore $x \in B \cup C$. Since $x \notin C$ ,therefore $x \in B$.

Since x is arbitrary, we can conclude $A \subseteq B$


Ex-5
Suppose $A \triangle B \subseteq A$. Let x be an arbitrary element of B. We will prove by contradiction that $x \in A$. Assume $x \notin A$. Since $x \in B$ and $x \notin A$, therefore $x \in B \setminus A$, and then $x \in (A \setminus B) \cup (B \setminus A)$. Thus $x \in A \triangle B$. Since $A \triangle B \subseteq A$, so $x \in A$ should be true and that contradicts our assumption of $x \notin A$. So the assumption is wrong and $x \in A$. Since x is arbitrary, we can conclude $B \subseteq A$


Ex-6
($\rightarrow$) Suppose $A \cup C \subseteq B \cup C$. Let x be an arbitrary element $A \setminus C$. It follows that $x \in A$ and $x \notin C$ and hence $x \in A \cup C$. Since $A \cup C \subseteq B \cup C$, so $x \in B \cup C$. Since $x \notin C$, therefore $x \in B$. Since x is arbitrary, we can conclude $A \setminus C \subseteq B \setminus C$

($\leftarrow$) Suppose $A \setminus C \subseteq B \setminus C$. Let x be arbitrary element of $A \cup C$. Let us consider the two exhaustive cases

Case1: $x \in C$
clearly $x \in (B \cup C)$ also

Case2: $x \notin C$
Since $x \in A \cup C$ and $x \notin C$, it follows that $x \in A$ and hence $x \in A \setminus C$. Since $A \setminus C \subseteq B \setminus C$, therefore $x \in B \setminus C$ and hence $x \in B$ and therefore $x \in (B \cup C)$

Since x is arbitrary, we can conclude $A \cup C \subseteq B \cup C$


Ex-7
Suppose x be an arbitrary element of $P(A) \cup P(B)$. Let us consider the two exhaustive cases

Case1: $x \in P(A)$
then, $x \subseteq A$. And then $x \subseteq (A \cup B)$, so $x \in P(A \cup B)$

Case2: $x \in P(B)$
then, $x \subseteq B$. And then $x \subseteq (A \cup B)$, so $x \in P(A \cup B)$

Since x is arbitrary, we can conclude $P(A) \cup P(B) \subseteq P(A \cup B)$


Ex-8
given:
goal: If $P(A) \cup P(B) = P(A \cup B)$ then $A \subseteq B$ or $B \subseteq A$

Assume the hypotheses

given: $P(A) \cup P(B) = P(A \cup B)$
goal: $A \subseteq B$ or $B \subseteq A$ $\equiv$ If A is not subset of B then $B \subseteq A$

Assume the hypotheses again

given: $P(A) \cup P(B) = P(A \cup B)$ , $\lnot (A \subseteq B)$
goal: $B \subseteq A$

Formal Proof:
Suppose $P(A) \cup P(B) = P(A \cup B)$ and $\lnot (A \subseteq B)$. Since $\lnot (A \subseteq B)$, so we can chose a y s.t. $y \in A$ and $y \notin B$.

Now, We will prove by contradiction that $B \subseteq A$. Let us assume that $\lnot (B \subseteq A)$. Then we can chose a x s.t. $x \in B$ and $x \notin A$. Let us call C to be the set {x,y}. Clearly C is neither a subset of A nor that of B but $C \subseteq A \cup B$. However $P(A) \cup P(B) = P(A \cup B)$ means, $P(A \cup B) \rightarrow P(A) \cup P(B)$ and that means for any arbitrary set D, if $D \subseteq A \cup B$ then either $D \subseteq A$ or $D \subseteq B$. Since $C \subseteq A \cup B$, so C should either be a subset of A or that of B but both of these are already false and this is a contradiction. Therefore $\lnot (B \subseteq A)$ is false and it means $B \subseteq A$.


Ex-9
$y + \frac{1}{x}$ = $1 + \frac{y}{x}$ iff
$\frac{xy + 1}{x}$ = $\frac{x + y}{x}$ iff
$xy + 1$ = $x + y$ iff
$xy - x - y + 1 = 0$ iff
$x(y-1) -(y - 1) = 0$ iff
$(x - 1)(y - 1) = 0$ iff
$(x - 1) = 0$ or $(y - 1) = 0$ iff
$x = 1$ or $y = 1$


Ex-10
Suppose |x - 3| > 3. Let us consider the two exhaustive cases

Case1: (x - 3) $\geq$ 0
Since |x - 3| > 3, so (x - 3) > 3, then x > 6. On multiplying both sides with x we get $x^2$ > $6x$

Case2: (x - 3) < 0
Since |x - 3| > 3, so -(x - 3) > 3
=> (x - 3) < -3
=> x < 0

therefore $x^2$ > 0 but $6x$ < 0
so clearly $x^2$ > $6x$


Ex-11
($\rightarrow$)
Suppose |2x - 6| > x. Let us consider the two cases

Case1: (2x - 6) $\geq$ 0
Then (2x - 6) > x
=> x - 6 > 0
=> x > 6
=> x - 4 > 2 , so (x - 4) is positive and hence |x - 4| = (x - 4)
=> |x - 4| > 2

Case2: (2x - 6) < 0
Then -(2x - 6) > x
=> 2x - 6 < -x
=> 3x < 6
=> x < 2
=> x - 4 < -2 , so (x - 4) is negative and hence |x - 4| = -(x - 4)
=> -(x - 4) > 2
=> |x - 4| > 2

($\leftarrow$)
Suppose |x - 4| > 2. Let us consider the two cases

Case1: (x - 4) $\geq$ 0
Then (x - 4) > 2
=> x > 6
=> x + x > 6 + x
=> 2x > 6 + x
=> 2x - 6 > x

Also since (x - 4) $\geq$ 0
=> x $\geq$ 4
=> x > 0

Since 2x - 6 > x and x > 0, so 2x - 6 > 0 and so |2x - 6| = (2x - 6)
hence |2x - 6| > x

Case2: (x - 4) < 0
Then -(x - 4) > 2
=> (x - 4) < -2
=> x < 2 ...(i)

=> 2x < 4
=> 2x - 6 < -2 and so 2x - 6 is negative and hence |2x - 6| = -(2x - 6)

Again x < 2
=> 3x < 6
=> 3x - 6 < 0
=> 2x - 6 < -x
=> -(2x - 6) > x
=> |2x - 6| > x


Ex-12

(a)
($\rightarrow$)
Suppose |a| $\leq$ b. Let us consider the two cases

Case1: a $\geq$ 0
then a $\leq$ b

Case2: a < 0
then -a $\leq$ b
=> a $\geq$ -b

So either a $\leq$ b or a $\geq$ -b and hence -b $\leq$ a $\leq$ b

($\leftarrow$)
Suppose -b $\leq$ a $\leq$ b. Let us consider the two cases

Case1: a $\geq$ 0
So , |a| = a
=> -b $\leq$ |a| $\leq$ b
=> |a| $\leq$ b

Case2: a < 0
So, |a| = -a
Since -b $\leq$ a $\leq$ b
=> b $\geq$ -a $\geq$ -b
=> b $\geq$ |a| $\geq$ -b
=> b $\geq$ |a|
=> |a| $\leq$ b

(b)
Above we proved |a| $\leq$ b iff -b $\leq$ a $\leq$ b

For any real number x
|x| = |x|

we could also say
|x| $\leq$ |x|

Let say a = x and b = |x|

Since -b $\leq$ a $\leq$ b
so -|x| $\leq$ x $\leq$ |x|

(c)
Let us consider following set of exhaustive cases

Case1: x $\geq$ 0 and y $\geq$ 0
Then |x| = x, |y| = y. Since (x + y) is also positive
So, |x + y| = x + y
=> |x + y| = |x| + |y|

Case2: x < 0 and y < 0
Then |x| = -x, |y| = -y. Since (x + y) is also negative
So, |x + y| = -(x + y)
=> |x + y| = -x + (-y)
=> |x + y| = |x| + |y|

Case3: x $\geq$ 0 , y < 0 , (x + y) $\geq$ 0
Then |x| = x, |y| = -y and |x + y| = (x + y)
=> |x + y| = |x| - |y|

Since |x| - |y| < |x| + |y|
So |x + y| < |x| + |y|

Case4: x $\geq$ 0 , y < 0 , (x + y) < 0
Then |x| = x, |y| = -y and |x + y| = -(x + y)
=> |x + y| = -|x| + |y|

Since -|x| + |y| < |x| + |y|
So |x + y| < |x| + |y|

Case5: x < 0, y $\geq$ 0 , (x + y) $\geq$ 0
Then |x| = -x, |y| = y and |x + y| = (x + y)
=> |x + y| = -|x| + |y|
=> |x + y| < |x| + |y|

Case6: x < 0, y $\geq$ 0 , (x + y) < 0
Then |x| = -x, |y| = y and |x + y| = -(x + y) = -x - y
=> |x + y| = |x| - |y|
=> |x + y| < |x| + |y|


Since above set of cases is exhaustive, hence |x + y| $\leq$ |x| + |y|


Ex-13
Let us consider two exhaustive cases.

Case1: x is even
Then there exists an integer k s.t. x = 2k
=> $x^2$ = $4k^2$
=> $x^2 + x$ = $4k^2 + 2k$
=> $x^2 + x$ = $2k(2k + 1)$

Since k(k+1) is an integer, thus $x^2 + x$ is even

Case2: x is odd
Then there exists an integer k s.t. x = 2k + 1
=> $x^2$ = $(2k + 1)^2$
=> $x^2$ = $4k^2 + 1 + 4k$
=> $x^2 + x$ = $(4k^2 + 1 + 4k) + (2k + 1)$
=> $x^2 + x$ = $4k^2 + 6k + 2$
=> $x^2 + x$ = $2(2k^2 + 3k + 1)$

Since $(2k^2 + 3k + 1)$ is an integer, thus $x^2 + x$ is even


Ex-14
Let us consider two exhaustive cases

Case1: x is even
Then there exists an integer k s.t. x = 2k
=> $x^4$ = $16k^4$
=> $x^4$ = $8(2k^4)$

Clearly $x^4$ is divisible by 8. Thus remainder, when $x^4$ is divided by 8, is 0

Case2: x is odd
Then there exists an integer k s.t. x = 2k + 1
=> $x^4$ = $(2k + 1)^4$
=> $x^4$ = $(4k^2 + 1 + 4k)^2$
=> $x^4$ = $16k^4 + 1 + 16k^2 + 2(4k^2 + 4k + 16k^3)$
=> $x^4$ = $16k^4 + 1 + 24k^2 + 8k + 32k^3$
=> $x^4$ = $8(2k^4 + 4k^3 + 3k^2 + k) + 1$

Clearly, remainder, when $x^4$ is divided by 8, is 1

Thus, when $x^4$ is divided by 8, remainder is either 0 or 1


Ex-15
(a)
Let x be an arbitrary element of $\cup (F \cup G)$

$x \in \cup (F \cup G)$ iff
there exists a set A s.t.
$x \in A \land A \in (F \cup G)$ iff
$x \in A \land (A \in F \lor A \in G)$ iff
$(x \in A \land A \in F) \lor (x \in A \land A \in G)$ iff
$x \in \cup F \lor x \in \cup G$ iff
$x \in (\cup F) \cup (\cup G)$

Since x is arbitrary, we can conclude that $\cup (F \cup G)$ = $(\cup F) \cup (\cup G)$

(b)
My conjecture is $\cap (F \cup G)$ = $(\cap F) \cap (\cap G)$

Proof:
Let x be an arbitrary element of $\cap (F \cup G)$

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

Since x is arbitrary, so $\cap (F \cup G)$ = $(\cap F) \cap (\cap G)$


Ex-16
(a)
($\rightarrow$)
Let x be an arbitrary element of $B \cup (\cup F)$. Let us consider the two cases

Case1: $x \in B$
It follows that $x \in \cup \{B\}$. And also $x \in \cup (F \cup \{B\})$

Case2: $x \in \cup F$
Then, there exists a set $A \in F$ s.t. $x \in A$, since $A \in F \cup \{B\}$ also. So $x \in \cup (F \cup \{B\})$

Since x is arbitrary, clearly $B \cup (\cup F) \subseteq \cup (F \cup \{B\})$

($\leftarrow$)
Let x be an arbitrary element of $\cup (F \cup \{B\})$. Then there exists a set $A \in (F \cup \{B\})$ s.t. $x \in A$. Let us consider the two cases

Case1: $A \in F$
Then $x \in \cup F$ and therefore $x \in B \cup (\cup F)$

Case2: $A \in \{B\}$
It means A = B, so $x \in B$ and hence $x \in B \cup (\cup F)$

Since x is arbitrary, we conclude that $\cup (F \cup \{B\}) \subseteq B \cup (\cup F)$

Thus, $B \cup (\cup F)$ = $\cup (F \cup \{B\})$

(b)
($\rightarrow$)
Let x be an arbitrary element of $B \cup (\cap F)$. Let us consider the two cases

Case1: $x \in B$
Then for any set A, $x \in B \cup A$. Thus for all $A \in F$, $x \in B \cup A$ and therefore $x \in \cap_{A \in F}(B \cup A)$

Case2: $x \in \cap F$
Then for all $A \in F$, $x \in A$. So $x \in B \cup A$ also and therefore $x \in \cap_{A \in F}(B \cup A)$

Since x is arbitrary, we conclude that $B \cup (\cap F) \subseteq \cap_{A \in F}(B \cup A)$

($\leftarrow$)
Let x be an arbitrary element of $\cap_{A \in F}(B \cup A)$. Then for any $A \in F$, $x \in B \cup A$. Let us consider the two cases

Case1: $x \in B$
Then $x \in B \cup (\cap F)$ also.

Case2: $x \in A$
Since A any set in $F$. So $x \in \cap F$ and therefore $x \in B \cup (\cap F)$

Since x is arbitrary, we conclude that $\cap_{A \in F}(B \cup A) \subseteq B \cup (\cap F)$

Thus, $B \cup (\cap F)$ = $\cap_{A \in F}(B \cup A)$

(c)
My conjecture: $B \cap (\cap F)$ = $\cap (F \cap \{B\})$

Proof:
Let x be an arbitrary element.

$x \in B \cap (\cap F)$ iff
$x \in B \land x \in \cap F$ iff
$x \in B \land \forall A \in F (x \in A)$ iff
$[\forall A \in \{B\} (x \in A)] \land [\forall A \in F (x \in A)]$ iff
$\forall A \in (F \cap \{B\}) (x \in A)$ iff
$x \in \cap (F \cap \{B\})$

Since x is arbitrary, we can conclude $B \cap (\cap F)$ = $\cap (F \cap \{B\})$


Ex-17
Let x be an arbitrary element of $\cap H$. So for all sets $C \in H$, $x \in C$. Let A be an arbitrary element of $F$ and B be an arbitrary element of $G$. Since $A \cup B \in H$, so $x \in A \cup B$. Let us consider the two cases

Case1: $x \in A$
Since A is arbitrary, so $x \in \cap F$, Thus $x \in (\cap F) \cup (\cap G)$

Case2: $x \in B$
Since B is arbitrary, so $x \in \cap G$, Thus $x \in (\cap F) \cup (\cap G)$

Since x is arbitrary, we can conclude $\cap H \subseteq (\cap F) \cup (\cap G)$


Ex-18
Let x be arbitrary element of $A \triangle B$

$x \in A \triangle B$ iff
$x \in (A \cup B) \setminus (A \cap B)$ iff
$x \in (A \cup B) \land \lnot (x \in A \cap B)$ iff
$(x \in A \lor x \in B) \land \lnot (x \in A \land x \in B)$ iff
$(x \notin B \rightarrow x \in A) \land (x \notin A \lor x \notin B)$ iff
$(x \notin B \rightarrow x \in A) \land (x \in A \rightarrow x \notin B)$ iff
$x \in A \leftrightarrow x \notin B$

Thus $\forall x (x \in A \triangle B \leftrightarrow (x \in A \leftrightarrow x \notin B))$


Ex-19
($\rightarrow$)
Suppose $A \triangle B$ and C are disjoint.

Let x be an arbitrary element of $A \cap C$. It follows that $x \in A$ and $x \in C$. Since $A \triangle B$ and C are disjoint and $x \in C$, so $x \notin A \triangle B$. By definition of $A \triangle B$, either $x \notin A \cup B$ or $x \in A \cap B$. Since $x \in A$ so $x \notin A \cup B$ can not be true and hence $x \in A \cap B$. Thus $x \in B$. Since $x \in C$ and $x \in B$, so $x \in B \cap C$. Since x is arbitrary, we can conclude $A \cap C \subseteq B \cap C$

By exactly similar argument as above we can prove that $B \cap C \subseteq A \cap C$. Thus $A \cap C$ = $B \cap C$

($\leftarrow$)
Suppose $A \cap C$ = $B \cap C$. Let x be an arbitrary element of $A \triangle B$. By definition of $A \triangle B$, $x \in A \setminus B$ or $x \in B \setminus A$. We will prove by contradiction that $x \notin C$. Let us assume that $x \in C$. Now consider the two cases

Case1: $x \in A \setminus B$
It follows that $x \in A$ and $x \notin B$. Since $x \in C$ also, so $x \in A \cap C$. Since $A \cap C$ = $B \cap C$, so $x \in B \cap C$ and hence $x \in B$ but that contradicts our assumption for this case. Thus $x \notin C$

Case2: $x \in B \setminus A$
It follows that $x \in B$ and $x \notin A$. Since $x \in C$ also, so $x \in B \cap C$. Since $B \cap C$ = $A \cap C$, so $x \in A \cap C$ and hence $x \in A$ but that contradicts our assumption for this case. Thus $x \notin C$.

Since above cases are the exhaustive set, so $x \notin C$. Since x is arbitrary, we can conclude that $A \triangle B$ and C are disjoint.


Ex-20
($\rightarrow$)
Suppose $A \triangle B \subseteq C$. Let x be an arbitrary element of $A \cup C$. It follows that $x \in A$ or $x \in C$. Let us consider both the cases

Case1: $x \in A$
We'll prove by contradiction that $x \in B \cup C$. Assume $x \notin B \cup C$, therefore $x \notin B$ and $x \notin C$. Since $x \in A$ and $x \notin B$,
so $x \in A \setminus B$
=> $x \in A \triangle B$

Since $A \triangle B \subseteq C$
therefore $x \in C$, but this contradicts our assumption and hence $x \in B \cup C$.

Case2: $x \in C$
so definitely $x \in B \cup C$

Since x is arbitrary, we conclude that $A \cup C \subseteq B \cup C$

By using an exactly similar argument we can prove that $B \cup C \subseteq A \cup C$ also. Thus $A \cup C$ = $B \cup C$

($\leftarrow$)
Suppose $A \cup C$ = $B \cup C$. Let x be an arbitrary element of $A \triangle B$. Then, either $x \in A \setminus B$ or $x \in B \setminus A$. let us consider both the cases

Case1: $x \in A \setminus B$
Then $x \in A$ and $x \notin B$. Since $x \in A$, so $x \in A \cup C$ also. And since $A \cup C$ = $B \cup C$, so $x \in B \cup C$. Since $x \notin B$, so $x \in C$

Case2: $x \in B \setminus A$
Then $x \in B$ and $x \notin A$. Since $x \in B$, so $x \in B \cup C$ also. And since $B \cup C$ = $A \cup C$, so $x \in A \cup C$. Since $x \notin A$, so $x \in C$

From above cases, we can conclude that $x \in C$. Since x is arbitrary, so $A \triangle B \subseteq C$


Ex-21
($\rightarrow$)
Suppose $C \subseteq A \triangle B$.

Let x be an arbitrary element of C, then $x \in A \triangle B$. Thus $x \in A \cup B$ and $x \notin A \cap B$. So $x \in A \cup B$. Since x is arbitrary, so $C \subseteq A \cup B$

Let x be an arbitrary element of $x \in A \cap B \cap C$. Then $x \in A$ and $x \in B$ and $x \in C$. Since $C \subseteq A \triangle B$, so $x \in A \triangle B$ and then $x \in A \setminus B$ or $x \in B \setminus A$. Let us consider both the cases

Case1: $x \in A \setminus B$
Then $x \in A$ and $x \notin B$. But we already said that $x \in B$. This is a contradiction and such x can not exist

Case2: $x \in B \setminus A$
Then $x \in B$ and $x \notin A$. But we already said that $x \in A$. This is a contradiction and such x can not exist

Hence a x s.t. $x \in A \cap B \cap C$ can not exist and hence $A \cap B \cap C = \emptyset$

So if $C \subseteq A \triangle B$ then $C \subseteq A \cup B$ and $A \cap B \cap C = \emptyset$

($\leftarrow$)
Suppose $C \subseteq A \cup B$ and $A \cap B \cap C = \emptyset$. Let x be an arbitrary element of C. So $x \in A \cup B$ and hence $x \in A$ or $x \in B$. Let us consider both the cases

Case1: $x \in A$
Since $x \in C$ and $x \in A$, then $x \notin B$ as $A \cap B \cap C = \emptyset$. Since $x \in A$ and $x \notin B$, so $x \in A \setminus B$ and hence $x \in A \triangle B$. Since x is arbitrary, we can conclude that $C \subseteq A \triangle B$

Case2: $x \in B$
Since $x \in C$ and $x \in B$, then $x \notin A$ as $A \cap B \cap C = \emptyset$. Since $x \in B$ and $x \notin A$, so $x \in B \setminus A$ and hence $x \in A \triangle B$. Since x is arbitrary, we can conclude that $C \subseteq A \triangle B$


Ex-22
(a)
Let x be an arbitrary element of $A \setminus C$. Then $x \in A$ and $x \notin C$. Let us consider two cases

Case1: $x \in B$
Then $x \in B \setminus C$, so $x \in (A \setminus B) \cup (B \setminus C)$

Case2: $x \notin B$
Then $x \in A \setminus B$, so $x \in (A \setminus B) \cup (B \setminus C)$

From two cases above, its clear that $x \in (A \setminus B) \cup (B \setminus C)$. Since x is arbitrary, so $A \setminus C \subseteq (A \setminus B) \cup (B \setminus C)$

(b)
Let x be an arbitrary element of $A \triangle C$. Let us consider the two cases

Case1: $x \in B$
Since $x \in A \triangle C$, so $x \in A \setminus C$ or $x \in C \setminus A$. Let us consider these cases further
Case-a: $x \in A \setminus C$
Then $x \in A$ and $x \notin C$. Since $x \in B$ and $x \notin C$, so $x \in B \setminus C$ and hence $x \in B \triangle C$
Case-b: $x \in C \setminus A$
Then $x \in C$ and $x \notin A$. Since $x \in B$ and $x \notin A$, so $x \in B \setminus A$ and hence $x \in A \triangle B$

So $x \in (A \triangle B)$ or $x \in (B \triangle C)$. Thus $x \in (A \triangle B) \cup (B \triangle C)$

Case2: $x \notin B$
Since $x \in A \triangle C$, so $x \in A \setminus C$ or $x \in C \setminus A$. Let us consider these cases further
Case-a: $x \in A \setminus C$
Then $x \in A$ and $x \notin C$. Since $x \notin B$ and $x \in A$, so $x \in A \setminus B$ and hence $x \in A \triangle B$
Case-b: $x \in C \setminus A$
Then $x \in C$ and $x \notin A$. Since $x \notin B$ and $x \in C$, so $x \in C \setminus B$ and hence $x \in B \triangle C$

So $x \in (A \triangle B)$ or $x \in (B \triangle C)$. Thus $x \in (A \triangle B) \cup (B \triangle C)$

Since x is arbitrary, so $A \triangle C \subseteq (A \triangle B) \cup (B \triangle C)$


Ex-23
(a)
Let x be an arbitrary element of $(A \cup B) \triangle C$. It follows that either $x \in (A \cup B) \setminus C$ or $x \in C \setminus (A \cup B)$. Let us consider both the cases

Case1: $x \in (A \cup B) \setminus C$
Then $x \in (A \cup B)$ and $x \notin C$. So, either $x \in A \setminus C$ or $x \in B \setminus C$. Thus $x \in A \triangle C$ or $x \in B \triangle C$. Hence $x \in (A \triangle C) \cup (B \triangle C)$

Case2: $x \in C \setminus (A \cup B)$
Then $x \in C$ and $x \notin (A \cup B)$. Since $x \notin (A \cup B)$, so $x \notin A$ and $x \notin B$. Hence $x \in C \setminus A$ and $x \in C \setminus B$. And therefore $x \in (A \triangle C)$ and $x \in (B \triangle C)$. So $x \in (A \triangle C)$ or $x \in (B \triangle C)$ also. Thus $x \in (A \triangle C) \cup (B \triangle C)$

Since x is arbitrary, we can conclude that $(A \cup B) \triangle C \subseteq (A \triangle C) \cup (B \triangle C)$

(b)
A = {3}
B = {4}
C = {3,4}


Ex-24
(a)
Let x be an arbitrary element of $(A \triangle C) \cap (B \triangle C)$. So $x \in A \triangle C$ and $x \in B \triangle C$. $x \in A \triangle C$ means either $x \in A \setminus C$ or $x \in C \setminus A$. Similarly $x \in B \triangle C$ means $x \in B \setminus C$ or $x \in C \setminus B$. So following 4 cases are possible.

Case1: $x \in A \setminus C$ and $x \in B \setminus C$
Then $x \in A$ and $x \in B$ and $x \notin C$. Thus $x \in A \cap B$ and $x \notin C$. So $x \in (A \cap B) \setminus C$. Hence $x \in (A \cap B) \triangle C$

Case2: $x \in A \setminus C$ and $x \in C \setminus B$
This case is not possible as $x \in A \setminus C$ suggests that $x \notin C$ while $x \in C \setminus B$ suggests $x \in C$

Case3: $x \in C \setminus A$ and $x \in B \setminus C$
This case is also not possible for the same reason as above

Case4: $x \in C \setminus A$ and $x \in C \setminus B$
Then $x \in C$ and $x \notin A$ and $x \notin B$. Since $x \notin A$ and $x \notin B$, so $x \notin A \cup B$ and then $x \notin A \cap B$ also. Thus $x \in C \setminus (A \cap B)$. Hence $x \in (A \cap B) \triangle C$

From above cases, it is clear that $x \in (A \cap B) \triangle C$. Since x is arbitrary, so we can conclude that $(A \triangle C) \cap (B \triangle C) \subseteq (A \cap B) \triangle C$

(b)
Here is the counterexample
A = {3}
B = {4}
C = {3,4}

$(A \cap B) \triangle C$ = {3,4}
$(A \triangle C) \cap (B \triangle C)$ = $\emptyset$


Ex-25
$(A \setminus B) \triangle C$ is not a subset of $(A \triangle C) \setminus (B \triangle C)$ and here is the counterexample
A = {1}
B = {2}
C = {3}

$(A \setminus B) \triangle C$ = {1,3}
$(A \triangle C) \setminus (B \triangle C)$ = {1}

and $(A \triangle C) \setminus (B \triangle C) \subseteq (A \setminus B) \triangle C$, here is the proof
Let x be an arbitrary element of $(A \triangle C) \setminus (B \triangle C)$. It follows that $x \in A \triangle C$ and $x \notin B \triangle C$.
$x \in A \triangle C$ means $x \in A \setminus C$ or $x \in C \setminus A$
$x \notin B \triangle C$ means $x \notin B \cup C$ or $x \in B \cap C$

So there are 4 cases to consider

Case1: $x \in A \setminus C$ and $x \notin B \cup C$
It means $x \in A$ and $x \notin C$ and $x \notin B$. So $x \in (A \setminus B) \setminus C$, thus $x \in (A \setminus B) \triangle C$

Case2: $x \in A \setminus C$ and $x \in B \cap C$
This case is not possible as $x \in A \setminus C$ suggests that $x \notin C$ while $x \in B \cap C$ suggests $x \in C$

Case3: $x \in C \setminus A$ and $x \notin B \cup C$
This case is also not possible for the same reason as above

Case4: $x \in C \setminus A$ and $x \in B \cap C$
It means $x \in C$ and $x \notin A$ and $x \in B$. Since $x \notin A$, so $x \notin A\setminus B$ should also be true. Since $x \in C$ and $x \notin A \setminus B$, therefore $x \in C \setminus (A \setminus B)$. Thus $x \in (A \setminus B) \triangle C$

From above cases, its clear that $x \in (A \setminus B) \triangle C$. Since x is arbitrary, we can conclude that $(A \triangle C) \setminus (B \triangle C) \subseteq (A \setminus B) \triangle C$

Ex-26
The theorem given is correct. However the proof presented is not correct, as it actually proves that (x > 0) OR (x < 6) wherease what we want to prove is that (x > 0) AND (x < 6). It can be fixed as follows.
In Case1, the assumption is that (x - 3 $\geq$ 0), so (x $\geq$ 3). And its concluded that (x < 6). So, from this case, we can conclude that (x $\geq$ 3) AND (x < 6)
Similarly from Case2, we can conclude that (x > 0) AND (x < 3)

Now, we can conclude that (0 < x < 6) (TODO: justify it)


Ex-27
The theorem as well as the proof given is correct.

Strategies:
Initial theorem is in the form $P \land Q \rightarrow R$

So, First strategy is to suppose that P and Q are true. Then we use existential instantiation on P that is $\lnot (A \subseteq B)$. Later we get $x \notin A$ or $x \in B$, that is $x \in A \rightarrow x \in B$, since $x \in A$ is known already so $x \in B$ is established through that.


Ex-28
The theorem as well as the proof given are correct.

Notice that, even thought there is no explicit given of the form $P \lor Q$, but since x being real can be divided in to 2 exhaustive cases $x = 0$ and $x \neq 0$, therefore the strategy of taking cases is used


Ex-29
Suppose $\forall x P(x) \rightarrow \exists x Q(x)$
=> $\lnot (\forall x P(x)) \lor (\exists x Q(x))$
=> $(\exists x \lnot P(x)) \lor (\exists x Q(x))$
=> $\exists x (\lnot P(x) \lor Q(x))$
=> $\exists x (P(x) \rightarrow Q(x))$

Thus if $\forall x P(x) \rightarrow \exists x Q(x)$ then $\exists x (P(x) \rightarrow Q(x))$


Ex-30
The theorem is incorrect. Here is the counterexample, A = {1,2} ; B = {0,1}; C = {2,3}

The flaw is in both cases. For example Case1 means $x \in A$ and $x \in B$, not $x \in A \rightarrow x \in B$. Same is the problem with the other one. (convincing enough??)


Ex-31
Prove that $\exists x (P(x) \rightarrow \forall x P(x))$.
TODO, no idea how to prove this. Is the given statement even correct?