Chapter - 3, Proofs

Section - 3.1 - Proof Strategies



Summary

  • A theorem is a statement that has been proven on the basis of previously established statements, such as other theorems—and generally accepted statements, such as axioms.
  • A theorem that says that if certain assumptions called the hypotheses of the theorem are true, then some conclusion must also be true.
  • The hypothesis and conclusion of a theorem often contains free variables. When values are substituted/assigned for these variables, it is called an instance of the theorem.
  • A proof of a theorem is simply a deductive argument whose premises are the hypotheses of the theorem and whose conclusion is the conclusion of the theorem.
  • To prove a conclusion of the form of , there can be two strategies:
    • Assuming is true, Prove . In this way this strategy transformed the problem of proving to proving . After this transformation, is now the part of the hypothesis.
    • Prove contra-positive: assuming is true, prove . Similarly here also problem is transformed from proving to proving .
  • Thus multiple transformations can be applied to convert the problem to simpler one.
  • At any point of the proof:
    • givens are the set of statements that are known or assumed to be true till that point.
    • goal is the final statement that remains to be proven.
    • Thus at the start of a proof, givens will be the initial hypothesis and goal will be the final conclusion.
    • In the course of the proof, the list of hypothesis will increase(during transformation).
    • Similarly, conclusion will change during the course of the proof.
  • In writing final proof:
    • Reasoning used for figuring the the proof are not used/written.
    • Steps to justify the conclusions are used/written but no explanations on how the steps were thought of.
    • Similarly Goals and Givens are also not part of the final proof.
  • Explanations are avoided in proofs to maintains the distinction between:
    • Explanation of thought process.
    • Justifying the conclusions.
  • Thus proof of the goal will look as follows:
    • Given: ,
      Goal
    • Using strategy-1:
      • Scratch work will look as:
        Given: ,
        Goal .
      • Final proof will look as:
        Suppose is true.
        [Proof of ]
        Therefore .
    • Using strategy-2:
      • Scratch work will look as:
        Given: ,
        Goal .
      • Final proof will look as: Suppose is false.
        [Proof of ]
        Therefore .

Soln1

(a)

Hypothesis:

  • is an integer and .
  • is not prime.

Conclusion:
is not prime.

  • For , hypothesis is true.
  • Conclusion is is not prime. This is also true.

(b)

  • For , hypothesis is true.
  • Conclusion is is not prime. This is also true: .

(c)

  • For , hypothesis is not true.
  • Thus theorem does not say anything.

Soln2

(a)

Hypothesis: .

Conclusion: has exactly 2 solutions.

(b) are free variables. is not a free variable.

(c) Substituting the values: gives . This is true. Thus hypothesis is true.

Conclusion is


Thus $ x = 1 x = 3/2 $$ are two solutions. That means conclusion is also correct.

(d) Substituting the values: gives . This is false. Thus hypothesis is false.
Theorem does not say anything as hypothesis is not true.


Soln3

Hypothesis:

  • is a natural number and .
  • is not prime.

Conclusion:
is not prime.

For , Hypothesis is true. Conclusion: , which is a prime number. Thus conclusion is not true.


Soln4

Suppose . Then .
Also . Multiplying by
We get . Which gives:
.
Since , it follows that .


Soln5

if then and
Thus, the product because product of a positive and negative number is negative.
Expanding the product, we get .
Now since , It follows that .


Soln6

if , Multiplying both sides by positive number .


Soln7

Suppose . Subtracting from both sides:
.
Multiplying by on both sides:

Simplifying:


Thus we have: .


Soln8

We are given that and .
Thus we have
For , we have:

As and suppose , then we get:

Simplifying:

It follows that , or .


Soln9

Given that , then adding to both sides:



Dividing both sides by 2:


Soln10

We shall prove it by proving contra-positive.
Suppose , we get

Simplifying:


Clearly which is not correct. Thus if , then
Thus if , then


Soln11

We shall prove this using contra-positive. Given that , and
Multiplying , by on both sides:
Suppose that , Multiplying both sides by gives:
Thus we have and , which gives
Or we can say that: .

Thus we proved that if , then .
It follows that if , then .


Soln12

Suppose , then
Adding 2 on both sides:
, or , which is same as

Also, given that
Subtracting 3x from both sides:

Thus we have
Simplifying:
, or


Soln13

Given that and
Adding both:

Simplifying:

Or
which means .


Soln14

Given that
As and , we can apply the theorem: If , then
Thus we have

Also, it is givem that .
Multiplying both sides by -2, and reverting the sign of inequality:

Adding both inequalities:
Or .


Soln15

(a)

The proof is for: if , then
while the required proof was for: if , then .

(b)

Given that
Cross multiplying:

Simplifying:
.


Soln16

(a)

The issue is that value of is not taken into consideration. As for this value .

(b)

If x = -3, then the equation gives , thus theorem is not correct as it says if , then .