This week, I was taught different types of proofs such as proof using contrapositive, proof using contradiction, proof for existence and proof about sequences. Among them, the hardest to grasp and understand is proof by contradiction. At first, I don’t know how to establish a contradiction and when should I apply it in proofs. However, as more examples are being shown in class, I realized that there is no such thing as the perfect timing to use proof by contradiction, because it can be used whenever.
Generally, proof by contradiction is used when I want to prove the conclusion without establishing or knowing anything about the antecedent. To be more specific, to arrive at a possible contradiction, I first have to identify the statements that I already know is true. Then I prove “P implies Q” by transforming the implication to its contrapositive, which is “not Q implies not P” and assume the conclusion (Q) to be false. I then write down some steps that leads to “not P”, which thus proves that a contradiction exists since P is previously established to be true.
A quick example to demonstrate proof by contradiction is to prove the statement “there are infinitely many natural numbers.”. First, to derive a contradiction, assume that there is a finite number of natural numbers (which is not Q). If this supposition is true, then there must exist a largest natural number x such that no other natural numbers are greater than it. However, a contradiction is generated since if I double x, I get another natural number y = 2x (y is a natural number because natural numbers are closed under multiplication) that is greater than x (since 2 > 1). Hence, there does not exist a largest natural number x, and I arrived at a contradiction by assuming not Q. As a result, the statement “there are infinitely many natural numbers” is true.
In conclusion, proof by contradiction is a great technique to use when one is not sure what the antecedent is in the statement.
No comments:
Post a Comment