Proof by Contradiction

Return to List of Lectures

Previous Lecture

Misc

Feel free to use office hours or make appointments for anything you want to talk with me about, not only for grading.

Questions?

Proof by Contradiction

Section 3.3

Progress check 3.16.

Congruence (“n ≡ 2 (mod 4) ...”)?

• a ≡ b (mod n) means a = kn + b for some integer k
• Sundstrom: a ≡ b (mod n) means n divides (a-b), i.e., a-b = kn for integer k
• Thus, some examples of...
  
  • n congruent to 2 (mod 4): 2, 6, 10, 14, 18, 22, ...
  • n congruent to 3 (mod 6): 3, 9, 15, 21, ... (generally any n of the form 6k + 3)

Reading ideas:

• Proof by contradiction is based on the idea that x can only be true or false, not both
• So you can show that x is true by showing that x can’t be false
• Such a proof assumes x is false and then shows that this leads to contradiction
• The contradiction is often of the form “R and not R” for some statement R
• Such a contradiction means that x isn’t false, so x must be true
• Proof by contradiction is often used with conditional statements
• It can also be helpful when proving that something doesn’t exist
• When writing a proof by contradiction (or any method), say what method you’re using, e.g., contradiction, contrapositive, etc.

Question: What would be an example with a non-numeric conditional statement?

• This isn’t precisely a conditional statement, but it is a classic non-numeric proof by contradiction: Prove that the set of all sets doesn’t exist.
• Proof by contradiction: assume there is a set S which is the set of all sets.
• From S you can construct P = { x ∈ S | x ∉ x }, i.e, the set of all sets that don’t contain themselves
  
  • {} ∈ P, {1} ∈ P, ....
  • S ∉ P
• By the way P was constructed, all members of S are either in P or not in P.
• This applies to P itself (which is a set, and so a member of S), i.e., either P ∈ P or P ∉ P.
• Suppose P ∈ P. But to be in P, a set must not be in itself. So P must not be in P. This is a contradiction.
• Suppose P ∉ P. Then P satisfies the condition for being in P, i.e., not being in itself, and so P ∈ P. This is also a contradiction.
• In either case, a contradiction is unavoidable. Therefore the assumption that S exists must be false.

Problem Set

See handout.

Next

Continue discussing proof by contradiction, particularly via some more accessible examples.

No new reading.

Next Lecture