Types of Proofs

Proof by Construction  

       In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object with certain properties by creating or providing a method for creating such an object. This is in contrast to a nonconstructive proof (also known as an existence proof or pure existence theorem) which proves the existence of a mathematical object with certain properties, but does not provide a means of constructing an example.

      Many nonconstructive proofs assume the non-existence of the thing whose existence is required to be proven, and deduce a contradiction. The non-existence of the thing has therefore been shown to be logically impossible, and yet an actual example of the thing has not been found. Nearly every proof which invokes the axiom of choice is nonconstructive in nature because this axiom is fundamentally nonconstructive. The same can be said for proofs invoking König's lemma.

      Constructivism is the philosophy that rejects all but constructive proofs in mathematics. Typically, supporters of this view deny that pure existence can be usefully characterized as "existence" at all: accordingly, a non-constructive proof is instead seen as "refuting the impossibility" of a mathematical object's existence, a strictly weaker statement.

Proof by Contradiction

       In logic, proof by contradiction is a form of proof that establishes the truth or validity of a proposition by showing that the proposition being false would imply a contradiction. Since by the law of bivalence a proposition must be either true or false, and its falsity has been shown impossible, the proposition must be true.

In other words, to prove by contradiction that P, show that  or its equivalent . Then, since  implies a contradiction, conclude P.

       Proof by contradiction is also known as indirect proof, apagogical argument, reductio ad impossibile. It is a particular kind of the more general form of argument known as reductio ad absurdum.

       The method of proof by contradiction is to assume that a statement is not true and then to show that that assumption leads to a contradiction. In the case of trying to prove  this is equivalent to assuming that  That is, to assume that P is true and Q is false. This is known by its latin reductio ad absurdum (reduction to absurdity), since it ends with a statement that cannot be true.

Examples

A classic proof by contradiction from mathematics is the proof that the square root of 2 is irrational. If it were rational, it could be expressed as a fraction a/b in lowest terms, where a and b are integers, at least one of which is odd. But if a/b = √2, then a² = 2b². Therefore a² must be even. Because the square of an odd number is odd, that in turn implies that a is even. This means that b must be odd because a/b is in lowest terms.

On the other hand, if a is even, then a² is a multiple of 4. If a² is a multiple of 4 and a² = 2b², then 2b² is a multiple of 4, and therefore b² is even, and so is b.

So b is odd and even, a contradiction. Therefore the initial assumption—that √2 can be expressed as a fraction—must be false.

The Length of the hypotenuse is less than the sum of the lengths of the two legs

       The method of proof by contradiction has also been used to show that for any non-degenerate Right triangle, the length of the hypotenuse is less than the sum of the lengths of the two remaining sides. The proof relies on the Pythagorean theorem. Letting c be the length of the hypotenuse and a and b the lengths of the legs, the claim is that a + b > c. As usual, we start the proof by negating the claim and assuming that a + b ≤ c. The next step is to show that this leads to a contradiction. Squaring both sides, we have (a + b)² ≤ c² or, equivalently,a² + 2ab + b² ≤ c². A triangle is non-degenerate if each edge has positive length, so we may assume that a and b are greater than 0. Therefore, a² + b² < a² + 2ab + b² ≤ c². Taking out the middle term, we have a² + b² < c². We know from the Pythagorean theorem thata² + b² = c². We now have a contradiction since strict inequality and equality are mutually exclusive. The latter was a result of the Pythagorean theorem and the former the assumption that a + b ≤ c. The contradiction means that it is impossible for both to be true and we know that the Pythagorean theorem holds. It follows that our assumption that a + b ≤ c must be false and hence a + b > c, proving the claim.

Proof by induction 
       is a very powerful weapon in the number theorist's armory. The idea behind it, though, is a very simple one. Given a conjecture that we wish to prove, we start off by showing that, if it is true for some number n, then it must also be true for the numbern + 1. The second and final stage is to show that the conjecture is true for a given, preferably low, n. If we can do both, then we have effectively shown that the theorem is true for all n greater than or equal to the low value of n for which we proved a specific case. Typically, the second stage involves proving that the conjecture is true for n = 0 or n = 1. (If you prefer, of course, you can do these two steps the other way around. It doesn't matter, as long as you do them both!)
The canonical example of proof by induction is the formula for summation of integers between 1 and n. Before we get going, though, I can't resist relating a (probably true) story on the history of summation.


       Karl Friedrich Gauss (1777 - 1855) was one of the greatest mathematicians who ever lived. He was responsible for a considerable number of mathematical advances. The story is often told of his confounding his mathematics teacher whilst still at a very tender age. Teachers the world over will sympathise when I explain that this particular teacher just wanted a quiet morning. Perhaps he had a lot of marking to do, or perhaps he was still recovering from a cheerful night in the tavern. We don't know. But he can perhaps be forgiven for believing that he could occupy his class for a good part of the morning by asking them to add up all the integers from 1 to 100.


       A proof by induction is just like an ordinary proof in which every step must be justified. However it employs a neat trick which allows you to prove a statement about an arbitrary number n by first proving it is true when n is 1 and then assuming it is true for n=k and showing it is true for n=k+1. The idea is that if you want to show that someone can climb to the nth floor of a fire escape, you need only show that you can climb the ladder up to the fire escape (n=1) and then show that you know how to climb the stairs from any level of the fire escape (n=k) to the next level (n=k+1).

       If you've done proof by induction before you may have been asked to assume the n-1 case and show the n case, or assume the n case and show the n+1 case. This is the same as what I'm explaining here but I will use a different letter because I think it avoids some confusion when trying to figure out what each case is.