How to Prove It - Solutions

Summary

• $\exists ! x P(x)$ means there exists only one value of $x$ for which $P (x)$ is true.
• $\exists ! x P(x)$ is equivalent to all of the following:
  • $\exists x (P(x) \land \forall y(P(y) \to y = x))$.
  • $\exists x \forall y(P(y) \leftrightarrow y = x)$.
  • $\exists x P(x) \land \forall y \forall z((P(y) \land P(z)) \to y = z)$.
• To prove a goal of the form of $\exists ! x P(x)$:
  • Strategy 1: Prove $\exists x P(x)$ and $\forall y \forall z((P(y) \land P(z)) \to y = z)$. The first of these goals shows that there exists an $x$ such that P(x) is true, and the second shows that it is unique. The two parts of the proof are therefore sometimes labeled existence and uniqueness.
  • Strategy 2: Prove $\exists x(P(x) \land \forall y(P(y) \to y = x))$, using strategies from previous sections.
• To use a given of the form of $\exists ! x P(x)$:
  Consider it as two given statements, $\exists x P(x)$ and $\forall y \forall z((P(y) \land P(z)) \to y = z)$. To use the first statement you should probably choose a name, say $x_0$, to stand for some object such that $P(x_0)$ is true. The second tells you that if you ever come across two objects $y$ and $z$ such that $P(y)$ and $P(z)$ are both true, you can conclude that $y = z$.

Soln1

Suppose $x$ is arbitrary. Lets say $P(y) = x^2y = x - y$. Thus we have to prove $\exists ! y P(y)$:

Existence:

Suppose $y = \frac x {1 + x^2}$. Then $x^2y = \frac {x^3} {1 + x^2}$. Also $x - y = \frac {x^3} {1 + x^2}$. Thus we have $x^2y = x - y$. Since $x$ is arbitrary, we can say that for all values of $x$, there exists a $y = \frac x {1 + x^2}$ such that $x^2y = x - y$. Thus we can conclude $\exists y P(y)$.

Uniqueness:

Suppose $P(z_1)$, then $x^2z_1 = x - z_1$, which give $z_1 = \frac x {1 + x^2}$. Similarly suppose $P(z_2)$, gives $z_2 = \frac x {1 + x^2}$. Thus $z_1 = z_2$. Thus we can conclude that $\forall y \forall z((P(y) \land P(z)) \to y = z)$ $$.

Thus we can say $\exists y P(y) \land \forall y \forall z((P(y) \land P(z)) \to y = z)$. Thus we can conclude $\exists ! y P(y)$. Since $x$ is arbitrary, we can conclude that for every value of $x$, $\exists ! y P(y)$ is true.

Soln2

Update(20th-May-2018)

Earlier solution was incorrect as pointed out by William. Here is the fixed version:

Suppose $P(x) = xy + x - 4 = 4y$. Then we have to prove $\exists ! x \forall y P(x)$.

Existence:

There are two possible cases:

• Case 1: Suppose $y = -1$. Suppose $x = 0$. Then $xy + x - 4 = -4$, and $4y = -4$. Thus LHS = RHS, or $xy + x - 4 = 4y$.

• Case 2: Suppose $y \ne -1$. Suppose $x = 4$. Then $xy + x - 4 = 4y$. Thus LHS = RHS, or $xy + x - 4 = 4y$.

Thus from both cases we have for any arbitrary $y$, $\exists x P(x)$ is true.

Uniqueness:

Suppose for a value z $P(z)$, then $P(z) = zy + z -4 = 4y$, or $z = \frac {4(y+1)} {y+1}$. Also suppose for a value $x$, $P(x)$.

For $\, P(z) \,$, We have two possible cases:

• Case 1: $y = -1$. Then we have $-z + z - 4 = -4$, which says that for any value of $z$, $P(z)$ is true.

• Case 2: $y \ne 1$. Then we have $z = \frac {4(y+1)} {y+1}$, or $z = 4$.

Thus, case-1 and case-2 together, for every value of $\, y \,$, $\, P(z) \,$ is true when $\, z = 4 \,$ .

Similarly, we can see that, for $\, P(x) \,$, when $\, x = 4 \,$, $\, P(x) \,$ is true.

