cs160 Tutorial 4

Tutorial 4: Proof Techniques


Study the Proofs slides and read Rosen chapters 1.6 and 1.7.

Terminology

Theorem:
Statement that can be proved to be true
Proof:
valid argument establishing the truth of a theorem
Axioms:
statements we assume to be true without proof
Lemma:
helper theorem used in the proof of a larger theorem
Corollary:
theorem that can be established directly from a theorem that has been proved
Conjecture:
statement that is proposed to be true

Quick Test

Given the statement to prove: "All primes are odd."

1. What are the "axioms"?
some prime number is odd
all numbers are prime
n is prime number

2. What is the "conclusion"?
n is odd
some prime number is odd
all numbers are odd

3. What is the "conjecture"?
For all n such that n is a prime number, n is odd.
some prime number is odd
n is a prime number


In this tutorial, we will go over four proof techniques along with examples and strategies for doing proofs.

Direct Proof

So far we have used one proof technique: the direct proof, where we have premises and use inference rules and equivalences to prove a conclusion.

Example 1
Theorem: if m and n are perfect squares (i.e., m = s2 and n=t2, where s and t are integers) then mn is a perfect square.

Proof. The premise is that m=s2 and n = 2t. Therefore mn = s2t2 = (st)2, and therefore mn is a perfect square.

QED.

(QED or Q.E.D.: a Latin term "quod erat demonstrandum" or "what was to be proved", sometimes used to indicate the end of a proof.)


Self Check:

Use a direct proof to show that the sum of two odd integers is even.
(Note: This is exercise 1 in Section 1.6 in the Rosen text.)


Proof by Contraposition

The next category of proof technique is that of indirect proofs. The idea here is to 'sneak up' on what you want to prove by casting the conjecture in a different way or showing that you cannot prove the opposite. The first indirect technique is "proof by contraposition": to prove p → q we assume ¬q and show that ¬p holds. This is based on the following equivalence: p → q ≡ ¬q → ¬p.


Self Check:

show this equivalence, p → q ≡ ¬q → ¬p, by truth table.


Example 2:
Show that "if n is an integer and n2+1 is odd, then n is even", using contraposition.

Proof using contraposition. We must show that if n is odd (n is not even), n2+1 is even. That is easy: if n is odd, n2 is odd, and therefore n2+1 is even.
QED

Note: because we had two premises in the example connected with "and", we only have to show that the negation of one of them is true -- it was not necessarily to negate "n is an integer".

A direct proof of example 2 would be more complicated because it is hard to derive a property of n from the fact that n2+1 is odd (or is it?).


Quick Test

Suppose we want to prove "If the average of four different integers is 10, then one of the integers is greater than 11." using proof by contraposition.

4. The first step in the proof is:
to give an example of four different integers that have an average of 10
to negate the premise that the average of four different integers is 10
to negate the conclusion that one of the integers is greater than 11.

5. The second step is to:
show that the largest set of four different integers that are still not greater than 11 (11, 10, 9, 8) have an average of 9.5.
identify rules of inference that can be applied to the premise.


Self Check:

Finish the proof started in the Quick Test above... Prove by contraposition the conjecture:
If the average of four different integers is 10, then one of the integers is greater than 11.


Self Check:

Use a proof by contraposition to show that if x + y ≥ 2, where x and y are real numbers, then x ≥ 1 or y ≥ 1.
(Note: This is exercise 15 in Section 1.6 in the Rosen text.)


The process of finding a proof is somewhat like trial and error. First we may attempt a direct proof of p→q, but we may not get there. So then we try it "from the other end": ¬q and we may get to the finish line: ¬p.

Why would we not start from q?

Notice that we had to prove an implication. Remember false → true, but also false → false. So how do we prove: "if bananas are straight, then apples are cubes"? By simply pointing out that bananas are not straight. This is called a vacuous proof: we can draw any conclusion from a false antecedent. To show that if 0=1 then pigs fly, we simply point out that 0 ≠ 1. Vacuous proofs occur often as part of a larger proof. For example, we want to prove P(n) = "if n is an integer and n>1 then n2 > n".

To show P(0), we simply point out that 0 is not larger than 1.


Quick Test

6. Which of the following cannot be proven with a vacuous proof?
Prove the proposition P(1), where P(n) is the proposition "If x is a prime number greater than 1, then the square root is not an integer."
Prove the proposition P(4), where P(n) is the proposition "If x is a prime number, then the square root is not an integer."
Prove the proposition P(2), where P(n) is the proposition "if n is an integer and n>1 then n2 > n".


Proof by Contradiction

Remember, proof by contraposition can be used to prove an implication. Another proof technique: proof by contradiction also uses a negation but can be used in cases other than implications.

