Beginning Rigorous Mathematics/Proving basic statements
The use of logic in proving mathematical statements
Theorems in rigorous mathematics often take on the form of implications or equivalences, therefore it is important to know how to go about prove such statements.
Looking at the truth table for implications we see that is always true when is false. When is true, is true, only when is true and false otherwise. Therefore, proving an implication we only need to prove (by using the rules of logical inference) that is true when we assume to be true.
Beginning a proof an implication , we will always write "Let be true." or just "Let ", and then use the above rules of inference to derive .
Often, conjunctions occur in the hypothesis of an implication when the truth of two or more statements imply the truth of the conclusion. Disjunctions sometimes occur in in the conclusion of implications as in the Fredholm alternative.
As we have shown above, the equivalence is logically equivalent to , so proving that both implications, and , are true (as explained in the previous paragraph) is sufficient to assert the truth of (by adjunction).
Writing the proof of an equivalence is always done in two parts. We will write "We first prove " and then proceed to prove the statement, after which we write "Conversely, we now prove " and then prove that statements.
Often one of the constituent implications of the equivalence is trivial, while the other is not.
Proof by contradiction (Reductio ad absurdum)
Proof by contradiction is a very important method of proof. Proving, by contradiction, that a statement is true, we will assume that it is false and then derive by the above rules of logical inference the truth of a statement which is clearly false. Since we assert consistency - that statements can only be either true or false - there must be a problem with our argument. This problem is the assumption that is false, therefore must be true.
To begin a proof by contradiction we will write "We will prove that is true. Suppose, to the contrary that is true". Then by logical inference and the assumption we derive the truth of a statement which will clearly be false, at which point we will write "But is in contradiction with , therefore must be true."