Beginning Rigorous Mathematics/Proving basic statements

From Wikibooks, open books for an open world
Jump to: navigation, search

The use of logic in proving mathematical statements[edit]

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.

Implications[edit]

Looking at the truth table for implications we see that P\Rightarrow Q is always true when P is false. When P is true, P\Rightarrow Q is true, only when Q is true and false otherwise. Therefore, proving an implication we only need to prove (by using the rules of logical inference) that Q is true when we assume P to be true.

Beginning a proof an implication P\Rightarrow Q, we will always write "Let P be true." or just "Let P", and then use the above rules of inference to derive Q.

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.

Equivalence[edit]

As we have shown above, the equivalence P\Leftrightarrow Q is logically equivalent to (P\Rightarrow Q)\land(Q\Rightarrow P), so proving that both implications, P\Rightarrow Q and Q\Rightarrow P, are true (as explained in the previous paragraph) is sufficient to assert the truth of P\Leftrightarrow Q (by adjunction).

Writing the proof of an equivalence is always done in two parts. We will write "We first prove P\Rightarrow Q" and then proceed to prove the statement, after which we write "Conversely, we now prove Q\Rightarrow P" 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)[edit]

Proof by contradiction is a very important method of proof. Proving, by contradiction, that a statement P 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 P is false, therefore P must be true.

To begin a proof by contradiction we will write "We will prove that P is true. Suppose, to the contrary that \lnot P is true". Then by logical inference and the assumption we derive the truth of a statement Q which will clearly be false, at which point we will write "But Q is in contradiction with \lnot Q, therefore P must be true."