“
La reductio ad absurdum, che Euclide amava tanto, è una delle armi più raffinate del matematico: è una
mossa molto più elegante di qualsiasi gambetto degli scacchi, perché un matematico, invece di un pezzo, offre
l’intera partita.”
— Godfrey Harold Hardy, A Mathematician’s Apology (1940)
____________________________________________________________________________________
Nei capitoli precedenti abbiamo costruito il linguaggio della logica: insiemi, connettivi, quantificatori, struttura ipotesi/tesi. Ora arriva il momento di usarli per fare la cosa che caratterizza davvero la matematica: dimostrare.
Dimostrare significa convincere chi ascolta che un’affermazione \(p\Rightarrow q\) è vera, partendo da definizioni e proprietà già accettate e procedendo per passi logici inattaccabili. Non c’è un solo modo di farlo: con il tempo si sono affermate alcune tecniche di dimostrazione, ciascuna adatta a un tipo di enunciato.
In questo capitolo ne presentiamo quattro, le più comuni al biennio:
Daremo infine un primo sguardo all’induzione matematica, che approfondiremo nel capitolo 163.
Definizione 6.1 — Dimostrazione diretta
Per dimostrare \(p\Rightarrow q\) in modo diretto, si parte dall’ipotesi \(p\) e, attraverso una catena di implicazioni valide, si arriva alla tesi \(q\):
Ogni passaggio deve essere giustificato da una definizione, da una proprietà nota o da un teorema dimostrato in precedenza.
È lo stile più naturale e quello cui si ricorre per primo. Si tratta di costruire un ponte logico fra le due rive dell’implicazione.
Procedura — Schema di una dimostrazione diretta
Esempio 6.1 — Somma di due pari è pari
Dimostrare: se \(m,n\in \mathbb{Z} \) sono entrambi pari, allora \(m+n\) è pari.
Dimostrazione (diretta). Supponiamo che \(m\) e \(n\) siano pari. Per definizione esistono \(h,k\in \mathbb{Z} \) tali che \(m=2h\) e \(n=2k\). Allora
Poiché \(h+k\in \mathbb{Z} \), \(m+n\) è divisibile per \(2\), dunque è pari. La tesi è dimostrata.
Esempio 6.2 — Quadrato di un pari
Dimostrare: se \(n\in \mathbb{Z} \) è pari, allora \(n^2\) è pari.
Dimostrazione (diretta). Sia \(n\) pari: esiste \(k\in \mathbb{Z} \) con \(n=2k\). Allora
con \(2k^2\in \mathbb{Z} \). Quindi \(n^2\) è pari.
Nota — Dimostrazione per contronominale: una variante della diretta
Esempio 6.3 — Per contronominale
Dimostrare: se \(n^2\) è pari, allora \(n\) è pari.
Dimostrazione (per contronominale). Mostriamo la contronominale: se \(n\) è dispari, allora \(n^2\) è dispari. Sia \(n\) dispari: esiste \(k\in \mathbb{Z} \) con \(n=2k+1\). Allora
e poiché \(2k^2+2k\in \mathbb{Z} \), \(n^2\) è della forma \(2m+1\) con \(m\in \mathbb{Z} \): è dispari. Per la legge di contrapposizione (capitolo 3), l’implicazione iniziale è dimostrata.
Definizione 6.2 — Dimostrazione per assurdo
Per dimostrare \(p\Rightarrow q\) per assurdo (o reductio ad absurdum) si suppone simultaneamente \(p\) e \(\lnot q\), e si deriva da queste ipotesi una contraddizione, cioè una proposizione del tipo \(r\land \lnot r\) che è certamente falsa.
Poiché da premesse vere non si può dedurre il falso, una delle ipotesi è insostenibile: l’unica che possiamo rifiutare è \(\lnot q\) (perché \(p\) è la nostra ipotesi). Concludiamo dunque \(q\).
La struttura ricalca la legge logica \(\lnot q\Rightarrow (p\Rightarrow r\land \lnot r)\): se negare la tesi conduce a un’assurdità, la tesi non può essere negata.
Procedura — Schema di una dimostrazione per assurdo
Esempio 6.4 — Irrazionalità di \(\sqrt {2}\)
Dimostrare: \(\sqrt {2}\) non è un numero razionale.
Dimostrazione (per assurdo). Supponiamo per assurdo che \(\sqrt {2}\) sia razionale. Allora si può scrivere come frazione \(\sqrt {2}=\tfrac {a}{b}\) con \(a,b\in \mathbb{Z} \), \(b\neq 0\), e \(\tfrac {a}{b}\) già ridotta ai minimi termini (cioè \(a\) e \(b\) non hanno fattori comuni). Elevando al quadrato:
Allora \(a^2\) è pari; per quanto dimostrato nell’esempio 6.2, anche \(a\) è pari: \(a=2k\) con \(k\in \mathbb{Z} \). Sostituendo:
quindi anche \(b^2\) è pari, e dunque anche \(b\). Ma allora \(a\) e \(b\) hanno il fattore \(2\) in comune: questo contraddice l’ipotesi che \(\tfrac {a}{b}\) fosse ridotta ai minimi termini. La supposizione iniziale è insostenibile: \(\sqrt {2}\) non è razionale.
Esempio 6.5 — Infinità dei numeri primi, da Euclide
Dimostrare: esistono infiniti numeri primi.
Dimostrazione (per assurdo). Supponiamo per assurdo che esistano solo un numero finito di primi: chiamiamoli \(p_1, p_2, \ldots , p_n\). Consideriamo il numero
\(N\) è un intero maggiore di \(1\), dunque ha almeno un divisore primo (proprietà nota di \(\mathbb{N} \)). Chiamiamo \(q\) uno di questi divisori primi: per ipotesi, \(q\) deve coincidere con uno dei \(p_i\) della lista. Ma allora \(q\) divide sia \(p_1 p_2\cdots p_n\) sia \(N=p_1 p_2\cdots p_n + 1\); quindi divide anche la loro differenza, cioè \(q\mid 1\). È impossibile, perché nessun primo divide \(1\). Contraddizione.
Concludiamo che l’elenco dei primi non può essere finito: i primi sono infiniti.
Attenzione!
La dimostrazione per assurdo è potente ma va maneggiata con cura: la contraddizione deve essere esplicita (una proposizione e la sua negazione), non un semplice “sembra strano”. Inoltre, se l’enunciato di partenza è \(p\Rightarrow q\), l’ipotesi assurda da assumere è \(p\land \lnot q\), non solo \(\lnot q\): l’ipotesi \(p\) rimane in vigore.
Un’altra strategia utile è la dimostrazione per casi: si esamina separatamente ogni possibile situazione, dimostrando la tesi in ciascuna. È giustificata dalla regola di inferenza “se \(p_1\lor p_2\lor \cdots \lor p_n\) e ogni \(p_i\Rightarrow q\), allora \(q\)”.
Esempio 6.6
Dimostrare: per ogni \(n\in \mathbb{Z} \), \(n(n+1)\) è pari.
Dimostrazione (per casi). Distinguiamo due casi sulla parità di \(n\).
Caso 1: \(n\) pari. Allora \(n=2k\) e \(n(n+1)=2k(n+1)\) è pari.
Caso 2: \(n\) dispari. Allora \(n+1\) è pari, \(n+1=2k\), e \(n(n+1)=n\cdot 2k=2(nk)\) è pari.
In entrambi i casi \(n(n+1)\) è pari, dunque la tesi è dimostrata.
Le tecniche viste finora servono a dimostrare che un’affermazione è vera. Spesso però ci troviamo di fronte a una congettura della forma “per ogni \(x\) vale \(P(x)\)” e vogliamo capire se è vera o falsa. Se è falsa, il modo più rapido di smentirla è esibire un controesempio.
Definizione 6.3 — Controesempio
Un controesempio a una proposizione universale \(\forall x\in D:\ P(x)\) è un elemento \(x_0\in D\) tale che \(P(x_0)\) è falso. Esibire un controesempio è sufficiente a smentire la proposizione.
La regola si giustifica con la legge di De Morgan per i quantificatori (capitolo 4):
Attenzione! — Cento esempi non bastano, un controesempio sì
Per smentire un universale basta un singolo controesempio. Al contrario, verificare l’universale su molti casi (cento, mille, un milione) non lo dimostra: la matematica richiede una dimostrazione per ogni elemento del dominio, non una statistica.
Esempio 6.7 — La formula di Eulero
Confutare la congettura: “per ogni \(n\in \mathbb{N} \), \(n^2+n+41\) è primo”.
Soluzione. La formula dà primi per \(n=0,1,2,\ldots ,39\) (caso curioso, già notato da Eulero). Però per \(n=40\):
non è primo. Il controesempio \(n=40\) smentisce la congettura.
Esempio 6.8 — Tutte le potenze di \(2\) aumentate di \(1\) sono prime?
Confutare: “per ogni \(n\in \mathbb{N} \), \(2^n+1\) è primo”.
Soluzione. Verifichiamo: \(n=0\) dà \(2\), \(n=1\) dà \(3\), \(n=2\) dà \(5\), \(n=4\) dà \(17\)…sembra promettente. Ma con \(n=3\) otteniamo \(2^3+1=9=3^2\): non è primo. Il controesempio \(n=3\) smentisce la frase. (I numeri della forma \(2^{2^k}+1\) si chiamano numeri di Fermat; il primo composto è \(2^{32}+1\), ma il problema dei primi della forma \(2^n+1\) è ancora più sottile.)
Le tecniche viste finora trattano un singolo enunciato \(p\Rightarrow q\). C’è però una situazione tipicissima in cui dobbiamo dimostrare un’infinità di enunciati contemporaneamente: una proposizione \(P(n)\) che dipende da un numero naturale \(n\). Ad esempio, “la somma dei primi \(n\) numeri naturali è \(\tfrac {n(n+1)}{2}\)”. Per dimostrarla per ogni \(n\), non possiamo verificarla un caso alla volta: useremo il principio di induzione matematica.
Nota — Principio di induzione
Per dimostrare \(\forall n\in \mathbb{N} : P(n)\), basta provare due cose:
Da queste due proprietà segue che \(P(n)\) è vera per ogni \(n\in \mathbb{N} \). È come una fila infinita di tessere del domino: se la prima cade (base) e se ogni tessera fa cadere la successiva (passo), allora cadono tutte.
Esempio 6.9 — Somma dei primi \(n\) naturali
Dimostrare: per ogni \(n\in \mathbb{N} ^*\), \(\displaystyle 1+2+\cdots +n = \frac {n(n+1)}{2}\).
Dimostrazione (per induzione). Sia \(P(n)\): “\(1+2+\cdots +n=\tfrac {n(n+1)}{2}\)”.
Base (\(n=1\)). \(P(1)\): “\(1=\tfrac {1\cdot 2}{2}=1\)”. Vera.
Passo induttivo. Supponiamo vera \(P(n)\) e mostriamo \(P(n+1)\). Per ipotesi induttiva,
Aggiungiamo \(n+1\) a entrambi i membri:
Questa è proprio \(P(n+1)\).
Per induzione, \(P(n)\) è vera per ogni \(n\ge 1\).
L’induzione meriterà un capitolo a sé: la riprenderemo in dettaglio nel capitolo 163, dove vedremo varianti (induzione forte, induzione a partire da \(n_0\neq 0\)) e numerose applicazioni.
Esempio 6.10 — Diretta: prodotto di due dispari è dispari
Dimostrare: se \(m,n\in \mathbb{Z} \) sono entrambi dispari, allora \(mn\) è dispari.
Dimostrazione (diretta). Siano \(m=2h+1\) e \(n=2k+1\) con \(h,k\in \mathbb{Z} \). Allora
con \(2hk+h+k\in \mathbb{Z} \). Dunque \(mn\) è dispari.
Esempio 6.11 — Per contronominale
Dimostrare: se \(n^3\) è pari (con \(n\in \mathbb{Z} \)), allora \(n\) è pari.
Dimostrazione (per contronominale). Mostriamo: se \(n\) è dispari, allora \(n^3\) è dispari. Sia \(n\) dispari: per l’esempio precedente \(n\cdot n=n^2\) è dispari, e \(n^2\cdot n=n^3\) è dispari (prodotto di due dispari). Per contrapposizione, la tesi iniziale è dimostrata.
Esempio 6.12 — Per assurdo: irrazionalità di \(\sqrt {3}\)
Dimostrare: \(\sqrt {3}\) non è razionale.
Dimostrazione (per assurdo). Supponiamo \(\sqrt {3}=\tfrac {a}{b}\) con \(a,b\in \mathbb{Z} \), \(b\neq 0\) e \(\tfrac {a}{b}\) ridotta. Allora \(a^2=3b^2\), dunque \(3\mid a^2\). Poiché \(3\) è primo, \(3\mid a\) (proprietà nota: se un primo divide un prodotto, divide uno dei fattori). Scriviamo \(a=3k\) con \(k\in \mathbb{Z} \). Sostituendo: \(9k^2=3b^2\), cioè \(b^2=3k^2\). Allora \(3\mid b^2\) e quindi \(3\mid b\). Ma allora \(a\) e \(b\) avrebbero il fattore \(3\) in comune, contro l’ipotesi che \(\tfrac {a}{b}\) fosse ridotta. Contraddizione. Quindi \(\sqrt {3}\) non è razionale.
Esempio 6.13 — Per casi: valore assoluto di una somma
Dimostrare: per ogni \(a,b\in \mathbb{R} \), \(|ab|=|a|\,|b|\).
Dimostrazione (per casi). Distinguiamo i segni.
Caso 1: \(a,b\ge 0\). Allora \(ab\ge 0\) e \(|ab|=ab=|a|\,|b|\).
Caso 2: \(a\ge 0\), \(b<0\). Allora \(ab\le 0\), quindi \(|ab|=-(ab)=a(-b)=|a|\,|b|\).
Caso 3: \(a<0\), \(b\ge 0\). Analogo al caso 2 scambiando i ruoli.
Caso 4: \(a,b<0\). Allora \(ab>0\) e \(|ab|=ab=(-a)(-b)=|a|\,|b|\).
In tutti i casi \(|ab|=|a|\,|b|\).
Esempio 6.14 — Controesempio
Confutare: “ogni primo dispari è della forma \(4k+1\) per qualche \(k\in \mathbb{N} \)”.
Soluzione. È falsa: il primo \(3\) è dispari ma \(3=4\cdot 0+3\), non della forma \(4k+1\). Più in generale tutti i primi \(\equiv 3\pmod 4\) (come \(3\), \(7\), \(11\), \(19\), \(\ldots \)) sono controesempi. Esibire \(p=3\) è sufficiente a smentire l’universale.
Esempio 6.15 — Induzione: somma di dispari
Dimostrare per induzione: \(1+3+5+\cdots +(2n-1)=n^2\) per ogni \(n\ge 1\).
Dimostrazione. Sia \(P(n)\): “\(1+3+\cdots +(2n-1)=n^2\)”.
Base (\(n=1\)). \(P(1)\): “\(1=1^2\)”. Vera.
Passo. Supposto \(P(n)\), sommiamo \(2(n+1)-1=2n+1\):
Quindi \(P(n+1)\) è vera. Per induzione \(P(n)\) vale per ogni \(n\ge 1\).
Esercizio 6.1
Riepilogo
![[Picture]](immagini_matematica/libro_matematica_a_capitoli152x.svg)
![[Picture]](immagini_matematica/libro_matematica_a_capitoli157x.svg)