Proofs by Contradiction

• Read carefully pages 124 through 132 (sections 5.2, 5.3)
• Some key questions to answer (try these without looking at the book, but after you’ve read the book):
  1. Describe how proof by contradiction works. What kinds of statements is it suited for?
  2. If we are trying to prove a statement \(\forall x,\,P(x)\Rightarrow Q(x)\), how would a proof by contradiction go, and what logical equivalence is it based on?
  3. Provide examples of proofs by contradiction.
  4. Reflect on the differences and similarities between proof by counterexample and proof by contradiction.
  5. Study in particular results 5.15 and 5.16.
  6. Make sure you think through the “three prisoners problem” and its solution. Then consider the following variation:
     • Three prisoners are lined up, so the first prisoner can see the two others, the second prisoner can see the third but not the first, and the third prisoner cannot see any of the other two. The warden has at his disposal 5 hats, three red and two blue. He then places one hat one each prisoner, in a way that they can’t see what color hat they have.
     • He then asks the first prisoner, who can see the two prisoners ahead of him, if he knows what color hat he has. The prisoner says no.
     • He then goes to the second prisoner, who can only see the third prisoner but also heard the first prisoner’s reply. He asks him if he knows what color hat he has, and the prisoner says no.
     • Finally he goes to the third prisoner, who can’t see the other two but heard their responses. He asks him if he knows what color hat he has, and the prisoner says YES!
     • What color is the prisoner’s hat?
• Practice problems from section 5.2 (page 138): 5.10, 5.13, 5.18, 5.19, 5.26, 5.27
• Practice problems from section 5.3 (page 139): 5.34, 5.35, 5.38