Principio d'induzione

Il principio d'induzione (da non confondersi con il metodo di induzione) è un enunciato sui numeri naturali che in matematica trova un ampio impiego nelle dimostrazioni, per provare che una certa proprietà è valida per tutti i numeri interi. L'idea intuitiva alla sua base è l'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 sia composta da infinite tessere.

Il principio d'induzione asserisce che se ${\displaystyle P}$ è una proprietà che vale per il numero 0, e se ${\displaystyle P(n)\Rightarrow P(n+1)}$ per ogni ${\displaystyle n}$, allora ${\displaystyle P(n)}$ vale per ogni ${\displaystyle n}$.

In simboli:

${\displaystyle (\forall P)[P(0)\land (\forall k\in \mathbb {N} )(P(k)\Rightarrow P(k+1))]\Rightarrow (\forall n\in \mathbb {N} )[P(n)],}$

dove ${\displaystyle k}$ e ${\displaystyle n}$ sono numeri naturali.

La prima attestazione specifica del principio è del 1861, a opera di Hermann Günther Grassmann^[1]. Il suo primo utilizzo in una dimostrazione risale al 1575 da parte dell'italiano Francesco Maurolico^[2]. Nel XVII secolo Pierre de Fermat ne raffinò l'utilizzo formulandolo come principio della discesa infinita^[2], e la nozione compare anche chiaramente nei lavori più tardi di Blaise Pascal (1653)^[2]. L'espressione "induzione matematica" apparentemente sembra essere stata coniata dal logico e matematico A. De Morgan nei primi del XIX secolo^[2]. La sua formulazione completa, usata ancora oggi, è essenzialmente quella data da Giuseppe Peano nei suoi Arithmetices Principia, pubblicati nel 1889. 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.

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

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

1. si dimostra che vale ${\displaystyle P(1)}$ (o ${\displaystyle P(0)}$), cioè che ${\displaystyle 1}$ (o ${\displaystyle 0}$) è nel sottoinsieme dei numeri naturali ${\displaystyle U}$ per cui vale ${\displaystyle P(n)}$,
2. si assume come ipotesi che l'asserto ${\displaystyle P(n)}$ valga per un generico ${\displaystyle n}$ e da tale assunzione si dimostra che vale anche ${\displaystyle P(n+1)}$ (cioè che ${\displaystyle n\in U\Rightarrow n+1\in U}$),

e quindi si conclude che l'insieme ${\displaystyle U}$ dei numeri per cui vale ${\displaystyle P(n)}$ coincide con 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

${\displaystyle P(0)}$

e del passo induttivo

${\displaystyle \forall n\,P(n)\Rightarrow P(n+1),}$

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

Dimostriamo che vale l'asserto: per ogni ${\displaystyle n\in \mathbb {N} ^{+}}$ risulta:

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

Abbiamo in questo caso definito ${\displaystyle P(n)=1+2+3+4+\ldots +n={\frac {n(n+1)}{2}}}$.

• Base dell'induzione: l'affermazione ${\displaystyle P(n)}$ è vera per ${\displaystyle n=1}$, infatti, per sostituzione, si verifica che ${\displaystyle P(1)={\frac {1\cdot (1+1)}{2}}={\frac {1\cdot 2}{2}}=1}$
• Passo induttivo: dobbiamo mostrare che per ogni ${\displaystyle n}$ la validità della formula, cioè che ${\displaystyle P(n)={\frac {n(n+1)}{2}}}$, implica che la formula valga anche per ${\displaystyle n+1}$ oppure, esplicitamente:

${\displaystyle {\frac {n(n+1)}{2}}\quad \Rightarrow \quad {\frac {(n+1)((n+1)+1)}{2}}}$

la dimostrazione di questa affermazione diventa più semplice dopo aver premesso che sommare i primi ${\displaystyle n+1}$ numeri interi equivale ad aggiungere ${\displaystyle n+1}$ alla somma dei primi ${\displaystyle n}$ numeri interi, cioè che:

${\displaystyle P(n+1)=1+2+3+4+\ldots +n+(n+1)=P(n)+(n+1)}$

quindi la dimostrazione che cerchiamo si ottiene aggiungendo ${\displaystyle n+1}$ a ${\displaystyle P(n)}$ e verificando che il risultato coincida con ${\displaystyle P(n+1)}$ i passaggi algebrici sono dunque:

${\displaystyle P(n)+(n+1)=1+2+3+4+\ldots +n+(n+1)={\frac {n(n+1)}{2}}+(n+1)={\frac {n(n+1)+2(n+1)}{2}}={\frac {(n+1)(n+2)}{2}}=}$

${\displaystyle ={\frac {(n+1)((n+1)+1)}{2}}=P(n+1).}$

