Principio di induzione

1 - Principio di induzione semplice

Definizione: principio di induzione semplice

Data una proprietà $P$ dei numeri naturali, il principio di induzione semplice stabilisce che, se vengono rispettate le seguenti condizioni:

1. Caso base: $P(0)$ è vera;
2. Passo induttivo: assunta per vera $P(k)$ per un generico $k\in \mathbb{N}$ (ipotesi induttiva), risulta che $P(k+1)$ è vera (tesi induttiva);

allora la proprietà $P$ è vera per ogni $n\in \mathbb{N}$. In simboli:

$$P(0)\wedge \forall k\in \mathbb{N}(P(k)⟹P(k+1))⟹\forall n\in \mathbb{N}(P(n))$$

Osservazione: funzionamento del principio di induzione

Intuitivamente, il principio di induzione semplice si può giustificare come segue. Supponiamo che valgano $P(0)$ e $\forall k\in \mathbb{N}(P(k)⟹P(k+1))$, allora:

• $P(0)$ vale perché è la prima ipotesi.
• Poiché valgono $P(0)$ per la prima ipotesi e $\forall k\in \mathbb{N}(P(k)⟹P(k+1))$ per la seconda ipotesi (applicata a $n=0$), si ha per modus ponens che vale $P(0+1)=P(1)$.
• Poiché valgono $P(1)$ per il punto precedente e $\forall k\in \mathbb{N}(P(k)⟹P(k+1))$ per la seconda ipotesi (applicata a $n=1$), si ha per modus ponens che vale $P(1+1)=P(2)$.
• Poiché valgono $P(2)$ per il punto precedente e $\forall k\in \mathbb{N}(P(k)⟹P(k+1))$ per la seconda ipotesi (applicata a $n=2$), si ha per modus ponens che vale $P(2+1)=P(3)$.

Proseguendo in questo modo, qualunque sia $k>0$, arriveremo a dimostrare che deve valere $P(k)$ (poiché valeva $P(k-1)$, che a sua volta seguiva da $P(k-2)$, che a sua volta seguiva da $P(k-3)$ e così via, fino a $P(0)$). Dunque si ha che $P(k)$ vale per ogni $k\in \mathbb{N}$ come desiderato.

Esempio

Proposizione

$$\forall n\in \mathbb{N}\left(\sum _{i=0}^{n}i=\frac{n(n+1)}{2}\right)$$

Dimostrazione

Dimostriamo per induzione che $\forall n\in \mathbb{N}(P(n))$, dove $P(n)$ è l’uguaglianza $\sum _{i=0}^{n}i=\frac{n(n+1)}{2}$.

1. Caso base: dobbiamo verificare $P(0)$, ovvero che $\sum _{i=0}^{0}i=\frac{0(0+1)}{2}$:

$$\left(\sum _{i=0}^{0}i=0\right)\wedge \left(\frac{0(0+1)}{2}=0\right)⟹\sum _{i=0}^{0}i=\frac{0(0+1)}{2}$$

2. Passo induttivo: dobbiamo dimostrare che $\forall n\in \mathbb{N}(P(n)⟹P(n+1))$. Consideriamo un generico $n\in \mathbb{N}$ e assumiamo che valga $P(n)$ (cioè $\sum _{i=0}^{n}i=\frac{n(n+1)}{2}$) al fine di dimostrare $P(n+1)$ (cioè $\sum _{i=0}^{n+1}i=\frac{(n+1)(n+2)}{2}$):

$$\begin{array}{rl}\sum _{i=0}^{n+1}i& =\sum _{i=0}^{n}i+(n+1)\\ & =\frac{n(n+1)}{2}+(n+1)\\ & =\frac{n(n+1)+2(n+1)}{2}\\ & =\frac{(n+1)(n+2)}{2}\end{array}$$

Avendo dimostrato sia il caso base $P(0)$ che il passo induttivo $\forall n\in \mathbb{N}(P(n)⟹P(n+1))$, possiamo concludere che la proposizione è verificata.

$■$

Esempio

Proposizione

$$\forall n\in \mathbb{N}\left(\sum _{i=0}^{n}2i+1=(n+1{)}^2\right)$$

Dimostrazione

Dimostriamo per induzione che $\forall n\in \mathbb{N}(P(n))$, dove $P(n)$ è l’uguaglianza $\sum _{i=0}^{n}2i+1=(n+1{)}^2$.

1. Caso base: dobbiamo verificare $P(0)$, ovvero che $\sum _{i=0}^{0}2i+1=(0+1{)}^2$:

$$\left(\sum _{i=0}^{0}2i+1=1\right)\wedge \left((0+1{)}^2=1\right)⟹\sum _{i=0}^{0}2i+1=(0+1{)}^2$$

2. Passo induttivo: dobbiamo dimostrare che $\forall n\in \mathbb{N}(P(n)⟹P(n+1))$. Consideriamo un generico $n\in \mathbb{N}$ e assumiamo che valga $P(n)$ (cioè $\sum _{i=0}^{n}2i+1=(n+1{)}^2$) al fine di dimostrare $P(n+1)$ (cioè $\sum _{i=0}^{n+1}2i+1=(n+2{)}^2$):

$$\begin{array}{rl}\sum _{i=0}^{n+1}2i+1& =\left(\sum _{i=0}^{n}2i+1\right)+2(n+1)+1\\ & =(n+1{)}^2+2(n+1)+1\\ & =(n+2{)}^2\end{array}$$

Avendo dimostrato sia il caso base $P(0)$ che il passo induttivo $\forall n\in \mathbb{N}(P(n)⟹P(n+1))$, possiamo concludere che la proposizione è verificata.

$■$

Osservazione: dimostrazione per induzione da $n>0$

