Siguiente: Inducción recurrente Un nivel arriba: Inducción matemática Anterior: Inducción matemática

Inducción numérica

Sea $\phi$ una fórmula con una variable libre x, definida en el lenguaje de la aritmética. Para demostrar la sentencia $\forall n(\phi(n))$, un primer esquema de inducción verifica primero que se cumple $\phi(0)$ y luego, suponiendo que se cumple $\phi(n)$ demuestra que se cumple $\phi(n+1)$; un segundo esquema de inducción verifica primero que se cumple $\phi(0)$ y luego, suponiendo que se cumple $\phi(m)$, para cualquier m<n, demuestra que se cumple $\phi(n)$. Estos esquemas, puestos como reglas de deducción quedan como sigue:

$$\begin{array}{lcl} \mbox{\it Esquema I} &:& \frac{\textstyle... ...}}{\textstyle {\textstyle \ \ \forall n(\phi(n))}} \end{array}$$

Teorema 2.1   Ambos esquemas son equivalentes.

En efecto:

1.

$\mbox{\it Esquema I} \;\Rightarrow \;\mbox{\it Esquema II}$): Supongamos válido el $\mbox{\it Esquema I}$. Sea $\phi$ una fórmula tal que se cumplen

$$\phi(0)\hspace{1cm}\&\hspace{1cm}\forall n(\forall m<n( \phi(m))\Rightarrow \phi(n)).\eqno(*)$$

Mostremos primero que

$$\forall n( \phi(0)\Rightarrow \forall m\leq n:\phi(m)).\eqno(**).$$

Para esto usemos el $\mbox{\it Esquema I}$ aplicado a la fórmula $\phi_1(n)\equiv\left[\phi(0)\Rightarrow \forall m\leq n:\phi(m)\right]$. $\phi_1(0)$ se cumple en virtud de que para cualquier fórmula $\psi$, la fórmula $(\psi\Rightarrow\psi)$ es un teorema del cálculo de predicados puro. Ahora, supongamos que vale $\phi_1(n)$. Hemos de probar que vale $\phi_1(n+1)$. Supongamos $\phi(0)$. Por $\phi_1(n)$ se tiene que es válido $(\forall m\leq n:\phi(m))$. Por (*) se cumple también $\phi(n+1)$. Así pues, la fórmula $(\forall m\leq (n+1):\phi(m))$ es válida, con lo cual se ve que, en efecto, la fórmula $\phi_1(n+1)$ se cumple. Demostremos ahora que vale $\forall n\left[\phi(n)\Rightarrow \phi(n+1)\right]$. Dado un n cualquiera, suponiendo que se cumple $\phi(n)$, puesto que $\phi(0)$ es cierto, se cumple por (**) que $\forall m\leq n:\phi(m)$ y por (*) resulta ya demostrado $\phi(n+1)$. Por el Esquema I, resulta como una consecuencia $\forall n\phi(n)$. Tenemos pues que se cumple el Esquema II.

2.

$\mbox{\it Esquema II} \;\Rightarrow \; \mbox{\it Esquema I}$): Supongamos válido el $\mbox{\it Esquema II}$. Sea $\phi$ una fórmula tal que se cumplen

$$\phi(0)\hspace{1cm}\&\hspace{1cm}\forall n( \phi(n)\Rightarrow \phi(n+1)).\eqno(*)$$

Resulta evidente que se cumple la fórmula $\forall n(\forall m<n( \phi(m))\Rightarrow \phi(n))$, pues, para cada n>0 la condición $[\forall m<n: \phi(m)]$ subsume a la fórmula $\phi(n-1)$, la cual, de acuerdo con la segunda fórmula en (*) de este apartado implica $\phi(n)$. Por el Esquema II, resulta como una consecuencia $\forall n\phi(n)$. Tenemos pues que se cumple también el Esquema I.

Siguiente: Inducción recurrente Un nivel arriba: Inducción matemática Anterior: Inducción matemática