## Thursday, April 29, 2010

### how to prove it - ch3, sec3.1(Proof Strategies) ex

In this section, we learn how to prove statements of the type $P \rightarrow Q$.

Strategy#1 Suppose P is true and from it derive that Q is also true.

Strategy#2 Prove the contrapositive. We know that $P \rightarrow Q$ $\equiv$ $\lnot Q \rightarrow \lnot P$

In the course of figuring out a proof, we have "givens" which are the statements that are facts or hypothesis or assumptions and "goal" that needs to be proven. We start with some givens and goal, apply a proof strategy and get different givens and goal. In other words, application of a proof strategy transforms a problem into another problem which is(hopefully) easier to solve.

We usually do "hit and trial" to figure out which strategy actually works and with practice it might start coming from gut feeling also.

For example the proof of $P \rightarrow Q$ with strategy#2 can be thought as follows...

Scratch work:

Before using any strategy -

givens: -
goal: $P \rightarrow Q$

After applying strategy#2

givens: -
goal: $\lnot Q \rightarrow \lnot P$

After applying strategy#1

givens: $\lnot Q$
goal: $\lnot P$

and the formal proof(after we've thought through the strategy will look like following)..

We're proving the contrapositive.
Suppose Q is false.
[Proof of $\lnot P$ goes here]
Therefore $P \rightarrow Q$

Notice that, it is usual to use a lot of logical notations in the scratch work to figure out the proof, but the final write up of the proof should be in plain english and simple to understand as much possible.

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

Ex-1
(a)
Hypotheses:
n is an integer larger than 1
n is not prime

Conclusion: $2^n - 1$ is not prime

For n = 6, hypotheses are true as 6 is larger than 1 and also not a prime. Theorem tells us that $2^6 - 1$ should not be a prime, which is true as $2^6 - 1$ = 63 is not a prime.

(b) 15 is not prime, so hypotheses are true.
$2^{15} - 1$ = 32767( = 7 * 4681) is not a prime so conclusion is also correct.

(c) 11 is prime, so hypotheses are false. So, theorem does not tell anything.

Ex-2
(a)
Hypotheses: $b^2 > 4ac$
Conclusion: $ax^2 + bx + c = 0$ has exactly two real solutions

(b) Because a,b and c are free variables while x is not. Fixing the values of a,b and c fixes the True/False value of the statement.

(c)
$(-5)^2 - 4(2)(3)$ = 26 > 0, so hypothesis is true and as per the theorem $2x^2 - 5x + 3 = 0$ should have two real solutions, which is true. 1 and 3/2 are two solutions.

(d)
$4^2 - 4(2)(3)$ = -8, -8 < 0 so hypothesis is false. So theorem does not tell anything.

Ex-3
Hypotheses:
n is a natural number
n > 2
n is not prime

Conclusion:
2n+13 is not prime

The instance for n = 8 is a counterexample. As 8 is a natural number, greater than 2 and not prime; so hypotheses are true. But 2(8)+13 = 29 is a prime, so conclusion is false.

Ex-4
Suppose 0 < a < b. Then b-a > 0.
b+a > 0 because both b and a are greater than 0
so (b-a)(b+a) > 0
=> $b^2 - a^2$ > 0
Since $b^2 - a^2$ > 0, it follows $a^2 < b^2$. Therefore if 0 < a < b then $a^2 < b^2$.

Ex-5
Suppose a < b < 0, Then a-b < 0
a+b < 0 because both b and a are less than 0
so (a-b)(a+b) > 0 (multiplication of two negative real numbers is a positive real number)
=> $a^2 - b^2$ > 0
Since $a^2 - b^2$ > 0, it follows $a^2 > b^2$. Therefore if a < b < 0 then $a^2 > b^2$.

Ex-6
Suppose 0 < a < b, Then a < b
On dividing both sides by ab we get
$\frac{a}{ab} < \frac{b}{ab}$
It follows, $\frac{1}{b} < \frac{1}{a}$
Therefore if 0 < a < b, then $\frac{1}{b} < \frac{1}{a}$

Ex-7 Suppose a is a real number and $a^3 > a$
So $a^3 - a$ > 0 ....... (i)
$a^2$ > 0 as a is real,
so $a^2 + 1$ > 0 ........(ii)

on multiplying eq (i) and (ii) we get
$(a^3 - a)(a^2 + 1)$ > 0
=> $a^5 - a$ > 0

It follows that $a^5 > a$, So if a is a real number and $a^3 > a$, then $a^5 > a$.

Ex-8 We will prove the contrapositive, If $x \notin B$ then $x \in D$.
Given that, $A \setminus B \subseteq C \cap D$
it means $\forall y [y \in (A \setminus B) \rightarrow y \in (C \cap D)]$
So, $\forall y [(y \in A \land y \notin B) \rightarrow (y \in C \land y \in D)]$

Now it must be true for y = x also, so
$(x \in A \land x \notin B) \rightarrow (x \in C \land x \in D)$ is true.

It is given that $x \in A$ and suppose $x \notin B$
=> $x \in C \land x \in D$
It follows that $x \in D$

So If $x \notin B$ then $x \in D$. And hence, If $x \notin D$ then $x \in B$

Ex-9 We will prove the contrapositive, If $\frac{a+b}{2} > b$ then $a > b$

Suppose $\frac{a+b}{2} > b$

on multiplying both sides by 2, we get
$a+b > 2b$

on subtracting b from both sides we get
$a > b$

So, If $\frac{a+b}{2} > b$ then $a > b$

And hence, If $a < b$ then $\frac{a+b}{2} < b$

Ex-10 We will prove the contrapositive, If x = 8 then $\frac{x^{1/3} + 5}{x^2 + 6} \neq \frac{1}{x}$

Suppose x = 8, Then $\frac{x^{1/3} + 5}{x^2 + 6}$
= $\frac{8^{1/3} + 5}{8^2 + 6}$
= $\frac{2+5}{64+6}$
= $\frac{7}{70}$
= $\frac{1}{10}$ $\neq$ $\frac{1}{8}$

And hence, If $\frac{x^{1/3} + 5}{x^2 + 6}$ = $\frac{1}{x}$ then $x \neq 8$

Ex-11 We'll prove the contrapositive. If $c \leq d$ then $ac < bd$.

Suppose $c \leq d$

on multiplying it with $a$ (given that $a > o$)
$ac \leq ad$ ............. (i)

also given that $a < b$

on multiplying it with $d$ (given that $d > 0$)
$ad < bd$ ........... (ii)

From eq (i) and (ii)
$ac \leq ac < bd$

It follows, $ad < bd$

And hence, If $ac \geq bd$ then $c > d$

Ex-12
It is given that $3x + 2y \leq 5$
=> $x \leq \frac{5 - 2y}{3}$

Suppose $x > 1$, then
$1 < x \leq \frac{5 - 2y}{3}$
=> $1 < \frac{5 - 2y}{3}$
=> $3 < 5 - 2y$
=> $2y < 5 - 3$
=> $y < 1$

Thus, If $x > 1$ then $y < 1$

Ex-13
Suppose $x^2 + y = -3$ ....... (i)
$2x - y = 2$ .......(ii)

From eq (i)
$y = -3 - x^2$

substituting the value of y in eq (ii)
$2x - (-3 - x^2) = 2$
=> $2x + 3 + x^2 = 2$
=> $x^2 +2x + 1 = 0$
=> $(x + 1)^2 = 0$
=> $x + 1 = 0$
=> $x = -1$

So, If $x^2 + y = -3$ and $2x - y = 2$ then $x = -1$

Ex-14 Prove that, If x > 3 and y < 2 then $x^2 - 2y > 5$.

Suppose x < 3 and y < 2

Since 0 < 3 < x, so from the theorem proven in Ex-4, it follows that
$3^2 < x^2$
=> $x^2 > 9$ ...... (i)

On multiplying -2 with both sides of y < 2
-2y > -4 ..... (ii)(sign changes because we're multiplying by a negative number)

$x^2 - 2y > 9 - 4$
=> $x^2 - 2y > 5$

Thus, If x > 3 and y < 2 then $x^2 - 2y > 5$

Ex-15
(a) We've proven that
$(x = 7) \rightarrow \frac{2x - 5}{x - 4}=3$
and NOT
$\frac{2x - 5}{x - 4}=3 \rightarrow (x = 7)$

and $(A \rightarrow B)$ is not logically equivalent to $(B \rightarrow A)$

(b) Suppose $\frac{2x - 5}{x - 4} = 3$
on multiplying both sides with (x - 4), which is $\neq 0$, we get
2x - 5 = 3(x - 4)
=> 2x - 5 = 3x - 12
=> 2x - 3x = -12 + 5
=> -x = -7
=> x = 7

Thus, If $\frac{2x - 5}{x - 4} = 3$ then x = 7

Ex-16
(a) The flaw is in, Since $x \neq 3$ so $x^2 \neq 9$. This is not true, as $x^2 = 9$ for x = -3

(b) One counterexample is, x = -3 and y = 1 as $(-3)^2(1) = 9(1)$