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