Dimostrazione per assurdo

La dimostrazione per assurdo è una tecnica di dimostrazione molto diffusa. Se vogliamo dimostrare che un certo enunciato è vero, lo neghiamo, supponiamo che sia vera la sua negazione e cerchiamo di arrivare a una contraddizione. L’obiettivo è dimostrare che l’ipotesi che abbiamo scelto porta a qualcosa di assurdo.

Un esempio banale

Prendiamo l’affermazione «non esiste il più piccolo numero razionale positivo». La dimostriamo per assurdo: prima la neghiamo, cioè «esiste il più piccolo numero razionale positivo», e chiamiamo questo numero q. Se q è il più piccolo numero razionale positivo, allora non possiamo trovare un numero razionale positivo più piccolo, perché altrimenti q non sarebbe il più piccolo.

Lo sfruttiamo nella ricerca della contraddizione. Se invece troviamo un numero più piccolo di q, che possiamo scegliere a piacere, allora siamo arrivati a una contraddizione e l’affermazione negata non è valida. Se come numero più piccolo scegliamo, per esempio, 0,1, vediamo che 0,01 è più piccolo. Poi 0,001 è ancora più piccolo, 0,0001 è più piccolo ancora, e così via. Basta dividere il numero q per dieci e otteniamo un numero più piccolo. In realtà basta dividerlo per un qualsiasi numero maggiore di uno, per esempio per due: la metà di q è sicuramente più piccola di q intero.

Quindi il numero q/2 è sicuramente più piccolo di q ed è anche un numero razionale positivo. Siamo così arrivati a una contraddizione con l’affermazione negata, quindi l’affermazione negata non vale e di conseguenza vale l’affermazione originale, quella non negata.

Numeri interessanti

Una classica dimostrazione scherzosa che illustra il principio della dimostrazione per assurdo è il seguente. Supponiamo che esistano dei numeri naturali in qualche modo interessanti. Per esempio il numero 2 è interessante, perché vale 2 · 2 = 2 + 2, una proprietà piuttosto insolita. Il numero 42 è interessante perché è la risposta a tutto. E così via. La domanda è: esistono infiniti numeri interessanti?

Supponiamo il contrario, cioè che i numeri interessanti siano soltanto un numero finito e che alcuni numeri siano non interessanti. Raccogliamo questi numeri naturali non interessanti in un insieme. Ora scegliamo il più piccolo numero non interessante. Un momento: il più piccolo numero non interessante? Suona piuttosto interessante, no? :-)

Siamo quindi arrivati a una contraddizione, perché il più piccolo numero non interessante è in realtà piuttosto interessante. Non può dunque esistere il più piccolo numero non interessante, e perciò l’insieme dei numeri non interessanti deve essere necessariamente vuoto.

Naturalmente è un’assurdità: non abbiamo definito con precisione che cosa sia un numero interessante, ma il procedimento della dimostrazione in sé è corretto.

Dimostrazione dell’infinità dei numeri primi

In questo esempio mostriamo un procedimento simile a quello del paragrafo precedente, ma stavolta sarà corretto sotto ogni aspetto.

Un numero primo è un numero divisibile soltanto per due numeri diversi: per se stesso e per uno. Osserva che la definizione non è soddisfatta dall’uno, mentre è soddisfatta dal due.

La scomposizione in fattori primi è la scomposizione di un numero naturale maggiore di uno in un prodotto di numeri primi. È una proprietà piuttosto interessante dei numeri naturali. Qualunque numero naturale prendi (tranne lo zero e l’uno), puoi scomporlo in un prodotto di alcuni numeri primi (anche uguali tra loro). Esempi:

$$\begin{array}{rcl}8& =& 2\cdot 2\cdot 2\\ 15& =& 3\cdot 5\\ 26& =& 2\cdot 13\\ 1800& =& 2^3\cdot 3^2\cdot 5^2\end{array}$$

