Reductio ad absurdum

The Reductio ad absurdum (from Latin for tracing back to what sounds bad, inconsistent, incongruous, meaningless ) is a final figure and a proof technique in logic . In the Reductio ad absurdum, a statement is refuted by showing that it leads to a logical contradiction or a contradiction to an already recognized thesis .

As proof technology, the reductio ad absurdum is known as " indirect evidence " or " proof by contradiction ", " proof by contradiction " known. This indirect proof is characterized by the fact that one does not derive the statement to be proven directly, but that its adversarial opposite (i.e. the assumption that the statement is incorrect) is refuted. In classical, two-valued logic , in which every statement is either true or false, this refutation of the opposite of a statement shows that the statement in question is correct.

Intuitive explanation and justification

A simple example: In order to show that not all people are Greek, it is first assumed that all people are Greek. From this assumption it follows, for example, that Cicero was a Greek. However, it is known that Cicero was not a Greek (but a Roman). The fact that Cicero was both a Greek and not a Greek is a contradiction. Thus the statement that all people are Greek was reduced to a contradiction (reductio ad absurdum) and thus showed that not all people are Greek.

A less simple example of a reductio ad absurdum - and perhaps in addition to the proof of the irrationality of the square root of 2 in Euclid the best example ever of such - is proof of Euclid's theorem , which shows that there is no largest prime number give can (that for every prime there is a larger one) by refuting the assumption that there is a largest one. Proofs of contradiction were often used by Euclid and can already be found in the proof of the theorem of Dinostratos , handed down by Pappos .

The indirect proof can be justified intuitively as follows: If a contradiction can be derived from an assumption, the following applies: if the assumption is true , the contradiction is also true. But a contradiction can never be true. The assumption cannot therefore be true, so it must be false.

Formal representation

Formally, the proof of contradiction can be presented as follows:

Applies and , then: . ${\displaystyle \Gamma \cup \{\mathrm {A} \}\vdash \mathrm {B} }$ ${\displaystyle \Gamma \cup \{\mathrm {A} \}\vdash \neg \mathrm {B} }$ ${\displaystyle \Gamma \vdash \neg \mathrm {A} }$

Read: If it is true that from the set of statements together with the statement both the statement and the statement do not follow, then it follows from non- . ${\displaystyle \Gamma }$ ${\displaystyle \mathrm {A} }$ ${\displaystyle \mathrm {B} }$ ${\displaystyle \mathrm {B} }$ ${\displaystyle \Gamma }$ ${\displaystyle \mathrm {A} }$

This connection is also known as the introduction of negation in the calculus of natural inference .

Classical and intuitionist contradiction proof

There is a second form of reductio ad absurdum, which is important in the discussion between classical and intuitionist logic:

Applies and , then: . ${\displaystyle \Gamma \cup \{\neg \mathrm {A} \}\vdash \mathrm {B} }$ ${\displaystyle \Gamma \cup \{\neg \mathrm {A} \}\vdash \neg \mathrm {B} }$ ${\displaystyle \Gamma \vdash \mathrm {A} }$

Read: If it is true that the statement set together with the statement does not follow - both the statement and the statement not - then it follows from . ${\displaystyle \Gamma }$ ${\displaystyle \mathrm {A} }$ ${\displaystyle \mathrm {B} }$ ${\displaystyle \mathrm {B} }$ ${\displaystyle \Gamma }$ ${\displaystyle \mathrm {A} }$

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

The first form can be converted into the second by means of the classic elimination of negation :

Applies , so shall also apply: . ${\displaystyle \Gamma \vdash \neg \neg \mathrm {A} }$ ${\displaystyle \Gamma \vdash \mathrm {A} }$

Since this law is only classically valid, not intuitionistically, the second form is also not generally valid intuitionistically.

Optionally, the second form can also be derived from the first using the sentence of the excluded third party . But this proposition is also not valid intuitionistically.

The rejection of the second form of contradiction proof has the consequence that in intuitionist mathematics the existence of certain objects of classical mathematics is not recognized (see also constructivism ).

Web links

Wikibooks: Math for non-freaks: Proof of contradiction  - learning and teaching materials

• Nicholas Rescher :  Entry in the Internet Encyclopedia of Philosophy .

Individual evidence

1. ^ Ivor Bulmer-Thomas, Article Dinostratus , Dictionary of Scientific Biography , Volume 4, p. 104