Principio del buen orden y Principio de Inducción

Principio del Buen Orden

Qué tal amigos, en esta ocasión me dispondré a enunciar el Principio del Buen Orden o también llamado Principio del buen ordenamiento de los números naturales. Nuestro principio dice así:

Sea $A$ un conjunto tal que $A\subseteq \mathbb{N}$ y además $A\neq \emptyset$, entonces $A$ tiene un elemento mínimo; esto es: $\exists a\in A$ tal que si $b\in A$, entonces $a\leq b$

 En efecto, con un poco de sencillo pensar, terminaremos aceptando este principio. Nuestra intuición nos dice que no puede ser posible que un subconjunto de los números naturales se extienda indefinidamente hacia $-\infty$ (Por así decirlo), ya que el elemento más pequeño que podría tener dicho conjunto sería $1$. Sería innecesario hacer una demostración formal de este hecho y por ello se le llama principio pero... ¿Es demostrable? Diremos entonces que en teoría sí es demostrable, les presentaré una "demostración" del principio del buen orden.

Sean $P$ y $Q$ las proposiciones lógicas definidas por:
$P:A\subseteq \mathbb{N}\wedge A\neq \emptyset$
$Q:(\exists a\in A)  (\forall b\in A)  [a\leq b]$
(La proposición Q simplemente dice que existe un mínimo, sería útil familiarizarse con esta notación)

Un detalle de todo este problema es que todos los números que manejamos son enteros, imaginemos que no existen los reales. Queremos entonces demostrar que $P\rightarrow Q$. En vez de realizar una prueba directa, realizaremos una prueba por Contrarecíproca, eso es, demostrar que se cumple $\sim Q \rightarrow  \sim P$  y por tablas de verdad, esto es equivalente a la primera implicación.

Tenemos que
$\sim Q:(\forall b\in A)  (\exists a\in A)  [b>a]$ 

Analicemos que nos dice $\sim Q$: para cada elemento $b$ de $A$, debe de existir otro elemento $a$ también en $A$ tal que $b>a$, esto es, que para cualquier elemento que escojamos en $A$, existirá otro estrictamente menor que el que escojimos. Ya que esto se cumple para cualquier $b \in A$, entonces escojamos un $b_{1}\in A$, luego existe un $b_{2}\in A$ tal que $b_{1}>b_{2}$, de la misma manera para $b_{2}$, existe un $b_{3}\in A$ tal que $b_{2}>b_{3}$. Si continuamos indefinidamente, tendremos que $b_{1}>b_{2}>b_{3}>\ldots >b_{i}$ para algún $b_{i}\in A$.

Como $i$ es una variable en este caso que denota cuántas veces hemos aplicado $\sim Q$, podremos hacer $i=b_{1}+1$, luego: $b_{1}>b_{2}>b_{3}>\ldots >b_{b_{1}}$. Esta desigualdad tiene $b_{1}+1$ términos y como todos son enteros (En esta entrada los reales no existen), la mínima distancia entre dos de ellos es $1$, entonces, descendiendo progresivamente desde $b_{1}$, llegamos a que aunque sea uno de ellos tiene que ser cero, de lo contrario, tendríamos $b_{1}+1$ términos distintos que acomodar entre $b_{1}$ números  positivos y si no se contase el cero, esto no podría suceder. Ya que existe un $b_{j}=0$ que además $b_{j}\in A$, luego $0\in A$, lo cual es condición suficiente para afirmar que $A\not\subseteq \mathbb{N}$.

Algo interesante es que para realizar el análisis anterior, hemos supuesto que $A\neq \emptyset$, ya que si $A=\emptyset$ no se podría concluir nada... ¡Este caso no provee mucha información! (Ley del medio excluido).

Finalmente, hemos demostrado que $\sim Q \rightarrow  \sim P$ y por tablas de verdad, esto asegura que $P\rightarrow Q$, luego, hemos "demostrado" el Principio del buen orden.

