how to prove it - ch3, sec3.3(Proofs Involving Quantifiers) ex

To prove a goal of the form $\forall x P(x)$:
Let x be arbitrary
[Prove P(x)]
Since x was arbitrary, we can conclude that $\forall x P(x)$

Here it is very important to make no assumption about x. Main advantage of this strategy is that it enables you to prove a goal about all objects by reasoning about only one object. If you find yourself using a lot of "all x's" or "every x", then you are probably making your proof unnecessarily complicated by not using this strategy.


To prove a goal of the form $\exists x P(x)$:
Find a particular value x such that P(x) is true. Thus, $\exists x P(x)$

Finding the right value to use for x may be difficult in some cases. One method that is sometimes helpful is to assume that P(x) is true and then see if you can figure out what x must be, based on this assumption.

Next important thing is to learn, how to use a given quantified sentence.


To use a given of the form $\exists x P(x)$:
We can use this by introducing a new variable $x_0$ into the proof to stand for an object for which $P(x_0)$ is true. That is, you can now assume $P(x_0)$ is true.

To use a given of the form $\forall x P(x)$:
This is useful only when you're talking about some value a in your proof, you can always assume that P(a) is true.

In general, its a good strategy to simplify the goal as much possible by using the strategies we're learning.


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

Ex-1 Given that $\exists x (P(x) \rightarrow Q(x))$, so we can find a $x_0$ s.t. $P(x_0) \rightarrow Q(x_0)$. Suppose $\forall x P(x)$, it follows that $P(x_0)$ is true and hence $Q(x_0)$ is also true. Thus $\exists x Q(x)$ is true. So, $\forall x P(x) \rightarrow \exists x Q(x)$ is true.


Ex-2 Scratch Work:

given:
goal: $A \cap B \setminus C = \emptyset \rightarrow A \cap B \subseteq C$

Assume the hypotheses

given: $A \cap B \setminus C = \emptyset$
goal: $A \cap B \subseteq C$ $\equiv$ $\forall x (x \in A \cap B \rightarrow x \in C)$

Let x be arbitrary

given: $A \cap B \setminus C = \emptyset$
goal: $x \in A \cap B \rightarrow x \in C$

Assume the hypotheses

given: $A \cap B \setminus C = \emptyset$ , $x \in A \cap B$
goal: $x \in C$

we can not analyse goal any further, so let us analyze the givens now.

It is given that
$A \cap B \setminus C = \emptyset$
$\equiv$ $\lnot \exists x x \in (A \cap B \setminus C)$
$\equiv$ $\forall x \lnot (x \in (A \cap B \setminus C))$
$\equiv$ $\forall x \lnot (x \in A \land x \in B \land x \notin C)$
$\equiv$ $\forall x [\lnot (x \in A \land x \in B) \lor x \in C]$
$\equiv$ $\forall x (x \in A \cap B \rightarrow x \in C)$

Hence $x \in C$


Formal Proof:
Let x be an arbitrary element of $A \cap B$. Suppose A and $B \setminus C$ are disjoint, so it can not happen that x belongs to A and B but not C. So x must be an element of C. Thus $x \in A \cap B \rightarrow x \in C$. Since x is arbitrary, hence $\forall x (x \in A \cap B \rightarrow x \in C)$ or $A \cap B \subseteq C$. So, If A and $B \setminus C$ are disjoint then $A \cap B \subseteq C$


Ex-3
given:
goal: If $A \subseteq B \setminus C$ then A and C are disjoint

Assume the hypotheses

given: $A \subseteq B \setminus C$
goal:
A and C are disjoint
= $\lnot \exists x (x \in A \land x \in C)$
= $\forall x (x \notin A \lor x \notin C)$
= $\forall x (x \in A \rightarrow x \notin C)$


Let x be arbitrary

given: $A \subseteq B \setminus C$
goal: $x \in A \rightarrow x \notin C$