A volte si deve dimostrare che una proprietà $P(n)$ vale non per tutti i numeri naturali, ma solo da un certo $k$ in poi, cioè si deve dimostrare che $P(n)$ vale per ogni $n\ge k>0$.

Dal punto di vista teorico, non è necessario introdurre un nuovo principio di induzione, dato che $\forall n\ge k((P(n))$ è equivalente a $\forall m(Q(m))$, dove $Q(m)$ è $P(m+k)$. Dimostrare per induzione $\forall m(Q(m))$ equivale a:

1. Verificare il caso base $Q(0)$, cioè $P(k)$;
2. Dimostrare il passo induttivo: fissato un $m$ arbitrario, verificare che $Q(m)⟹Q(m+1)$, cioè $P(m+k)⟹P(m+k+1)$; in altre parole, fissato un $m\ge k$ arbitrario, dobbiamo verificare che $P(m)⟹P(m+1)$.

2 - Un uso fallace dell’induzione

3 - Principio di induzione forte

Definizione: principio di induzione forte

Data una proprietà $P$ dei numeri naturali, il principio di induzione forte stabilisce che, se vengono rispettate le seguenti condizioni:

1. Caso base: $P(0)$ è vera;
2. Passo induttivo: assunti per veri tutti i $P(0),P(1),\dots ,P(k)$ per un generico $k\in \mathbb{N}$ (ipotesi induttiva), risulta che $P(k+1)$ è vera (tesi induttiva);

allora la proprietà $P$ è vera per ogni $n\in \mathbb{N}$. In simboli:

$$P(0)\wedge \forall k\in \mathbb{N}(P(0)\wedge P(1)\wedge \dots \wedge P(k)⟹P(k+1))⟹\forall n\in \mathbb{N}(P(n))$$

Proposizione: principio di induzione forte equivalente a quello semplice

Si dimostra che anche il principio di induzione forte è equivalente al principio di induzione semplice (e quindi anche al principio del minimo).

Esempio

Utilizziamo il principio di induzione forte per dare una nuova dimostrazione della seguente

Proposizione

Ogni numero naturale $\ge 2$ ha una scomposizione in fattori primi.

Dimostrazione

È sufficiente dimostrare che, dato un generico $n$, se la proprietà $P(m)$ data da

$$n\ge 2⟹m\text{ha una scomposizione in fattori primi}$$

vale per ogni $m<n$, allora vale anche $P(n)$. Distinguiamo i due casi:

• Caso base: se $n$ è un numero primo non c’è nulla da dimostrare, la sua scomposizione in fattori primi è $n$ stesso.
• Passo induttivo: se invece $n$ è composto, allora $n=m\cdot l$ con $2\le m,l<n$. Per ipotesi induttiva, sia $m$ che $l$ possono essere scomposti in fattori primi:

$$m=p_1\cdot p_2\cdot \dots \cdot p_k\wedge l=q_1\cdot q_2\cdot \dots \cdot q_k$$

Quindi anche $n$ ha una scomposizione in fattori primi:

$$n=(p_1\cdot p_2\cdot \dots \cdot p_k)\cdot (q_1\cdot q_2\cdot \dots \cdot q_k)$$

$■$

4 - Principio di induzione strutturale semplice

Il principio di induzione può talvolta essere utilizzato per dimostrare proprietà universali per insiemi (non necessariamente numerici) “stratificati” in maniera opportuna. Il principio di induzione strutturale semplice è una tecnica utilizzata per dimostrare proprietà su oggetti definiti in modo ricorsivo o induttivo, come stringhe, alberi, o termini di linguaggi formali.

Definizione: principio di induzione strutturale semplice

Data una proprietà $P$ su un insieme della forma $A=\bigcup _{n\in \mathbb{N}}{A}_n$, il principio di induzione strutturale semplice stabilisce che, se vengono rispettate le seguenti condizioni:

1. Caso base: $P(a)$ è vera per ogni $a\in A_0$;
2. Passo induttivo: per ogni $n\in \mathbb{N}$, assunta per vera $P(a)$ per un generico $a\in A_n$ (ipotesi induttiva), risulta che $P(a)$ vale per un generico $a\in A_{n+1}$ (tesi induttiva);

allora la proprietà $P$ è vera per ogni $a\in A$. In simboli:

$$\forall a\in A_0(P(a))\wedge \forall n\in \mathbb{N}(\forall a\in A_n(P(a))⟹\forall a\in A_{n+1}(P(a)))⟹\forall a\in A(P(a))$$

5 - Principio di induzione strutturale forte

Similmente, anche il principio di induzione forte può essere generalizzato.

Definizione: principio di induzione strutturale forte

Data una proprietà $P$ su un insieme della forma $A=\bigcup _{n\in \mathbb{N}}{A}_n$, il principio di induzione strutturale semplice stabilisce che, se vengono rispettate le seguenti condizioni:

1. Caso base: $P(a)$ è vera per ogni $a\in A_0$;
2. Passo induttivo: per ogni $n\in \mathbb{N}$, assunta per vera $P(a)$ per ogni $a\in \bigcup _{k=0}^n{A}_k$ (ipotesi induttiva), risulta che $P(a)$ vale per ogni $a\in A_{n+1}$​ (tesi induttiva);

allora la proprietà $P$ è vera per ogni $a\in A$. In simboli:

$$\forall a\in A_0(P(a))\wedge \forall n\in \mathbb{N}\left(\forall a\in \bigcup _{k=0}^n{A}_k(P(a))⟹\forall a\in A_{n+1}(P(a))\right)⟹\forall a\in A(P(a))$$

Fonti

• 🏫 Lezioni e slide del Prof. Viale Matteo del corso di Logica Matematica (canale B), Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2024-25:
  • 3.1 - Le Diverse Forme del Principio di Induzione_moodle.pdf