Principio d'induzione

Poll without page-refresh

Article on other languages:

Il principio d'induzione è un enunciato sui numeri naturali che in matematica trova un ampio impiego nelle dimostrazioni.

Esso asserisce che

Se $\mathcal{P}$ è una proprietà che vale per $k\in\mathbb{N}$ ;
Se $\mathcal{P}(n) \Rightarrow \mathcal{P}(n+1)$ per $n\ge k$ ;
allora $\mathcal{P}$ vale per ogni $n\in\mathbb N$ con $n\ge k$ .

Il principio d'induzione deriva direttamente dal quinto assioma di Peano, ed è ad esso equivalente: assumendolo cioè come assioma, ne deriva il quinto assioma di Peano.

L' effetto domino fornisce una metafora esplicativa per il principio d'induzione

L'idea intuitiva con cui si può comprendere il senso dell'enunciato è quella di un "effetto domino": affinché le tessere da domino disposte lungo una fila cadano tutte sono sufficienti due condizioni:

che cada la prima tessera
che ogni tessera sia posizionata in modo tale che cadendo provochi la caduta della successiva.

Il principio d'induzione estende quest'idea al caso in cui la fila è composta da infinite tessere.

Indice

1 Dimostrazioni per induzione
- 1.1 Un esempio
2 Il principio d'induzione forte
3 Forme equivalenti del principio d'induzione
4 L'induzione è un assioma o un teorema?
5 Generalizzazioni
- 5.1 Base diversa dallo zero
- 5.2 Induzione transfinita
6 Errori e fraintendimenti
7 Voci correlate

Dimostrazioni per induzione

Il principio d'induzione offre un importante strumento per le dimostrazioni. Per dimostrare che un certo asserto $P (n)$ in cui compare un numero naturale $n$ vale per qualunque $n \in \mathbb N$ si può sfruttare il principio d'induzione nel seguente modo:

Si pone $U=\{n\in \mathbb N: \mbox{vale } P(n)\}$ ,

si dimostra che vale $P (1)$ (o $P (0)$ ), cioè che $1$ (o $0$ ) è nell'insieme dei numeri naturali $U$ per cui vale $P (n)$ ;
si assume come ipotesi che l'asserto $P (n)$ valga per un generico $n$ e da tale assunzione si dimostra che vale anche $P (n + 1)$ (cioè che $n\in U \Rightarrow n+1\in U$ )

e quindi si conclude che l'insieme $U$ dei numeri per cui vale $P (n)$ coincide con tutto l'insieme dei numeri naturali. Il punto 1 è generalmente chiamato base dell'induzione, il punto 2 passo induttivo.

Un modo intuitivo con cui si può guardare a questo tipo di dimostrazioni è il seguente: se disponiamo di una dimostrazione della base

P (0)

e del passo induttivo

$\forall n\, P(n) \Rightarrow P(n+1)$

allora chiaramente possiamo sfruttare queste dimostrazioni per dimostrare $P (1)$ usando la regola logica modus ponens su $P (0)$ (la base) e $P(0) \Rightarrow P(1)$ (che è un caso particolare del passo induttivo per $n = 0$ ), poi possiamo dimostrare $P (2)$ poiché adesso usiamo il modus ponens su $P (1)$ e $P(1) \Rightarrow P(2)$ , così per $P (3)$ , $P (4)$ , eccetera... è chiaro a questo punto che possiamo produrre una dimostrazione in un numero finito di passi (eventualmente lunghissimo) di $P (n)$ per qualunque numero naturale $n$ , da cui deduciamo che $P (n)$ è vero per ogni $n \in \N$ .

Un esempio

Dimostriamo che vale l'asserto

per ogni $n \in \mathbb N$ risulta $0+1+2+3+4+...+n=\frac{n(n+1)}{2}$

Abbiamo in questo caso $P(n) \quad \equiv \quad 0+1+2+3+4+...+n=\frac{n(n+1)}{2}$ .

Base dell'induzione: dobbiamo dimostrare che l'affermazione $P (n)$ è vera per $n = 0$ , cioè, sostituendo, che $0=\frac{0\cdot 1}2$ , e in effetti c'è ben poco da lavorare, si tratta di un calcolo elementare;
Passo induttivo: dobbiamo mostrare che per ogni n vale l'implicazione $P(n)\Rightarrow P(n+1)$ , cioè, sostituendo:

$0+1+2+3+4+...+n=\frac{n(n+1)}{2} \quad \Rightarrow \quad 0+1+2+3+4+...+n+(n+1)=\frac{(n+1)((n+1)+1)}{2}$