Assume the hypotheses

given: $A \subseteq B \setminus C$ , $x \in A$
goal: $x \notin C$

Formal Proof:
Let x be an arbitrary element of A and $A \subseteq B \setminus C$. It follows that x must belong to $B \setminus C$, so x must not be in C. Hence, If $A \subseteq B \setminus C$ and $x \in A$ then $x \notin C$. Since x is arbitrary, so If $A \subseteq B \setminus C$ then A and C are disjoint.


Ex-4
Note: In this exercise $P(A)$ means Power Set of A.

given: $A \subseteq P(A)$
goal: $P(A) \subseteq P(P(A))$ = $\forall x (x \in P(A) \rightarrow x \in P(P(A)))$

Let x be arbitrary

given: $A \subseteq P(A)$
goal: $x \in P(A) \rightarrow x \in P(P(A))$

Assume the hypotheses

given: $A \subseteq P(A)$, $x \in P(A)$
goal: $x \in P(P(A))$ = $x \subseteq P(A)$ = $\forall y (y \in x \rightarrow y \in P(A))$

Let y be arbitrary

given: $A \subseteq P(A)$, $x \in P(A)$
goal: $y \in x \rightarrow y \in P(A)$

Assume the hypotheses

given: $A \subseteq P(A)$, $x \in P(A)$, $y \in x$
goal: $y \in P(A)$

Since $x \in P(A)$
=> $x \subseteq A$
and Since $A \subseteq P(A)$
=> $x \subseteq P(A)$
and Since $y \in x$, so $y \in P(A)$


Formal Proof:
Let x be an arbitrary element of $P(A)$, it follows that $x \subseteq A$. Since $A \subseteq P(A)$, so $x \subseteq P(A)$ and hence $x \in P(P(A))$. It means if $A \subseteq P(A)$ and $x \in P(A)$ then $x \in P(P(A))$. Since x is arbitrary, it follows, if $A \subseteq P(A)$ then $P(A) \subseteq P(P(A))$


Ex-5
(a) Yes, the empty set $\emptyset$
(b) {$\emptyset$}


Ex-6(a)
given:
goal: if $x \neq 1$ then $\exists y (\frac{y+1}{y-2} = x)$

Assume the hypotheses

given: $x \neq 1$
goal: $\exists y (\frac{y+1}{y-2} = x)$

in order to prove it, we have to find a $y_0$ s.t. $\frac{y_0+1}{y_0-2} = x$
=> $y_0 + 1$ = $x(y_0 - 2)$
=> $y_0 + 1$ = $xy_0 - 2x$
=> $xy_0 - y_0$ = $1 + 2x$
=> $y_0$ = $\frac{1 + 2x}{x - 1}$

It is defined since $(x-1) \neq 0$.

Formal Proof:
Assume $y$ = $y_0$ = $\frac{1 + 2x}{x - 1}$
Now, $\frac{y+1}{y-2}$
= $\frac{y_0+1}{y_0-2}$
= $\frac{(\frac{1 + 2x}{x - 1}) + 1}{(\frac{1 + 2x}{x - 1}) - 2}$
= $\frac{1 + 2x + x - 1}{1 + 2x - 2x + 2}$
= $\frac{3x}{3}$
= $x$

Thus, If $x \neq 1$ then there exists a real number y s.t. $\frac{y+1}{y-2} = x$

Ex-6(b)
For $\frac{y+1}{y-2} = x$ to be true
$y$ = $\frac{1 + 2x}{x - 1}$
which is defined only when $(x-1) \neq 0$ => $x \neq 1$

Thus, if there exists a real number y s.t. $\frac{y+1}{y-2} = x$ then $x \neq 1$


Ex-7 Let x be an arbitrary real number and x > 2.
For a real number y = $\frac{x + \sqrt{x^2 - 4}}{2}$
$\sqrt{x^2 - 4}$ is defined because $x > 2$ => $x^2 > 4$ => $x^2 - 4 > 0$

