Equivalencias de inducción

Enunciados

Empezamos presentando los enunciados de las equivalencias que veremos. En las dos formas de inducción daremos el enunciado de primer orden que los define. El principio del buen orden no se puede escribir en primer orden, así que no lo podemos enunciar con el mismo nivel de formalidad.

Inducción (débil)

Este es el principio de inducción más común. Para usarlo necesitamos una propiedad de números naturales, es decir, una fórmula de primer orden \(\varphi(x)\). El principio de inducción débil dice que si se \(0\) satisface la propiedad y si para todo \(n\), si \(n\) satisface la propiedad entonces \(n+1\) también la satisface, entonces todos los números naturales satisfacen la propiedad. En una fórmula, esto se escribe como:

\[\begin{equation} \label{eq:ind} \Big(\varphi(0)\land\forall n\big(\varphi(n)\to\varphi(n+1)\big)\Big) \to\forall n\;\varphi(n). \end{equation}\]

Inducción fuerte

Hay algunas propiedades para las cuales demostrar que \(n+1\) satisface la propiedad requiere que no sólo \(n\) la satisfaga, sino que más números anteriores satisfagan la propiedad. Para este caso, se puede usar inducción fuerte. La formula que define la inducción fuerte es:

\[\begin{equation} \label{eq:indf} \Big(\forall n\big(\forall m<n\;\varphi(m)\big)\to\varphi(n)\Big) \to\forall n\;\varphi(n). \end{equation}\]

Como se puede ver en la fórmula, este principio no requiere un “caso base”. De hecho el caso base está resumido en el antecedente.

Principio del buen orden

Este principio dice que \(\langle\mathbb{N},<\rangle\) es un conjunto bien ordenado. Esto es, dado \(A\subseteq\mathbb{N}\) si \(A\neq\emptyset\) entonces \(A\) tiene un elemento mínimo.

Equivalencias

Podríamos hacer una cadena de implicaciones entre los tres principios, pero mostraremos que el principio del buen orden es equivalente a inducción fuerte para enfatizar que la inducción fuerte no require caso base. De hecho, veremos que técnicamente uno es la contrapuesta del otro.

Buen orden implica inducción fuerte

Supongamos que \(\langle\mathbb{N},<\rangle\) es un conjunto bien ordenado y veamos que \(\mathbb{N}\) satisface \(\eqref{eq:indf}\). Sea \(\varphi(n)\) una propiedad de números naturales. Veamos que se satisface la contrapuesta de \(\eqref{eq:indf}\), es decir,

\[\begin{equation*} \exists n\;\neg\varphi(n)\to \Big(\exists n\; (\forall m<n\;\varphi(m))\land\neg\varphi(n)\Big). \end{equation*}\]

Así, supongamos que existe \(n\in\mathbb{N}\) tal que \(\neg\varphi(n)\) y consideramos el conjunto

\[A = \{n\in\mathbb{N}\mid \neg\varphi(n)\}.\]

Por nuestra suposición \(A\neq\emptyset\), así que por el principio del buen orden \(A\) tiene un elemento mínimo, digamos \(n_0\). Como \(n_0\) es el mínimo de \(A\), entonces \(n_0\in A\) y para todo \(m<n_0\) se tiene que \(m\notin A\). Por la definción de \(A\), esto significa que \(\neg\varphi(n_0)\) y para todo \(m<n_0\) se satisface \(\varphi(m)\). Lo cual es el consecuente de la implicación que queríamos mostrar.

Inducción fuerte implica buen orden

Supongamos que \(\mathbb{N}\) satisface \(\eqref{eq:indf}\) y veamos que es un conjunto bien ordenado. Sea \(A\subseteq\mathbb{N}\). Veamos que se satisface la contrapuesta del principio del buen orden, es decir, que si \(A\) no tiene mínimo, entonces \(A=\emptyset\).

Supongamos que \(A\) no tiene mínimo. Definimos la propiedad \(\varphi(n)\) como

\[\varphi(n) = n\notin A.\]

