Accedi
giovedì 15 febbraio 2018 - Fabiano Colombari

Dimostrazioni e il principio di Induzione

Le tecniche e i metodi dimostrativi rappresentano un requisito fondamentale per il rigorismo ed il formalismo matematico. La dimostrazione è di fondamentale importanza affinché ci si possa convincere della validità del teorema. Quest’ultimo è un’asserzione con la quale si afferma la verità di un enunciato così formato:

α,β,γ, … ⇒ K

dove gli enunciati α,β,γ,… sono dette ipotesi e K è la tesi. In assenza di ipotesi si tratta di dimostrare che la tesi K sia sempre vera.

Le ipotesi si effettuano secondo i principi logici ed insiemistici, gli assiomi ( enunciati ritenuti veri dalla maggior parte senza il bisogno di dimostrazione) o altri teoremi.

  • Principali tecniche dimostrative
    • Connettivi e quantificatori

Vale la pena ricordare che dati due enunciati A e B si possono costruire gli enunciati composti tramite i connettivi logici di seguito usati.

 

A \land  B letto come “A e B” \land  → connettivo della congiunzione

Per dimostrare questo enunciato composto bisogna dimostrare sia A che B.

A \vee B letto come “A e B”  \lor  → connettivo della disgiunzione

Per dimostrare l’enunciato composto con la disgiunzione basta dimostrare A o B.

A ⇒ B letto come “A implica B o se A allora B” ⇒ → connettivo dell’implicazione

Per dimostrare l’implicazione bisogna dedurre B dall’ipotesi A.

A ⇔ B letto come “A se e solo se B” ⇔ → connettivo dell’equivalenza

L’enunciato composto con l’equivalenza equivale dire (A⇒ B) \land  (B⇒ A), per dimostrarlo basta verificare che sia vera la congiunzione.

¬ A letto come “non A” ¬ → connettivo della negazione. Per dimostrare la negazione basta raggiungere enunciati falsi e contraddittori partendo da A non negato.

I quantificatori :

∀ x E(x) significa E(x) per ogni x dove E(x) è un enunciato che dipende da una variabile ( in questo caso x). ∀ → è il quantificatore universale. Esempio: per ogni numero reale y (y∈ℜ) minore di 5 esiste un numero naturale (x∈ℕ) tale che n*5>5 (In realtà questa è una conseguenza della proprietà di Archimede(**)).

∃ x E(x) significa “esiste x tale che E(x) oppure E(x) per qualche x”. ∃ → è il quantificatore esistenziale.Esempio: esiste un numero intero razionale (x) tra due numeri interi (E(x)).

  • Dimostrazione per assurdo

Un’altra tecnica dimostrativa riguarda la cosiddetta dimostrazione per assurdo in cui per dimostrare un enunciato generico E ⇔ ¬¬E (un enunciato E equivale alla sua doppia negazione secondo il principio della logica classica dell’eliminazione della doppia negazione chiamato duplex negatio affirmat). Dimostrare per assurdo E significa ricondurci ad una contraddizione utilizzando solo ¬E, il che significa che è necessario ricondurci alla doppia negazione, ossia E, per non avere la contraddizione.

  • Dimostrazione per induzione

E’ la principale tecnica dimostrativa con la quale si dimostra che un enunciato vale per tutti i naturali maggiore di un n∈ℕ fissato o per tutti i naturali. Il principio di induzione afferma che per procedere alla dimostrazione di un enunciato E(n) si deve procedere :

– dimostrando il caso base n∈ℕ fissato inizialmente ( Base induttiva);

– dimostrando che ∀n∈ℕ ( E(n) ⇒ E(n+1)) (Passo induttivo) in cui E(n) è chiamata ipotesi induttiva e E(n+1) è la tesi induttiva. Nel passo si utilizza l’ipotesi induttiva, data per vera, per verificare la tesi (come nell’esempio posto sotto).

Esempio di dimostrazione per induzione:

Sia a ≥ −1. Dimostrare che vale la seguente disuguaglianza (chiamata disuguaglianza di Bernoulli):

(1 + a)^k ≥ 1 + k*a       ∀k ∈ ℕ≥ 0. 

Base k = 0: (1 + a)^0 = 1 + 0 1 = 1 Verificato caso base di partenza.

Passo induttivo k → k+1

Ipotesi induttiva: (1 + a)^k ≥ 1 + k*a

Tesi induttiva: (1 + a)^(k+1) ≥ 1 + (k+1)*a

(1 + a)^(k+1) =

(1 + a) · (1 + a)^k (1) ≥ (1 + a) · (1 + k*a) = 1 + k*a + a + k*a^2 (2) ≥ 1 +(k + 1)*a

dove in (1) è stata usata l’ipotesi induttiva ed in (2) il fatto che k*a^2 ≥ 0.

Q.E.D.

 Nonostante la loro remotezza dall’esperienza dei sensi, noi abbiamo un qualcosa simile a una percezione anche degli oggetti della teoria degli insiemi, come si può vedere dal fatto che gli assiomi stessi ci forzano a considerarli veri. Non vedo motivo perché dovremmo avere una fiducia minore in questo tipo di percezione, vale a dire l’intuizione matematica, piuttosto che nella percezione sensoriale, che ci induce a costruire teorie fisiche e aspettarci che future sensazioni sensoriali si accordino ad esse.

 Kurt Gödel, matematico, logico e filosofo austriaco 

  • Induzione Forte
Il principio d’induzione forte deriva da una versione con ipotesi più restrittive del quinto assioma di Peano (*), ma equivalente: se T è un sottoinsieme dell’insieme ℕ dei numeri naturali tale che: 
– 0 ∈ T
– se T contiene tutti i numeri minori di n, allora contiene anche n.
Allora T = ℕ
In formule:
∀ n ∈ ℕ (∀ k ∈ ℕ(k<n ⇒ k ∈ T) ⇒ n ∈ T)
allora T = ℕ
Quindi il principio di induzione forte richiede delle ipotesi più stringenti rispetto al principio di induzione: per richiedere che un enunciato valga per un numero n ∈ ℕ (tesi induttiva) è richiesto che l’enunciato valga su tutti i sui predecessori (ipotesi induttiva).
Rispetto al principio di induzione semplice si osserva che:
  • non abbiamo la distinzione base/passo induttivo: la base dell’induzione è infatti compresa nella formula ∀ n ∈ ℕ (∀ k ∈ ℕ(k<n ⇒ k ∈ T) ⇒ n ∈ T);
  •     l’ipotesi induttiva risulta più stringente.
 

La matematica è un’arte.
Paul Lockhart

 

 

(*) Quinto Assioma di Peano:

Ogni sottoinsieme di numeri naturali che contenga lo zero e il successore di ogni proprio elemento coincide con l’intero insieme dei numeri naturali (assioma dell’induzione).

Definiamo,assiomaticamente, i numeri naturali con gli assiomi di Peano:

  1. 0∈ ℕ;
  2. ogni n∈ ℕ ha un suo successore n’∈ ℕ;
  3. ∀ n ∈ ℕ(n’≠0);
  4. ∀ n,m ∈ ℕ(n≠m⇒m’≠n’)
  5. Per ogni S⊆ℕ (Assioma dell’Induzione):
  • 0∈ S;
  • ∀ n∈ ℕ(n∈ S⇒n’∈ S) Allora S = ℕ.

(**) Proprietà di Archimede:

Siano a,b ∈ ℜ, sia a < b, allora esiste n ∈ ℕ tale che n*a>b. 


Lasciare un commento