Now, $y + \frac{1}{y}$
= $\frac{x + \sqrt{x^2 - 4}}{2}$ + $\frac{2}{x + \sqrt{x^2 - 4}}$
= $\frac{(x + \sqrt{x^2 - 4})(x + \sqrt{x^2 - 4}) + 4}{2(x + \sqrt{x^2 - 4})}$
= $\frac{x^2 + (x^2 - 4) + 2x\sqrt{x^2 - 4} + 4}{2(x + \sqrt{x^2 - 4})}$
= $\frac{2x^2 + 2x\sqrt{x^2 - 4}}{2(x + \sqrt{x^2 - 4})}$
= $x$

Thus, for any real number x, if x > 2, then there exists a real number y s.t. $y + \frac{1}{y}$ = x.


Ex-8
Note: $F$ in this ex means a Family of Sets.

given:
goal: if $A \in F$ then $A \subseteq \cup F$

Assume the hypotheses

given: $A \in F$
goal: $A \subseteq \cup F$ $\equiv$ $\forall x (x \in A \rightarrow x \in \cup F)$

Let x be arbitrary

given: $A \in F$
goal: $x \in A \rightarrow x \in \cup F$

Assume the hypotheses

given: $A \in F$, $x \in A$
goal: $x \in \cup F$ $\equiv$ $\exists y \in F (x \in y)$

Since, $x \in A$ and $A \in F$, so y = A satisfies the goal.

Formal Proof:
Suppose $A \in F$ and x be an arbitrary element of A. Since $\cup F$ is union of all the sets in $F$ and that includes A, it follows that $x \in \cup F$. Thus if $A \in F$ then $x \in A \rightarrow x \in \cup F$. Since x is arbitrary, hence If $A \in F$ then $A \subseteq \cup F$


Ex-9 Suppose $A \in F$ and x be an arbitrary element of $\cap F$. Since $\cap F$ is intersection of all sets in $F$, it follows that $x \in A$. In other words, If $A \in F$ and $x \in \cap F$ then $x \in A$. Since x is arbitrary, we can conclude that If $A \in F$ then $\cap F \subseteq A$


Ex-10
given: $F$ is a non-empty family of sets, B is a set, $\forall A \in F (B \subseteq A)$
goal: $B \subseteq \cap F$

Formal Proof:
Let x be an arbitrary element of B. Since $\forall A \in F (B \subseteq A)$, that is B is subset of each element of $F$, it follows that x must be an element of every set in $F$. So $x \in \cap F$. Hence $x \in B \rightarrow x \in \cap F$. Since x is arbitrary, Therefore $B \subseteq \cap F$


Ex-11
given:
goal: If $\emptyset \in F$ then $\cap F = \emptyset$

Assume the hypotheses

given: $\emptyset \in F$
goal:
$\cap F = \emptyset$
$\equiv$ $\lnot \exists x (x \in \cap F)$
$\equiv$ $\forall x \lnot (x \in \cap F)$

Let x be arbitrary

given: $\emptyset \in F$
goal:
$\lnot (x \in \cap F)$
$\equiv$ $\lnot \forall y (y \in F \rightarrow x \in y)$
$\equiv$ $\exists y (y \in F \land x \notin y)$

$y = \emptyset$ satisfies the goal, because no matter what x is, it can not be an element of $\emptyset$

Formal Proof:
Suppose $\emptyset \in F$. Now We will prove by contradiction that $\cap F = \emptyset$. Let x be an arbitrary element of $\cap F$, it follows that x must belong to every element of $F$. Since $\emptyset \in F$, so x should also belong to $\emptyset$ which is not possible, hence x can not belong to $\cap F$. Since x is arbitrary, we can conclude that If $\emptyset \in F$ then $\cap F = \emptyset$


Ex-12
Note: $F$ and $G$ are families of sets.

