Introducción
En esta entrada demostraremos que el conjunto de los números naturales es un conjunto bien ordenado.
Lema: Si $n, m$ son naturales tales que $n\subset m$, entonces $n\in m$.
Demostración:
Sean $n,m\in \mathbb{N}$ tales que $n\subset m$. Consideremos $m\setminus n\subseteq m$ no vacío. Luego, como $m\setminus n\not=\emptyset$ existe $k=\min(m\setminus n)$ con respecto a $\in_{m}$.
Afirmación: $k=n$
Demostración de la afirmación:
$\subseteq$) Sea $y\in k$, entonces $y\in m$ por ser $m$ un conjunto transitivo. Luego, $y\in n$, pues de lo contrario $y\in m\setminus n$ y así, $y$ sería un elemento en $m\setminus n$ por debajo de $k$, pero esto es imposible pues $k=\min(m\setminus n)$. Por tanto, $y\in n$ y, por ende, $k\subseteq n$.
$\supseteq$) Sea $y\in n$. Como $n\subset m$, entonces $y\in m$. Ahora, por ser $m$ un natural, entonces $m$ está ordenado totalmente por la pertenencia. Así, como $y,k\in m$, o bien $y\in k$ o bien $k\in y$ o bien $y=k$. No puede ocurrir que $k\in y$, pues de ser así se tendría que $k\in n$ ya que $y\in n$ y $n$ es transitivo por ser un número natural, de modo que tendríamos que $k\in m\cap n$ y, por tanto, $k\notin m\setminus n$, lo cual contradice la elección de $k$. Ahora, no puede ocurrir que $k=y$, pues nuevamente tendríamos que $k\in n$ y ya vimos que esto conduce a una contradicción. Luego entonces tiene que ocurrir que $y\in k$. Esto demuestra que $n\subseteq k$.
Por lo tanto, $n=k$ y, en consecuencia, $n\in m$.
$\square$
Lema: Si $n$ y $m$ son naturales, entonces $n\in m$ o $m\in n$ o $n=m$, es decir, $n,m$ son $\in$-comparables.
Demostración:
Sean $n,m\in\mathbb{N}$. Tenemos los siguientes casos:
Caso 1. Si $n=m$ no hay más que probar.
Caso 2. $n\not=m$.
Consideremos a la intersección $n\cap m$. Luego, $n\cap m\subseteq m$ y $n\cap m\subseteq n$. Si $n\cap m=m$, entonces $m\subseteq n$, pero $m\not=n$, por lo que $m\subset n$ y por el lema anterior tenemos que $m\in n$. Si $n\cap m=n$, entonces $n\subseteq m$, pero $n\not=m$, por lo que $n\subset m$ y, en consecuencia, $n\in m$. Ahora, si $m\not=n\cap m\not=n$, se sigue que $n\cap m\subset n$ y $n\cap m\subset m$ y dado que $n\cap m$ es un número natural de acuerdo a lo que probamos en la entrada anterior, se sigue que $n\cap m\in n$ y $n\cap m\in m$, por el lema anterior. De modo que $n\cap m\in n\cap m$ lo cual no puede ocurrir pues un número natural no se puede pertenecer a sí mismo. Así que no puede ocurrir que $m\not=n\cap m\not=n$.
Por tanto, si $n\not=m$, entonces $n\in m$ o $m\in n$.
En consecuencia, cualesquiera dos números naturales son $\in-$comparables.
$\square$
Buen orden
Teorema: $(\mathbb{N}, \leq)$ es un conjunto bien ordenado.
Demostración:
Veamos primero que $\leq$ en $\mathbb{N}$ es reflexiva, antisimétrica y transitiva. Luego, veremos que $\mathbb{N}$ es un conjunto bien ordenado con $\leq$.
Reflexividad:
Sea $n\in \mathbb{N}$. Dado que $n=n$ se cumple que $n\leq n$.
Antisimetría:
Sean $n,m\in \mathbb{N}$. Supongamos que $n\leq m$ y $m\leq n$.
Entonces, $n\in m$ o $n=m$ y $m\in n$ o $m=n$.
Dado que dos naturales $n$ y $m$ no pueden cumplir al mismo tiempo que $n\in m$ y $m\in n$, sólo tenemos los siguientes casos:
Caso 1: $n\in m$ y $m=n$. Este caso no puede ocurrir, pues de ser así tendríamos que $n\in n$, lo cual no es posible para $n$ por ser un número natural.
Caso 2: $n=m$ y $m\in n$. Este caso tampoco puede ocurrir, pues de ser así tendríamos que $m\in m$, lo cual no es posible para $m$ por ser un número natural.
Caso 3: $n=m$. En este caso no hay más que probar.
Los argumentos anteriores muestran que $\leq$ es una relación antisimétrica en $\mathbb{N}$.
Transitividad:
Sean $n,m,l\in \mathbb{N}$. Supongamos que $n\leq m$ y $m\leq l$. Veamos que $n\leq l$
Dado que $n\leq m$, entonces $n\in m$ o $n=m$ y como $m\leq l$, entonces $m\in l$ o $m=l$.
Caso 1: Si $n\in m$ y $m\in l$, entonces $m\subseteq l$ por ser $l$ un conjunto transitivo y así, $n\in l$.
Caso 2: Si $n\in m$ y $m=l$, entonces $n\in l$.
Caso 3: Si $n=m$ y $m\in l$, entonces $n\in l$.
Caso 4: Si $n=m$ y $m=l$, entonces $n=l$.
En cualquier caso ocurre que $n\in l$ o $n=l$, es decir, $n\leq l$.
Por tanto, $\leq$ es una relación transitiva. Estas propiedades nos permiten concluir que $\leq$ es un orden parcial en $\mathbb{N}$.
Para mostrar que $\mathbb{N}$ es un conjunto bien ordenado con $\leq$, sólo resta probar que cualquier subconjunto no vacío de $\mathbb{N}$ tiene elemento mínimo con respecto a $\leq$.
Buen orden:
Sea $B\not=\emptyset$ tal que $B\subseteq \mathbb{N}$ y veamos que $B$ tiene elemento mínimo. Dado que $B\not=\emptyset$, podemos fijar $x\in B$. Luego, $x\in \mathbb{N}$ y por tanto $s(x)\in \mathbb{N}$. Consideremos $s(x)\cap B$ conjunto no vacío pues $x\in s(x)$ y $x\in B$. Notemos además que $s(x)\cap B$ es subconjunto no vacío de $s(x)$, por lo que $s(x)\cap B$ tiene elemento mínimo con respecto a $\in$ en $s(x)$.
Sea $k=\min(s(x) \cap B)$. Luego, $k=\min(B)$ en $\leq$. En efecto, si $n\in B$, entonces $n\in s(x)\cap B$ o $n\notin s(x)$; si $n\in s(x)\cap B$, entonces $n=k$ o $k\in n$ pues $k=\min(s(x)\cap B)$ con respecto a $\in$. Supongamos ahora que $n\notin s(x)$. Por un lema visto en esta entrada, y dado que $n$ y $s(x)$ son naturales tales que $n\notin s(x)$ , entonces $s(x)\in n$ o $s(x)=n$. Si $n=s(x)$, entonces $k\in n$ pues $k\in s(x)$. Finalmente, si $s(x)\in n$, entonces $s(x)\subseteq n$ por ser $n$ conjunto transitivo y, en consecuencia, $k\in n$, ya que $k\in s(x)$. En cualquier caso tenemos que $k\leq n$, lo que demuestra que $k=\min(B)$ con respecto a la relación $\leq$ definida en $\mathbb{N}$.
Por lo tanto, $(\mathbb{N}, \leq)$ es un conjunto bien ordenado.
$\square$
Tarea moral
La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta sección:
- Demuestra que el $0$ es $\leq-$comparable con cualquier número natural $m$ utilizando inducción sobre $m$.
- Utilizando el ejercicio anterior, demuestra que cualesquiera naturales $n$ y $m$ son $\leq-$comparables, aplicando inducción sobre $n$.
- Demuestra que para todo natural $n\not=0$, existe un natural $k$ tal que $n=s(k)$.
- Demuestra que para cualquier $n\in \mathbb{N}\setminus \set{0,1}$, existe $k\in \mathbb{N}$ tal que $n=s(s(k))$.
Más adelante
En la siguiente entrada haremos una breve pausa en funciones compatibles, esto nos servirá más adelante para probar el teorema de recursión.
Enlaces
Entrada anterior: Teoría de los Conjuntos I: Principio de inducción
Siguiente entrada: Funciones compatibles
Contenido relacionado: Álgebra Superior II: El principio del buen orden