Proof by contradiction

The reductio ad absurdum (from the Latin for reduction to the contrary Chime, absurdity, incongruity, Senseless ) is a final figure and proof technique in logic. The reductio ad absurdum of a statement is refuted by showing that from it a logical contradiction or conflict with an already approved thesis follows.

As proof technique is the reductio ad absurdum of the term " substantial evidence " or " proof by contradiction " known. The indirect evidence is characterized in that the statement to be proved is not directly derived, but that one ( that is, the assumption that the statement not the case ) refuted their contradictory opposite. In the classical, two-valued logic in which every statement is either true or false, is this refuting the contrary a statement showed that the affected statement is correct.

Intuitive explanation and justification

A simple example: To show that not all people are Greeks, it is first assumed the exact opposite, namely, that all men are Greeks. From this assumption follows, for example, that Cicero was a Greek. It is known, however, that Cicero was not a Greek ( but Romans ). That Cicero was but at the same time both a Greek and not a Greek, is a contradiction. This was the statement that all men are Greeks attributed to a contradiction ( reductio ad absurdum ), and as shown, that not all people are Greeks.

A less simple example of a reductio ad absurdum - and perhaps the most famous example at all for such - is proof to theorem of Euclid, in which it is shown that there can be no largest prime number ( it thus to each prime number is a greater ) by the assumption admit it is a largest refuted.

The indirect evidence can be intuitively justified as follows: If you can derive a contradiction from an assumption applies: If the assumption is true, the contradiction true. A contradiction can never be true. The assumption may not be true, therefore, that must be wrong.

Formal representation

Formally, the proof by contradiction represented as follows:

Gilt and then:.

Read: Does that from the set of statements, together with the statement, both the statement and the statement is not followed, then it follows from non-.

This relationship is known in the calculus of natural deduction as a negation introduction.

Classical and intuitionistic proof by contradiction

From the reductio ad absurdum, there is a second form, which is important in the conflict between classical and intuitionistic logic:

Gilt and then:.

The difference between the two forms is that in the first of a statement and a contradiction to the negation of the statement is closed, while in the second from the negation and a contradiction to the statement itself is closed. The second form can be reduced to the short formula: An assertion is proven if a contradiction from its negation can be derived.

The first form can be converted by means of the classical negation elimination in the second:

Applies, as is also true:.

As this law but it is just classic, not intuitionistically valid, the second form is not intuitionistic universal.

Optionally, the second form can also be derived with the law of excluded middle from the first. This set is also but not intuitionistically valid.

The rejection of the second form of proof by contradiction with the result that in the intuitionistic mathematics the existence of certain objects of classical mathematics is not accepted (see constructivism).