Mathematical proof

A proof is in mathematics recognized as error-free derivation of the correctness or incorrectness of a statement from a set of axioms that are assumed to be true, and other statements that are already proven. To clearly distinguish the proof of the valid conclusion, one also speaks of axiomatic proof.

More extensive evidence of mathematical theorems are usually divided into several small part of the evidence, see theorem and lemma.

In the proof theory, a branch of mathematical logic, proofs are formally regarded as derivatives and even regarded as mathematical objects in order to prove about the provability or unprovable sentences from given axioms themselves.

Constructive and non- constructive proofs

In a constructive proof of existence the solution, a method is either called itself, whose existence is to show or specified, which leads to the solution, that is, it is constructed a solution.

In a non - constructive proof is concluded that the existence of a solution based on properties. Sometimes even indirectly the assumption that there is no solution, leads to a contradiction, which implies that there is a solution. From such evidence does not indicate how to win the solution.

A simple example will illustrate this.

Claim: The function has a zero in the interval.

Constructive Proof: Let. Then we have. Furthermore, in the interval. Thus the assertion is proved. The zero point is even specified.

Non- constructive proof: is continuous. Furthermore, and. After the intermediate value theorem for continuous functions, the assertion follows. However, over the value of the zero of this evidence provides no information.

Methods of proof

Some mathematical theorems or logical rules of inference can be used for a variety of evidence and influence the structure of the proof particularly strong. The systematic approach to the application of these then called method of proof, proof methods, proof technique or proof principle. The validity of a proof method itself requires a proof, in the context of the axioms and logic valid to be ( as is the reductio ad absurdum (see below) in its basic form is not in intuitionistic logic, and a transfinite induction on all cardinal numbers only on the assumption the well-ordering theorem possible). Here is a selection of standard methods of proof:

Reductio ad absurdum

In an indirect proof ( reductio ad absurdum, proof by contradiction ), one can show that a contradiction arises if the assertion to be proved would be wrong. For this purpose, it is believed that the assertion is false, and then applies the same methods as in the direct proof. That this leads to a contradiction, then the claim can not be wrong, so it must be right ( law of excluded middle ). Is Important ( and by no means self-evident! ) Condition for the validity of a proof by contradiction, that in the underlying system, the statement can not be both true and false (no contradictions ).

A classic example of a proof by contradiction is the Euclidean proof that there are infinitely many prime numbers.

Simple proofs that do not operate this way of conclusion are referred to as direct evidence in distinction from it. An example:

Proposition 1: The square of an odd natural number n is always odd.

Proof: Let n be an odd natural number. Then n can be represented as, where k is a natural number or zero. It follows using the first binomial formula

From the ability to present it follows that is odd.

Now an example of a reductio ad absurdum, the previous statement is used:

Assertion 2: If the root of an even natural number n is a natural number, so this is even.

Proof: Suppose that would be odd. Then, because of the already proved assertion 1 is also odd, and this is a contradiction to the assumption that n is even. So the assumption made is false, that is, is straight.

Another classic example:

Assertion 3: The number is irrational.

Proof: Suppose that this number would be rational. Then they can be represented as a fraction, where l and k are natural numbers, and without limiting the generality are relatively prime (otherwise you can shorten the break so far up that's the case ). It follows by squaring

Consequently, an even number. Since the root of an even square number also is even ( assertion 2), l is even just so is a natural number. By rearranging the last equation is obtained

This shows that k is even and therefore are natural numbers. So l and k are both even and both have thus the divider 2 This means that l and k are not relatively prime - in contradiction to the assumption of their coprimality. So is also the original assumption is rational, wrong.

Mathematical induction

The proof by induction is a frequent practice to the proof of sentences of the form " For every natural number ... ". For this purpose, one shows first that the statement for (or even a different initial value ) is valid, and then that they are always also applies if it is for one. The induction can be illustrated with a domino effect. It makes the stones so on, that if one falls over, always falling over the next (→ ), and pushes the first stone at ().

A simple example:

Claim: It is true for all natural numbers:

Proof:

So the assertion is also true for n 1, so that the statement on the induction principle is proved.

Complete case analysis

In the proof of a statement by complete case analysis, a finite number of cases is considered, the overlap in their entirety all possible cases and each of which allows a simpler treatment of the problem.

Claim: Every prime number has the form of a natural number.

Proof: We distinguish the following four cases for the number of which is always exactly one occurs:

In the first of these cases is divisible by 4 and hence not prime, in the third case is divisible by 2 and thus also not a prime number. So one of the two or four cases must occur, ie has the form of a natural number.

It should be noted that the case distinction indeed must be complete, but the cases studied do not have to be mutually exclusive.

Diagonal method

The diagonal method developed by Georg Cantor to prove two specific statements. They have proven themselves since as a general proof methods.

The first Cantor's diagonal method is a direct proof of the countability of a set. It is shown that it is possible to assign to each element of the volume to be examined is a natural number.

The second Cantor's diagonal method is an indirect proof of the uncountable amount. The contrary, It is believed, namely that the amount is countable. Then a contradiction is derived, so it must be dropped from this assumption.

Pigeonhole principle

The pigeonhole principle goes back to the German mathematician Dirichlet and can be formulated very clearly: If one distributes objects on drawers, then located in at least one drawer at least two objects.

Transfinite induction

In the transfinite induction, the induction is generalized to arbitrary well-ordered classes.

93695
de