Tecniche di dimostrazione

Prerequisito: Logica e quantificatoriProposizioni, connettivi, predicati e quantificatori (per ogni, esiste), con le regole per negarli.Logica e quantificatori → (implicazione, negazione). Esercizi svolti: Esercizio 8 - n dispari implica n^2 dispari (dimostrazione diretta) e Esercizio 9 - la radice di 2 non è razionale (per assurdo). Una quarta tecnica, per le affermazioni "per ogni $n$", è il Principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →.

Che cosa vuol dire dimostrare

Un teorema ha quasi sempre la forma $p \Rightarrow q$:

• $p$ = ipotesi (ciò che sappiamo, o supponiamo, vero);
• $q$ = tesi (ciò che vogliamo ottenere).

Dimostrare il teorema = mostrare che l'implicazione $p \Rightarrow q$ è vera, cioè che ogni volta che vale $p$ vale anche $q$, con una catena di passaggi ciascuno giustificato (da una definizione, da un teorema già dimostrato o da una regola di calcolo).

Ci sono tre modi principali, logicamente equivalenti: dimostrano la stessa cosa, e si sceglie di volta in volta quello che rende i conti più semplici.

1. Dimostrazione diretta: $p \Rightarrow q$

Si parte dall'ipotesi $p$ e, passaggio dopo passaggio, si arriva alla tesi $q$.

Linguaggio: se $p \Rightarrow q$ si dice che $p$ è condizione sufficiente per $q$ (basta sapere $p$ per avere $q$).

Esempio. "Se $n$ è dispari allora $n^2$ è dispari": si scrive $n = 2k + 1$ e si calcola $n^2 = 2(2k^2 + 2k) + 1$, che è dispari. Dettagli nell'Esercizio 8 - n dispari implica n^2 dispari.

2. Dimostrazione indiretta (per contronominale): $\text{non}\,q \Rightarrow \text{non}\,p$

Invece di $p \Rightarrow q$ si dimostra l'implicazione "rovesciata e negata": se la tesi è falsa, allora l'ipotesi è falsa.

Perché è la stessa cosa. $p \Rightarrow q$ è falsa solo nel caso "$p$ vera, $q$ falsa". Anche $\text{non}\,q \Rightarrow \text{non}\,p$ è falsa solo quando $\text{non}\,q$ è vera e $\text{non}\,p$ è falsa, cioè di nuovo "$q$ falsa, $p$ vera". Sono false esattamente negli stessi casi, quindi sono equivalenti:

Linguaggio: se $p \Rightarrow q$ si dice che $q$ è condizione necessaria per $p$ (senza $q$ non può esserci $p$: se manca $q$, manca anche $p$).

Esempio di vita quotidiana. "Se piove, la strada è bagnata" equivale a "se la strada non è bagnata, allora non piove". Attenzione: non equivale a "se la strada è bagnata allora piove" (potrebbero aver lavato la strada): quella è l'implicazione inversa $q \Rightarrow p$, che è un'altra affermazione.

Conseguenza utile: ogni teorema ne dà due. Dall'esercizio 8 ("$n$ dispari $\Rightarrow$ $n^2$ dispari") si ottiene gratis anche "$n^2$ pari $\Rightarrow$ $n$ pari" (contronominale: non-dispari = pari). È proprio questa seconda forma che serve per dimostrare che $\sqrt{2}$ non è razionale.

3. Dimostrazione per assurdo: $p \wedge \text{non}\,q \Rightarrow$ contraddizione

Si suppone che l'ipotesi sia vera e la tesi falsa, e si ragiona fino ad arrivare a una contraddizione (un'affermazione impossibile, per esempio una cosa che è vera e falsa insieme, oppure $0 = 1$). La prof la indica con il simbolo di un fulmine (⚡).

Perché funziona. $p \Rightarrow q$ è falsa solo nel caso "$p$ vera e $q$ falsa", cioè $p \wedge \text{non}\,q$ (vedi la negazione dell'implicazione in Logica e quantificatoriProposizioni, connettivi, predicati e quantificatori (per ogni, esiste), con le regole per negarli.Logica e quantificatori →). Se si dimostra che questo caso porta a una contraddizione, quel caso non può verificarsi: resta solo la possibilità che l'implicazione sia vera.

Esempio. "$c^2 = 2 \Rightarrow c \notin \mathbb{Q}$": si suppone $c^2 = 2$ e $c \in \mathbb{Q}$, si scrive $c = \frac{m}{n}$ ai minimi termini e si scopre che $m$ e $n$ sono entrambi pari, contro l'ipotesi di averli scelti primi tra loro. Dettagli nell'Esercizio 9 - la radice di 2 non è razionale.

Anche la dimostrazione del Principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione → e quella dell'Archimedeità di NPer ogni numero reale esiste un naturale più grande: serve a trovare n con 1/n più piccolo di qualunque epsilon.Archimedeità di N → sono per assurdo.

Come scegliere

Esempi numerici non bastano

Verificare $n = 1$ ($1^2 = 1$ dispari) e $n = 3$ ($3^2 = 9$ dispari) aiuta a intuire, ma non dimostra nulla per tutti gli infiniti $n$ dispari. Bisogna ragionare su un $n$ generico, cioè scritto con una lettera ($n = 2k + 1$ con $k$ qualunque), in modo che il ragionamento valga per tutti.

Errori comuni

• Dimostrare l'inversa $q \Rightarrow p$ invece di $p \Rightarrow q$.
• Confondere contronominale e inversa: $\text{non}\,q \Rightarrow \text{non}\,p$ è equivalente all'originale; $\text{non}\,p \Rightarrow \text{non}\,q$ no.
• Nella dimostrazione per assurdo, negare male la tesi (vedi le regole di negazione in Logica e quantificatoriProposizioni, connettivi, predicati e quantificatori (per ogni, esiste), con le regole per negarli.Logica e quantificatori →).
• Dimenticare di dire dove sta la contraddizione: va scritto esplicitamente con quale ipotesi (o fatto noto) si va in conflitto.