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 .
- Scratch work will look as:
- Using strategy-2:
- Scratch work will look as:
Given: ,
Goal . - Final proof will look as:
Suppose is false.
[Proof of ]
Therefore .
- Scratch work will look as:
- Given: ,
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 .