Introducción
En la entrada pasada definimos una relación de orden en el conjunto de números naturales, más aun, probamos algunas propiedades de esta nueva relación, de las cuales, la más importante fue que este orden era un orden total. Ya en los ejercicios morales, vimos que podíamos restringir esta relación a cualquier número natural $n$ para definir un orden en los conjuntos con $n$ elementos.
En esta entrada definiremos una de las propiedades más importantes del orden en los naturales: el principio de buena ordenación, veremos que en cierto sentido es equivalente al principio de inducción, y daremos una breve presentación a algunos otros conjuntos que en este sentido se comportan de forma similar a los naturales.
La propiedad de buena ordenación
Pensemos en un número natural $n\neq 0$ con el orden que este hereda de $\mathbb{N}$, abusando de la notación, podemos escribir de forma ordenada a $n$ como $\{0<1<…<n-1\}$, parece ser que no habrá muchas sorpresas a la hora de estudiar a los números como conjuntos ordenados. Sin embargo, vale la pena notar que debido a lo que probamos en la sección de El tamaño de los naturales, cualquier subconjunto $A$ de $n$ será finito. Gracias a esto, y a que demostramos que el orden es total, podemos comparar todos los elementos de $A$ y fijarnos en el menor de todos ellos. Antes de formalizar esta prueba, recordaremos qué significa que un elemento de un conjunto sea mínimo.
Definición. Si $A$ es un conjunto ordenado por $\leq$, decimos que $a_0\in A$ es un elemento mínimo, si para todo $a\in A$ se tiene que $a_0\leq a$.
Ahora sí, enunciamos y demostramos nuestro primer teorema.
Teorema. Si $n\neq 0$ y $A\subseteq n$ es distinto del vacío, entonces existe $a_0$ mínimo en $A$.
Demostración. El hecho de que $A$ sea un conjunto finito no necesita más demostración que la que se mencionó en el párrafo anterior. Entonces podemos proceder por inducción sobre $m=\vert A\vert$.
Como $A\neq \emptyset$ la base de inducción se probará para $m=1$. Es decir que $A=\{a\}$, evidentemente, el elemento $a$ es el mínimo de $A$.
Supongamos ahora que si un conjunto no vacío tiene $m$ elementos, entonces tiene un elemento mínimo y supongamos que $A$ es un conjunto con $\sigma(m)$ elementos. Como $A$ es no vacío, entonces podemos elegir algún $a\in A$ arbitrario, entonces el conjunto $A\setminus\{a\}$ es un conjunto con $m$ elementos, y por la hipótesis de inducción, tiene un mínimo, llamémoslo $a’$. Como el orden en $A$ es el de los naturales, y este es total, $a’$ y $a$ son comparables, llamemos $a_0$ al mínimo entre estos dos elementos y demostremos que $a_0$ es el mínimo de $A$.
Sea $x\in A$ arbitrario, si $x=a$, ya terminamos, pues por definición $a_0\leq a$, en caso contrario $x \in A\setminus\{a\}$, pero como $a’$ es el mínimo de este conjunto, entonces $a’\leq x$, y como $a_0\leq a’$, por transitividad concluimos que $a_0\leq x$, por lo que $A$ sí tiene mínimo.
$\square$
Como mencionamos antes, la propiedad de que todos los subconjuntos de un conjunto arbitrario tengan mínimo elemento es importante, por lo que damos la siguiente definición.
Definición. Si $B$ es un conjunto ordenado por $\leq$, decimos que $B$ tiene la propiedad del buen orden si todo subconjunto no vacío de $B$ tiene un mínimo.
Entonces el teorema anterior puede ser reformulado como
Teorema. Si $n$ es un número natural, entonces $n$ está bien ordenado.
El conjunto de los números naturales está bien ordenado.
Un error lógico, sería asumir que por el teorema anterior, el conjunto de los números naturales también cumple la propiedad del buen orden, ya que a diferencia de cualquier número natural, en $\mathbb{N}$ existen conjuntos con una infinidad de elementos; sin embargo, aunque esta prueba no funcione, no se sigue que $\mathbb{N}$ no esté bien ordenado, es por esto que enunciamos el siguiente teorema.
Teorema. $\mathbb{N}$ satisface la propiedad del buen orden.
Demostración. Sea $A$ un subconjunto no vacío de números naturales, procedamos por contradicción, es decir, supongamos que $A$ no tiene elemento mínimo. Consideremos $B=\{n\in\mathbb{N}\mid m\leq n \Rightarrow m\notin A\}$, veamos que B es inductivo.
Evidentemente $0$ está en $B$, porque si no, existiría $m\leq 0$ tal que $m\in A$, como el único natural menor o igual a $0$ es $0$, tenemos que $0\in A$, pero entonces, $0$ sería un mínimo de $A$, ya que es menor o igual a todo natural.
Supongamos entonces que $n\in B$ y demostremos que $\sigma(n)\in B$, supongamos que no, entonces existirá $m\leq\sigma(n)$, tal que $m\in A$, como $m\in A$, por la definición de $B$, debe ocurrir que $n<m$ y por uno de los resultados de la entrada pasada, tenemos que $\sigma(n) \leq m$, por la antisimetría del orden, tenemos que $m=\sigma(n)$.
De nuevo usemos reducción al absurdo para probar que $\sigma(m)$ es un mínimo de $A$, si no lo fuera, existiría $a \in A$ tal que es falso que $\sigma(n)\leq a$, esto implicaría que es falso que $n<a$, es decir que $a\leq n$ y como $n\in B$, esto implicaría que $a\notin A $ lo cual es absurdo, entonces $\sigma(n)$ sí es un mínimo de $A$, pero de nuevo, esto es contradictorio con la suposición de que $A$ no tenía elemento mínimo, esta contradicción se deriva de suponer que $\sigma(n)\notin B$, entonces $\sigma(n)\in B$, por lo que el paso inductivo queda probado y $B=\mathbb{N}$.
Como $B=\mathbb{N}$, debe ocurrir que $A= \emptyset$ ya que si $a\in A$, como $a\leq \sigma(a)$, por la definición de $B$ debería pasar que $\sigma(a)\notin B$, contradiciendo que $B=\mathbb{N}$, pero desde un inicio, supusimos que $A\neq \emptyset$, esto quiere decir que suponer que $A$ no tiene mínimo es absurdo. Entonces, concluimos que $A$ sí debe de tener un elemento mínimo.
$\square$
El principio de inducción y el principio del buen orden
La idea de una prueba más corta de este resultado se da en los ejercicios morales; sin embargo, damos esta prueba para ver como el principio de inducción prueba el del buen orden. De forma análoga podemos demostrar el principio de inducción a partir del principio del buen orden.
Teorema. Supongamos cierto que $\mathbb{N}$ satisface la propiedad del buen orden, entonces, el principio de inducción también es cierto.
Demostración. Sea $A$ un conjunto inductivo, debemos de demostrar que $A=\mathbb{N}$, supongamos que no lo es, entonces $\mathbb{N}\setminus A\neq\emptyset$, por lo que, por el principio del buen orden, este conjunto tiene un elemento mínimo, sea $n$ el mínimo. Como $A$ es inductivo, $0\in A$. por lo que $n\neq 0$, entonces existe un $m$ tal que $\sigma(m)=n$, como $n$ es el mínimo, de $\mathbb{N}\setminus A$, tenemos que $m\notin \mathbb{N}\setminus A$, por lo que $m\in A$, pero como $A$ es inductivo, $\sigma(m)=n\in A$, lo cual es una contradicción, entonces, $A=\mathbb{N}$.
$\square$
En $\mathbb{N}$, existe otra formulación equivalente al principio de inducción, llamado principio de inducción fuerte, y dice que
Teorema. Si $A$ es un conjunto tal que:
- $0\in A$.
- Es cierto que si $n\in A$ y para todo $m\leq n$, se tiene que también $m\in A$ entonces $\sigma(n)\in A$.
Entonces $A=\mathbb{N}$.
Los detalles de la prueba se mencionan en uno de los ejercicios morales.
Conjuntos bien ordenados
Antes de estudiar otros conjuntos bien ordenados damos la siguiente proposición elemental.
Teorema. Si $A$ es un conjunto bien ordenado por $\leq$, entonces $A$ es un orden lineal.
Demostración. Sean $a,b\in A$, consideremos el conjunto $\{a,b\}\subset A$, como $A$ es un buen orden, entonces, este subconjunto tiene un elemento mínimo, es decir que $a\leq b$ ó $b\leq a$, esto quiere decir que los elementos son comparables.
$\square$
Hemos demostrado que todo número natural y el conjunto de los naturales, tienen un buen orden natural, una pregunta natural es si estos son los únicos conjuntos bien ordenados, la respuesta es que no; sin embargo hay varias cosas que analizar.
Lo primero que mencionaremos, es que todo conjunto finito $A$ y linealmente ordenado, satisface la propiedad del buen orden y más aun, se puede probar que si $\vert A\vert=n$, entonces el orden de $A$ y de $n$ son indistinguibles, detallamos esta afirmación en uno de los problemas de la tarea moral.
El caso infinito es más complicado, ya que existen muchos conjuntos numerables que pueden ordenarse de forma distinta a $\mathbb{N}$ y aun así tener la propiedad del buen orden, en realidad, es muy sencillo construirlos, como mencionamos en el siguiente teorema.
Teorema. Si $A$ es un conjunto bien ordenado bajo $\leq$, entonces $\sigma(A)$ es un conjunto bien ordenado con el orden $\leq’=\leq\cup\bigcup_{a\in \sigma(A)}(a,A)$.
Demostración. El hecho de que $\leq’$ es un orden, será un ejercicio moral, veamos que $\leq’$ está bien ordenado. Sea $B\subseteq \sigma(A)$ distinto del vacío, entonces debemos encontrar un elemento mínimo para $B$. Si $B=\{A\}$ el resultado es trivial.
Entonces supongamos que $B\neq\{A\}$ y consideremos $B\setminus \{A\}\subseteq A$, el cual es distinto del vacío. Como $A$ es un buen orden, entonces, existe $b$ elemento mínimo para este conjunto, afirmamos que $b$ también es un elemento mínimo para $B$. Para ver esto, sea $b’\in B$, si $b’\in B\setminus \{A\}\subseteq A$ el resultado se sigue de la definición de $b$, mientras que si $b’=A$, tenemos que $b’\leq A$ ya que por definición $(b’,A)\in \leq’$. Con esto finaliza la prueba.
$\square$
Aplicando el teorema anterior a $\mathbb{N}$, tenemos que $\mathbb{N}\cup\{\mathbb{N}\}$ es un buen orden con $\leq$ definido como $a\leq b$ si y solo si $a\in b$ o $a=b$, sin embargo, a diferencia de $\mathbb{N}$, este conjunto tiene un máximo, dígase $\mathbb{N}$ (ahora visto como elemento).
Otra cosa curiosa que podemos notar del conjunto $\sigma(\mathbb{N})$ es que aunque el principio del buen orden es válido, el principio de inducción no lo es, a diferencia de como pasaba en $\mathbb{N}$, en realidad, esta no es la única propiedad que perdemos, por ejemplo, en $\sigma(\mathbb{N})$, el cero no es el único elemento sin un antecesor, en realidad, esta es una de las razones por las que la prueba del principio de inducción a partir del principio del buen orden no es válida para este conjunto.
El estudio de los buenos ordenes es importante en Teoría de conjuntos y está muy relacionada con la teoría de conjuntos transitivos.
Más adelante…
Ya que hemos estudiado la propiedad más importante del orden en los naturales. solo falta ver como es que esta propiedad se relaciona con las operaciones que definimos, los resultados vistos en esta sección y en la siguiente, serán muy importantes en los siguientes temas que desarrollemos, ya que serán la base de muchos resultados, sobre todo al ver los resultados de la teoría de números en $\mathbb{Z}$, donde el orden, la inducción y el buen orden tendrán papeles fundamentales.
Tarea moral
A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.
- Si $A$ es un conjunto con $n$ elementos, y $\leq_A$ es un orden total en $A$, demuestra que existe una función $f:n \longrightarrow A$ tal que $n\leq m \Leftrightarrow f(n)\leq_A f(m)$. Sugerencia: Usa inducción sobre $n$ y después el principio del buen orden.
- Prueba el principio del buen orden a partir del axioma de regularidad y de la definición de $<$. Sugerencia: recuerda que el axioma de regularidad prohíbe la existencia de sucesiones infinitas de conjuntos tales que $…\in a_2\in a_1\in a_0$.
- Demuestra que en $\mathbb{N}$, el principio de inducción fuerte es equivalente al principio de inducción. Sugerencia: Prueba el principio de inducción fuerte a partir del débil, y el principio del buen orden a partir del fuerte.
- Usando la notación del último teorema, demuestra que $\leq’$ sí define una relación de orden en $\sigma(A)$.
- Si $A$ es un conjunto bien ordenado e infinito con $a_0$ elemento mínimo, prueba que existe una función $f:\mathbb{N}\longrightarrow A$ tal que $f(0)= a_0$ y si $n\leq m$ entonces $f(n)\leq f(m)$. Sugerencia: Usa la técnica que se ocupó a la hora de demostrar que los naturales son el conjunto infinito más pequeño.
Entradas relacionadas
- Ir a Álgebra Superior II
- Entrada anterior del curso: La relación de orden en los naturales
- Siguiente entrada del curso: Compatibilidad del orden con las operaciones de los naturales
Agradecimientos
Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»