Archivo de la etiqueta: números naturales

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

Teoría de los Conjuntos I: Construcción de los números naturales

Por Gabriela Hernández Aguilar

Introducción

Hasta ahora hemos usado a los números naturales como los conocemos desde la educación básica, sin embargo dado que estamos en un curso de teoría de conjuntos hablaremos de los números naturales desde la perspectiva de los conjuntos. En esta sección comenzaremos con la construcción rigurosa de los números naturales, sin dejar de lado la noción intuitiva que ya tenemos.

Construcción

Al principio del curso hablamos acerca de los primeros axiomas de la teoría de los conjuntos, vimos que existía un conjunto y que tal conjunto (vacío) no tiene elementos, además probamos su unicidad. Con base a los demás axiomas y al conjunto vacío construimos más conjuntos como $\set{\emptyset}$, $\set{\set{\emptyset}}, \set{\emptyset, \set{\emptyset}}$, $\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$, etcétera.

Si nos fijamos en la cantidad de elementos que tienen estos conjuntos notaremos que varía o que algunos tienen la misma cantidad pero son conjuntos distintos, como $\set{\emptyset}$ y $\set{\set{\emptyset}}$.

Dado que queremos construir a los números naturales lo que intentaremos hacer es asociarle a cada número un conjunto según la cantidad de elementos que tenga. Por el argumento anterior podemos deducir que existe más de una forma de hacer esto, por ejemplo:

\begin{align*}
0 &-\emptyset\\
1&-\set{\set{\emptyset}}\\
2&-\set{\emptyset, \set{\set{\emptyset}}}\\
3&-\set{\emptyset, \set{\set{\emptyset}}, \set{\emptyset, \set{\set{\emptyset}}}}\\
\vdots
\end{align*}

Otra forma posible es la siguiente:

\begin{align*}
0 &-\emptyset\\
1&-\set{\emptyset}\\
2&-\set{\emptyset, \set{\emptyset}}\\
3&-\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}\\
\vdots
\end{align*}

Sin embargo, según la definición que daremos más adelante, vamos a requerir que nuestra construcción tenga ciertas características, por lo que aunque exista más de una forma de asociarle un número a un conjunto según la cantidad de elementos que este tenga nos quedaremos con la segunda forma.

Para definir formalmente a los números naturales comenzaremos definiendo una de las características que a simple vista cumplirá un número natural, tal característica es la de ser un conjunto transitivo.

Conjuntos transitivos

Definición: Sea $x$ un conjunto. Decimos que $x$ es un conjunto transitivo si para cualquier $y\in x$ se cumple que $y\subseteq x$.

Ejemplo:

Dado que nos quedamos con la segunda forma que dimos para identificar a los números naturales, al vacío le asociamos el número natural 0, por lo que este conjunto tendría que ser transitivo. En efecto, si $x=\emptyset$, se cumple por vacuidad que para cualquier $y\in \emptyset$, $y\subseteq \emptyset$. Por lo tanto, $\emptyset$ es un conjunto transitivo.

$\square$

Ejemplo:

Sea $x=\set{\emptyset}$. Dado que su único elemento es $y=\emptyset$, para ver que $x$ es transitivo basta ver que $\emptyset\subseteq \set{\emptyset}$ lo cuál sabemos que es cierto. Por lo tanto, $\set{\emptyset}$ es un conjunto transitivo.

$\square$

Ejemplo:

Sea $x=\set{\emptyset, \set{\set{\emptyset}}}$. Tenemos que $x$ no es transitivo. En efecto, pues $\set{\set{\emptyset}}\in x$ pero $\set{\set{\emptyset}}\not\subseteq x$ dado que $\set{\emptyset}\in \set{\set{\emptyset}}$ pero $\set{\emptyset}\notin x$. Por lo tanto, $\set{\emptyset, \set{\set{\emptyset}}}$ no es un conjunto transitivo.

$\square$

A continuación veremos algunas equivalencias para conjunto transitivo.

Proposición: Sea $x$ un conjunto. Entonces, $x$ es un conjunto transitivo si y sólo si $x\subseteq \mathcal{P}(x)$.

Demostración:

Si $x=\emptyset$, entonces se cumple que $\emptyset\subseteq \mathcal{P}(x)=\set{\emptyset}$.

Supongamos ahora que $x\not=\emptyset$. Sea $y\in x$, como $x$ es un conjunto transitivo se tiene que $y\subseteq x$ y por lo tanto, $y\in \mathcal{P}(x)$. Así, $x\subseteq \mathcal{P}(x)$.

Ahora, supongamos que $x\subseteq \mathcal{P}(x)$ y veamos que $x$ es un conjunto transitivo. Sea $y\in x$, tenemos que $y\in \mathcal{P}(x)$ y así, $y\subseteq x$.

Por lo tanto, $x$ es un conjunto transitivo.

$\square$

Proposición: Sea $x$ un conjunto. Si $x$ es un conjunto transitivo, entonces $\bigcup x\subseteq x$.

Demostración:

Si $x=\emptyset$, entonces $\bigcup x= \emptyset\subseteq \emptyset=x$.

Si $x\not=\emptyset$.
Sea $y\in \bigcup x$, entonces existe $z\in x$ tal que $y\in z$. Luego, como $z\in x$ y $x$ es un conjunto transitivo entonces $z\subseteq x$ y así, $y\in x$. Por lo tanto, $\bigcup x\subseteq x$.

$\square$

Otros resultados para conjuntos transitivos

A continuación y para concluir esta entrada veremos algunos resultados para conjuntos transitivos, esta vez con respecto a la intersección y la unión.

Proposición: Si $x$ y $y$ son conjuntos transitivos, entonces $x\cap y$ es un conjunto transitivo.

Demostración:

Sean $x$ y $y$ conjuntos transitivos. Veamos que $x\cap y$ es un conjunto transitivo, es decir, para cada $z\in x\cap y$ se cumple que $z\subseteq x\cap y$.

  1. Como $x$ es un conjunto transitivo, entonces para cualquier $z\in x$ se cumple que $z\subseteq x$.
  2. Dado que $y$ es un conjunto transitivo, entonces para cualquier $z\in y$ se cumple que $z\subseteq y$.

De $1$ y $2$ podemos concluir que para cualquier $z\in x\cap y$ se satisface que $z\subseteq x\cap y$.

Por lo tanto, $x\cap y$ es un conjunto transitivo.

$\square$

Proposición: Si $x$ y $y$ son conjuntos transitivos, $x\cup y$ es un conjunto transitivo.

Demostración:

Sean $x$ y $y$ conjuntos transitivos. Veamos que $x\cup y$ es un conjunto transitivo, es decir, para cada $z\in x\cup y$ se cumple que $z\subseteq x\cup y$.

  1. Como $x$ es un conjunto transitivo, entonces para cualquier $z\in x$ se cumple que $z\subseteq x$.
  2. Dado que $y$ es un conjunto transitivo, entonces para cualquier $z\in y$ se cumple que $z\subseteq y$.

De $1$ y $2$ podemos concluir que para cualquier $z\in x\cup y$ se satisface que $z\subseteq x\cup y$.

$\square$

Tarea moral

  • ¿Cuál de los siguientes conjuntos es transitivo?
    1. $\set{\emptyset, \set{\emptyset}}$,
    2. $\set{\set{\emptyset}}$,
    3. $\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$.
  • Demuestra que $(\set{\emptyset, \set{\emptyset}}, \in)$ es un conjunto totalmente ordenado.
  • Demuestra que $x=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ tiene elemento máximo y elemento mínimo en el orden $\in_x$.
  • Sea $x$ un conjunto. Demuestra que si $\bigcup x\subseteq x$, entonces $x$ es un conjunto transitivo.

Más adelante

En la siguiente entrada daremos la definición formal y rigurosa de que es un número natural. Además demostraremos algunas de sus propiedades.

Enlaces

Para ver contenido acerca de números naturales puedes consultar el siguiente enlace: Álgebra Superior I: Introducción a números naturales.

Para recordar la definición de orden total puedes consultar el siguiente enlace: Teoría de los Conjuntos I: Orden total

Para recordar las definiciones de mínimo y máximo consulta el siguiente enlace: Teoría de los Conjuntos I: Mínimos, máximos, minimales y maximales