A veces, uno se pregunta por qué la inducción es una técnica de demostración válida. Desde luego, es una cuestión natural por más intuitiva que parezca esa validez. Incluso, podemos comparar el misterio de la inducción con otras técnicas usuales de demostración, como el principio del buen ordenamiento o la inducción fuerte. La cuestión es más precisa al enfocarla desde la perspectiva del por qué podemos aplicar la inducción en los números naturales, pero no profundizaré dicha explicación aquí; una de las razones es que la respuesta depende de cómo se define los números naturales. El lector puede inferir de esto que estoy diciendo que la inducción es independiente de los números naturales. ¿Es esto posible? ¿Acaso es la inducción algo más que probar que una afirmación se cumple para {0} y que también se cumple para {n+1} cuando {n} la cumple? ¿Cómo puede tener sentido esto fuera del ámbito de los números naturales?

   Bueno, lo de estar fuera del “ámbito” es un tanto exagerado; pero es posible adaptar la idea de inducción a ámbitos más generales que sólo los números naturales. Este es el punto de vista que veremos a continuación con mayor detalle: dado algún conjunto {X}, ¿qué necesitamos para habilitar la inducción en {X} y que sea una herramienta para demostrar que una afirmación se cumple para todos elementos de {X}?

— 1. Lo usual —

   Veamos como formulamos usualmente la inducción.

Teorema 1. Sea {A\subseteq\mathbf N} tal que {0\in A} y {n\in A\implies n+1\in A} para cualquier {n\in \mathbf N}. Entonces {A=\mathbf N}.

   Aparentemente esta formulación parece requerir algunas propiedades de los números naturales: el hecho que hay un elemento {0} y que podemos “añadir” una unidad {1} a cualquier elemento. Pero veamos una versión diferente de la inducción (frecuentemente llamada inducción fuerte). Es común decir que esta versión es equivalente a la inducción usual; aunque, veremos que este hecho es un tanto trivial en tanto ambos se aplican sobre los números naturales, o falso cuando empecemos a generalizarlos sobre los mismos conjuntos.

Teorema 2. Sea {A\subseteq\mathbf N} tal que {(m<n\implies m\in A)\implies n\in A} para cualquier {n\in\mathbf N}. Entonces {A=\mathbf N}.

   Notar que parece no haber caso base, pero esto es satisfecho trivialmente; se cumple para el {0} ya que si {n=0} entonces {m<n} es falso y, por lo tanto, la primera implicación es cierta, sin importar si {m\in A}, lo que quiere decir que la segunda implicación es únicamente cierta si {n\in A}. De esta manera, tenemos un versión de la inducción que usa únicamente el ordenamiento de los números naturales, lo que luce como algo más sencillo de generalizar. Así, tomemos un conjunto {X} cualquiera. ¿Qué clase de ordenamiento deberíamos aplicar en {X} para poder demostrar que una afirmación es cierta para todo {x\in X} mediante la inducción? La respuesta usual es el un buen ordenamiento; pero esto no es del todo preciso, principalmente porque un buen ordenamiento es un ordenamiento total, lo que a nos permite afirmar que es posible usar la inducción con sólo un orden parcial. Pero iniciaremos con una cuestión más específica: ¿qué clase de orden total en {X} nos permite aplicar la inducción?

— 2. Órdenes totales —

Analicemos un poco la siguiente definición:

Definición 3. Un orden total sobre un conjunto no vacío {X} es un buen orden si cualquier subconjunto no vacío de {X} tiene un elemento mínimo.

   Así, dado que {X} es un conjunto totalmente ordenado, podemos aplicar la inducción sobre {X} si, y sólo si, {X} está bien ordenado. Pero esto se refiere a la inducción fuerte. ¿Es posible aplicar la inducción si contamos sólo con un orden total? Casi. S contamos con un conjunto bien ordenado (con una pequeña condición adicional), podemos aplicar la inducción usual. Pero de hecho, es necesario afinar algunos detalles. Antes veamos por qué para aplicar la inducción usual es suficiente y necesario tener un buen ordenamiento. Primero veamos que es suficiente.