Example 3: Suppose I have blue socks, white socks and red socks. Then at least two out of four of my socks have the same color.

Proof by contradiction. Suppose that not at least two socks are the same color. That means that all four socks are a different color. But I only have three different color socks, so I arrive at a contradiction. That must mean that my assumption: not at least two socks are the same color was false, and hence the opposite is true: at least two out of four of my socks are the same color.

QED

Proof by contradiction works as follows: to prove p, we assume ¬p and derive a contradiction, meaning we deduce something to be true that we know from the premises is false (or vice versa with the true and false). Here is a very famous proof that √2 is irrational, i.e. there are no integers p and q such that √2 = p/q.

Proof by contradiction.

Assume that there are integers p and q such that √2 = p/q. We can take all common factors out of p and q arriving at √2 = a/b, where a and b have no common factors. Now we are going to show a contradiction, namely that a and b have common factors. If √2 = a/b then 2b2 = a2. Therefore a2 is even, and therefore a is even. ( If you do not believe that, you need to prove the lemma: if a2 is even, then a is even).

So a is even or a = 2c. But then 2b2 = a2 = 4c2 , and thus b2 = 2c2 . So b2 is even, so b is even. But if both a and b are even then they have a common factor 2, which is the contradiction we were hunting for. Because we have arrived at a contradiction, our assumption "there are integers p and q such that √2 = p/q" was false, hence there are no integers p and q such that √2 = p/q.

QED

A proof by contraposition can be converted into a proof by contradiction by adding the assumption that the premise is true and then showing that there is a contradiction.

Example 4:
Show that "if n is an integer and n2+1 is odd, then n is even" is true, using proof by contradiction.

Proof using contradiction. We assume that n is odd (the conclusion) and that n2+1 is odd. But if n is odd, then n2 is odd, and therefore n2+1 is even. Thus, a contradiction with our assumption.
QED


Quick Test

As in the Self Check above, prove that if x and y are real numbers and x + y ≥ 2, then x ≥ 1 or y ≥ 1.
7. Which of the following is a proof by contradiction?
Assume that it is not true that x ≥ 1 or y ≥ 1. Then x < 1 and y < 1. Adding these two inequalities, we obtain x + y < 2, which is the negation of x + y ≥ 2.
Assume that it is true that x + y ≥ 2 and it is not true that x ≥ 1 or y ≥ 1. This means that it is true that x < 1 and y < 1. Adding these two inequalities, we obtain x + y < 2, which is a contradiction of our assumption that x + y ≥ 2.

Suppose that we are constructing a proof for the statement: if n is an integer and n3 + 5 is odd, then n is even.
8. For a proof by contradiction, what should be assumed first?
n3+ 5 is even
n is even
n is odd

9. For a proof by contradiction, what should be inferred that causes the contradiction?
that n3+ 5 is even
that n is even
that n is odd


Self Check:

Show that "if n is an integer and n3+5 is odd, then n is even" using a proof by contradiction.
(Note: This is exercise 17b in Section 1.6 in the Rosen text.)


Proof by Cases

To prove p → q we can sometimes break p into a number of cases: p ≡ p1 ∨ p2 ∨ … ∨ pn. Proving p → q is equivalent with proving p1 ∨ p2 ∨ … ∨ pn → q, which is equivalent with proving ( p1 → q ) ∧ ( p2 → q ) ∧ … ( pn → q )

Example 5: Prove that every for integer n, n2 ≥ n.

Proof by cases: n is either less than zero or equal to 0 or greater than zero.

Case 1: n<0 then n2 ≥ n because n<0 and n2 > 0

Case 2: n=0 then n2 = 0 and hence n2 = n, so n2 ≥ n

Case 3: n>0 then because n is an integer n ≥ 1, and hence n2 ≥ n

Q.E.D.


Quick Test

Answer the following questions about using proof by cases to prove the triangle inequality: if x and y are real numbers then |x| + |y| ≥ |x + y| (where |x| represents the absolute value of x).

10. The proof requires
2 cases
4 cases
5 cases

11. Which of the following is not one of the required cases?
x ≥ 0 and y < 0
x < 0 and y < 0
x = 0 and y = 0


Self Check:

Complete the proof by cases started in the Quick Test above.
(Note: This is exercise 5 in Section 1.7 in the Rosen text.)


Proofs of Equivalence
So far, we have used truth tables to prove equivalence. Instead, we could convert equivalence (or the biconditional) into the two conditionals and use the proof techniques we have covered to prove that both are true. This is based on the tautology: (p ↔ q) ↔ [(p → q) ∧ (q → p)]. So this is a particular type of proof by cases.

