Sunday, May 23, 2010

how to prove it - ch3, sec3.7(More Proofs) ex

Ex-1 Existence: Try A = $\cup F$

Let x be an arbitrary element of $F$. It follows that $x \subseteq \cup F$, and hence $x \in P(\cup F)$. Since x is arbitrary, so $F \subseteq P(\cup F)$. clearly $A = \cup F$, satisfies the property that $F \subseteq P(A)$

Now let us see if $\forall B (F \subseteq P(B) \rightarrow A \subseteq B)$.
Let B be an arbitrary set s.t. $F \subseteq P(B)$. Suppose x is an arbitrary element of $\cup F$, then there exists a set $D \in F$ s.t. $x \in D$. Since $F \subseteq P(B)$, so $D \in P(B)$ also. Thus $D \subseteq B$, hence $x \in B$ also. Since x is arbitrary, therefore $\cup F \subseteq B$, clearly $A = \cup F$, satisfies the property that $\forall B (F \subseteq P(B) \rightarrow A \subseteq B)$

Uniqueness: Let there exists another such set D. Then $F \subseteq P(D)$ and $\forall B (F \subseteq P(B) \rightarrow D \subseteq B)$. We can chose B = $\cup F$. Since $F \subseteq P(\cup F)$, so $D \subseteq \cup F$. Since $F \subseteq P(D)$ and $D \subseteq \cup F$, it follows that $D = \cup F = A$


Ex-2 Let x be arbitrary s.t.
$x \in P(A \setminus B) \setminus (P(A) \setminus P(B))$ iff
$x \in P(A \setminus B) \land \lnot x \in (P(A) \setminus P(B))$ iff
$x \in P(A \setminus B) \land \lnot (x \in P(A) \land \lnot x \in P(B))$ iff
$x \in P(A \setminus B) \land (x \notin P(A) \lor x \in P(B))$ iff
$x \subseteq (A \setminus B) \land (\lnot x \subseteq A \lor x \subseteq B)$

clearly $x \subseteq (A \setminus B)$ and either $\lnot x \subseteq A$ or $x \subseteq B$. Since $x \subseteq (A \setminus B)$, so $x \subseteq A$ and $\lnot x \subseteq B$. Clearly there is only one such x possible and that is $\emptyset$.

Hence $P(A \setminus B) \setminus (P(A) \setminus P(B))$ = {$\emptyset$}


Ex-3 We will prove that (a) $\rightarrow$ (b) $\rightarrow$ (c) $\rightarrow$ (a)

Proof for (a) $\rightarrow$ (b):
Suppose $(A \triangle C) \cap (B \triangle C)$ = $\emptyset$. Let x be an arbitrary element of $A \cap B$. We will prove by contradiction that $x \in C$. Assume $x \notin C$, Then $x \in (A \setminus C)$ and hence $x \in (A \triangle C)$. By similar argument $x \in (B \triangle C)$, so $x \in (A \triangle C) \cap (B \triangle C)$. This is a contradiction and hence $x \in C$. Since x is arbitrary, we can conclude that $A \cap B \subseteq C$.
Now, let x be an arbitrary element of C. Again we will prove by contradiction that $x \in A \cup B$. Assume $x \notin A \cup B$, then $x \notin A$ and $x \notin B$. Clearly $x \in (C \setminus A)$, so $x \in (A \triangle C)$. By similar argument $x \in (B \triangle C)$. So $x \in (A \triangle C) \cap (B \triangle C)$, which is a contradiction and hence $x \in A \cup B$. Since x is arbitrary, we can conclude that $A \cap B \subseteq C \subseteq A \cup B$

Proof for (b) $\rightarrow (c):
Suppose $A \cap B \subseteq C \subseteq A \cup B$. Let x be an arbitrary element of $A \triangle C$. So either $x \in A \setminus C$ or $x \in C \setminus A$. Let us consider both the cases

Case#1: $x \in A \setminus C$
Then $x \in A$ and $x \notin C$. Since $A \cap B \subseteq C$, so $x \notin B$. Thus $x \in A \setminus B$, therefore $x \in A \triangle B$

Case#2: $x \in C \setminus A$
Thus $x \in C$ and $x \notin A$. Since $C \subseteq A \cup B$, so $x \in B$. Thus $x \in B \setminus A$, therefore $x \in A \triangle B$

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

Proof for (c) $\rightarrow (a):
Suppose $A \triangle C \subseteq A \triangle B$. 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)$. Since $x \in (A \triangle C)$, it follows that either $x \in A \setminus C$ or $x \in C \setminus A$. Let us consider both the cases

Case#1: $x \in A \setminus C$
Then $x \in A$ and $x \notin C$. Since $x \in (A \triangle C)$, therefore $x \in (A \triangle B)$. Since $x \in (A \triangle B)$ and $x \in A$, so $x \notin B$. It means $x \notin B$ and $x \notin C$, hence $x \notin (B \triangle C)$ and this is a contradiction, so this case is not possible.

