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

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

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 xP\left(x\right)$:
Find a particular value x such that P(x) is true. Thus, $\exists xP\left(x\right)$

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 xP\left(x\right)$:
We can use this by introducing a new variable $x_0$ into the proof to stand for an object for which $P\left(x_0\right)$ is true. That is, you can now assume $P\left(x_0\right)$ is true.

To use a given of the form $\forall xP\left(x\right)$:
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\left(P\right(x)\to Q(x\left)\right)$, so we can find a $x_0$ s.t. $P\left(x_0\right)\to Q\left(x_0\right)$. Suppose $\forall xP\left(x\right)$, it follows that $P\left(x_0\right)$ is true and hence $Q\left(x_0\right)$ is also true. Thus $\exists xQ\left(x\right)$ is true. So, $\forall xP\left(x\right)\to \exists xQ\left(x\right)$ is true.


Ex-2 Scratch Work:

given:
goal: $A\cap B\backslash C=\varnothing \to A\cap B\subseteq C$

Assume the hypotheses

given: $A\cap B\backslash C=\varnothing$
goal: $A\cap B\subseteq C$ $\equiv$ $\forall x(x\in A\cap B\to x\in C)$

Let x be arbitrary

given: $A\cap B\backslash C=\varnothing$
goal: $x\in A\cap B\to x\in C$

Assume the hypotheses

given: $A\cap B\backslash C=\varnothing$ , $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\backslash C=\varnothing$
$\equiv$ $\neg \exists xx\in (A\cap B\backslash C)$
$\equiv$ $\forall x\neg (x\in (A\cap B\backslash C\left)\right)$
$\equiv$ $\forall x\neg (x\in A\wedge x\in B\wedge x\notin C)$
$\equiv$ $\forall x[\neg (x\in A\wedge x\in B)\vee x\in C]$
$\equiv$ $\forall x(x\in A\cap B\to x\in C)$

Hence $x\in C$


Formal Proof:
Let x be an arbitrary element of $A\cap B$. Suppose A and $B\backslash 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\to x\in C$. Since x is arbitrary, hence $\forall x(x\in A\cap B\to x\in C)$ or $A\cap B\subseteq C$. So, If A and $B\backslash C$ are disjoint then $A\cap B\subseteq C$


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

Assume the hypotheses

given: $A\subseteq B\backslash C$
goal:
A and C are disjoint
= $\neg \exists x(x\in A\wedge x\in C)$
= $\forall x(x\notin A\vee x\notin C)$
= $\forall x(x\in A\to x\notin C)$


Let x be arbitrary

given: $A\subseteq B\backslash C$
goal: $x\in A\to x\notin C$

Assume the hypotheses

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

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


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

given: $A\subseteq P\left(A\right)$
goal: $P\left(A\right)\subseteq P\left(P\right(A\left)\right)$ = $\forall x(x\in P(A)\to x\in P(P\left(A\right)\left)\right)$

Let x be arbitrary

given: $A\subseteq P\left(A\right)$
goal: $x\in P\left(A\right)\to x\in P\left(P\right(A\left)\right)$

Assume the hypotheses

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

Let y be arbitrary

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

Assume the hypotheses

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

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


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


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


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

Assume the hypotheses

given: $x\ne 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$ = $x{y}_0-2x$
=> $x{y}_0-y_0$ = $1+2x$
=> $y_0$ = $\frac{1+2x}{x-1}$

It is defined since $(x-1)\ne 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{\left(\frac{1+2x}{x-1}\right)+1}{\left(\frac{1+2x}{x-1}\right)-2}$
= $\frac{1+2x+x-1}{1+2x-2x+2}$
= $\frac{3x}{3}$
= $x$

Thus, If $x\ne 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)\ne 0$ => $x\ne 1$

Thus, if there exists a real number y s.t. $\frac{y+1}{y-2}=x$ then $x\ne 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\to x\in \cup F)$

Let x be arbitrary

given: $A\in F$
goal: $x\in A\to 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\to 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\to x\in \cap F$. Since x is arbitrary, Therefore $B\subseteq \cap F$


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

Assume the hypotheses

given: $\varnothing \in F$
goal:
$\cap F=\varnothing$
$\equiv$ $\neg \exists x(x\in \cap F)$
$\equiv$ $\forall x\neg (x\in \cap F)$

Let x be arbitrary

given: $\varnothing \in F$
goal:
$\neg (x\in \cap F)$
$\equiv$ $\neg \forall y(y\in F\to x\in y)$
$\equiv$ $\exists y(y\in F\wedge x\notin y)$

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

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


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\to 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\left(A_i\right)\subseteq P\left({\cup }_{i\in I}{A}_i\right)$
$\equiv$ $\forall x(x\in {\cup }_{i\in I}P(A_i)\to x\in P({\cup }_{i\in I}{A}_i\left)\right)$

Let x be arbitrary

given:
goal: $x\in {\cup }_{i\in I}P\left(A_i\right)\to x\in P\left({\cup }_{i\in I}{A}_i\right)$

Assume the hypotheses

given: $x\in {\cup }_{i\in I}P\left(A_i\right)$
goal: $x\in P\left({\cup }_{i\in I}{A}_i\right)$
$\equiv$ $x\subseteq {\cup }_{i\in I}{A}_i$

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

Thus, if $x\in {\cup }_{i\in I}P\left(A_i\right)$ then $x\in P\left({\cup }_{i\in I}{A}_i\right)$. Since x is arbitrary, we can conclude that ${\cup }_{i\in I}P\left(A_i\right)\subseteq P\left({\cup }_{i\in I}{A}_i\right)$


Ex-15
given: $I\ne \varnothing$
goal: ${\cap }_{i\in I}{A}_i\in {\cap }_{i\in I}P\left(A_i\right)$

Let us try to see what it means for an arbitrary x to be an element of ${\cap }_{i\in I}P\left(A_i\right)$
$x\in {\cap }_{i\in I}P\left(A_i\right)$
=> $\forall i\in I(x\in P(A_i\left)\right)$
=> $\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\left)\right)$
=> ${\cap }_{i\in I}{A}_i\in {\cap }_{i\in I}P\left(A_i\right)$


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

assume the hypotheses

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

Formal Proof:
Suppose $F\subseteq P\left(B\right)$ 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\left(B\right)$, therefore $A\in P\left(B\right)$ 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\left(B\right)$ 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.
$a{k}_1=b$ ..... (i)
and
$a{k}_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\ne 0$. There exists an integer k s.t. ack = bc
=> ack - bc = 0
=> c(ak - b) = 0
Since $c\ne 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. $x{y}^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=\varnothing$ because no such A can exist, which is not true.
Suppose $A=\varnothing$, then clearly both, $A\subseteq (\cup F\cap \cup G)$ and $\cup F\cap \cup G=\varnothing$, are true.

(b) A counter example is
$F$ = {$\varnothing$,{1}}
$G$ = {$\varnothing$,{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 xP\left(x\right)$ we can immediately initiate the proof by assuming x arbitrary and P(x) true. And for given of the form $\$\exists xP\left(x\right)$ also we can immediately initiate the proof by assuming one $x_0$ that satisfies $P\left(x_0\right)$
For both, the goal of the form $\exists xP\left(x\right)$ and given of the form $\forall xP\left(x\right)$, 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.