# Proof (math)

Exemplary, schematic structure of a proof

In mathematics, a proof is the derivation of the correctness or incorrectness of a statement from a set of axioms that are assumed to be true and other statements that have already been proven, recognized as being error-free . One therefore speaks of axiomatic proofs .

More extensive proofs of mathematical theorems are usually divided into several small partial proofs, see theorem and auxiliary theorem .

In proof theory , a branch of mathematical logic , proofs are formally understood as derivations and are themselves viewed as mathematical objects, for example to prove the provability or unprovability of sentences from given axioms themselves.

## Constructive and non-constructive evidence

### Evidence of existence

In the case of a constructive proof of existence , either the solution itself is named, the existence of which is to be shown, or a procedure is given that leads to the solution, that is, a solution is constructed .

In the case of a non-constructive proof , the existence of a solution is concluded based on properties. Sometimes even the indirect assumption that there is no solution leads to a contradiction, from which it follows that there is a solution. From such evidence it is not clear how to find the solution.

A simple example should make this clear.

Claim: The function with has at least one zero in the interval . ${\ displaystyle f}$${\ displaystyle f (x) = 2x-1}$${\ displaystyle [0,1]}$${\ displaystyle x_ {0}}$

Constructive proof: be . Then applies . Furthermore lies in the interval . Therefore the statement is proven. The zero is even indicated. ${\ displaystyle x_ {0} = 0 {,} 5}$${\ displaystyle f (x_ {0}) = 2 \ cdot x_ {0} -1 = 2 \ cdot 0 {,} 5-1 = 1-1 = 0}$${\ displaystyle x_ {0} = 0 {,} 5}$${\ displaystyle [0,1]}$${\ displaystyle x_ {0} = 0 {,} 5}$

Non-constructive proof: is continuous . Furthermore is and . After the intermediate value theorem for continuous functions the assertion follows. However, this proof does not provide any information about the value of the zero. ${\ displaystyle f}$${\ displaystyle f (0) = - 1 <0}$${\ displaystyle f (1) = 1> 0}$

### Set theory

In set theory based on the axiom system ZFC , proofs are called non-constructive if they use the axiom of choice . Because all other axioms of ZFC describe what sets exist or what can be done with sets, and give the constructed sets. Only the axiom of choice postulates the existence of some choice without specifying how that choice should be made. In the early days of set theory, the axiom of choice was highly controversial because of its non-constructive character ( mathematical constructivism deliberately avoids the axiom of choice), hence its special position not only in abstract set theory but also in proofs in other areas of mathematics . In this sense, all proofs using Zorn's lemma are considered non-constructive, since this lemma is equivalent to the axiom of choice.

All of the mathematics can essentially be built on ZFC and proven within the framework of ZFC. The working mathematician usually does not give an account of the fundamentals of set theory, only the use of the axiom of choice is mentioned, usually in the form of the lemma of Zorn. Further set theoretical assumptions are always given, for example when using the continuum hypothesis or its negation.

## Formal evidence

Formal proofs reduce the proof steps to a series of defined operations on strings. Such proofs can usually only be created with the help of a machine (see e.g. Coq (software) ) and are barely legible for humans, even just transferring the sentences to be proven into a purely formal language leads to very long, cumbersome and incomprehensible strings. A number of well-known sentences have since been formalized and their formal proof checked by machine. As a rule, however, mathematicians are satisfied with the certainty that their chains of arguments can in principle be transferred to formal proofs without actually carrying out this; they use the proof methods presented below.

## Evidence Methods

Some mathematical theorems or logical inference rules can be used for a variety of proofs and have a particularly strong influence on the structure of the proof. The systematic procedure for applying these is then referred to as the proof method , proof procedure , proof technique or proof principle . The validity of a method of proof itself requires a proof to be valid in the context of the axioms and logic (such as the reductio ad absurdum (s. U.) In the basic form not is intuitionistic logic , and a transfinite induction on all cardinals only under condition of well-ordering theorem possible ). Here is a selection of standard proof methods:

### Direct evidence

