Proof Technique CD Contradiction
¶Another proof technique is known as “proof by contradiction” and it can be a powerful (and satisfying) approach. Simply put, suppose you wish to prove the implication, “If \(A\text{,}\) then \(B\text{.}\)” As usual, we assume that \(A\) is true, but we also make the additional assumption that \(B\) is false. If our original implication is true, then these twin assumptions should lead us to a logical inconsistency. In practice we assume the negation of \(B\) to be true (see Proof Technique N). So we argue from the assumptions \(A\) and \(\text{not}(B)\) looking for some obviously false conclusion such as \(1=6\text{,}\) or a set is simultaneously empty and nonempty, or a matrix is both nonsingular and singular.
You should be careful about formulating proofs that look like proofs by contradiction, but really are not. This happens when you assume \(A\) and \(\text{not}(B)\) and proceed to give a “normal” and direct proof that \(B\) is true by only using the assumption that \(A\) is true. Your last step is to then claim that \(B\) is true and you then appeal to the assumption that \(\text{not}(B)\) is true, thus getting the desired contradiction. Instead, you could have avoided the overhead of a proof by contradiction and just run with the direct proof. This stylistic flaw is known, quite graphically, as “setting up the strawman to knock him down.”
Here is a simple example of a proof by contradiction. There are direct proofs that are just about as easy, but this will demonstrate the point, while narrowly avoiding knocking down the straw man.
Theorem: If \(a\) and \(b\) are odd integers, then their product, \(ab\text{,}\) is odd.
Proof: To begin a proof by contradiction, assume the hypothesis, that \(a\) and \(b\) are odd. Also assume the negation of the conclusion, in this case, that \(ab\) is even. Then there are integers, \(j\text{,}\) \(k\text{,}\) \(\ell\) so that \(a=2j+1\text{,}\) \(b=2k+1\text{,}\) \(ab=2\ell\text{.}\) Then
Again, we do not offer this example as the best proof of this fact about even and odd numbers, but rather it is a simple illustration of a proof by contradiction. You can find examples of proofs by contradiction in Theorem RREFU, Theorem NMUS, Theorem NPNT, Theorem TTMI, Theorem GSP, Theorem ELIS, Theorem EDYES, Theorem EMHE, Theorem EDELI, and Theorem DMFE, in addition to several examples and solutions to exercises.