Dunque dobbiamo assumere che sia vero

$P(n) \quad \equiv \quad 0+1+2+3+4+...+n=\frac{n(n+1)}{2}$ ,

lavorare su questa uguaglianza e concludere con l'analoga uguaglianza per $n + 1$ , vale a dire:

$P(n+1) \quad \equiv \quad 0+1+2+3+4+...+n+(n+1)=\frac{(n+1)((n+1)+1)}{2}$ .

Potremmo ad esempio aggiungere $n + 1$ a entrambi i membri dell'uguaglianza P(n):

$0+1+2+3+4+...+n+(n+1)=\frac{n(n+1)}{2}+(n+1)$ ,

poi facciamo qualche semplice passaggio algebrico:

$0+1+2+3+4+...+n+(n+1)=\frac{n(n+1)}{2}+\frac{2(n+1)}2$ ,

$0+1+2+3+4+...+n+(n+1)=\frac{(n+1)(n+2)}{2}$ ,

$0+1+2+3+4+...+n+(n+1)=\frac{(n+1)((n+1)+1)}{2}$

e quest'ultima uguaglianza è esattamente $P (n + 1)$ . Questo conclude la dimostrazione del passo induttivo.

Avendo dunque dimostrato la base dell'induzione e il passo induttivo possiamo concludere (dal principio d'induzione) che $P (n)$ deve essere vera per ogni $n\in \mathbb N$ . $\square$

Il principio d'induzione forte

Il principio d'induzione forte deriva da una versione con ipotesi più restrittive del quinto assioma di Peano, ma equivalente, ossia:

Se $U \,\!$ è un sottoinsieme dell'insieme $\mathbb N$ dei numeri naturali tale che

$U$ contiene $1$ (o $0$ ),

se $U$ contiene tutti i numeri minori di $n$ allora contiene anche $n$

allora $U=\mathbb N$

La parola "forte" è legata al fatto che questa formulazione richiede delle ipotesi apparentemente più forti e stringenti per inferire che l'insieme $U$ coincide con $\mathbb N$ : per ammettere un numero nell'insieme è richiesto infatti che tutti i precedenti ne facciano già parte (e non solo il numero precedente). In pratica la proprietà $\mathcal{P}$ deve valere non solo per n, ma per ogni $x \in \mathbb N : x < n$ . Non è difficile dimostrare la sua equivalenza al principio d'induzione, ragionando così: se vale per 1 ( o 0), vale anche per il suo successore, e per il successore di quest'ultimo, etc etc fino ad n. Inoltre, se la proprietà vale per ogni numero minore di n, vale anche per 1 (o 0), e se vale per b, vale anche per b+1 <= n, ed è perciò equivalente al principio d'induzione.

Questa formulazione rende talvolta le dimostrazioni per induzione più agevoli data la possibilità di poter disporre di una platea più ampia di ipotesi (tutti i numeri minori di $n$ ) per la dimostrazione del successivo "passo induttivo". Questo si verifica, ad esempio, nella dimostrazione della fattorizzabilità dei numeri interi: laddove si voglia usare il principio d'induzione, la regressione da un numero n a fattori più piccoli non porta al numero precedente m ma a numeri più piccoli. La stessa situazione si incontra nella la fattorizzazione dei polinomi.

Forme equivalenti del principio d'induzione

In totale le forme del principio d'induzione sono 4:

induzione classica
induzione estesa
principio del minimo intero
principio della discesa infinita

Queste forme sono equivalenti nel senso che assumendone vera una si possono dimostrare le altre tre.

L'induzione è un assioma o un teorema?

Generalmente, il principio d'induzione è indicato come assioma dei numeri naturali: a volte viene considerato al posto del quinto assioma di Peano, ottenendo un modello equivalente, in quanto, come detto in precedenza, i due sono equivalenti. La teoria che si ottiene considerando gli assiomi classici di Peano formalizzati (cioè gli assiomi dell'aritmetica di Peano) eccettuato il principio d'induzione viene chiamata Aritmetica di Robinson ed ammette modelli alternativi in cui il principio d'induzione è falso.

Esistono però alcuni sistemi logici in cui esso può essere dimostrato: ad esempio, quando viene usato l'assioma

L'insieme dei numeri naturali è bene ordinato

ovvero

Ogni sottoinsieme non vuoto dell'insieme dei numeri naturali ha un numero minimo

noto anche come Principio del Buon Ordinamento per i numeri naturali. In realtà, questo assioma aggiuntivo è una formulazione alternativa del principio d'induzione matematica: i due assiomi sono infatti equivalenti.