L’affermazione sulla scomposizione in fattori primi si chiama teorema fondamentale dell’aritmetica. Tra l’altro ci dice che tale scomposizione è unica, cioè non troveremo due scomposizioni in fattori primi diverse dello stesso numero naturale. Inoltre soltanto i numeri primi hanno una scomposizione formata da un unico numero: se stessi. La scomposizione in fattori primi del sette sarebbe quindi il numero sette. Useremo questi fatti per costruire la dimostrazione dell’affermazione seguente.

Ora dimostriamo l’affermazione «i numeri primi sono infiniti». Anche stavolta la neghiamo: «i numeri primi sono in quantità finita». Supponiamo che la successione di numeri

$$a_1,a_2,a_3,\dots ,a_n$$

rappresenti tutti i numeri primi esistenti. Se in questa successione ci sono tutti i numeri primi, allora sicuramente non potremo trovare un numero che sia primo e che allo stesso tempo non appartenga a questa successione. Tutti i numeri primi sono nella successione e fuori dalla successione non può trovarsi nessun numero primo.

Per arrivare a una contraddizione dobbiamo quindi costruire un numero primo che non è in questa successione. Ci aiuta il numero q. Lo costruiamo moltiplicando tutti i numeri primi della successione e sommando uno:

$$q=a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1$$

Ora dobbiamo mostrare che questo numero o è primo, oppure in qualche modo genera un numero primo. Sappiamo che q è un numero naturale e che ogni numero naturale si può esprimere come prodotto di numeri primi. Tuttavia nessun numero primo a_i divide q senza resto: dopo la divisione resta sempre uno. Se provassimo a dividere q, per esempio, per il numero primo a₂, otterremmo questo:

$$\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1}{a_2}=\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1\cdot a_3\cdot a_4\cdot \dots \cdot a_n+\frac{1}{a_2}$$

Prima spezziamo la frazione in due. Nella prima frazione semplifichiamo a₂ e resta un prodotto di numeri primi, cioè semplicemente un altro numero intero, che non ci interessa. Nella seconda frazione non c’è niente da semplificare: questa frazione sarà sempre un numero non intero (perché il denominatore non può essere uno, dato che uno non è un numero primo). La somma è quindi un numero che non è intero, perciò il numero primo a₂ non divide q.

Abbiamo così dimostrato che nessuno dei numeri primi della successione a_n divide q. (Nota: lo abbiamo mostrato solo per a₂, ma si generalizza facilmente se al posto di a₂ scriviamo un generico a_i.) Ma poiché ogni numero naturale si può scomporre in un prodotto di numeri primi, devono esistere altri numeri primi, che non sono nella successione a_n, ma che compaiono nella scomposizione di q. Del resto, lo stesso q può benissimo essere primo, e allora la sua scomposizione in fattori primi comprenderà soltanto il numero q. Ripercorriamo dunque un’ultima volta il ragionamento:

1. Ogni numero naturale si può esprimere come prodotto di numeri primi.
2. Per ipotesi la successione a_n contiene tutti i numeri primi esistenti.
3. Riformuliamo la prima affermazione: ogni numero naturale si può esprimere come prodotto di alcuni termini della successione a_n, perché questa contiene tutti i numeri primi.
4. Abbiamo dimostrato che nessun numero della successione a_n divide q.
5. Ne nasce una contraddizione con l’ipotesi → se dobbiamo poter scomporre ogni numero naturale in un prodotto di numeri primi e la successione a_n non contiene nessun numero che divida q, allora devono esistere altri numeri primi che dividono q e che fanno parte della scomposizione in fattori primi di q.

Siamo così arrivati a una contraddizione. La scomposizione in fattori primi di q comprende numeri primi che non sono contenuti nella successione che avevamo supposto contenere tutti i numeri primi. Dunque l’affermazione negata non vale e vale l’affermazione originale, non negata. I numeri primi sono infiniti.