Teorema 4. Sea {X} un conjunto bien ordenado y {A\subseteq X} tal que {(y<x\implies y\in A)\implies x\in A} cualquiera que sea {x\in X}. Entonces {A=X}.

Demostración. Sea {B:=X\setminus A} y supongamos en pos de la contradicción que {B} es no vacío. Ya que {X} está bien ordenado, se tiene que {X} tiene un elemento mínimo, digamos {b:=\min B}. Pero, si {x\in X} con {x<b}, entonces {x\notin B} ya que {b} es el mínimo elemento en {B}. Por lo tanto, por hipótesis, para todo {x\in X} con {x<b} tenemos {x\in A}, lo que quiere decir que {b\in A}, una contradicción a la elección de {b}. \Box

   Veamos que es necesario.

Teorema 5. Sea {X} un conjunto no vacío totalmente ordenado tal que {A=X} siempre que {A\subseteq X} satisface {(y<x\implies y\in A)\implies x\in A} para cualquier {x\in A}. Entonces {X} está bien ordenado.

Teorema 6. Sea {B\subseteq X} un subconjunto de {B} que no tiene elemento mínimo. Sea {A:=X\setminus B}. Necesitamos mostrar que {A=X} y así, por hipótesis, basta con probar que si {x\in X} e {y\in A} para cualquier {y<x}, entonces {x\in A}. Pero si {y\in A} para todo {y<x}, entonces {x} no puede encontrarse en {B}, ya que sería el mínimo elemento de {B} (porque todos elementos estrictamente menores no están en {B}), así tenemos {x\in A}, como se deseaba.

   Ahora, la cuestión que queda es cómo podemos darle sentido a la inducción usual; para lo cual, necesitamos contar con un elemento {0} y ser capaces de añadir {1} a cualquier elemento. Hay una manera natural de dar ese sentido a un conjunto bien ordenado {X} si asumimos una condición extra: {X} no tiene elemento máximo. De esta manera, podemos tomar por {0} al elemento mínimo del conjunto (que existe por hipótesis), y, para añadir {1}, es decir, tomar el siguiente elemento, basta considerar que para cualquier {x\in X} sabemos que el conjunto {\{y\in X:y>x\}} es no vacío (para esto necesitamos que {X} no tenga elemento máximo); así, su mínimo elemento es el siguiente elemento de {x} (llamado sucesor de {x}). Contando con estas definiciones, ¿podemos aplicar la inducción sobre {X}? ¡No! El siguiente ejemplo ilustra aquello que necesitamos cambiar para lograr hacer funcionar la inducción:

Ejemplo 1. Sea {X:=\{0,1\}\times\mathbf N} y el orden lexicográfico sobre {X} (i.e., {(m,n)\le(m',n')} si {m<m'} o {m=m'} y {n\le n'}). Entonces es sencillo verificar que {(0,0)} es el elemento mínimo de {X} (denotamos {0:=(0,0)}); también, es fácil verificar que “{+1}” se puede definir mediante {(m,n)+1=(m,n+1)}. Ahora, sea {A:=\{(0,n):n\in\mathbf N\}\subseteq X}. Entonces podemos mostrar que {0\in A} y {a\in A\implies a+1\in A} pero {A\ne X}. Pero {X} está de hecho bien ordenado (¿por qué?), de manera que es un conjunto bien ordenado sin un elemento máximo donde no podemos aplicar el primer tipo de inducción.

¿Qué va mal en el ejemplo anterior? Al parecer la inducción sólo funciona para los números naturales, pero es muy similar a la inducción fuerte que aplicamos a cualquier conjunto bien ordenado, excepto en un punto: necesitamos que si {n\ne0}, entonces {n-1} tenga sentido (consideremos que complemento de un conjunto, tomando el elemento mínimo del elemento {n} es fácil ve que este no puede ser {0} y así podríamos usar la hipótesis inductiva en {n-1}). Pero, ¿cómo no sería posible definir “restar {1}” en cualquier conjunto bien ordenado? Esto es imposible, por eso es precisamente el quid de la cuestión del ejemplo: el elemento {(1,0)} no tiene un predecesor inmediato ya que los elementos menores que {(1,0)} son aquellos que están en el conjunto {A}, y un predecesor inmediato no puede ser un elemento máximo en {A}, que ciertamente no existe. Esto sugiere cómo podríamos remediar la situación: reemplazar “{0\in A}” por “{x\in A} para cualquier {x\in X} que no tiene un predecesor inmediato”. Así, con esta versión, podemos aplicar la inducción. (¿Por qué? Basta con adaptar las demostraciones anteriores.)

— 3. Órdenes parciales —

Veamos el caso más general: sea {X} un conjunto parcialmente ordenado. ¿Qué necesitamos para aplicar la inducción fuerte en {X}? (En este caso, no podemos hablar de un inducción simple, ya que no tiene sentido en este nivel de generalidad.) La respuesta es que {X} debe ser bien fundado. (De hecho, no es necesario tener algún ordenamiento, basta tener una relación bien fundada.) De esta manera, definimos

Definición 7. Una conjunto no vació parcialmente ordenado {X} está bien fundado si cualquier subconjunto no vacío de {X} tiene un elemento minimal.

   Como hicimos con los órdenes totales, ahora necesitamos probar que esta condición es suficiente y necesaria para aplicar la inducción. Primero, veamos que es suficiente.

Teorema 8. Sea {X} un conjunto bien fundado y {A\subseteq X} tal que {(y<x\implies y\in A)\implies x\in A} cualquiera que sea {x\in X}. Entonces {A=X}.

Demostración. Sea {B:=X\setminus A}. Supongamos en pos de la contradicción que {B} es no vacío y sea {b\in B} un elemento minimal. Es claro que si {x\in X} con {x<b}, entonces {x\in A} ya que de otro modo {b} no sería minimal. Pero entonces {b\in A}, lo que contradice la elección de {b}. \Box

   Ahora, veamos que es necesario.

Teorema 9. Sea {X} un conjunto no vacío parcialmente ordenado tal que {A=X} siempre que {A\subseteq X} satisface {(y<x\implies y\in A)\implies x\in A} para cualquier {x\in A}. Entonces {X} está bien fundado.

Demostración. Sea {B\subseteq X} y asumamos que {B} no tiene elemento minimal. Sea {A:=X\setminus B}. Tenemos que si {x\in X} e {y\in A} para todo {y<x}, entonces también {x\in A}, caso contrario, {x} sería un elemento minimal de {B}. Pero, por hipótesis, {A=X}, de modo que {B} es vacío. \Box

   Ahora sabemos cuándo podemos aplicar la inducción. ¿Pero siempre es útil? ¡Seguro! Para un ejemplo de un conjunto bien fundado sin orden total, podemos tomar {\mathbf Z} con el orden {m\ne n} si {m=n} o {|m|<|n|} (el ordenamiento “más cercano a cero”). A veces, uno puede querer contar con un orden total. (Añadiré un ejemplo elaborado pronto.) También es útil para probar que cierto conjuntos son bien fundados; por ejemplo

Proposición 10. Sea {X} un conjunto no vacío parcialmente ordenado tal que {\{y\in X:y\le x\}} es finito para todo {x\in X}. Entonces {X} es bien fundado.

Demostración. Sea {A\subseteq X} un subconjunto no vacío de {X} y sea {x\in A}. Tenemos que el conjunto {\{x\in X:x\le a\}\cap A} es finito y no vacío; así, tiene un elemento minimal, que, a su vez, es elemento minimal en {A}. \Box

Anuncios