Questo conclude la dimostrazione del passo induttivo.

Avendo dunque verificato la validità sia della base dell'induzione che del passo induttivo, possiamo concludere che la formula

${\displaystyle 1+2+3+4+\ldots +n={\frac {n(n+1)}{2}}}$

è vera per ogni ${\displaystyle n\in \mathbb {N} ^{+}}$.

Il principio d'induzione forte deriva da una versione con ipotesi apparentemente più restrittive del quinto assioma di Peano, ma equivalente: se ${\displaystyle U}$ è un sottoinsieme dell'insieme ${\displaystyle \mathbb {N} }$ dei numeri naturali tale che

• ${\displaystyle U}$ contiene ${\displaystyle 1}$ (o ${\displaystyle 0}$),
• se ${\displaystyle U}$ contiene tutti i numeri minori di ${\displaystyle n}$ allora contiene anche ${\displaystyle n,}$

allora ${\displaystyle 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 ${\displaystyle U}$ coincide con ${\displaystyle \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à ${\displaystyle {\mathcal {P}}}$ deve valere non solo per ${\displaystyle n}$, ma per ogni ${\displaystyle x\in \mathbb {N} :x<n}$. Non è difficile dimostrare la sua equivalenza logica con il principio d'induzione, ragionando così: se vale per 1 (o 0), vale anche per il suo successore, e per il successore di quest'ultimo, ecc., fino a ${\displaystyle n.}$ Inoltre, se la proprietà vale per ogni numero minore di ${\displaystyle n,}$ vale anche per 1 (o 0), e se vale per b, vale anche per ${\displaystyle b+1\leq n,}$ ed è perciò equivalente al principio d'induzione.

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

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.

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.

Ossia

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 ${\displaystyle 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 ${\displaystyle \mathbb {N} }$. Esisterà, per il buon ordinamento, il minimo numero che non gli appartiene e sia questo ${\displaystyle m.}$ Allora ${\displaystyle m}$ non può essere 0. Il suo precedente ${\displaystyle 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 ${\displaystyle \mathbb {N} }$ per via assiomatica (con gli assiomi di Peano) avrò che il principio d'induzione è un assioma, come precedentemente detto, viceversa se definisco l'insieme ${\displaystyle \mathbb {N} }$ come il più piccolo insieme induttivo contenuto in ${\displaystyle \mathbb {R} }$, e più precisamente come l'intersezione di tutti gli insiemi induttivi contenuti in ${\displaystyle \mathbb {R} }$, avrò che il principio d'induzione non si potrà considerare un assioma non essendo l'insieme ${\displaystyle \mathbb {N} }$ definito per via assiomatica, ma sarà una conseguenza del fatto che ${\displaystyle \mathbb {N} }$ è il più piccolo insieme induttivo.

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

Lo stesso argomento in dettaglio: 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 ${\displaystyle U}$ è un sottoinsieme della classe ${\displaystyle On}$ di tutti gli ordinali che verifica le seguenti due proprietà:

• ${\displaystyle U}$ contiene ${\displaystyle 0}$,
• ogni volta che ${\displaystyle U}$ contiene tutti gli ordinali ${\displaystyle a}$ minori di ${\displaystyle b}$ allora ${\displaystyle U}$ contiene anche ${\displaystyle b}$,

allora ${\displaystyle U}$ coincide con l'intera classe degli ordinali ${\displaystyle On}$.

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.

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 ${\displaystyle n\in \mathbb {N} }$ vale ${\displaystyle P(n)}$="un insieme di ${\displaystyle n}$ cavalli contiene tutti cavalli dello stesso colore":

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

2. Passo induttivo: supponiamo vero ${\displaystyle P(n)}$="un insieme di ${\displaystyle n}$ cavalli contiene tutti cavalli dello stesso colore" e dimostriamo ${\displaystyle P(n+1)}$: un insieme di ${\displaystyle n+1}$ cavalli si può guardare come l'unione di due insiemi di ${\displaystyle n}$ cavalli che hanno in comune ${\displaystyle 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 ${\displaystyle n+1}$ cavalli hanno lo stesso colore, cioè abbiamo dimostrato ${\displaystyle P(n+1)}$.

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

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

• Principio del buon ordinamento
• Assiomi di Peano
• Induzione transfinita

• Wikimedia Commons contiene immagini o altri file sul principio d'induzione

• Giovanni Vacca, INDUZIONE, in Enciclopedia Italiana, Istituto dell'Enciclopedia Italiana, 1933.
• (EN) mathematical induction, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Opere riguardanti Induction (Mathematics), su Open Library, Internet Archive.
• (EN) Eric W. Weisstein, Induction, su MathWorld, Wolfram Research.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri

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