Case#2: $x \in C \setminus A$
Then $x \in C$ and $x \notin A$. Since $x \in (A \triangle C)$, therefore $x \in (A \triangle B)$. Since $x \notin A$ and $x \in (A \triangle B)$, so $x \in B$. Since $x \in B$ and $x \in C$, so $x \notin (B \triangle C)$ and this is a contradiction, so this case is not possible.

Since none of the above cases are possible, it means such an x can not exist. Hence $(A \triangle C) \cap (B \triangle C)$ = $\emptyset$


Ex-4
given: $P(\cup_{i \in I}A_i) \subseteq \cup_{i \in I}P(A_i)$
goal: $\exists i \in I (\forall j \in I (A_j \subseteq A_i))$

Let us analyze the goal a little bit. Let us say for a particular $k \in I$, for all $j \in I$, $A_j \subseteq A_k$. Then clearly, $(\cup i \in I A_i) \subseteq A_k$

Formal Proof:
Suppose $P(\cup_{i \in I}A_i) \subseteq \cup_{i \in I}P(A_i)$. Let x be arbitrary element of $P(\cup_{i \in I}A_i)$, Then
$x \in P(\cup_{i \in I}A_i) \rightarrow x \in \cup_{i \in I}P(A_i)$ iff
$x \subseteq (\cup_{i \in I}A_i) \rightarrow \exists i \in I (x \in P(A_i))$ iff

Let us chose a particular $k \in I$ for the conclusion in the above statement. Then

$x \subseteq (\cup_{i \in I}A_i) \rightarrow (x \in P(A_k))$ iff
$x \subseteq (\cup_{i \in I}A_i) \rightarrow x \subseteq A_k$

Thus $(\cup i \in I A_i) \subseteq A_k$.