For a direct proof ( direct conclusion ) one takes a proposition that has already been proven to be correct (premise) and derives the proposition to be proven (conclusion) from it through logical conclusions. As a simple example, consider the following:

Claim: The square of an odd natural number is always odd. ${\ displaystyle n}$

Proof: Let it be an odd natural number. Then can be represented as , where is a natural number or zero. From this follows with the help of the first binomial formula${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n = 2k + 1}$${\ displaystyle k}$

${\ displaystyle n ^ {2} = (2k + 1) ^ {2} = 4k ^ {2} + 4k + 1 = 2 \ cdot (2k ^ {2} + 2k) +1}$.

From the possibility of representing this, it follows that is odd. ${\ displaystyle n ^ {2}}$${\ displaystyle n ^ {2}}$

### Indirect evidence

In the case of an indirect proof ( reductio ad absurdum , proof of contradiction ) one shows that a contradiction arises if the assertion to be proven is false. To do this, assume that the claim is false and then use the same methods as for direct proof. If a contradiction arises from this, then the assertion cannot be false, so it must be correct ( theorem of the excluded third party ). An important (and by no means self-evident!) Prerequisite for the validity of a contradiction proof is that in the underlying system the statement cannot be both true and false at the same time ( consistency ). A classic contradiction proof is the Euclidean proof that there are infinitely many prime numbers .

Now an example of a reductio ad absurdum:

Claim: If the root of an even natural number is a natural number, then this is even. ${\ displaystyle n}$

Proof: Suppose would be odd. Then is also odd (see example above for direct proof), and that contradicts the assumption that is even. So the assumption made is wrong, that is, is straight. ${\ displaystyle {\ sqrt {n}} = k}$${\ displaystyle k ^ {2} = n}$${\ displaystyle n}$${\ displaystyle {\ sqrt {n}}}$

Another classic example:

Claim: The number is irrational . ${\ displaystyle {\ sqrt {2}}}$

Proof: Suppose this number was rational. Then you can represent it as a fraction , with and natural numbers and without restriction of generality being coprime (otherwise you can shorten the fraction until this is the case). From this it follows by squaring ${\ displaystyle {\ sqrt {2}} = {\ tfrac {l} {k}}}$${\ displaystyle l}$${\ displaystyle k}$

${\ displaystyle 2 = {\ frac {l ^ {2}} {k ^ {2}}} \,}$ , so ${\ displaystyle \, l ^ {2} = 2k ^ {2}.}$

Hence is an even number. Since the root of an even square number is also even (see previous claim), is itself even, so is a natural number. Transforming the last equation gives ${\ displaystyle l ^ {2}}$${\ displaystyle l}$${\ displaystyle {\ tfrac {l} {2}}}$

${\ displaystyle k ^ {2} = {\ frac {l ^ {2}} {2}} = 2 \ cdot \ left ({\ frac {l} {2}} \ right) ^ {2}.}$

This shows that and therefore are also natural numbers. So and both are even and thus both have the factor 2. So and are not coprime - in contradiction to the assumption of their coprime. So the original assumption that is rational is also wrong. ${\ displaystyle k ^ {2}}$${\ displaystyle k}$${\ displaystyle l}$${\ displaystyle k}$${\ displaystyle l}$${\ displaystyle k}$${\ displaystyle {\ sqrt {2}}}$

### Complete induction

Illustration of complete induction

Proof by complete induction is a method that is often used to prove sentences of the form “For every natural number ...”. To do this, one shows first that the statement applies to (or another initial value ), and then that it always applies to if it applies to a . Complete induction can be illustrated with a domino effect . The stones are set up in such a way that if one falls over, the next one always falls over ( → ), and the first stone is knocked over ( ). ${\ displaystyle n}$${\ displaystyle n = 0}$${\ displaystyle n_ {0}}$${\ displaystyle n + 1}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n + 1}$${\ displaystyle n = 0}$

A simple example:

Claim: The following applies to all natural numbers :${\ displaystyle n}$${\ displaystyle 1 + 3 + \ dotsb + (2n + 1) = (n + 1) ^ {2}}$

Proof:

