Esercizio 8

Testo (Lezione 2, esercizio 1 — dimostrazione diretta). Dimostrare che $\forall n \in \mathbb{N}$, $n$ dispari $\Rightarrow$ $n^2$ è dispari.

Passo 0: ipotesi e tesi

• UniversoL'insieme in cui varia la variabile: qui $n$ è sempre un numero naturale.: $X = \mathbb{N}$.
• IpotesiCiò che si suppone vero; la tesi è ciò che si vuole dedurre a partire dall'ipotesi.Tecniche di dimostrazione → $p$: "$n$ è dispari".
• Tesi $q$: "$n^2$ è dispari".

Vogliamo dimostrare $p \Rightarrow q$Implicazione "se $p$ allora $q$": è falsa solo quando $p$ è vera e $q$ è falsa.Logica e quantificatori → direttamenteDimostrazione diretta: si assume vera l'ipotesi $p$ e con passaggi logici giustificati si deduce la tesi $q$.Tecniche di dimostrazione →: partire dal fatto che $n$ è dispari e arrivare, con passaggi giustificati, al fatto che $n^2$ è dispari.

Passo 1: gli esempi aiutano, ma non dimostrano

• $n = 1$: $1^2 = 1$, dispari ✓;
• $n = 3$: $3^2 = 9$, dispari ✓;
• $n = 5$: $5^2 = 25$, dispari ✓.

Questo ci fa intuire che l'affermazione è vera, ma i dispari sono infiniti: non possiamo controllarli tutti. Serve un ragionamento su un $n$ dispari genericoPer dimostrare un "per ogni" si ragiona su un elemento qualsiasi: ciò che si dimostra per lui vale per tutti.Logica e quantificatori →, cioè rappresentato con una formula che descriva tutti i dispari contemporaneamente.

Passo 2: come si scrive "dispari" (e "pari") con una formula

• $n$ è pari se $n = 2k$ per qualcheQuantificatore esistenziale $\exists$: basta che esista almeno un $k$ con quella proprietà.Logica e quantificatori → $k \in \mathbb{N}$ (è un multiplo di $2$);
• $n$ è dispari se $n = 2k + 1$ per qualche $k \in \mathbb{N}$ (è un pari più $1$).

Esempi: $7 = 2 \cdot 3 + 1$ (dispari, con $k = 3$), $10 = 2 \cdot 5$ (pari, con $k = 5$), $1 = 2 \cdot 0 + 1$ (dispari, con $k = 0$).

Queste due formule sono da ricordare: trasformano una parola ("dispari") in qualcosa con cui si può fare un calcolo.

Passo 3: la dimostrazione

Supponiamo $p$Primo passo della dimostrazione diretta: si assume vera l'ipotesi e la si traduce in una formula.Tecniche di dimostrazione →: $n$ è dispari. Allora esiste $k \in \mathbb{N}$ tale che $n = 2k + 1$.

Calcoliamo $n^2$ con il quadrato di binomioLo sviluppo del quadrato di una somma di due termini; attenzione al doppio prodotto $2ab$, che non va dimenticato. $(a + b)^2 = a^2 + 2ab + b^2$, con $a = 2k$ e $b = 1$:

$$n^2 = (2k + 1)^2 = (2k)^2 + 2 \cdot 2k \cdot 1 + 1^2 = 4k^2 + 4k + 1$$

Facciamo comparire la forma "$2 \cdot (\text{qualcosa}) + 1$". I primi due termini sono entrambi multipli di $2$, quindi raccogliamoMettere in evidenza un fattore comune: si divide ogni termine per $2$ e si scrive il $2$ fuori dalla parentesi. $2$:

$$n^2 = 2(2k^2 + 2k) + 1$$

Chiamiamo $m = 2k^2 + 2k$. Poiché $k \in \mathbb{N}$, anche $m \in \mathbb{N}$ (somme e prodotti di naturali sono naturaliSommando o moltiplicando due numeri naturali si ottiene ancora un naturale: non si esce da $\mathbb{N}$.Insiemi numerici (N, Z, Q, R) →). Quindi

$$n^2 = 2m + 1 \quad \text{con } m \in \mathbb{N}$$

che è esattamente la forma di un numero dispari. Abbiamo dimostrato la tesi $q$ ∎Simbolo di fine dimostrazione: significa "come volevasi dimostrare"..

Perché raccogliere $2$ e non $4$. Anche $4k^2 + 4k = 4(k^2 + k)$ sarebbe corretto, ma a noi serve la forma $2 \cdot (\ldots) + 1$ della definizione di dispari. Si sceglie la scrittura che fa comparire la definizione da verificare.

Controllo numerico della formula. $n = 7$, cioè $k = 3$: $m = 2 \cdot 9 + 2 \cdot 3 = 24$, e $2m + 1 = 49 = 7^2$ ✓.

Passo 4: la conseguenza gratuita (contronominale)

L'implicazione $p \Rightarrow q$ equivale a $\text{non}\,q \Rightarrow \text{non}\,p$È la contronominale di $p \Rightarrow q$: ha sempre lo stesso valore di verità, quindi dimostrarne una dimostra anche l'altra.Tecniche di dimostrazione →. Qui $\text{non}\,q$ = "$n^2$ non è dispari" = "$n^2$ è pari", e $\text{non}\,p$ = "$n$ è pari". Quindi abbiamo dimostrato anche:

$$n^2 \text{ pari} \ \Rightarrow \ n \text{ pari}$$

Questo secondo risultato è quello che servirà nella dimostrazione che $\sqrt{2}$ non è razionale: Esercizio 9 - la radice di 2 non è razionale.

Attenzione: questo non è la stessa cosa di "$n$ pari $\Rightarrow$ $n^2$ pari" (che è vera anch'essa, perché $(2k)^2 = 2 \cdot 2k^2$, ma è un altro teorema, che andrebbe dimostrato a parte).

Errori comuni

• Concludere dopo qualche esempio: gli esempi non dimostrano un "per ogniQuantificatore $\forall$: la proprietà deve valere per tutti gli elementi, quindi qualche caso controllato non basta.Logica e quantificatori →".
• Usare la stessa lettera per due cose diverse, per esempio scrivere $n = 2n + 1$: la lettera $k$ serve proprio a non confondersi.
• Fermarsi a $4k^2 + 4k + 1$ senza mostrare che è della forma $2m + 1$ con $m$ naturale.