Proof

A proof is a mathematical argument used to verify the truth of a statement. This usually takes the form of an orderly series of statements based upon axioms. When a statement has been proven true, it is considered to be a theorem.

Proofs generally use an implication as the statement to prove. The goal of a proof is to show that for all values of a given number, object, etc., that if a given condition is met, the conclusion will be true. For example, the implication, "for all natural numbers n, if n is a prime greater than 2, then n is odd" gives the domain of the implication (n is a natural number), a condition or hypothesis (n is a prime greater than 2) and the conclusion (n is odd).

Methods of proof

There are many ways to go about proving any one statement. However, some statements are more conducive to a particular method.

Direct proof

A direct proof of an implication proceeds in an orderly fashion from the hypothesis, using logical arguments to get directly from the hypothesis to the conclusion.

Proof by contradiction

Proof by contradiction assumes a true hypothesis and false conclusion and shows how this presents a contradiction.

Indirect proof

An indirect proof follows the same method as the direct proof, but it uses the contrapositive of the implication (if the conclusion is false, then the hypothesis is false).

Mathematical induction

Main article: Mathematical induction

Mathematical induction seeks to show by implication that if a value is true for a given natural number, it is true for all natural numbers greater than that number. Induction is generally only applied to the natural numbers. The induction principle proceeds as follows:

Let P be a predicate with the natural numbers as its domain. Suppose that P has these two properties:

• $P\left(1\right)$ is true (or $P\left(0\right)$, if $0$ is included as a natural number)
• For all natural numbers $k$, if $P\left(k\right)$ is true, then $P\left(k+1\right)$ is true.

Then $P\left(n\right)$ is true for all natural numbers $n$.

Complete induction

Complete induction is similar to mathematical induction, except that the hypothesis of the implication in the second property of implication is not only for P(n), but for all values less than or equal to n.

List of proofs

Please see our list of proofs.