Davanti a un enunciato da dimostrare, la difficoltà spesso non è la matematica in sé, ma scegliere da dove cominciare. Esiste un piccolo catalogo di strategie che coprono la grande maggioranza dei casi. Conoscerle aiuta non solo a scrivere dimostrazioni, ma anche a ragionare sulla correttezza di un algoritmo o a capire perché un'idea non funziona.
Dimostrazione diretta
Si parte dalle ipotesi e, con una catena di passaggi, si arriva alla tesi. È la strategia più semplice e conviene provarla per prima.
Enunciato: la somma di due numeri dispari è pari.
Dimostrazione: siano a e b dispari. Per definizione a = 2h + 1 e b = 2k + 1 per qualche intero h e k. Allora a + b = 2h + 2k + 2 = 2(h + k + 1), che è un multiplo di 2, quindi pari.
Il trucco della dimostrazione diretta è quasi sempre lo stesso: tradurre le parole nelle definizioni. «Dispari» diventa «2k + 1», «divisibile per 3» diventa «3m», e a quel punto resta solo algebra.
Dimostrazione per contronominale
Invece di p → q si dimostra ¬q → ¬p, che è equivalente. Conviene quando la negazione della tesi dà più informazioni della tesi stessa. Esempio classico: «se n² è pari, allora n è pari» si dimostra mostrando che se n è dispari anche n² è dispari.
Dimostrazione per assurdo
Si suppone che la tesi sia falsa e si arriva a una contraddizione. Poiché la contraddizione non può essere vera, l'ipotesi assurda va scartata e la tesi è vera.
Enunciato: √2 non è un numero razionale.
Dimostrazione: supponiamo per assurdo che √2 = a/b, con a e b interi e la frazione ridotta ai minimi termini. Allora 2 = a²/b², cioè a² = 2b². Quindi a² è pari, e allora a è pari: a = 2c. Sostituendo, 4c² = 2b², cioè b² = 2c², quindi anche b è pari. Ma allora a e b hanno il fattore comune 2, contro l'ipotesi che la frazione fosse ridotta. Contraddizione.
Un secondo esempio celebre, attribuito a Euclide: i numeri primi sono infiniti. Supponiamo che siano finiti, p₁, …, pₙ. Consideriamo N = p₁ · p₂ · … · pₙ + 1. Diviso per ciascun pᵢ dà resto 1, quindi nessuno dei primi elencati lo divide. Ma N > 1 ha almeno un fattore primo, che dunque non è nella lista. Contraddizione con l'ipotesi che la lista fosse completa.
Attenzione a un dettaglio: non si sta dicendo che N sia primo. Per esempio 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 509. Si dice solo che ha un fattore primo fuori dalla lista.
Dimostrazione per casi
Quando le ipotesi si dividono naturalmente in situazioni diverse, si dimostra la tesi in ciascuna. L'importante è che i casi siano esaustivi: devono coprire tutte le possibilità.
Enunciato: per ogni intero n, n² diviso per 3 dà resto 0 oppure 1, mai 2.
Dimostrazione: ogni intero ha la forma 3k, 3k + 1 o 3k + 2.
- Se n = 3k: n² = 9k² = 3(3k²), resto 0.
- Se n = 3k + 1: n² = 9k² + 6k + 1 = 3(3k² + 2k) + 1, resto 1.
- Se n = 3k + 2: n² = 9k² + 12k + 4 = 3(3k² + 4k + 1) + 1, resto 1.
I tre casi coprono tutti gli interi, quindi la tesi è dimostrata. Una conseguenza pratica: un numero che diviso per 3 dà resto 2 non può essere un quadrato perfetto.
Dimostrazioni di esistenza
Per dimostrare ∃x P(x) ci sono due strade.
- Costruttiva: si esibisce un x concreto. «Esiste un numero che si scrive come somma di due cubi in due modi diversi»: 1729 = 1³ + 12³ = 9³ + 10³.
- Non costruttiva: si mostra che un x deve esistere senza indicarlo. Il principio dei cassetti fornisce molti esempi di questo tipo.
In informatica le dimostrazioni costruttive sono particolarmente preziose, perché spesso corrispondono a un algoritmo che trova la soluzione.
Controesempi
Per mostrare che un enunciato universale ∀x P(x) è falso basta un solo x per cui P(x) non vale. «Ogni numero della forma n² + n + 41 è primo» regge per molti valori piccoli di n, ma per n = 40 si ottiene 40² + 40 + 41 = 1681 = 41², che non è primo. Un esempio non dimostra un universale; un controesempio basta a demolirlo.
Come scegliere
| Se la tesi… | Prova prima |
|---|---|
| segue «in avanti» dalle definizioni | dimostrazione diretta |
| è una negazione (non razionale, non esiste) | per assurdo |
| ha una negazione più maneggevole | contronominale |
| dipende da parità, resti, segni | per casi |
| afferma un'esistenza | costruzione esplicita |
| sembra falsa | cerca un controesempio |
In sintesi
- La dimostrazione diretta parte dalle definizioni tradotte in algebra.
- Per assurdo si nega la tesi e si cerca una contraddizione; è naturale per enunciati negativi.
- Nei casi multipli, l'esaustività dei casi è parte essenziale della dimostrazione.
- Le dimostrazioni costruttive spesso equivalgono a un algoritmo.
- Un solo controesempio basta a smentire un enunciato universale.