Example 6:
Prove the equivalence ¬(p → q) ↔ (p ∧ ¬ q).
Direct proof. We need to prove both [¬(p → q) → (p ∧ ¬ q)]

StepStatementReason
1.¬(p → q) → (p ∧ ¬ q)Given
2.¬(¬p ∨ q) → (p ∧ ¬ q)Equivalence of 1
3.(p ∧ ¬ q) → (p ∧ ¬ q)DeMorgan's Law of 2
4.¬ (p ∧ ¬ q) ∨ (p ∧ ¬ q)Equivalence of 3
5.TNegation Law of 4
and [(p ∧ ¬ q) → ¬(p → q)].
StepStatementReason
1.(p ∧ ¬ q) → ¬(p → q)Given
2.(p ∧ ¬ q) → ¬(¬p ∨ q)Equivalence of 1
3.(p ∧ ¬ q) → (p ∧ ¬q)DeMorgan's Law of 2
4.¬(p ∧ ¬ q) ∨ (p ∧ ¬q)Equivalence of 3
5.TNegation Law of 4

QED

Self Check:

Show that these statements about the integer x are equivalent: (1) 3x+2 is even, (2) x+5 is odd, (3) x2 is even.
(Note: This is exercise 31 in Section 1.6 in the Rosen text.)


Exhaustive proofs proceed by proving all possible cases, when there are a small number of cases.

Example 7:
A version of the famous game theory problem Prisoner's Dilemma can be explained as follows.

Two people have been arrested for a crime. They are put in separate cells, and each is offered a chance to betray the other for a reduced sentence. Naturally the prisoners are not allowed to talk to each other. The offers can be summarized in this table:
Prisoner B Stays SilentPrisoner B Betrays
Prisoner A Stays SilentEach serves 6 monthsPrisoner A: 10 years
Prisoner B: goes free
Prisoner A BetraysPrisoner A: goes free
Prisoner B: 10 years
Each serves 5 years
By examining all possible cases, we can prove that a selfish criminal is best off in the worst case when he/she chooses "betray".
  1. Prisoner A Stays Silent: in the worst case, Prisoner B betrays and A gets 10 years.
  2. Prisoner A Betrays: in the worst case, Prisoner B also betrays and each serves 5 years.
  3. Prisoner B cases are symmetric with above two.
Since 5 years is less than 10 years, the best self-interested strategy for both prisoners is to betray.

Proofs by Counterexample:
The idea of counter examples was discussed in the second tutorial. We can turn it into a proof technique -- assume we want to prove some statement false, we can do so by finding an example that violates the statement.

The example in the second tutorial can be made into a proof be re-stating it as follows:
Prove that ∀x ∈ R x≥ 0 is false.
This statement can be proven by finding an example of a Real number that is negative, which is pretty easy.


Quick Test

For each of the following statements, determine whether it is true or whether a counterexample exists.

12. If x is a real number, then there exists a real number y such that xy=1.
True
Counterexample

13. The sum of two odd integers is even.
True
Counterexample


Existence Proofs are like proofs by counterexample. The idea is to prove statements that "there exists some value such that" by finding a value that has the property. So for example, we can prove that prime numbers exist by giving an example of one.

Proof Strategies and Mistakes

Read the last part of Section 1.6 in Rosen to learn about mistakes in proofs. Certain mistakes happen occur because one of the steps does not (always) follow from those that precede it. For instance, when a division occurs the proof may quietly assume that the divider is not zero, but this assumption is incorrect.

Finding a proof can be difficult. Some famous conjectures (such as Fermat's last theorem -- see Section 1.7 in Rosen for more on this one) have been taken without proof for a considerable length of time. We can suggest some rules of thumb (called heuristics in the artificial intelligence community) for selecting proof techniques are:

Once you have decided on a proof technique, it can still be difficult to know how to proceed. One strategy is to look for a proof of a similar statement and then adapt that proof. For example, you will see in the book several proofs involving odd and even numbers where these numbers are re-written as 2k for even or 2n+1 for odd. This is a well known approach for relating these numbers.

Quick Test

What kind of proof technique should you select to prove the following statements?

14. Prove that n2+1≥2n when n is a positive integer with 1≤n≤4.
Direct proof
Proof by cases
Proof by counterexample

15. Prove that the sum of two odd integers is even.
Direct proof
Proof by cases
Proof by counterexample

16. Prove that the sum of an irrational number and a rational number is irrational.
Proof by contradiction
Proof by cases
Existence proof


Self Check:

Prove the three statements listed in the quick test above.
(Note: The first is exercise 1 and the third is exercise 11 in Section 1.7 in the Rosen text.)