Principio de inducción (débil)

[lindtaylor]

Pongo para la web el teorema del principio de inducción que encontre en uno de mis cuadernos, me pareció una bella demostración .

Teorema: Sea $\alpha (n)$ una proposición que depende de $n \in {\mathbb {N}}$.

Si $\alpha (1) \wedge \forall {n}\in {\mathbb {N}} (\alpha (n) \Rightarrow \alpha (n+1)) \Rightarrow \forall {n}\in {\mathbb {N} (\alpha (n))$ se cumple.


Dem:

Si no es cierto entonces se cumple que:

$\alpha (1) \wedge \forall {n} \in {\mathbb {N}} (\alpha (n) \Rightarrow \alpha (n+1))$ y no se cumple $\forall {n}\in {\mathbb {N}} (\alpha(n))$

Entonces $\exists{n}\in {\mathbb {N}} (\sim \alpha (n))$

Por tanto $A=\left\{ n \in {\mathbb {N}} : \sim\alpha (n) \right\} \not = \emptyset$

Por Principio del buen orden, $A$ tiene un menor elemento, sea $m$ este elemento.

Como $\alpha (1)$ se cumple, $m>1$ ($1\not \in A$)

Luego $m-1\in \mathbb {N}$ y como $m$ es el menor elemento de $A$, $m-1$ $\not \in A$

Por tanto se cumple $\alpha (m-1).$

Como $\forall {n} \in \mathbb {N} (\alpha (n)\Rightarrow \alpha (n+1))$ obtengo $\alpha (m).$ cumple.

Por tanto, $m\not \in A$. ($\Rightarrow\Leftarrow$)

Luego $\forall {n} \in {\mathbb {N}} \alpha (n)$.

qed

[javier m]

La primera vez que lo vi no lo entendí.

Hoy que de casualidad vuelvo a verlo, lo entiendo

Es bonito ¿cierto?