Non esiste un numero pari più grande di tutti

Dimostra che non esiste un numero pari più grande di tutti gli altri.

Scrivi la negazione come prima riga: Supponiamo per assurdo che esista un numero pari più grande di tutti, $N$ = Ipotesi: $N$ è pari e $N \ge$ ogni numero pari

Usa la definizione di pari: $N = 2k$ per un intero $k$, quindi $N + 2 = 2k + 2 = 2(k + 1)$ = $N + 2$ è pari

Confronta i due numeri: $N + 2 > N$ = Esiste un numero pari più grande di $N$

Individua la contraddizione e concludi: $N$ è il numero pari più grande, eppure $N + 2$ è un numero pari più grande = L'ipotesi è falsa

Answer: L'ipotesi porta a una contraddizione, quindi non esiste un numero pari più grande di tutti. c.v.d.

Due persone su 13 sono nate nello stesso mese

Dimostra che in ogni gruppo di 13 persone almeno due sono nate nello stesso mese.

Scrivi la negazione: Supponiamo per assurdo che le 13 persone siano nate tutte in mesi diversi = Ipotesi: 13 mesi diversi

Conta che cosa richiede l'ipotesi: 13 persone senza mesi ripetuti richiedono almeno 13 mesi diversi = Servono almeno $13$ mesi

Confronta con i fatti: Un anno ha solo $12$ mesi, e $13 > 12$ = Impossibile

Concludi: L'ipotesi è falsa = Due persone condividono un mese

Answer: Almeno due delle 13 persone sono nate nello stesso mese. È il principio dei cassetti: 13 oggetti, 12 cassetti. c.v.d.

Non esiste un numero razionale positivo più piccolo di tutti

Dimostra che non esiste un numero razionale positivo più piccolo di tutti gli altri.

Scrivi la negazione: Supponiamo per assurdo che $r$ sia il più piccolo numero razionale positivo = Ipotesi: $r > 0$, $r$ razionale, nessuno è più piccolo

Costruisci un nuovo numero: Se $r = \frac{a}{b}$, allora $\frac{r}{2} = \frac{a}{2b}$, una frazione di interi = $\frac{r}{2}$ è razionale

Controlla la sua grandezza: $r > 0$, quindi $0 < \frac{r}{2} < r$ = $\frac{r}{2}$ è positivo e più piccolo di $r$

Individua la contraddizione e concludi: $r$ era il più piccolo, eppure $\frac{r}{2}$ è più piccolo = L'ipotesi è falsa

Answer: Non esiste un numero razionale positivo più piccolo di tutti. Per esempio, se qualcuno propone $\frac{1}{1000}$, allora $\frac{1}{2000}$ è più piccolo. c.v.d.

La radice quadrata di 2 è irrazionale

Dimostra che $\sqrt{2}$ è irrazionale.

Scrivi la negazione: Supponiamo per assurdo che $\sqrt{2}$ sia razionale: $\sqrt{2} = \frac{a}{b}$ con $a, b$ interi, $b \neq 0$, e la frazione ridotta ai minimi termini = $a$ e $b$ non hanno fattori comuni

Eleva al quadrato entrambi i membri: $2 = \frac{a^2}{b^2}$, quindi $a^2 = 2b^2$ = $a^2$ è pari

Deduci che a è pari: Se $a$ fosse dispari, $a^2$ sarebbe dispari (dimostrato nella lezione sulla dimostrazione diretta) = $a = 2k$ per un intero $k$

Sostituisci: $(2k)^2 = 2b^2$, quindi $4k^2 = 2b^2$, quindi $b^2 = 2k^2$ = $b^2$ è pari, quindi $b$ è pari

Individua la contraddizione: $a$ e $b$ sono entrambi pari, quindi entrambi divisibili per $2$ = Questo contraddice "ai minimi termini"

Answer: L'ipotesi che $\sqrt{2}$ sia razionale porta a una contraddizione, quindi $\sqrt{2}$ è irrazionale. c.v.d.

Esistono infiniti numeri primi (Euclide)

Dimostra che esistono infiniti numeri primi.

Scrivi la negazione: Supponiamo per assurdo che esista solo un numero finito di primi: $p_1, p_2, \ldots, p_n$ = La lista contiene tutti i numeri primi

Costruisci un nuovo numero: $N = p_1 \cdot p_2 \cdots p_n + 1$ = $N > 1$

Dividi N per ogni primo della lista: $N$ supera di uno un multiplo di ogni $p_i$ = Il resto è sempre $1$, quindi nessun $p_i$ divide $N$

Usa un fatto noto: Ogni intero maggiore di $1$ ha almeno un fattore primo = $N$ ha un fattore primo che non è nella lista

Individua la contraddizione: La lista doveva contenere tutti i numeri primi = L'ipotesi è falsa