1. The assertion applies to : is a true statement.${\ displaystyle n = 0}$${\ displaystyle (2 \ cdot 0 + 1) = 1 = (0 + 1) ^ {2}}$
2. The assertion is valid for a . For one examines the sum${\ displaystyle n}$${\ displaystyle n + 1}$
${\ displaystyle 1 + 3 + \ dotsb + (2n + 1) + (2n + 3)}$
Since the assertion is valid, it follows${\ displaystyle n}$
{\ displaystyle {\ begin {aligned} 1 + 3 + \ dotsb + (2n + 1) + (2n + 3) & = (n + 1) ^ {2} + (2n + 3) \\ & = (n +1) ^ {2} +2 (n + 1) +1 \\ & = ((n + 1) +1) ^ {2} \ end {aligned}}}
So the assertion also holds for , thus the statement according to the induction principle is proven.${\ displaystyle n + 1}$

### Complete case distinction

In the case of a proof by complete case distinction (English proof by exhaustion "by exhaustion"), each of the possible cases is considered individually. The number of possible cases must therefore be finite.

Claim: Every prime number has the form with a natural number . ${\ displaystyle p \ geq 3}$${\ displaystyle p = 4 \ cdot k \ pm 1}$${\ displaystyle k}$

Proof: One distinguishes the following four cases for the number , of which exactly one occurs: ${\ displaystyle p}$

1. ${\ displaystyle p = 4k}$
2. ${\ displaystyle p = 4k + 1}$
3. ${\ displaystyle p = 4k + 2}$
4. ${\ displaystyle p = 4k + 3 = 4 (k + 1) -1}$

In the first of these cases it is divisible by 4 and therefore not a prime number, in the third case it is divisible by 2 and therefore also not a prime number. So has one of the cases occur two or four, that is, has the form of a natural number . ${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle p = 4 \ cdot k \ pm 1}$${\ displaystyle k}$

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

### Diagonal method

The diagonal methods were developed by Georg Cantor to prove two special statements. They have since proven themselves as general methods of proof.

The first Cantor diagonal method is a direct proof of the countability of a set. It is shown that a natural number can be assigned to each element of the set to be examined.

The second Cantor diagonal method is an indirect proof for the uncountability of a set. So the opposite is assumed, namely that the set is countable. Then a contradiction is derived from this assumption, so that it has to be dropped.

### Drawer principle / dovecote principle

The drawer principle goes back to the German mathematician Dirichlet and can be formulated very clearly: If you distribute objects in drawers, then there are at least two objects in at least one drawer. As an example we consider: ${\ displaystyle n + 1}$${\ displaystyle n}$

Assertion : Has at least elements, so there is with . ${\ displaystyle A \ subset \ {1,2, \ ldots, 2n \}}$${\ displaystyle n + 1}$${\ displaystyle a, b \ in A}$${\ displaystyle a | b}$

Proof : All elements from have the shape with an odd number . Of these, there are only different in , so that an odd number must appear twice in the above decomposition of the at least numbers from (this is the drawer principle). Hence contains two numbers and with the same odd number . Apparently the smaller one divides the larger one. ${\ displaystyle A}$${\ displaystyle 2 ^ {k} m}$${\ displaystyle m}$${\ displaystyle n}$${\ displaystyle \ {1,2, \ ldots, 2n \}}$${\ displaystyle n + 1}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle 2 ^ {k} m}$${\ displaystyle 2 ^ {l} m}$${\ displaystyle m}$

### Transfinite induction

In the case of transfinite induction , the complete induction is generalized to any well-ordered classes .

Often one has to do with statements about all ordinal numbers . As with the complete induction in presented above , one has to prove the claim for the first ordinal number 0, and then that, if the claim is assumed for an ordinal number, it also holds for its successor. In contrast to the induction above, one also has to show that the assertion also applies to every Limesordinal number if it applies to all smaller ordinal numbers. If you do without this additional part, the transfinite induction only works below the first ordinal limit, i.e. only for the ordinal numbers . One then obtains the usual full induction in the natural numbers, because these are the ordinal numbers up to the first Limesordinal number. ${\ displaystyle \ mathbb {N}}$${\ displaystyle 0,1,2, \ ldots}$