Infatti se un insieme non vuoto non ha minimo lo 0 non gli appartiene. Assumendo poi che numeri inferiori a m numeri non gli appartengono, allora anche m non gli appartiene (altrimenti sarebbe il minimo. Applicando l'induzione forte si ottiene che nessun numero gli appartiene.

Viceversa, dato un insieme goda delle due proprietà enunciate dal principio d'induzione senza coprire tutto $\mathbb N$ . Esisterà, per il buon ordinamento, il minimo numero che non gli appartiene e sia questo m. Allora m non può essere 0. Il suo precedente m-1 non rispetta l'ipotesi induttiva.

Tuttavia, in alcuni casi il principio d'induzione non è considerato assioma, ciò dipende da come è definito l'insieme dei numeri naturali. Se definisco l'insieme $\mathbb N$ per via assiomatica (con gli assiomi di Peano) avrò che il pricipio d'induzione è un assioma, come precedentemente detto, viceversa se definisco l'insieme $\mathbb N$ come il più piccolo insieme induttivo contenuto in $\mathbb R$ , e più precisamente come l'intersezione di tutti gli insiemi induttivi contenuti in $\mathbb R$ , avrò che il principio d'induzione non si potrà considerare un assioma non essendo l'insieme $\mathbb N$ definito per via assiomatica, ma sarà una conseguenza del fatto che $\mathbb N$ è il più piccolo insieme induttivo.

Generalizzazioni

Base diversa dallo zero

Una prima generalizzazione molto elementare consiste nel far partire l'induzione da un numero naturale k diverso da zero. Ovvero: se vogliamo dimostrare che un enunciato $P (n)$ vale per ogni numero naturale $n$ maggiore di un numero prefissato $k$ applichiamo la tecnica di dimostrazione per induzione considerando come base dell'induzione $P (k)$ anziché $P (0)$ .

Induzione transfinita

Per approfondire, vedi la voce induzione transfinita.

Il principio d'induzione transfinita generalizza il principio d'induzione alla classe degli ordinali transfiniti On (di cui i numeri naturali sono un sottoinsieme).
Esso afferma che:

Se $U$ è un sottoinsieme della classe $O n$ di tutti gli ordinali che verifica le seguenti due proprietà:

$U$ contiene $0$ ,

ogni volta che $U$ contiene tutti gli ordinali $a$ minori di $b$ allora $U$ contiene anche $b$ ,

allora $U$ coincide con l'intera classe degli ordinali $O n$ .

Il principio d'induzione transfinita, a differenza del principio d'induzione forte, è un principio strettamente più potente del principio d'induzione, infatti esistono teoremi come il Teorema di Goodstein che possono essere dimostrati per induzione transfinita ma non possono essere dimostrati mediante l'induzione semplice.

Errori e fraintendimenti

Una classica applicazione sbagliata del Principio d'induzione è la seguente "dimostrazione" che porta a concludere che

Tutti i cavalli sono dello stesso colore

Ragioniamo per induzione sulla grandezza dei possibili insiemi di cavalli: dimostriamo che per ogni $n \in \mathbb N$ vale $P (n)$ ="un insieme di $n$ cavalli contiene tutti cavalli dello stesso colore":

1. Base dell'induzione: un insieme formato da un unico cavallo (n=1) contiene tutti cavalli dello stesso colore.

2. Passo induttivo: supponiamo vero

P (n)

="un insieme di

n

cavalli contiene tutti cavalli dello stesso colore" e dimostriamo

P (n + 1)

: un insieme di

n + 1

cavalli si può guardare come l'unione di due insiemi di

n

cavalli che hanno in comune

n - 1

elementi, quindi dall'ipotesi induttiva questi insiemi hanno tutti cavalli dello stesso colore, e dal fatto che hanno intersezione non vuota deduciamo che tutti gli

n + 1

cavalli hanno lo stesso colore, cioè abbiamo dimostrato

P (n + 1)

Segue dal principio d'induzione che qualunque sia il numero di cavalli presenti al mondo, questi hanno tutti lo stesso colore.

In realtà: la dimostrazione del passo induttivo precedente è solo apparente: infatti per n=1 i due insiemi di n elementi hanno in comune n-1 = 0 elementi e non si può quindi dedurre che n+1 = 2 cavalli abbiano lo stesso colore.

Voci correlate

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

Estratto da "http://it.wikipedia.org/wiki/Principio_d%27induzione"

Categorie: Logica matematica | Teoria dei numeri

Categoria nascosta: Voci di qualità su he.wiki

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.