Reducció a l'absurd

En matemàtica, la demostració per contradicció o per reducció a l'absurd (o en llatí, reductio ad absurdum) és un mètode indirecte. Aquest tipus de prova es fa assumint com a veritat el contrari del que volem provar, i aleshores arribant a una contradicció. En la lògica matemàtica, la prova de reducció a l'absurd es representa com:

Si

$S\cup \{p\}\vdash F$

Aleshores

$S\vdash \neg p$

o bé

Si

$S\cup \{\neg p\}\vdash F$

Aleshores

$S\vdash p$

I és p la proposició que volem provar o desaprovar i S és el conjunt d'axiomes donats com a certs i F la contradicció lògica.

La prova per contradicció és molt usada en teoremes d'existència. En alguns teoremes, només es coneix aquest mètode per demostrar-los, com en el cas de l'argument de diagonalització de Cantor, publicat el 1891 per Georg Cantor, que demostra la no enumerabilitat dels nombres reals.

Exemple

Provar que existeixen infinits nombres primers.

Prova: suposem, pel mètode de contradicció, que existeixen n (una quantitat finita) de nombres primers p₁ < p₂ < ... < p_n.

Considerem el número x = p₁·p₂·...·p_n + 1. El nombre x no és divisible per cap dels nombres p₁, p₂, ..., p_n (el residu de la divisió sempre és 1). Aleshores, o bé x és nombre primer o bé existeix un nombre entre p_n i x tal que divideix x (per exemple, en el cas x = 2·3·...·11·13 + 1, x no és primer, però el més petit dels seus factors és 59, que és més gran que 13). En qualsevol dels dos casos, hem trobat un nombre primer més gran del nombre que havíem suposat com a màxim nombre primer, i això contradiu la nostra hipòtesi inicial que existeixen només n nombres primers.

Aleshores, la nostra hipòtesi inicial està errada i, per tant, existeixen infinits nombres primers.

Altres utilitats possibles

A part de les seves aplicacions per a la ciència i les matemàtiques, el mètode de reducció a l'absurd també és utilitzat (si bé per altres mètodes no científics) per la dialèctica i per la religió, com a aparents demostracions de certs dogmes. Entre els filòsofs que utilitzaren d'aquesta forma aquest mètode de deducció, hi ha Sòcrates, Procle i Anselm de Canterbury.