NOTAS
  • He puesto la palabra demostración entre comillas, ya que no es propiamente una demostración, el lenguaje sigue siendo aún muy informal. 
  • Si se dan cuenta, hay muchas cosas que al fin y al cabo hemos aceptado sin una demostración formal. Por ejemplo cuando concluimos que $0\in A$, hemos utilizado una especie de conteo intuitivo para realizar dicha conclusión (texto en negrita), más precisamente el principio del palomar. La teoría de Ramsey se encarga de estudiar esta clase de problemas.
  • Las pruebas por contradicción suelen parecerse a las pruebas por contrarecíproca. En este caso... Si hubiéramos querido probar esto por contradicción, hubieramos supuesto inicialmente que se pueden cumplir $P$ y $\sim Q$ al mismo tiempo, hubieramos llegado a una contradicción y por ende $P\wedge \sim Q$ sería falso con lo cual (Por leyes de De Morgan) $\sim P \vee Q$ sería verdadero, por tablas de verdad, esto es equivalente con $P\rightarrow Q$.
  • El Principio del Buen Orden en sí parece inútil por lo obvio que es (o por lo menos eso pensé yo la primera vez que me encontré con él). Un ejemplo de su utilidad (aunque no es el único) aparece en la demostración del importantísimo Principio de Inducción Matemática.


Principio de Inducción Matemática

Hemos presentado y "demostrado" el Principio del Buen Orden, hemos impartido una notación estricta para hacerlo y hemos complicado las cosas en gran medida para mostrar algo que en efecto no podría ser falso. Un Principio se define, según la RAE, como cada una de las primeras proposiciones o verdades fundamentales por donde se empiezan a estudiar las ciencias o las artes, lo cual nos dice en otras palabras que un principio es algo que "aceptamos" sin que exista una verdad que lo preceda, esto es... que no hay una forma de demostrarlo.

Pero... ¿Hemos demostrado el Principio del Buen Orden? En realidad no, hemos demostrado que es válido sólo si el conteo que hicimos para concluir que $0\in A$ es válido, y éste último lo hemos fundamentado en un axioma o principio cuando decimos "Esto no podría suceder". Si prosiguiéramos demostrando el porqué no podría suceder, llegaremos a Axiomas tan obvios que finalmente tendremos que aceptarlos.

Entonces, ¿Por qué no tomar el Principio del Buen Orden como un Axioma? La verdad es que me parece demasiado obvio y en un momento lo consideré axioma, pero después de conocer el Principio de Inducción Matemática, vi que lo obvio o elemental no implica la falta de una demostración.

El Principio de Inducción Matemática Generalizado establece lo siguiente:
Si $A$ es un conjunto tal que $A\subseteq \mathbb{N}$ que además $A\neq \emptyset$, y también tiene las siguientes propiedades:
(i) $k\in A$ y si $b<k$ entonces $b\not\in A$
(ii) Si $l\geq k$ y $l\in A$ entonces $l+1\in A$
Entonces  $A$ es el conjunto de todos los números naturales mayores o iguales a $k$
Traduzcamos esto en palabras: Dice que si $A$ es un subconjunto de los Números Naturales que cumple dos cosas:
  1. Tiene un mínimo elemento $k$ y
  2. Para cualquier elemento mayor o igual a $k$, si dicho elemento pertenece a $A$, entonces su sucesor también pertenecerá a $A$
Entonces el Principio de Inducción Generalizado nos dice que $A$ es el conjunto de todos los números naturales mayores que $k$ ¿Tiene sentido? Bien, analicemos las propiedades (i) y (ii). $k$ cumple ser mayor o igual que $k$, además $k\in A$ por la propiedad (i), luego, por la propiedad (ii) $k+1\in A$, si seguimos sucesivamente tiene sentido pensar que llenaremos a $A$ con todos los elementos precedentes a $k$ y que además los que están antes de $k$ no entrarán en $A$.

