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

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.