Para ver que \(A=\emptyset\), veamos que todos los naturales satisfacen \(\varphi(n)\), por inducción fuerte. Como estamos suponiendo que la implicación en \(\eqref{eq:indf}\) se cumple, entonces basta mostrar que se satisface el antecedente para concluir el consecuente, que es lo que queremos.

Sea \(n\in\mathbb{N}\) y supongamos que para todo \(m<n\) se tiene que \(\varphi(m)\), es decir, \(m\notin A\). Si \(n\in A\), entonces \(n\) sería el mínimo de \(A\), lo cual contradice nuestra suposición. Por lo tanto, \(n\notin A\) o bien, \(\varphi(n)\) se satisface. Así, por inducción fuerte, \(\forall n\in\mathbb{N}\;\varphi(n)\), lo cual significa que \(A=\emptyset\).

Inducción fuerte implica inducción débil

Dados los nombres de los principios, esta implicación debería ser fácil. Sea \(\varphi(n)\) una propiedad de números naturales. Supongamos que se satisface \(\eqref{eq:indf}\) y veamos que se satisface \(\eqref{eq:ind}\).

Supongamos que se satisface el antecedente de \(\eqref{eq:ind}\), es decir, que \(\varphi(0)\) y que para todo \(n\), si \(\varphi(n)\) entonces \(\varphi(n+1)\). Veamos que se satisface el consecuente, es decir, que para todo \(n\) se satisface \(\varphi(n)\). Esto lo haremos por inducción fuerte, es decir, mostraremos que se satisface el antecedente de \(\eqref{eq:indf}\).

Sea \(n\in\mathbb{N}\) y supongamos que para todo \(m<n\) se tiene que \(\varphi(m)\).Para ver que se satisface \(\varphi(n)\), hay dos casos. Si \(n=0\), entonces por hipótesis \(\varphi(0)\) se satisface. Si \(n=k+1\), como estamos suponiendo que todos los menores a \(n\) satisfacen la propiedad, entonces \(\varphi(k)\) se satisface y por nuestra hipótesis, \(\varphi(k+1)\) se satisface, es decir, \(\varphi(n)\) se satisface. Así, se satisface el antecedente de \(\eqref{eq:indf}\), lo cual implica que se satisface el consecuente, que es lo que queríamos mostrar.

Inducción débil implica inducción fuerte

Esta implicación no es tan fácil y requiere un truco. Sea \(\varphi(n)\) una propiedad de números naturales. Supongamos que se satisface \(\eqref{eq:ind}\) y que se satisface el antecedente de \(\eqref{eq:indf}\). Definimos otra propiedad como sigue:

\[\psi(n) = \forall m\leq n\;\varphi(m).\]

Veremos que \(\forall n\;\psi(n)\), lo cual implica que se satisface \(\forall n\;\varphi(n)\). Para ver que se satisface \(\forall n\;\psi(n)\) usaremos inducción débil.

El caso base es \(\psi(0)=\forall m\leq 0\;\varphi(m)\). Es claro que lo anterior es equivalente a \(\varphi(0)\). Por hipótesis en el caso \(n=0\), se satisface

\[(\forall m<0\;\varphi(m)) \to \varphi(0).\]

Además, el antecedente es cierto por vacuidad, no hay naturales menores que \(0\). Por lo tanto se satisface \(\varphi(0)\) y con esto tenemos \(\psi(0)\).

La hipótesis de inducción es que se satisface \(\psi(n)\), es decir, que se satisface \(\forall m\leq n\;\varphi(m)\). Veamos que se satisface \(\psi(n+1)\). Lo que tenemos que demostrar es \(\forall m\leq n+1\;\varphi(m)\). Por hipótesis de inducción, sólo falta ver que se satisface \(\varphi(n+1)\). Como supusimos el antecedente de inducción fuerte, ahora lo escribimos con \(n+1\):

\[(\forall m<n+1\;\varphi(m))\to\varphi(n+1).\]

Luego, notamos que \(m<n+1\) es equivalente a \(m\leq n\). Así, la hipótesis de inducción es el antecedente de la implicación de arriba. Por lo tanto, se satisface \(\varphi(n+1)\) y con esto se satisface \(\psi(n+1)\).

Por inducción débil concluimos \(\forall n\;\psi(n)\), como queríamos.