Prova per contradicció
De Viquipèdia
En matemàtica la prova 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 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
- Aleshores
o bé
- Si
- Aleshores
Essent p la proposició que volem provar o desaprovar i S és el conjunt d'axiomes donats com 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 que demostra la no enumerabilitat dels nombres reals.
[edita] Exemple
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 nombre 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 haviem suposat com a màxim nombre primer, i això contradiu la nostra hipòtesi inicial que existeixen només nnombres primers.
Aleshores la nostra hipòtesi inicial està errada i per tant existeixen infinits nombres primers.