given:
goal: If $F \subseteq G$ then $\cup F \subseteq \cup G$

Suppose the hypotheses

given: $F \subseteq G$
goal: $\cup F \subseteq \cup G$

Formal Proof:
Suppose $F \subseteq G$ and Let x be an arbitrary element of $\cup F$. By definition of $\cup F$ it follows that there must be atleast one element A of $F$ s.t. $x \in A$. Since $F \subseteq G$, so A should be an element of $G$ also. That is we have $x \in A$ and $A \in G$, so $x \in \cup G$. Since x is arbitrary, Therefore If $F \subseteq G$ then $\cup F \subseteq \cup G$


Ex-13 Suppose $F \subseteq G$ and x be an arbitrary element of $\cap G$. By definition of $\cap G$ it follows that x must be an element of every element of $G$. Since $F \subseteq G$, therefore x must be an element of every element of $F$ also. So $x \in \cap F$. Thus If $F \subseteq G$ then $x \in \cap G \rightarrow x \in \cap F$. Since x is arbitrary, we can conclude that If $F \subseteq G$ then $\cap G \subseteq \cap F$


Ex-14
given:
goal:
$\cup_{i \in I}P(A_i) \subseteq P(\cup_{i \in I}A_i)$
$\equiv$ $\forall x (x \in \cup_{i \in I}P(A_i) \rightarrow x \in P(\cup_{i \in I}A_i))$

Let x be arbitrary

given:
goal: $x \in \cup_{i \in I}P(A_i) \rightarrow x \in P(\cup_{i \in I}A_i)$

Assume the hypotheses

given: $x \in \cup_{i \in I}P(A_i)$
goal: $x \in P(\cup_{i \in I}A_i)$
$\equiv$ $x \subseteq \cup_{i \in I}A_i$

Formal Proof:
Let x be an arbitrary element of $\cup_{i \in I}P(A_i)$. It follows, there should exist atleast one $k \in I$ s.t. $x \in P(A_k)$.
So $x \subseteq A_k$
=> $x \subseteq \cup_{i \in I}A_i$
=> $x \in P(\cup_{i \in I}A_i)$

Thus, if $x \in \cup_{i \in I}P(A_i)$ then $x \in P(\cup_{i \in I}A_i)$. Since x is arbitrary, we can conclude that $\cup_{i \in I}P(A_i) \subseteq P(\cup_{i \in I}A_i)$


Ex-15
given: $I \neq \emptyset$
goal: $\cap_{i \in I}A_i \in \cap_{i \in I}P(A_i)$

Let us try to see what it means for an arbitrary x to be an element of $\cap_{i \in I}P(A_i)$
$x \in \cap_{i \in I}P(A_i)$
=> $\forall i \in I (x \in P(A_i))$
=> $\forall i \in I (x \subseteq A_i)$

Formal Proof:
By definition of $\cap_{i \in I}A_i$ it follows that
$\forall i \in I (\cap_{i \in I}A_i \subseteq A_i)$
=> $\forall i \in I (\cap_{i \in I}A_i \in P(A_i))$
=> $\cap_{i \in I}A_i \in \cap_{i \in I}P(A_i)$


Ex-16
given:
goal: If $F \subseteq P(B)$ then $\cup F \subseteq B$

assume the hypotheses

given: $F \subseteq P(B)$
goal: $\cup F \subseteq B$

Formal Proof:
Suppose $F \subseteq P(B)$ and Let x be an arbitrary element of $\cup F$. By definition of $\cup F$ it follows that there exists atleast one $A \in F$ s.t. $x \in A$. Since $F \subseteq P(B)$, therefore $A \in P(B)$ is also true. It follows that $A \subseteq B$ and hence $x \in B$. Thus, If $x \in \cup F$ then $x \in B$. Since x is arbitrary, we conclude that If $F \subseteq P(B)$ then $\cup F \subseteq B$


