Teoría de los Conjuntos I: Buen orden en los naturales

Por Gabriela Hernández Aguilar

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:

  1. Demuestra que el $0$ es $\leq-$comparable con cualquier número natural $m$ utilizando inducción sobre $m$.
  2. Utilizando el ejercicio anterior, demuestra que cualesquiera naturales $n$ y $m$ son $\leq-$comparables, aplicando inducción sobre $n$.
  3. Demuestra que para todo natural $n\not=0$, existe un natural $k$ tal que $n=s(k)$.
  4. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.