Reducció a l'absurd

De Viquipèdia
Dreceres ràpides: navegació, cerca

En matemàtica, la demostració per contradicció o de reducció a l'absurd (o en llatí, reductio ad absurdum) es tracta d'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[modifica | modifica el codi]

Provar que existeixen infinits nombres primers.

Prova: suposem, pel mètode de contradicció, que existeixen n (una quantitat finita) de nombres primers p1 < p2 < ... < pn.

Considerem el número x = p1·p2·...·pn + 1. El nombre x no és divisible per cap dels nombres p1, p2, ..., pn (el residu de la divisió sempre és 1). Aleshores, o bé x és nombre primer o bé existeix un nombre entre pn 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[modifica | modifica el codi]

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.