Thus we have, for any arbitrary $\, y \,$, $\forall x \forall z((P(x) \land P(z)) \to x = z)$.

It follows that $\exists ! x \forall y P(x)$ is true.

Earlier Solution(with mistakes)

Suppose $P(x) = xy + x - 4 = 4y$. Then we have to prove $\forall y \exists ! x P(x)$.

Existence:

There are two possible cases:

• Case 1: Suppose $y = -1$. Suppose $x = 0$. Then $xy + x - 4 = -4$, and $4y = -4$. Thus LHS = RHS, or $xy + x - 4 = 4y$.

• Case 2: Suppose $y \ne -1$. Suppose $x = 4$. Then $xy + x - 4 = 4y$. Thus LHS = RHS, or $xy + x - 4 = 4y$.

Thus from both cases we have for any arbitrary $y$, $\exists x P(x)$ is true.

Uniqueness:

Suppose for a value z $P(z)$, then $P(z) = zy + z -4 = 4y$, or $z = \frac {4(y+1)} {y+1}$. Also suppose for a value $x$, $P(x)$. We have two possible cases:

• Case 1: $y = -1$. Then we have $-z + z - 4 = -4$, which says that for any value of $z$, $P(z)$ is true. Similarly, it can be shown that for $P(x)$ is true for any value of $x$.

• Case 2: $y \ne 1$. Then we have $z = \frac {4(y+1)} {y+1}$, or $z = 4$. Similarly it can be proved that, if $P(x)$, then $x = 4$. Or we can say that $\forall x \forall z((P(x) \land P(z)) \to x = z)$.

Thus from both cases, if $y \ne 1$, then $\forall y \exists ! x P(x)$ is true.

Soln3

Suppose $x$ is arbitrary. Suppose $P(y) = \frac y x = y - x$.

Existence:

Suppose $y = \frac {x^2} {x - 1}$. Thus $\frac y x = \frac {x^2} {x - 1} \times \frac 1 x$. Since $x \ne 0$, we get $\frac x {x - 1}$. Also $y - x = \frac {x^2} {x - 1} - x = \frac x {x-1}$. Thus $\frac y x = y - x$. It follows that $\exists y P(y)$.

Uniqueness:

Suppose $P(z) \land P(y)$ for values $z$ and $y$ respectively. Since $P(z)$, then $\frac z x = z - x$. Since $x \ne 0 \land x \ne 1$, it can be simplified to $z = \frac {x^2} {x - 1}$.
Similarly, since $P(y)$, we can get $y = \frac {x^2} {x - 1}$.

Thus we have $y = z = \frac {x^2} {x - 1}$. It follows that $\forall y \forall z((P(y) \land P(z)) \to y = z)$.

Thus we can conclude that for all $x$, $\exists ! y P(y)$.

Soln4

Existence:

Suppose $x \ne 0$, then $\frac 1 x$ is defined. Suppose $y = \frac 1 x$. Suppose $z$ is arbitrary, then $zy = z \times \frac 1 x = \frac z x$. Thus there exists a $y = \frac 1 x$ such that for all $x \ne 0$ and for all $z$, we have $zy = \frac z x$.

Uniqueness:

Suppose $y_1$, such that $zy_1 = \frac z x$. Multiplying each side by $\frac 1 z$, we get $y_1 = \frac 1 x$. Thus $y_1 = y = \frac 1 x$. Thus we can say that $y = \frac 1 x$ is a unique value of $y$ for the given statement is to be correct.

Soln5

(a)

Suppose $x \in \cup ! \mathcal F$. Then there exists a set $A \in \mathcal F$ such that $x \in \mathcal F$. Thus we can also say that $x \in \cup \mathcal F$. Since $x$ is arbitrary, it follows that $\cup ! \mathcal F \subseteq \cup \mathcal F$.

(b)

($\cup ! \mathcal F \subseteq \cup \mathcal F$)

This is already proved in first part.

($\cup \mathcal F \subseteq \cup ! \mathcal F$)