Ex-17
given: $F$ and $G$ are non-empty family of sets, every element of $F$ is subset of every element of $G$
goal: $\cup F \subseteq \cup G$

Formal Proof:
Let x be an arbitrary element of $\cup F$. By definition of $\cup F$ it follows that there exists atleast on $A \in F$ s.t. $x \in A$. Since every element of $F$ is subset of every element of $G$, therefore A is subset of every element of $G$ and hence $A \subseteq \cup G$. So $x \in \cup G$. Since x is arbitrary, we conclude that $\cup F \subseteq \cup G$


Ex-18(a) Suppose a|b and a|c, so there exists atleast two integers $k_1$ and $k_2$ s.t.
$ak_1 = b$ ..... (i)
and
$ak_2 = c$ ..... (ii)

adding eq (i) and (ii) we get
$a(k_1 + k_2) = (b+c)$
since $k_1 + k_2$ is another integer, so a|(b+c).

Ex-18(b) Suppose ac|bc and $c \neq 0$. There exists an integer k s.t. ack = bc
=> ack - bc = 0
=> c(ak - b) = 0
Since $c \neq 0$, therefore (ak - b) = 0
=> ak = b
=> a|b

Ex-19
(a)Let x and y be arbitrary real numbers and z = $\frac{y-x}{2}$.
x + z
= x + $\frac{y-x}{2}$
= 2x + y - x
= y + x

and
y - z
= y - $\frac{y-x}{2}$
= 2y - y + x
= y + x

so x+z = y-z
Thus, for all real numbers x and y there exists a real number z such that x+z = y-z

(b) No, it wouldn't be justified as z = $\frac{y-x}{2}$ might not be an integer even though x and y are.


Ex-20 The flaw is in the conclusion that "for every real number x, $x^2$ < 0" because assumption of negation of the statement given in the theorem being true means just that "there exists atleast one real number x s.t. $x^2$ < 0.


Ex-21
(a) x being an arbitrary element of A does not mean its an arbitrary element of B also.

(b) A = {1}; B{0,1}


Ex-22 Given proof does not consider y to be arbitrary. For a particular value of x = $\frac{y}{y^2 + 1}$, there is only one(not all real number) real number y s.t. $xy^2 = y-x$


Ex-23
(a) Let us focus on the second half of the proof given, which basically says $A \subseteq (\cup F \cap \cup G)$ contradicts $\cup F \cap \cup G = \emptyset$ because no such A can exist, which is not true.
Suppose $A = \emptyset$, then clearly both, $A \subseteq (\cup F \cap \cup G)$ and $\cup F \cap \cup G = \emptyset$, are true.

(b) A counter example is
$F$ = {$\emptyset$,{1}}
$G$ = {$\emptyset$,{3}}


Ex-24
(a) x and y are not considered completely arbitrary but equal.

(b) Theorem is incorrect. x = 2, y = 1 is a counterexample as $x^2 + xy -2y^2$
= 4 + 2 - 2
= 4, which is non-zero


Ex-25 Let x be an arbitrary real number and y = 2. Let z be an arbitrary real number.
$(x + z)^2 - (x^2 + z^2)$
= $x^2 + z^2 + 2z - x^2 + z^2$
= 2z
= yz
Thus, for every real number x there is a real number y s.t. for every real number z, yz = $(x + z)^2 - (x^2 + z^2)$


Ex-26
(a) For goals of the form $\forall x P(x)$ we can immediately initiate the proof by assuming x arbitrary and P(x) true. And for given of the form $$\exists x P(x)$ also we can immediately initiate the proof by assuming one $x_0$ that satisfies $P(x_0)$
For both, the goal of the form $\exists x P(x)$ and given of the form $\forall x P(x)$, we can not immediately start the proof unless we find a value $x_0$ of interest.

(b) Because negation of universal quantifier is existential quantifier and viceversa.