Más que tener sentido, en mi opinión esto se vuelve obvio ¡O que a alguien se le ocurra pensar que no es así!. Pero el "Principio" de Inducción Matemática se demuestra utilizando el Principio del Buen Orden, entonces... ¿Qué se demuestra y qué no? ¿Qué es Principio y qué no? Se le llama "Principio" de Inducción por ser bastante obvio, pero es demostrable; por eso tratamos de demostrar todo lo que pueda y dejarle poco a la intuición para salvarnos de estos interrogantes. Esto es, actuar como si fuéramos máquinas carentes de intuición (en el buen sentido), ayudándonos en esta pero comprobando (o más bien demostrando) con las matemáticas.

Aquí les va la demostración del Principio de Inducción Matemática Generalizado.

Vamos a probarlo por contradicción. Supongamos que $A\neq \{k, k+1,...\}$ (1) y que además cumple las hipótesis (i) y (ii). Luego, como sabemos por (i) que $\{1, 2,..., k-1\}\not\in A$, entonces por (1) existe mínimamente un elemento $a\in \{k, k+1,...\}$ tal que $a\not\in A$. Denotemos $I$ el conjunto formado por todos los números mayores que $k$ y que no están en $A$, esto es: $I=\mathbb{N} - A - \{1, 2,..., k-1\}$.

Sabemos que $I\neq \emptyset$ por (1), luego, por el principio del buen orden, tenemos que $I$ tiene un mínimo. Denotemos $b$ dicho mínimo, esto implica que $b-1\not\in I$. Por (i) tenemos que $k\in A$, luego $\{1, 2,..., k-1, k\} \not\in I$, así, se cumple que $b>k$ y por ende $b-1\geq k$, esto nos garantiza que $b-1\not\in \{1, 2,..., k-1\}$ y se deduce por definición de $I$ que $b-1\in A$ (lo deducimos con álgebra proposicional y definición de sustracción de conjuntos); pero por (ii) y por las características expuestas de $b-1$, se deduce que $(b-1)+1\in A$, o sea $b\in A$ ¡ABSURDO! Porque habíamos dicho que $b\in I$, y como $A$ e $I$ son disjuntos entre sí, $b$ no puede estar en ambos conjuntos a la vez. Esta contradicción surge de haber supuesto (1), luego (1) no se cumple y se tiene que cumplir $A= \{k, k+1,...\}$.

¡Lo hemos hecho! Hemos escrito varios párrafos para mostrar casi formalmente un hecho que era obvio, pero que debía ser demostrado. Al inicio de esta entrada, he querido hacer una "demostración" del principio del buen orden porque estaba motivado por el principio de inducción, el cual es también sumamente obvio e igual es demostrable. Tal vez la diferencia en que uno se conozca con demostración y el otro como axioma sea que el Principio de Inducción surge del Principio del Buen Orden y que este último no surge de algún principio conocido, pero bien podemos fundamentarlo en algún otro axioma (en nuestro caso lo hicimos con el conteo) que aunque no es necesariamente más claro, es más básico o elemental.

Un caso particular del Principio de Inducción surge cuando nuestro $k$ de la condición (i) es $1$. Ya que en la práctica es este el caso de más ocurrencia, el principio de inducción matemática generalizado cuando $k=1$ se denomina simplemente Principio de Inducción Matemática y quedaría así:
Si $A$ es un conjunto tal que $A\subseteq \mathbb{N}$ que además $A\neq \emptyset$, y también tiene las siguientes propiedades:
(i) $1\in A$
(ii) Si $l\in A$ entonces $l+1\in A$
Entonces  $A=\mathbb{N}$
Verifiquen que cuando $k=1$ tenemos que la segunda parte de (i) es siempre verdadera ya que todo número menor que $1$ no pertenecerá a $A$ por ser subconjunto de los naturales; además la primera parte de (ii) es también cierta siempre ya que todo elemento de $A$ será mayor o igual que $1$. Además, en la parte de la conclusión tendremos que el conjunto de todos los números naturales mayores o iguales a $1$ es precisamente el conjunto de los números naturales.