Suppose $x \in \cup \mathcal F$. Thus there atleast exists one set, say $A$, in $\mathcal F$ such that $x \in A$. Now suppose there is one more set, say $B$, such that $B \in \mathcal F$ and $x \in B$. Since $x \in A \land x \in B$, it follows that $A \cap B \ne \phi$. But it contradicts with the given that all sets of $\mathcal F$ are disjoint. Thus $A = B$. Or we can say that only one set exists such that $x \in A \land A \in \mathcal F$. It follows that $x \in \cup ! \mathcal F$. Now since $x$ is arbitrary, it follows $\cup \mathcal F \subseteq \cup ! \mathcal F$.

Thus from both directions, we can say that $\cup \mathcal F = \cup ! \mathcal F$.

Soln6

(a)

Existence:
Suppose $A = \phi$. Clearly $\phi \in \mathcal P(U)$. Also $\phi \cup B = B$. Thus there exist a set, $A = \phi \in \mathcal P(U)$ such that for every set $B \in \mathcal P(U)$, $A \cup B = B$.

Uniqueness:
Suppose there is another set say, $A' \in \mathcal P(U) \land A' \cup B = B$. Now for $B = \phi$, $A' \cup \phi = \phi$. Thus we can say that $A' = A$. Thus $A$ is unique set such that $A \in \mathcal P(U) \land A \cup B = B$.

(b)

Existence:
Suppose $A = U$. Clearly $U \in \mathcal P(U)$. Also $U \cup B = U$. Thus there exist a set, $A = U \in \mathcal P(U)$ such that for every set $B \in \mathcal P(U)$, we have $A \cup B = A$.

Uniqueness:
Suppose there is another set say, $A' \in \mathcal P(U) \land A' \cup B = A'$. Now for $B = U$, $A' \cup U = A'$. Since $A' \in \mathcal P(U)$, it follows $A' \subseteq U$. Thus it follows that $A' \cup U = U$. Since $A' \cup U = A'$, it follows that $A' = U$, or $A' = A = U$. Thus $A$ is unique set such that $A \in \mathcal P(U) \land A \cup B = A$.

Soln7

(a)

Existence:
Suppose $B$ is arbitrary and $B \in \mathcal P(U)$, or $B \subseteq U$. Suppose $A = U$. Clearly $U \in \mathcal P(U)$. Also since $B \subseteq U$, it follows that $U \cap B = B$. Thus there exist a set, $A = U \in \mathcal P(U)$ such that for every set $B \in \mathcal P(U)$, and $A \cap B = B$.

Uniqueness:
Suppose $A' \in \mathcal P(U)$ such that $A' \cap B = B$. Now for $B = U$, we have $A' \cap U = U$. But since $A' \subseteq U$, $A' \cap U = A'$. It follows that $A' = U$. Thus $A' = A = U$.

(b)

Existence:

Suppose $B \in \mathcal P(U)$. Suppose $A = \phi$. Clearly $\phi \in \mathcal P(U)$. Also $\phi \cap B = \phi$. Thus there exist a set, $A = \phi \in \mathcal P(U)$ such that for every set $B \in \mathcal P(U)$, $A \cap B = A$.

Uniqueness:
Suppose there is another set say, $A' \in \mathcal P(U) \land A' \cap B = A'$. Now for $B = \phi$, $A' \cap \phi = \phi$. But $A' \cap \phi = A'$, it follows that $A' = A = \phi$. Thus we can conclude that $A$ is unique.

Soln8

(a)

Existence:

Suppose $A$ is arbitrary and $A \in \mathcal P(U)$. Also suppose $B = U \setminus A$. Suppose $C \in \mathcal P (U)$. Suppose $x \in C \cap B$. Then:

$\leftrightarrow x \in C \cap B$
$\leftrightarrow x \in C \land x \in B$
$\leftrightarrow x \in C \land (x \in U \setminus A)$
$\leftrightarrow x \in C \land (x \in U \land x \notin A)$
$\leftrightarrow x \in C \land x \in U \land x \notin A$
Since $C \subseteq U$,
$\leftrightarrow x \in C \land x \notin A$
$\leftrightarrow x \in C \setminus A$

Since $x$ is arbitrary, we have $C \cap B = C \setminus A$.

Thus there exists a set $B = U \setminus A$ such that $C \setminus A = C \cap B$.

Uniqueness:

Now for uniqueness proof. Lets assume $B' \in P(U)$ such that $C \setminus A = C \cap B'$. Suppose $C = U$, it follows that $U \setminus A = U \cap B'$. But since $B' \subseteq U$, $U \cap B' = B'$, it follows that $U \setminus A = B'$. Thus we have $B' = B = U \setminus A$.

