Siguiente: Enumeración de Cantor Un nivel arriba: Inducción matemática Anterior: Inducción numérica

Inducción recurrente

Este esquema se utiliza para demostrar predicados cuantificados universalmente definidos sobre conjuntos determinados constructivamente de manera recurrente. Sea T un conjunto numerable. Sea $A_0\subset T$ un conjunto inicial. Supongamos $A\subset T$ definido recurrentemente con las reglas siguientes:

$$\begin{array}{lcrcl} \mbox{\it Regla}_0 &:& \forall a: a\in ... ...rrow& \Phi_j(a_1,\ldots,a_{j_k})\in A \vspace{3ex} \end{array}$$

para $j=1,\ldots,m$, donde cada función $\Phi_j:T^{j_k}\rightarrow T$ es, en la práctica, una regla de composición. Para todo predicado $\Psi$ se tiene el esquema de demostración siguiente:

$$\begin{array}{lcl} \mbox{\it Esquema III} &:& \begin{array... ... \hline \forall a\in A &:& \Psi(a) \end{array} \end{array}$$

Como un ejemplo de construcción mediante este tipo de reglas, consideremos al siguiente: Ejemplo. Sea T el conjunto formado por las palabras (de longitud finita) sobre el alfabeto (0+1), i.e. T=(0+1)^*. Definimos el conjunto de palabras 0-preponderadas de manera recurrente como sigue:

$$\begin{array}{lcrcr} \mbox{\it Regla}_0 &:& &\ & \mbox{\it n... ...0\alpha_11\alpha_2\mbox{\rm es $0$-preponderada.} \end{array}$$

El conjunto $A\subset T$ de palabras 0-preponderadas se ajusta a la construcción anterior, donde $A_0=\{\mbox{\it nil}\}$ consta únicamente de la palabra vacía y hay dos reglas de composición $\Phi_1$, $\Phi_2$ dadas por sendas reglas. Más adelante veremos que una palabra es 0-preponderada si cualquier prefijo de ella posee más ceros que unos.

Proposición 2.1   El esquema III se prueba mediante el esquema II por inducción en el número de reglas para generar un elemento en A.

En efecto, con la notación utilizada en la formulación del Esquema III, sea

$$\phi(n)\equiv\mbox{\rm\begin{minipage}[t]{35em} [$\Psi(a)$ ... ...$ aplicaciones de las reglas que definen a $A$] \end{minipage}}$$

Como A se define únicamente por las reglas enlistadas, la fórmula $\forall a\in A:\Psi(a)$ es lógicamente equivalente a la fórmula $\forall n:\phi(n)$. Mostremos pues que esta última es válida a partir de las hipótesis

$$\forall a\in A_0 : \Psi(a) \hspace{1cm},\hspace{1cm} \foral... ... \Psi(a_i)\right)\Rightarrow \Psi(\Phi_j(a_1,\ldots,a_{j_k}))$$

La primera de estas ecuaciones equivale a $\phi(0)$. La segunda es claramente equivalente a $\forall n(\forall m<n( \phi(m))\Rightarrow \phi(n))$. Por el Esquema II tenemos que se cumple $\forall n:\phi(n)$, y con esto queda demostrado el Esquema III.


Ejemplo. Retomando nuestro ejemplo anterior, sea A el conjunto de palabras 0-preponderadas. Sea $\Psi(\alpha)$ la proposición

$$\Psi(\alpha)\equiv\mbox{\rm\begin{minipage}[t]{35em} [En cu... ...o de $1$'s a lo sumo coincide con el de $0$'s.] \end{minipage}}$$

Procedamos de acuerdo con el Esquema III para ver que $\forall\alpha\in A: \Psi(\alpha)$. Inicialmente tenemos, trivialmente, que para la palabra vacía se cumple $\Psi$, es decir, vale $\Psi(0)$. Ahora, de manera inductiva:

$$\begin{array}{lcl} \mbox{\it Regla}_1 &:& \mbox{\rm\begin{mi... ... vale $\Psi(0\alpha_11\alpha_2)$. \end{minipage}} \end{array}$$

Siguiente: Enumeración de Cantor Un nivel arriba: Inducción matemática Anterior: Inducción numérica