Friday, May 21, 2010

how to prove it - ch3, sec3.6(Existence and Uniqueness Proofs) ex

This section is about proving statements of the form of $\exists ! x P(x)$, which means there exists *only* one x s.t. P(x) is true. It starts out with describing that all of the following statements are equivalent.

$\exists ! x P(x)$
$\exists x (P(x) \land \forall y (P(y) \rightarrow y = x))$
$\exists x (P(x) \land \lnot \exists y (P(y) \land y \neq x))$
$\exists x \forall y (P(y) \leftrightarrow y = x)$
$\exists x P(x) \land \forall y \forall z (P(y) \land P(z) \rightarrow y = z)$

To Prove a goal of the form $\exists ! x P(x)$

Strategy#1:
Use $\exists x P(x) \land \forall y \forall z (P(y) \land P(z) \rightarrow y = z)$. That is prove two goals, $\exists x P(x)$ and $\forall y \forall z (P(y) \land P(z) \rightarrow y = z)$.
$\exists x P(x)$ proves that there exists such an x. It is labeled as existence proof.
$\forall y \forall z (P(y) \land P(z) \rightarrow y = z$ proves that such an x is unique. It is labeled as uniqueness proof.

So, form of the final proof looks like following.

Existence: [Proof of $\exists x P(x)$ goes here]
Uniqueness: [Proof of $\forall y \forall z (P(y) \land P(z) \rightarrow y = z$ goes here]

Strategy#2:
Use $\exists x (P(x) \land \forall y (P(y) \rightarrow y = x))$.

In general, however, we can use any of the formulas listed in the starting of this post.


To Use a given of the form $\exists ! x P(x)$
In general, again we can use any one of the statements listed but very usually $\exists x P(x) \land \forall y \forall z (P(y) \land P(z) \rightarrow y = z)$ is used. It means we can assume that $\exists x P(x)$ and $\forall y \forall z (P(y) \land P(z) \rightarrow y = z)$. $\exists x P(x)$ can probably be used by chosing an object named $x_0$ s.t. $P(x_0)$.


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

Ex-1
[Existence]
Let us try y = $\frac{x}{x^2 + 1}$, $x^2 + 1$ has got to be non-zero for any real x
$x^2y$
= $x^2 * \frac{x}{x^2 + 1}$
= $\frac{x^3}{x^2 + 1}$

$x - y$
= $x - \frac{x}{x^2 + 1}$
= $\frac{x^3 + x - x}{x^2 + 1}$
= $\frac{x^3}{x^2 + 1}$

clearly $x^2y = x - y$ for y = $\frac{x}{x^2 + 1}$

[Uniqueness]
To see that above solution is unique, suppose $x^2z = x - z$
Then, $x^2z + z = x$
=> $z(x^2 + 1) = x$
=> $z = \frac{x}{x^2 + 1} = y$


Ex-2 To see that it exists, try x = 4 and y be arbitrary real number.

LHS = xy + x - 4
= 4y + 4 - 4
= 4y = RHS

To prove it is unique, let say there exists another real number z s.t. (zy + z - 4 = 4y)
Then, z(y + 1) = 4y + 4
=> z = $\frac{4y + 4}{y + 1} = \frac{4(y + 1)}{(y + 1)}$
which is clearly not defined if y+1 = 0 else z = 4 = x.

Ex-3
To see that it exists, try y = $\frac{x^2}{x - 1}$ , its defined since $x - 1 \neq 0$

$\frac{y}{x}$
= $\frac{x^2}{x(x - 1)}$
= $\frac{x}{x - 1}$

y - x
= $\frac{x^2}{x - 1} - x$
= $\frac{x^2 - x^2 + x}{x - 1}$
= $\frac{x}{x - 1}$

clearly $\frac{y}{x} = y - x$

To see that its unique. Let say there exists another real number z s.t.$\frac{z}{x} = z - x$
=> $z = xz - x^2$
=> $xz - z = x^2$
=> z = $\frac{x^2}{x - 1}$ = y


Ex-4
To see that it exists, try y = $\frac{1}{x}$

For any real number z,

zy = $\frac{z}{x}$

To see that it is unique, Let say there exists another real number w s.t. for all real number z
$zw = \frac{z}{x}$
=> $z(w - \frac{1}{x}) = 0$

Since z can be any real number, so

$w - \frac{1}{x} = 0$
=> w = $\frac{1}{x}$ = y


Ex-5
(a) Let x be an arbitrary element of $\cup ! F$. Then there exists exactly one set A s.t. $A \in F$ and $x \in A$. So by definition of $\cup F$, x is an element of $\cup F$ also. Since x is arbitrary, we can conclude that $\cup ! F \subseteq \cup F$

(b)
($\rightarrow$)
Suppose $\cup ! F = \cup F$. Let A and B are two different arbitrary set in $F$. We'll prove by contradiction that A and B are disjoint. Let x be an element s.t. $x \in A$ and $x \in B$. By definition of $\cup F$, $x \in \cup F$. Since $\cup F = \cup ! F$, so $x \in \cup ! F$. It means there is only one set in $F$ to which x belongs. So either A = B or such an x can not exist. Since A and B are different, so x can not exist and hence A and B are disjoint. Since A and B are arbitrary, we can conclude that $F$ is pairwise disjoint.

($\leftarrow$)
Suppose $F$ is pairwise disjoint.

we've already proven in (a) that $\cup ! F \subseteq \cup F$

Now we'll prove that, for this case, $\cup F \subseteq \cup ! F$ also and that will establish $\cup ! F = \cup F$. Let x be an arbitrary element of $\cup F$. So there exists atleast one set A s.t. $A \in F$ and $x \in A$. Since $F$ is pairwise disjoint, so there can not exist another set in $F$ such that x belongs to it and hence there is only one set A s.t. $A \in F$ and $x \in A$. Thus $x \in \cup ! F$. Since x is arbitrary, we can conclude that $\cup F \subseteq \cup ! F$.
Hence $\cup ! F = \cup F$


Ex-6
(a) To prove the existence, try A = $\emptyset$ as $\emptyset \subset U$ and hence $\emptyset \in P(U)$. For any set $B \in P(U)$, $\emptyset \cup B = B$.
To prove the uniqueness, let say there exists another set $C \in P(U)$ s.t. $\forall B \in P(U) (C \cup B = B)$. We can put $B = \emptyset$ in this equation to get $C \cup \emptyset = \emptyset$ and hence C = $\emptyset$ = A.

(b) To prove the existence, try $A = U$. For any $B \in P(U)$, $B \subseteq U$ and so $U \cup B = U$.

To prove the uniqueness, let say there is another set $C \in P(U)$ s.t. $\forall B \in P(U) (C \cup B = C)$. We can put $B = U \setminus C$ in this equation to get $C \cup U \setminus C = C$, therefore $U = C$ and hence $C = U = A$


Ex-7
(a) To prove the existence, try A = $U$. For any $B \in P(U)$, $B \subseteq U$ and hence $U \cap B = B$
To prove the uniqueness, assume there is another set $C \in P(U)$ s.t. $\forall B \in P(U) (C \cap B = B)$. We can put B = $U$ in this equation, then $C \cap U = U$. Thus $C = U = A$

(b) To prove the existence, try A = $\emptyset$. For any set $B \in P(U)$, clearly $\emptyset \cap B = \emptyset$
To prove the uniqueness, assume there is another set $C \in P(U)$ s.t. $\forall B \in P(U) (C \cap B = C)$. We can put $B = \emptyset$ in this equation, then $C \cap \emptyset = C$. Hence $C = \emptyset = A$


Ex-8
(a) To prove the existence of such a set B for every set A, choose B = $U \setminus A$. Clearly for any set $C \in P(U)$
$C \cap B$ = $C \cap U \setminus A$ = all the elements that are in C and not in A = $C \setminus A$

To prove the uniquencess, assume there exists another set D for every set A s.t. $\forall C \in P(U) (C \setminus A = C \cap D)$. We can put C = $U$ in this equation, then $U \setminus A = U \cap D$ and therefore $D = U \setminus A = B$

(b)
To prove the existence of such a set B for every set A, choose B = $U \setminus A$. For any set $C \in P(U)$
$C \setminus (U \setminus A)$ = all elements that are in C and they're either not in $U$ or they are in A, since $U$ is the universe of discourse and there is nothing that is not in $U$. So it means, all elements that are in C and also in A = $C \cap A$

To prove the uniqueness, assume there exists another set D for every set A s.t. $\forall C \in P(U) (C \cap A = C \setminus D)$. We can put C = $U$ in this equation, then $U \cap A = U \setminus D$. So $A = U \setminus D$ and therefore $D = U \setminus A = B$


Ex-9
(a) Existence: Try X = $\emptyset$. For any set,
$A \triangle \emptyset$
= $A \setminus \emptyset \cup \emptyset \setminus A$
= $A \cup \emptyset$
= A

Uniqueness: Let say there exists another set B s.t. $\forall A (A \triangle B = A)$. We can put A = $\emptyset$ in this equation, Then
$\emptyset \triangle B = \emptyset$
=> $\emptyset \setminus B \cup B \setminus \emptyset = \emptyset$
=> $\emptyset \cup B = \emptyset$
=> $B = \emptyset = X$

(b) Here we want to prove, For every set A there exists a unique set B s.t. $A \triangle B = \emptyset$
Existence: Try B = A. Clearly $A \triangle A$
= $A \setminus A \cup A \setminus A$
= $\emptyset \cup \emptyset$
= $\emptyset$

Uniqueness: Let say, For every set A there exists another such set C. Then for a particular set A we can chose a particular set C s.t. $A \triangle C = \emptyset$
Then, $A \setminus C \cup C \setminus A = \emptyset$
=> clearly $A \setminus C = \emptyset$ and $C \setminus A = \emptyset$
=> $C = A = B$

(c) Existence: Try C = $A \triangle B$

$A \triangle C$
= $A \triangle (A \triangle B)$
= $(A \triangle A) \triangle B$
= $\emptyset \triangle B$
= B

Uniquenses: Let say there exists another such set D, Then
$A \triangle D = B$

For both sides, let us take their symmetric difference with A. Then

$A \triangle (A \triangle D) = A \triangle B$
=> $(A \triangle A) \triangle D = A \triangle B$
=> $\emptyset \triangle D = A \triangle B$
=> D = $A \triangle B$ = C

(d) Existence: Try B = A.
For any $C \subseteq A$,
$B \triangle C$
= $A \triangle C$
= $A \setminus C \cup C \setminus A$

Since $C \subseteq A$, therefore $C \setminus A = \emptyset$. So

$B \triangle C$
= $A \setminus C \cup C \setminus A$
= $A \setminus C \cup \emptyset$
= $A \setminus C$

Uniqueness: Let say there exists another such set D. Then
$\forall C (C \subseteq A \rightarrow D \triangle C = A \setminus C)$

we can chose C to be $\emptyset$, Then

$D \triangle \emptyset = A \setminus \emptyset$
=> $D = A = B$


Ex-10
Proof provided by Stavros Mekesis, original link: https://www.dropbox.com/s/fg8hes2nnwrm7ac/velleman.pdf

First we prove that $A \neq \emptyset$ and then we prove that A can not have more than 1 element and that establishes that A has only 1 element.

Proof for $A \neq \emptyset$:
We use proof by contradiction. Suppose $A = \emptyset$.
For $F = \emptyset$ in particular, $\cup F = \emptyset = A$ but clearly $A \notin \emptyset$. So $A \neq \emptyset$

Proof for A not having more than 1 element:
Again we use proof by contradiction. Suppose A has more than 1 elements. Consider an element $x \in A$ and $A \backslash {x} \neq \emptyset$ as A has more than 1 elements by assumption.
Now consider the particular family of sets $F$ = {{x},A\{x}}$
clearly, $\cup F = A$, but $A \notin F$. So A can not have more than 1 elements.


Ex-11
Existence: Try A = $\cup F$, such an A exists because its given that for any family of set $G \subseteq F$, $\cup G \in F$ so clearly $\cup F$ should also be in $F$.
For any set $B \in F$, clearly $B \in \cup F$

Uniqueness: Let say there exists another set $C \in F$ s.t. $\forall B \in F (B \subseteq C)$. We can chose B = $\cup F$, then $\cup F \subseteq C$. So C = $\cup F$ = A


Ex-12
(a) $\exists x (P(x) \land \exists y (P(y) \land (y \neq x) \land \forall z (P(z) \rightarrow (z = x \lor z = y))))$

(b) Strategy would be to first find two values x and y s.t. $x \neq y$ and P(x) and P(y). Next, one needs to prove that $\forall z (P(z) \rightarrow (z = x \lor z = y))$

(c) First we need to find two such values, clearly for x = 0 and for x = 1, $x^3 = x^2$. Now let us say there is another value z s.t. $z^3 = z^2$.
Then $z^3 = z^2$
=> $z^3 - z^2 = 0$
=> $z^2(z - 1) = 0$
=> either z = 0 or (z - 1) = 0
=> either z = 0 or z = 1

9 comments:

  1. Ex-10
    https://www.dropbox.com/s/fg8hes2nnwrm7ac/velleman.pdf

    ReplyDelete
    Replies
    1. Uniqueness part of the proof looks OK.
      However, in the existence part it only seems to prove that A is not empty-set but not that A necessarily exists, am i missing something?

      Delete
    2. My proof is fine. In the existence part I proved that A has at least one element.

      Delete
    3. Hmmm.. I guess, the problem can be rephrased, that if there is a set A s.t. for-all F (UF = A -> A belongs-to F), then A has only one element. I will update the post with your proof.

      Delete
  2. Ex-2
    Your solution is wrong. Let x = 4.

    ReplyDelete
  3. Your proof for 10 doesn't say anything. There is no conclusion. You can't assume the conditional without proving the first portion

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

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

    ReplyDelete