(b)

Existence:

Suppose $A$ is arbitrary and $A \in \mathcal P(U)$. Also suppose $B = U \setminus A$. Suppose $C \in \mathcal P (U)$. Suppose $x \in C \setminus B$. Then:

$\leftrightarrow x \in C \land x \notin B$
$\leftrightarrow x \in C \land \lnot (x \in U \setminus A )$
$\leftrightarrow x \in C \land \lnot (x \in U \land x \notin A )$
$\leftrightarrow x \in C \land (x \notin U \lor x \in A )$
Since $x \notin U$ is always false as we assumed $x \in C \setminus B$:
$\leftrightarrow x \in C \land (false \lor x \in A )$
$\leftrightarrow x \in C \land x \in A$
$\leftrightarrow x \in C \cap A$

Since $x$ is arbitrary, we have $C \setminus B = C \cap A$.

Uniqueness:

Now for uniqueness proof. Lets assume $B' \in P(U)$ such that $C \setminus B' = C \cap A$. Suppose $C = U$, it follows that $U \setminus B' = U \cap A$. Since $A \subseteq U$, it follows $U \cap A = A$. Thus we have $U \setminus B' = A$. Thus if if $x \in B'$, then $x \notin A$. Thus $B'$ contains all the elements which are not in $A$, or $B' = U \setminus A$. Thus $B' = B = U \setminus A$.

Soln9

(a)

Existence:

Suppose $X = \phi$. Now suppose $x \in A \triangle \phi$, then it follows that $x \in A$. Similarly if $x \in A$, then $x \in A \triangle \phi$. Since $x$ is arbitrary, $A \triangle \phi = \phi$.

Uniqueness:

Suppose $X'$ is a set such that $A \triangle X' = A$. Now for $A = \phi$, we have $\phi \triangle X' = \phi$. But $\phi \triangle X' = X'$. It follows that $X' = X = \phi$. Or we can say that $X$ is unique.

(b)

Suppose $A$ is arbitrary. From last part we know that $X = \phi$.

Existence:

Suppose $B = A$. Then $A \triangle B = A \triangle A$. Since $A \triangle A$ contains all element which exists in $A \setminus A$. But clearly $A \setminus A = \phi$. Thus $A \triangle A = \phi$. Thus there exists a set $B = A$ such that $A \triangle B = \phi$.

Uniqueness:

Suppose $B'$ is a set such that $A \triangle B' = \phi$. Now for $A = \phi$, we have $\phi \triangle B' = \phi$. But since $\phi \triangle B' = B'$, it follows that $B' = \phi$. Or we can conclude that $B$ is unique.

(c)

Existence:

Suppose $C = A \triangle B$. Then we have $A \triangle C$: $\leftrightarrow= A \triangle ( A \triangle B)$
$\leftrightarrow= (A \triangle A) \triangle B$
$\leftrightarrow= \phi \triangle B$
$\leftrightarrow= B$

Uniqueness:

Suppose $C'$ is a set such that $A \triangle C' = B$. Suppose $A = C' \triangle B$. Thus we have $A \triangle B$ : $\leftrightarrow (C' \triangle B) \triangle B$
$\leftrightarrow C' \triangle (B \triangle B)$
$\leftrightarrow C' \triangle \phi$
$\leftrightarrow C'$

Thus we have $C' = A \triangle B$. Or we can say that $C$ is unique.

(d)

Suppose $A$ is arbitrary.

Existence:

Suppose $B = A$. Suppose $C \subseteq A$. Then we have $B \triangle C$ : $\leftrightarrow A \triangle C$.
$\leftrightarrow A \setminus C \cup C \setminus A$.
Since $C \subseteq A$, $C \setminus A = \phi$:
$\leftrightarrow A \setminus C \cup \phi$.
$\leftrightarrow A \setminus C$.

Thus there exists a $B = A$, such that $B \triangle C = A \setminus C$.

Uniqueness:

Suppose $B'$ is a set such that $B' \triangle C = A \setminus C$. Since this is true for all sets $A$ and all sets $C$ such that $C \subseteq A$, this must be true for $C = \phi$. Thus $B' \triangle \phi = A \setminus \phi$, which is equivalent to $B' = A$. Thus we can conclude that $B'$ is unique.