Answer: Esistono infiniti numeri primi. Attenzione: $N$ stesso non è per forza primo. Con i primi fino a 13, $N = 30031 = 59 \times 509$, e 59 e 509 sono primi che mancano nella lista. c.v.d.

Mistake: Negare "Esistono infiniti numeri primi" con "Non esistono numeri primi"

Why: Il contrario di "infiniti" non è "nessuno". La negazione deve coprire tutti i casi in cui l'enunciato è falso, cioè "solo un numero finito".

Correct: Supponi "Esiste solo un numero finito di numeri primi". Allo stesso modo, la negazione di "ogni primo è dispari" è "almeno un primo non è dispari", non "ogni primo è pari".

Mistake: Negare $x > 5$ con $x < 5$

Why: Si dimentica il caso $x = 5$. Se la dimostrazione esclude solo $x < 5$, il numero $5$ resta possibile.

Correct: La negazione di $x > 5$ è $x \le 5$, e la negazione di $x \ge 5$ è $x < 5$.

Mistake: Dimenticare "ai minimi termini" nella dimostrazione che $\sqrt{2}$ è irrazionale

Why: Senza questa condizione, scoprire che $a$ e $b$ sono entrambi pari non è affatto una contraddizione: $\frac{4}{2}$ ha numeratore e denominatore pari.

Correct: Scrivi $\sqrt{2} = \frac{a}{b}$ ridotta ai minimi termini. Ogni frazione si può semplificare, quindi non costa nulla, ed è proprio il fatto che la dimostrazione poi contraddice.

Mistake: Chiamare contraddizione un risultato sorprendente

Why: Un risultato che sembra strano (un numero molto grande, una frazione inattesa) non è impossibile. Una contraddizione deve scontrarsi con l'ipotesi o con un fatto noto.

Correct: Indica i due enunciati che si scontrano, per esempio "$r$ è il più piccolo" e "$\frac{r}{2} < r$", e poi scrivi la conclusione.

Calzini dello stesso colore al buio

Il principio dei cassetti, dimostrato per assurdo, ti dice il numero minimo di oggetti che garantisce una ripetizione.

In un cassetto ci sono calzini neri, bianchi e grigi. Se potessi prendere 4 calzini tutti di colori diversi, ti servirebbero 4 colori, ma ce ne sono solo 3. Quindi 4 calzini contengono sempre una coppia dello stesso colore.

Collisioni di hash in informatica

I computer assegnano ai file codici brevi chiamati hash. Poiché i file possibili sono più dei codici, a volte due file diversi devono condividere lo stesso codice.

Un sistema assegna a ogni file un codice da 00 a 99. Con 101 file, supporre che tutti i codici siano diversi richiederebbe 101 codici, ma ce ne sono solo 100, quindi due file condividono un codice.

Perché la calcolatrice non mostra mai la radice di 2 esatta

Poiché $\sqrt{2}$ è irrazionale, la sua espansione decimale non finisce mai e non si ripete mai. Ogni decimale sullo schermo è solo un'approssimazione, e gli ingegneri devono tenerne conto quando calcolano le diagonali.

Una piastrella quadrata di lato 1 m ha una diagonale di $\sqrt{2} \approx 1{,}4142$ m. Il valore 1,4142 è vicino, ma non esatto.

Q: Perché basta arrivare a una contraddizione?

A: Un ragionamento corretto a partire da enunciati veri produce solo enunciati veri. Se arriviamo a qualcosa di impossibile, almeno un punto di partenza era falso, e l'unico punto di partenza che abbiamo aggiunto noi è l'ipotesi $\neg P$. Quindi $\neg P$ è falso e $P$ è vero.

Q: Quando conviene usare la dimostrazione per assurdo?

A: È una buona scelta quando l'enunciato afferma che qualcosa non esiste (nessun numero più grande di tutti, nessuna frazione uguale a $\sqrt{2}$) o che esistono infiniti oggetti di un certo tipo. In questi casi, supporre il contrario ti dà un oggetto concreto con cui lavorare.

Q: La dimostrazione per assurdo è la stessa cosa della dimostrazione per contronominale?

A: No. La dimostrazione per contronominale prova direttamente "se non q, allora non p" e finisce con "non p". La dimostrazione per assurdo suppone che l'enunciato sia falso e può finire con una qualsiasi impossibilità. Ogni dimostrazione per contronominale si può riscrivere come dimostrazione per assurdo, ma non ogni dimostrazione per assurdo è una dimostrazione per contronominale.

Q: Che cosa significa c.v.d. e che cos'è la "reductio ad absurdum"?

A: c.v.d. ("come volevasi dimostrare", in latino quod erat demonstrandum) segna la fine di una dimostrazione. Reductio ad absurdum, "riduzione all'assurdo", è il nome latino della dimostrazione per assurdo.