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

This section is about proving statements of the form of $\exists !xP\left(x\right)$, 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 !xP\left(x\right)$
$\exists x\left(P\right(x)\wedge \forall y(P\left(y\right)\to y=x\left)\right)$
$\exists x\left(P\right(x)\wedge \neg \exists y(P\left(y\right)\wedge y\ne x\left)\right)$
$\exists x\forall y\left(P\right(y)\leftrightarrow y=x)$
$\exists xP\left(x\right)\wedge \forall y\forall z\left(P\right(y)\wedge P(z)\to y=z)$

To Prove a goal of the form $\exists !xP\left(x\right)$

Strategy#1:
Use $\exists xP\left(x\right)\wedge \forall y\forall z\left(P\right(y)\wedge P(z)\to y=z)$. That is prove two goals, $\exists xP\left(x\right)$ and $\forall y\forall z\left(P\right(y)\wedge P(z)\to y=z)$.
$\exists xP\left(x\right)$ proves that there exists such an x. It is labeled as existence proof.
$\forall y\forall z\left(P\right(y)\wedge P(z)\to 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 xP\left(x\right)$ goes here]
Uniqueness: [Proof of $\forall y\forall z\left(P\right(y)\wedge P(z)\to y=z$ goes here]

Strategy#2:
Use $\exists x\left(P\right(x)\wedge \forall y(P\left(y\right)\to y=x\left)\right)$.

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 !xP\left(x\right)$
In general, again we can use any one of the statements listed but very usually $\exists xP\left(x\right)\wedge \forall y\forall z\left(P\right(y)\wedge P(z)\to y=z)$ is used. It means we can assume that $\exists xP\left(x\right)$ and $\forall y\forall z\left(P\right(y)\wedge P(z)\to y=z)$. $\exists xP\left(x\right)$ can probably be used by chosing an object named $x_0$ s.t. $P\left(x_0\right)$.


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

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^{2}y$
= $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^{2}y=x-y$ for y = $\frac{x}{x^2+1}$

[Uniqueness]
To see that above solution is unique, suppose $x^{2}z=x-z$
Then, $x^{2}z+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\ne 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)
($\to$)
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 = $\varnothing$ as $\varnothing \subset U$ and hence $\varnothing \in P\left(U\right)$. For any set $B\in P\left(U\right)$, $\varnothing \cup B=B$.
To prove the uniqueness, let say there exists another set $C\in P\left(U\right)$ s.t. $\forall B\in P\left(U\right)(C\cup B=B)$. We can put $B=\varnothing$ in this equation to get $C\cup \varnothing =\varnothing$ and hence C = $\varnothing$ = A.

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

To prove the uniqueness, let say there is another set $C\in P\left(U\right)$ s.t. $\forall B\in P\left(U\right)(C\cup B=C)$. We can put $B=U\backslash C$ in this equation to get $C\cup U\backslash 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\left(U\right)$, $B\subseteq U$ and hence $U\cap B=B$
To prove the uniqueness, assume there is another set $C\in P\left(U\right)$ s.t. $\forall B\in P\left(U\right)(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 = $\varnothing$. For any set $B\in P\left(U\right)$, clearly $\varnothing \cap B=\varnothing$
To prove the uniqueness, assume there is another set $C\in P\left(U\right)$ s.t. $\forall B\in P\left(U\right)(C\cap B=C)$. We can put $B=\varnothing$ in this equation, then $C\cap \varnothing =C$. Hence $C=\varnothing =A$


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

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

(b)
To prove the existence of such a set B for every set A, choose B = $U\backslash A$. For any set $C\in P\left(U\right)$
$C\backslash (U\backslash 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\left(U\right)(C\cap A=C\backslash D)$. We can put C = $U$ in this equation, then $U\cap A=U\backslash D$. So $A=U\backslash D$ and therefore $D=U\backslash A=B$


Ex-9
(a) Existence: Try X = $\varnothing$. For any set,
$A△\varnothing$
= $A\backslash \varnothing \cup \varnothing \backslash A$
= $A\cup \varnothing$
= A

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

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

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△C=\varnothing$
Then, $A\backslash C\cup C\backslash A=\varnothing$
=> clearly $A\backslash C=\varnothing$ and $C\backslash A=\varnothing$
=> $C=A=B$

(c) Existence: Try C = $A△B$

$A△C$
= $A△(A△B)$
= $(A△A)△B$
= $\varnothing △B$
= B

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

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

$A△(A△D)=A△B$
=> $(A△A)△D=A△B$
=> $\varnothing △D=A△B$
=> D = $A△B$ = C

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

Since $C\subseteq A$, therefore $C\backslash A=\varnothing$. So

$B△C$
= $A\backslash C\cup C\backslash A$
= $A\backslash C\cup \varnothing$
= $A\backslash C$

Uniqueness: Let say there exists another such set D. Then
$\forall C(C\subseteq A\to D△C=A\backslash C)$

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

$D△\varnothing =A\backslash \varnothing$
=> $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\ne \varnothing$ 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\ne \varnothing$:
We use proof by contradiction. Suppose $A=\varnothing$.
For $F=\varnothing$ in particular, $\cup F=\varnothing =A$ but clearly $A\notin \varnothing$. So $A\ne \varnothing$

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\setminus x\ne \varnothing$ 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\left(P\right(x)\wedge \exists y(P\left(y\right)\wedge (y\ne x)\wedge \forall z\left(P\right(z)\to (z=x\vee z=y\left)\right)\left)\right)$

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

(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