Soln10

We can have following cases:

Case 1: $A = \phi$.
Suppose $\mathcal F$ does not contain any set. Thus $\cup \mathcal F = \phi$. But since $\mathcal F$ is empty, $A \in \mathcal F$ is false. Thus if $A = \phi$ then $\cup \mathcal F = A \to A \in \mathcal F$ is false. Or by contra-positive, we can conclude that if $\cup \mathcal F = A \to A \in \mathcal F$ then $A \ne \phi$.

Case 2: $A$ contains more than one element:
Suppose $x \in A$. Suppose $\mathcal F = \{ A_1, A_2 \}$ such that sets $A_1 = \{ x \}$ and $A_2 = A \setminus A_1$. Thus $A = A_1 \cup A_2$. Or we can say that $\cup \mathcal F = A$. But clearly $A \notin \mathcal F$. Or $\cup \mathcal F = A \to A \in \mathcal F$ is false. Thus by contrapositive we can say that if $\cup \mathcal F = A \to A \in \mathcal F$ then $A$ does not contains more then one element.

Thus combining both cases 1 and 2, there is only one possibility that $A$ contains only one element.

Soln11

Existence:
Suppose $A = \cup \mathcal F$. Since $\mathcal F \subseteq \mathcal F$, it follows that $\cup \mathcal F \in \mathcal F$. Suppose $P \in \mathcal F$, then if $x \in P$, it follows that $x \in \cup \mathcal F$. Thus $P \subseteq \cup \mathcal F$. Since $P$ is arbitrary, $\forall P \in \mathcal F (P \subseteq \cup \mathcal F))$.

Uniqueness:

(Update: (04 Feb. 2019) As pointed out in comments, earlier this part of the solution was not correct. Here is the fixed version.)

Suppose $Q_1 \in \mathcal F$ and $Q_2 \in \mathcal F$ are two different sets such that $\forall P \in \mathcal F (P \subseteq Q_1 ))$ and $\forall P \in \mathcal F (P \subseteq Q_2 ))$. Since $Q_1 \in \mathcal F$, we can replace $P$ with $Q_1$ in $\forall P \in \mathcal F (P \subseteq Q_2 ))$ and $P$ with $Q_2$ in $\forall P \in \mathcal F (P \subseteq Q_1 ))$. Thus we get $Q_1 \subseteq Q_2$ and $Q_2 \subseteq Q_1$. It follows that $Q_1 = Q_2$.

Earlier version:

Suppose $Q_1 \subseteq \mathcal F$ and $Q_2 \subseteq \mathcal F$ are two different sets such that $\forall P \in \mathcal F (P \subseteq Q_1 ))$ and $\forall P \in \mathcal F (P \subseteq Q_2 ))$. Since $Q_1 \subseteq \mathcal F$, we can replace $P$ with $Q_1$ in $\forall P \in \mathcal F (P \subseteq Q_2 ))$ and $P$ with $Q_2$ in $\forall P \in \mathcal F (P \subseteq Q_1 ))$. Thus we get $Q_1 \subseteq Q_2$ and $Q_2 \subseteq Q_1$. It follows that $Q_1 = Q_2$.

Soln12

(a)

Required statement: $\exists x \exists y ( P(x) \land P(y) \land x \ne y \land \forall z (P(z) \to (z = x \lor z = y)) )$.

(b)

We shall prove it in two steps:

Existence Proof: First prove two such value exists so that $P(x)$ is true.

Uniqueness Proof: Prove if there is any value, say $z$ so that $P(z)$ is true, then this value must be equal to any of the two values find in previous step.

(c)

Existence:

Suppose $x = 0$, then we have $x^3 = x^2 = 0$.

Also suppose $x = 1$, then we have $x^3 = x^2 = 1$.

Uniqueness:

Suppose for a value $x = z$ such that $z \ne 0 \land z \ne 1$, and $x^3 = x^2$. Thus $z^3 = z^2$. Since $z \ne 0$, multiplying both sides by $\frac 1 {z^2}$, we get $z = 1$. Thus it contradicts with the assumption $z \ne 1$. So we can conclude that $0$ and $1$ are the only possible values for $x$.