Ex-5
(a) Let x be an arbitrary element s.t.
$x \in \cup_{X \in F}(\cup_{i \in X}A_i)$ iff
$\exists X \in F (x \in \cup_{i \in X}A_i)$ iff
$\exists X \in F (\exists i \in X x \in A_i)$ iff
$\exists X [X \in F \land \exists i (i \in X \land x \in A_i)$ iff
$\exists X \exists i (X \in F \land i \in X \land x \in A_i)$ iff
$\exists i \exists X (X \in F \land i \in X \land x \in A_i)$ iff
$\exists i (\exists X (X \in F \land i \in X)) \land x \in A_i$ iff
$\exists i (i \in \cup F) \land x \in A_i$ iff
$\exists i (i \in I) \land x \in A_i$ iff
$x \in \cup_{i \in I}A_i$

Therefore $\cup_{i \in I}A_i$ = $\cup_{X \in F}(\cup_{i \in X}A_i)$

(b) Let x be an arbitrary element s.t.
$x \in \cap_{X \in F}(\cap_{i \in X}A_i)$ iff
$\forall X [X \in F \rightarrow (x \in \cap_{i \in X}A_i)]$ iff
$\forall X [X \in F \rightarrow (\forall i (i \in X \rightarrow x \in A_i))]$ iff
$\forall X \forall i [X \in F \rightarrow (i \in X \rightarrow x \in A_i)]$ iff
$\forall i \forall X [X \in F \rightarrow (i \in X \rightarrow x \in A_i)]$ iff
$\forall i ([\forall X (X \in F \rightarrow i \in X)] \rightarrow x \in A_i)$ iff
$\forall i (i \in \cap F \rightarrow x \in A_i)$ iff
$\forall i \in J (x \in A_i)$ iff
$x \in \cap_{i \in J}A_i$

Therefore $\cap_{i \in J}A_i$ = $\cap_{X \in F}(\cap_{i \in X}A_i)$

(c) Suppose x be an arbitrary element of $\cup_{i \in J}A_i$. It follows that there is a particular $k \in J$ s.t. $x \in A_k$. Since J = $\cap F$, so for any arbitrary $X \in F$, $k \in X$. Since $k \in X$ and $x \in A_k$, so $x \in \cup_{i \in X}A_i$. Since X is arbitrary, so $x \in \cap_{X \in F}(\cup_{i \in X}A_i)$. Since x is arbitrary, we can conclude that $\cup_{i \in J}A_i \subseteq \cap_{X \in F}(\cup_{i \in X}A_i)$

Now, let x be an arbitrary element of $\cap_{X \in F}(\cup_{i \in X}A_i)$. Let X be an arbitrary element of $F$. Then $x \in \cup_{i \in X}A_i$, it follows there exists a particular $k \in X$ s.t. $x \in A_k$. Since $k \in X$ and X is arbitrary element of $F$, so $k \in \cap F$. Since J = $\cap F$, so $k \in J$. Since $k \in J$ and $x \in A_k$, therefore $x \in \cup_{i \in J}A_i$. Since x is arbitrary, we can conclude that $\cap_{X \in F}(\cup_{i \in X}A_i) \subseteq \cup_{i \in J}A_i$

Hence, $\cup_{i \in J}A_i$ = $\cap_{X \in F}(\cup_{i \in X}A_i)$

(d) We will prove that $\cap_{i \in J}A_i \subseteq \cup_{X \in F}(\cap_{i \in X}A_i)$.

Suppose x is an arbitrary element of $\cap_{i \in J}A_i$. So for any arbitrary $i \in \cap F$, $x \in A_i$. Since $i \in \cap F$, so for any arbitrary $X \in F$, $i \in X$. Since $i \in X$ and $x \in A_i$, therefore $x \in \cap_{i \in X}A_i$. Since X is arbitrary, so $x \in \cap_{X \in F}(\cap_{i \in X}A_i)$, hence clearly $x \in \cup_{X \in F}(\cap_{i \in X}A_i)$. Since x is arbitrary, therefore $\cap_{i \in J}A_i \subseteq \cup_{X \in F}(\cap_{i \in X}A_i)$

However, $\lnot [\cup_{X \in F}(\cap_{i \in X}A_i) \subseteq \cap_{i \in J}A_i]$. Here is the counter example

$F$ = { {1}, {2} }
$A_1$ = {2}
$A_2$ = {3}
J = $\cap F$ = $\emptyset$

$\cup_{X \in F}(\cap_{i \in X}A_i)$ = {2,3}
$\cap_{i \in J}A_i$ = $\emptyset$


Ex-6 Analysis:
We need to prove that $\forall \epsilon > 0 \exists \delta > 0 \forall x (0 < |x-2| < \delta \rightarrow |\frac{3x^2 - 12}{x-2} - 12| < \epsilon)$

Given arbitrary $\epsilon > 0$, we want to find out a $\delta > 0$ s.t.
$0 < |x-2| < \delta \rightarrow |\frac{3x^2 - 12}{x-2} - 12| < \epsilon$

Let us solve for, $|\frac{3x^2 - 12}{x-2} - 12| < \epsilon$
=> $|\frac{3x^2 - 12 -12 x + 24}{x-2}| < \epsilon$
=> $|\frac{3(x-2)^2}{x-2}| < \epsilon$

Since $|x-2| > 0$, so $(x - 2) \neq 0$, so

=> $|3(x-2)| < \epsilon$
=> $|x - 2| < \frac{\epsilon}{3}$

So, $\delta = \frac{\epsilon}{3}$ satisfies the condition.

Formal Proof:
Suppose $\epsilon$ is an arbitrary positive real number and $\delta = \frac{\epsilon}{3}$. Suppose $0 < |x-2| < \delta$.

So, $|\frac{3x^2 - 12}{x-2} - 12|$
= $|\frac{3(x-2)^2}{x-2}|$
= $|3(x-2)|$ (Since $|x-2| > 0$, so $(x-2) \neq 0$)
< $3 \delta$ = $3 \frac{\epsilon}{3}$ = $\epsilon$

clearly, $\forall \epsilon > 0 \exists \delta > 0 \forall x (0 < |x-2| < \delta \rightarrow |\frac{3x^2 - 12}{x-2} - 12| < \epsilon)$.


Ex-7
Suppose $\lim_{x \to c}f(x) = L$. It follows that for every $\epsilon > 0$ there exists $\delta > 0$ s.t. if $0 < |x-c| < \delta$ then $|f(x) - L| < \epsilon$. We can chose $\epsilon = L$ because $L > 0$. Thus If $0 < |x-c| < \delta$ then $|f(x) - L| < L$. For the two cases where

Case#1: |f(x)-L| = f(x) - L
Then, f(x)-L > 0, so f(x) > L, and so f(x) > 0

Case#2: |f(x)-L| = L - f(x)
So, $L - f(x) < L$
Then, f(x) > 0

Thus, There exists $\delta > 0$ s.t. If $0 < |x-c| < \delta$ then f(x) > 0


Ex-8 Suppose $\lim_{x \to c}f(x) = L$.
Let $\epsilon$ be an arbitrary positive number. It follows that $\frac{\epsilon}{7}$ is also a positive number. So there exists $\delta > 0$ s.t. If $0 < |x-c| < \delta$ then $|f(x)-L| < \frac{\epsilon}{7}$. So clearly, for the same $\delta$, If $0 < |x-c| < \delta$ then $|7f(x) - 7L| < \epsilon$. Hence $\lim_{x \to c}7f(x) = 7L$


Ex-9
The proof and theorem, both are correct.

Strategies Used:

Since goal is of the form of "there exist irrantional numbers a and b s.t. ...", so we start with thinking about finding such particular values for a and b. Since, its already known that $\sqrt{2}$, so author applies the nice trick to come up with a implicit given that either $\sqrt{2}^\sqrt{2}$ is rational or irrational and then applies the cases.

1 comment:

  1. I think your answer to 3.7.5.d is incorrect. Let F = {{1,2},{1,3}} and A_1 = {1}, A_2 = {2} and A_3 = {3}. This comes out to {1} ⊆ ∅.

    ReplyDelete