In this section we will learn two new proof techniques, contradiction and contrapositive. Both proof techniques rely on being able to negate mathematical statements.
As we add more proof techniques, it is important to realize that you are not expected to know which technique to use when you start a proof. Proof-writing often takes some trial and error. First try a direct proof, if you get stuck, you may think about whether breaking your set into cases will help, or whether negating a statement will make it easier to use. It is also quite possible that different methods can be used to prove the same statement.
The basic idea behind proof by contradiction is that if you assume the statement you want to prove is false, and this forces a logical contradiction, then you must have been wrong to start. Thus, you can conclude the original statement was true. By a logical contradiction, we generally mean a statement that must be both true and false at the same time. When writing a proof by contradiction you must be very careful in your logical reasoning. It must be clear that you reach a contradiction though careful logical deduction.
Show you reach some logical contradiction. This means you have a statement in your proof that must be both true and false.