Sunday, May 16, 2010

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?

10 comments:

  1. Ex-8
    A shorter proof. Suppose P(A)∪P(B)=P(A∪B). Since A∪B ∈ P(A∪B), A∪B ∈ P(A)∪P(B). Then either A∪B ∈ P(A) or A∪B ∈ P(B). We will consider these cases separately.
    Case 1. A∪B ∈ P(A). Then A∪B ⊆ A, so B⊆A.
    Case 2. A∪B ∈ P(B). Then A∪B ⊆ B, so A⊆B.

    ReplyDelete
  2. Ex-31
    It is correct. http://en.wikipedia.org/wiki/Drinker_paradox

    ReplyDelete
  3. I think for Q26 :
    Suppose |x - 3| < 3 and x ∈ ℝ. There are 2 cases.

    1. x - 3 ≥ 0, hence x ≥ 3. Thus |x - 3|= x - 3. It follows that x < 6 from |x - 3| < 3. Thus if x ≥ 3 then x > 0 and x < 6.

    2. x - 3 < 0. Hence x < 3. And |x - 3| = 3 - x. It follows that x > 0 from |x - 3| < 3. Thus if x < 3 then x < 6 and x > 0.

    Since both cases conclude with 0 < x < 6, we can deduce that if |x -3| < 3 then 0 < x < 6.

    ReplyDelete
    Replies
    1. You're right. On re-reading my proof, I guess, I kept it too short for others to follow but it is essentially the same as yours with a lot of steps skipped. Thanks.

      Delete
  4. This comment has been removed by the author.

    ReplyDelete
  5. Thank you for doing this and posting. This is really a tremendous resource that gets me going when I get stumped, as we use this text in class. To show that I am motivated to think by reading your work rather than do just what you have done, I propose the following for Q8. It doesn't involve negation or arbitrary sets. Does it seem rigorous to you?

    PROOF: Suppose A and B are sets such that P(A) ∪ P(B) = P(A ∪ B).
    Case 1: A ⊆ B. Trivial.
    Case 2: A ⊈ B. Suppose X is an arbitrary element such that x ∈ A and x ∉ B. Suppose y is an arbitrary element such that y ∈ B and y ∉ A. By definition of union, {x,y} ∈ p(A ∪ B). Since P(A) ∪ p(B) = P(A ∪ B), {x,y} ⊆ P(A) or {x,y} is subset P(B). Since x ∉ B, {x,y} ⊆ P(A). This contradicts our assumption that y ∉ A. Then by contradiction, if y ∈ B then y ∈ A. By definition of subset, B ⊆ A. ▄

    ReplyDelete
  6. Ex-31 Can be proved as follows:
    Either P is a tautology or it is not.
    If P is a tautology, then the implication can not be false since left and right side of arrow will always be true, so the implication must be true.
    If P is not a tautology, then there exists an x for which P(x) is false. For this x the implication can not be false, since it is impossible for the right side of the arrow to be true while the left side is false. Hence, the implication is true in this case as well. Since the cases are exhaustive, the proof is complete.

    ReplyDelete
  7. Ex-31 Can be proved as follows:
    Either P is a tautology or it is not.
    If P is a tautology, then the implication can not be false since left and right side of arrow will always be true, so the implication must be true.
    If P is not a tautology, then there exists an x for which P(x) is false. For this x the implication can not be false, since it is impossible for the right side of the arrow to be true while the left side is false. Hence, the implication is true in this case as well. Since the cases are exhaustive, the proof is complete.

    ReplyDelete
  8. Could not figure out problem 8 by myself. I found your solution really clever. Thanks for posting these here.

    ReplyDelete
  9. It turns out there are a couple major mistakes in your solution to 3.5.17. To be specific, you took an arbitrary A in F and assumed that x is an element of A, then you used this assumption to wrongly conclude that for all A in F x is an element of A. This is a mistake. You've only proven that for all A in F, x is an element of A implies that x is an element of A. Obviously this is a tautology.
    Instead of breaking the problem into the two cases you chose (ie Case 1:x is an element of A and Case 2: x is an element of B), you should have chosen a different pair of cases. Namely. Case 1 would be that there is a set A in F such that x is not an element of A, and Case 2 would be that there is not a set A in F such that x is not an element of A.

    ReplyDelete