El Omegón y todo eso... (Parte 10)

(A la parte 9 – A la parte 11)

Principio de inducción

Pensemos en estas afirmaciones:

“Todo entero mayor que 1 es, o bien un primo, o bien es producto de una cantidad finita de primos.”

“$\alpha $ es el ordinal correspondiente a S($\alpha $)” (recuérdese que S(x) es el conjunto de todos los elementos menores que x).

Ambas son afirmaciones que se refieren a los elementos de familias bien ordenadas, en el primer caso la familia de los enteros positivos, en el segundo caso, la familia de los ordinales. La pregunta es: ¿cómo podríamos demostrarlas?

Existe una técnica de demostración, el llamado Principio de Inducción, que permite demostrar afirmaciones referidas a conjuntos bien ordenados. El principio dice lo siguiente:

Si P(x) es una afirmación referida a los elementos de una familia bien ordenada de la que se demuestra que

1) P(m) es verdadera, donde m es el primer elemento de la familia.
2) Si P(a) es verdadera para todo $a < b$ entonces P(b) es verdadera.

Entonces puede asegurarse que P(x) es verdadera para todo x del conjunto.

Demostremos que este principio en efecto funciona. Supongamos que P(x) satisface las condiciones 1) y 2), pero que no sea verdadera para todo x. Entonces el conjunto de todos los x tales que P(x) es falsa es no vacío y en consecuencia tiene un primer elemento, llamémoslo b. Es decir P(b) es falsa y b es el mínimo elemento tal que eso sucede. Notemos que la condición 1) implica que b no puede ser m.

Si $a < b$ entonces la minimalidad de b implica que P(a) es verdadera, luego, por la condición 2) P(b) es verdadera, pero esto contradice lo dicho en el párrafo anterior. Por lo tanto no puede suceder que haya algún x tal que P(x) sea falsa, es decir P(x) es verdadera para todo x.

Usemos esta técnica para probar que “todo entero mayor que 1 es, o bien un primo, o bien es producto de una cantidad finita de primos”. En este caso P(x) es “si x es mayor que 1 entonces x es un primo o es producto de una cantidad finita de primos”.

P(1) es verdadera (pues el antecedente de la implicación es falso).

Sea ahora n un número natural mayor que 1 y supongamos que P(k) es verdadera para todo $k < n$; hay que probar entonces que P(n) es verdadera, es decir que n es primo o producto de primos.

Si n resulta ser primo, ya está, no hay nada que probar. Si no es primo entonces, por definición de primo, $n = k_1\cdot k_2$, donde $k_1$ y $k_2$ son números mayores que 1 y menores que n. Como $k_1$ y $k_2$ son menores que n entonces P($k_1$) y P($k_2$) son verdaderas y en consecuencia $k_1$ y $k_2$ son primos o producto de finitos primos. Se deduce inmediatamente que n es producto de finitos primos.

Cuando se usa en el contexto de los números enteros al Principio de Inducción se lo suele llamar Principio de Inducción Global, para distinguirlo del principio más popular (aunque no siempre tan útil) en el que la condición 2) se reemplaza por “P(k) implica P(k + 1)”.

Probemos ahora la segunda de las afirmaciones: “x es el ordinal correspondiente a S(x)”.

Notemos que P(0) es verdadera ya que S(0) es el vacío y 0 es su ordinal. Supongamos que P($\alpha $) es verdadera para todo $\alpha < \beta $, hay que probar que P($\beta $) es verdadera, es decir que $\beta $ es el ordinal de S($\beta $).

Sea A un conjunto bien ordenado cuyo ordinal es $\beta $, basta demostrar que A es equivalente a S($\beta $).

Recordemos que en la parte 8 hemos probado que si todo segmento S de S($\beta $) es equivalente a algún segmento T de A y, recíprocamente, todo segmento T de A es equivalente a un segmento S de S($\beta $), entonces A y S($\beta $) son equivalentes.

Sea entonces S un segmento de S($\beta $), luego S = S($\alpha $) para algún ordinal $\alpha $ menor que $\beta $. Por la suposición que estamos haciendo (que suele llamarse hipótesis inductiva) $\alpha $ es el ordinal de S($\alpha $) y entonces $S(\alpha ) < A$, por lo que S($\alpha $) es equivalente a algún segmento inicial de A.

Recíprocamente, sea T un segmento inicial de A. Como $T < A$ entonces el ordinal de T es algún $\alpha $ menor que $\beta $. Y como $\alpha $ (nuevamente por la hipótesis inductiva) es también el ordinal de S($\alpha $) , entonces S($\alpha $) es equivalente a T.

Hemos probado así, por el Principio de Inducción, que el ordinal de S($\beta $) es $\beta $. Así por ejemplo S(2) es {0, 1}, cuyo ordinal es 2, S($\omega + 1$) = {0, 1, 2, 3,..., $\omega $}, cuyo ordinal es $\omega + 1$.

Cuando se usa el Principio de Inducción para demostrar afirmaciones referidas a los ordinales se dice que la demostración se ha hecho por Inducción Transfinita.

(A la parte 9 – A la parte 11)