Archivo del Autor: Gabriela Hernández Aguilar

Teoría de los Conjuntos I: Principio de inducción

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada hablaremos acerca del principio de inducción. Será de gran importancia pues una vez que lo demostremos, se podrá utilizar como método de demostración para proposiciones cuyo enunciado depende de un número natural. En otras palabras, el principio de inducción nos ayudará a demostrar que ciertas proposiciones o propiedades se cumplen para cualquier natural $n$.

Principio de inducción1

El principio de inducción dice lo siguiente.

Teorema. Sea $P(n)$ una proposición (como las que se vieron en la primera unidad) que depende de un número natural $n$. Supongamos que las siguientes dos cosas son ciertas.

  1. $P(0)$ se cumple.
  2. Para cualquier $n\in \mathbb{N}$, si $P(n)$ es verdadero, entonces $P(s(n))$ también es verdadero.

Entonces, $\set{n\in \mathbb{N}:P(n)}=\mathbb{N}$, es decir, la proposición es cierta para cualquier número natural $n$.

Demostración.

Tomemos $P(n)$ una propiedad. Si se cumplen 1) y 2), entonces

$A=\set{n\in \mathbb{N}: P(n)}$

es un conjunto inductivo.

En la entrada anterior probamos que cualquier conjunto inductivo contiene a los naturales. Así, $\mathbb{N}\subseteq A$.

Además, $A\subseteq \mathbb{N}$ pues para cualquier $n\in A$, $n\in \mathbb{N}$ y por lo tanto, $A=\mathbb{N}$.

$\square$

Para entender este teorema, podemos imaginar una fila con tantas fichas de dominó como números naturales, como en la imagen. Hay una primera ficha. Para cualquier ficha hay una siguiente. ¿Qué necesitamos para garantizar que se caigan todas las fichas mediante el «efecto dominó»?

Por Leonardo Martínez con Stable Difussion

Podemos interpretar al teorema como sigue. Tomemos informalmente la proposición $P(n):$»el dominó $n$ cae». Lo que nos diría el punto 1) del principio de inducción es que la ficha correspondiente a cero. Lo que nos diría el punto 2) del principio de inducción es que tenemos la garantía de que para cualquier natural $n$ «si el dominó $n$ se cae, entonces el dominó $n+1$ también», por ejemplo, porque el dominó $n$ y $n+1$ están suficientemente cerca como para que el dominó $n$ empuje al $n+1$ al caer. Lo que garantizaría el principio de inducción es que todas las fichas caerán.

Orden de los naturales

A continuación definiremos una relación en el conjunto de números naturales, la cual resultará ser una relación de orden, pero esto último lo probaremos en la próxima entrada.

Definición. Sean $n,m\in \mathbb{N}$. Decimos que $n\leq m$ si y sólo si $n\in m$ o $n=m$.

Ejemplos.

  • $0=\emptyset$ y $1=\set{\emptyset}$ son números naturales. Luego, $0\leq 1$ pues $\emptyset\in \set{\emptyset}$.
  • $0=\emptyset$ y $2=\set{\emptyset, \set{\emptyset}}$ son números naturales. Luego, $0\leq 2$ pues $\emptyset\in \set{\emptyset, \set{\emptyset}}$.
  • $1=\set{\emptyset}$ y $2=\set{\emptyset, \set{\emptyset}}$ son números naturales. Luego, $1\leq 2$ pues $\set{\emptyset}\in \set{\emptyset, \set{\emptyset}}$.

$\square$

A continuación veremos un ejercicio en el que usaremos la relación que definimos arriba y el principio de inducción.

Proposición. $0\leq m$ para cualquier $m\in \mathbb{N}$.

Demostración.

Debemos probar que $\set{m\in \mathbb{N}: 0\leq m}=\mathbb{N}$. Procederemos usando el principio de inducción.

  • $0\leq 0$ pues $0=0$.
  • Ahora, si $0\leq m$ para algún $m\in \mathbb{N}$, veamos que $0\leq s(m)$. Dado que $0\leq m$, $0=m$ ó $0\in m$. Consecuentemente, $0\in s(m)$, es decir, $0\leq s(m)$.

Por lo tanto, $\set{m\in\mathbb{N}:0\leq m}=\mathbb{N}$.

$\square$

Tarea moral

  1. Demuestra que la relación $\leq$ que definimos en esta entrada es un orden parcial.
  2. Demuestra que cualesquiera naturales $n$ y $m$ son $\leq$-comparables, aplicando inducción sobre $n$. ¿Puedes dar una demostración alternativa que use un resultado de la entrada?
  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))$.
  5. Muestra que $\mathbb{N}$ no tiene máximo con el orden $\leq$ que hemos definido.

Más adelante…

En la siguiente entrada probaremos que el conjunto de los naturales con el orden que hemos definido en esta entrada es un buen orden.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

  1. Puedes consultar más contenido acerca del principio de inducción en el siguiente libro: Hrbacek, Karel y Jech, Thomas, Introduction to Set Theory, Marcel Dekker Inc. 1984, p. 42-44. ↩︎

Teoría de los Conjuntos I: Conjuntos inductivos y axioma del infinito

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada hablaremos acerca de los conjuntos inductivos, así como de un nuevo axioma que nos permitirá establecer la existencia de conjuntos que tengan esta propiedad. Un poco después conectaremos esto con la existencia de conjuntos infinitos. El axioma de infinito será clave para probar que la colección de todos los números naturales, como la hemos pensado, es en verdad un conjunto.

Conjuntos inductivos y el axioma del infinito

Comenzaremos definiendo a un conjunto inductivo.

Definición. Sea $A$ un conjunto. Diremos que $A$ es un conjunto inductivo si:

  1. $0\in A$,
  2. Si $x\in A$, entonces $s(x)\in A$.

En la entrada anterior probamos un teorema que nos asegura que si $n$ es un número natural, entonces $s(n)$ es un número natural. Sin embargo, no hemos demostrado que la colección de todos los números naturales sea un conjunto y, de hecho, los axiomas que hemos presentado hasta ahora no nos permiten hacerlo. Así, aún no podemos decir que «el conjunto de los números naturales es inductivo».

A continuación haremos mención de un nuevo axioma: el axioma del infinito. Este axioma nos garantiza la existencia de un conjunto inductivo.

Axioma (axioma del infinito). Existe un conjunto inductivo.

Aún no hemos presentado formalmente la noción de que un conjunto sea finito o infinito. Esto lo haremos hasta la cuarta parte del curso. Pero por el momento, puedes quedarte con la idea de que un conjunto inductivo será infinito, y por ello el axioma del infinito implica la existencia de un conjunto infinito.

Los naturales y conjuntos inductivos

Ahora que hemos definido a los conjuntos inductivos y aseguramos por el axioma de existencia que existe al menos uno, veremos que cualquier natural es elemento de cualquier conjunto inductivo.

Teorema. Sea $A$ un conjunto inductivo. Si $n$ es un natural, entonces $n\in A$.

Demostración.

En busca de una contradicción, supongamos que $n\notin A$. Como $n$ es un natural, se tiene que $s(n)$ es un natural. Luego, $n\in s(n)\setminus A$, de donde $s(n)\setminus A$ es un subconjunto no vacío de $s(n)$, por lo que tiene elemento mínimo respecto a $\in_{s(n)}$.

Sea $b=\min(s(n)\setminus A)$. Por definición de elemento mínimo se tiene que $b\in s(n)\setminus A$ y así $b\notin A$, por lo que $b\not=0$ pues al ser $A$ un conjunto inductivo sabemos que $0\in A$.

Luego, como $b$ es no vacío y $b\in s(n)\setminus A$, entonces $b$ tiene elemento máximo respecto a $\in_{s(n)}$. Sea $z=\max(b)$. Se cumple que $z\in b$ y como $b\in s(n)$, por la transitividad de $\in$ en $s(n)$, se tiene que $z\in s(n)$. Además $z\in A$ pues de lo contrario, $z\in s(n)\setminus A$, lo que contradice el hecho de que $b=\min(s(n)\setminus A)$.

Así, como $z\in A$, por ser $A$ conjunto inductivo se satisface que $s(z)\in A$.

Afirmación. $s(z)=b$.

Demostración de la afirmación.

Veamos primero que $s(z)\subseteq b$. Sea $y\in s(z)=z\cup \set{z}$, entonces $y\in z$ o $y=z$.

Caso 1: Si $y\in z$, como $z\in b$ concluimos que $y\in b$ por transitividad de $\in$ en $b$.

Caso 2: Si $y=z$, entonces $y\in b$.

Por lo tanto, $s(z)\subseteq b$.

Ahora veamos que $b\subseteq s(z)$.

Si $y\in b$, dado que $z\in b$ y los elementos de $b$ son $\in$-comparables, entonces $y\in z$ o $z\in y$ o $y=z$.

El caso $z\in y$ no puede ocurrir pues $z=\max(b)$. Así, $y\in z$ o $y=z$, esto es, $y\in z\cup\set{z}=s(z)$. Por lo tanto, $b\subseteq s(z)$.

Por lo tanto, $b=s(z)$ y así $b\in A$ pues $s(z)\in A$ lo cual no puede ocurrir pues $b\notin A$.

Dado que la contradicción vino de suponer que $n$ no está en $A$, concluimos que $n$ está en $A$.

$\square$

El conjunto de los naturales

Con el teorema anterior, el axioma del infinito y el esquema de comprensión, podemos demostrar que la colección de números naturales es un conjunto.

Corolario. La colección de todos los números naturales es un conjunto.

Demostración.

Sea $A$ un conjunto inductivo, que existe por el axioma del infinito. Por el teorema anterior sabemos que si $n$ es un natural, entonces $n\in A$. Así,

$N=\set{n\in A: n\ \text{es natural}}$

es un conjunto por el esquema de comprensión, cuyos elementos son exactamente los números naturales.

$\square$

A este conjunto le llamaremos el conjunto de los naturales y lo denotaremos por $\mathbb{N}$.

Tarea moral

Los siguientes ejercicios te permitirán reforzar el contenido que hemos visto hasta este momento acerca de números naturales.

  1. Demuestra que si $n\in \mathbb{N}$, entonces no existe $k\in \mathbb{N}$ tal que $n\in k$ y $k\in<s(n)$. Esto prueba que entres dos naturales no hay ningún otro natural.
  2. Demuestra que $\mathbb{N}$ es un conjunto transitivo.
  3. Prueba que $\mathbb{N}$ no tiene máximo con respecto a $\in_{\mathbb{N}}$. ¿Tiene mínimo? Demuéstra tu afirmación.

Más adelante…

En las siguientes entradas definiremos al principio de inducción y al principio del buen orden. Estos principios nos ayudarán a demostrar resultados que se cumplen en conjunto de los naturales.

Entradas relacionadas

Los siguientes enlaces te ayudarán a reforzar en contenido acerca de los naturales y tener un acercamiento con el principio de inducción.

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

Teoría de los Conjuntos I: Sucesor

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta nueva entrada hablaremos acerca del sucesor de un número natural. Este concepto nos permitirá definir un poco más adelante qué son los conjuntos inductivos, que simultáneamente nos dará un método de demostración muy versátil, y conectará nuestro estudio de los números naturales con el de los conjuntos infinitos.

Sucesor

La noción que estudiaremos ahora es la siguiente.

Definición. Sea $x$ un conjunto. Definimos al sucesor de $x$ como $s(x)=x\cup \set{x}$.

Ejemplos.

  • El sucesor de $\emptyset$ es $s(\emptyset)=\emptyset\cup \set{\emptyset}=\set{\emptyset}$.
  • El sucesor de $\set{\emptyset}$ es $s(\set{\emptyset})=\set{\emptyset}\cup \set{\set{\emptyset}}=\set{\emptyset, \set{\emptyset}}$.
  • Luego, el sucesor de $\set{\emptyset, \set{\emptyset}}$ es $s(\set{\emptyset, \set{\emptyset}})=\set{\emptyset,\set{\emptyset}}\cup \set{\set{\emptyset, \set{\emptyset}}}=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$.
  • El sucesor de $\set{\set{\emptyset}}$ es $s(\set{\set{\emptyset}})=\set{\set{\emptyset}}\cup \set{\set{\set{\emptyset}}}= \set{\set{\emptyset}, \set{\set{\emptyset}}}$.

$\square$

La noción de sucesor está definida para cualquier conjunto. Pero dado que en esta unidad únicamente estaremos trabajando con números naturales, prácticamente nos limitaremos a usar la definición de sucesor para conjuntos que son números naturales. En este caso sucede algo especial: si $n$ es un número natural, entonces $s(n)$ también lo es. Vamos a demostrar esto, pero antes demostraremos algunos lemas que nos serán de utilidad.

Unos lemas sobre la pertenencia

A continuación probaremos algunos resultados sobre la pertenencia de números naturales en sí mismos y de unos en otros. Cuando los leas, te darás cuenta de que ya habíamos demostrado resultados similares y más generales en la entrada del axioma de buena fundación. Sin embargo, nota que en las siguientes demostraciones no es necesario utilizar este axioma, pues la definición de número natural nos da todo lo que necesitamos.

Lema 1. Para cualquier número natural $n$, no es posible que $n\in n$.

Demostración.

Sea $n$ un número natural. Entonces $\in_n$ es un orden total estricto para $n$. Si sucediera que $n\in n$, entonces tendríamos una contradicción pues tendríamos $n\in_n n$ y $n\in_n n$, lo que contradice la asimetría de $\in_n$. Así, $n\not \in n$.

$\square$

Lema 2. Si $n$, $m$ son números naturales, entonces no es posible que $n\in m$ y $m\in n$ al mismo tiempo.

Demostración.

Sean $n$ y $m$ números naturales. Si $n\in m$ y $m\in n$, entonces $n\in n$ pues $n$ es conjunto transitivo. Esto contradice el lema anterior.

Por lo tanto, no es posible que $n\in m$ y $m\in n$ al mismo tiempo.

$\square$

Así, hemos logrado hacer estas demostraciones sin recurrir al axioma de buena fundación. Como comentario tangencial, en teoría de los conjuntos no sólo resulta de interés probar resultados que se deducen de los axiomas, sino que a veces también es interesante identificar realmente cuáles son los «axiomas suficientes» para tener algún resultado de la teoría. Nos encontraremos nuevamente con preguntas de este estilo cuando hablemos del axioma de elección.

El sucesor de un natural

Ahora que demostramos los lemas anteriores, estamos listos para probar que el sucesor de un número natural es un número natural.

Teorema. Si $n$ es un número natural, entonces $s(n)$ es un número natural.

Demostración.

Sea $n$ un número natural. Veamos que $s(n)$ es un número natural. Para ello tenemos que probar todo lo siguiente:

  • $s(n)$ es transitivo.
  • $\in_{s(n)}$ es un orden total estricto en $s(n)$.
  • Cualquier $B\subseteq s(n)$ no vacío tiene mínimo y máximo con respecto a $\in_{s(n)}$.

A continuación hacemos todo esto.

$s(n)$ es transitivo.

Sea $y\in s(n)=n\cup\set{n}$. Si $y\in n$, dado que $n$ es un número natural, entonces $n$ es transitivo y por lo tanto, $y\subseteq n$. Así, $y\subseteq n\cup\set{n}$. Si $y\in \set{n}$, entonces $y=n$ y en particular, $y\subseteq n$ y así, $y\subseteq n\cup\set{n}$. En cualquier caso, $y\subseteq s(n)$. Por lo tanto, $s(n)$ es un conjunto transitivo.

$\in_{s(n)}$ es un orden total estricto en $s(n)$.

Para esta parte debemos probar que $\in_{s(n)}$ es una relación asimétrica, transitiva y que cualquiera dos elementos de $s(n)$ son $\in_{s(n)}$ comparables.

Veamos que $\in_{s(n)}$ es asimétrica. Sean $y,z\in s(n)$. Como $y\in s(n)=n\cup \{n\}$, entonces o bien $y=n$, y entonces $y$ es natural, o bien $y\in n$, y entonces $y$ es natural por el teorema de la entrada anterior. De manera análoga, $z$ es natural. Por el Lema 2 de esta entrada, es imposible que $y \in_{s(n)} z$ y $z \in_{s(n)} y$ simultáneamente, por lo que $\in_{s(n)}$ es asimétrica.

Antes de ver que la relación es transitiva, veamos que cualesquiera dos elementos son comparables. Tomemos $y,z \in s(n)$ arbitrarios. Si ambos están en $n$, entonces como $\in_n$ es total, tenemos que o $y\in_n z$, o $y=z$, o $z\in_n y$. Respectivamente tendríamos que $y\in_{s(n)} z$, o $y=z$, o $z\in_{s(n)} y$. Si ambos están en $\{n\}$, entonces $y=n=z$ y así $y=z$. Si $y$ está en $n$ y $z$ está en $\{n\}$, entonces $z=n$ y por lo tanto $y\in z$, de donde $y\in_{s(n)} z$. Si $z$ está en $n$ y $y$ está en $\{n\}$, entonces $y=n$ y por lo tanto $z\in_{s(n)} y$, de donde $z\in_{s(n)} y$.

Para terminar de ver que $\in_{s(n)}$ es un orden total estricto, falta ver que es una relación transitiva. Para ello tomemos $w,y,z\in s(n)$ arbritarios tales que $w\in_{s(n)} y$ y $y\in_{s(n)} z$ y veamos que $w\in_{s(n)} z$. De acuerdo a en dónde están $w,y,z$ en $s(n)=n\cup \{n\}$, tenemos 8 casos. Pero podemos reducirlos a las siguientes tres posibilidades.

  • $w,y,z\in n$, en cuyo caso se da $w\in_n z$ por transitividad de $\in_n$, y así $w\in_{s(n)} z$.
  • Exactamente uno de $w,y,z$ es igual a $n$. No se puede $w=n$ pues llegamos a la contradicción $n=w\in y$ (por nuestra suposición) y $y\in n$ (pues exactamente hay uno igual a $n$). Análogamente, tampoco se puede $y=n$ pues llegamos a la contradicción $n\in z$ y $z\in n$. Así, sólo puede ser $z$, pero entonces $w\in n=z$, de donde $w\in_{s(n)} z$.
  • Al menos dos de $w,y,z$ es igual a $n$. Este caso es imposible pues lleva o bien a una contradicción del estilo $n\in n$ (cuando $w=n=y$ o $y=n=z$), o bien a la contradicción $n\in y \in n$.

Lo anterior cubre todos los casos para mostrar que la relación es transitiva. Hemos entonces mostrado que $\in_{s(n)}$ es un orden total y estricto para $s(n)$.

Cualquier $B\subseteq s(n)$ no vacío tiene mínimo y máximo con respecto a $\in_{s(n)}$.

Supongamos que $B$ conjunto no vacío es subconjunto de $s(n)$ y veamos que $B$ tiene máximo y mínimo.

Caso 1: Si $B\subseteq \set{n}$, como $B\not=\emptyset$ entonces $B=\set{n}$.

Luego, $n=\min (B)$ pues se satisface que para cualquier $y\in B\setminus \set{n}=\emptyset$, se tiene que $n\in y$ por vacuidad.

Finalmente, $n=\max (B)$ pues se satisface que para cualquier $y\in B\setminus \set{n}=\emptyset$, se tiene que $y\in n$ por vacuidad.

Caso 2: Si $B\subseteq n$, entonces $B$ es un subconjunto no vacío de $n$, así que tiene un mínimo $a$ y un máximo $b$ con respecto a $\in_n$, que son a la vez mínimo y máximo con respecto a $\in_{s(n)}$.

Caso 3: Si no pasa que $B\subseteq \set{n}$, ni $B\subseteq n$, entonces hay elementos de $B$ en $\set{n}$ y en $n$. Así, $n\in B$ y podemos definir $a$ como el mínimo de $B\cap n$. Afirmamos que $n=\max(B)$ y $a=\min(B)$.

En efecto, todo $y\in B\setminus\{n\}$ está en $n$ y por lo tanto $y\in_{s(n)} n$. Además, si tomamos $z\in B\setminus \{a\}$, entonces hay dos posibilidades. O bien $z=n$, que acabamos de ver que cumple $a\in_{s(n)} n$. O bien $z\in n$, pero entonces $z\in B\cap n$ y como $a$ es mínimo de $B\cap n$, tenemos entonces $a\in_n z$ y por lo tanto $a\in_{s(n)} z$.

Con esto terminamos de demostrar todo lo que necesitábamos para ver que $s(n)$ es un natural.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá aprender otras propiedades del sucesor de un número natural:

  1. Describe al sucesor del natural $\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}, \set{\emptyset, \set{\emptyset},\set{\emptyset, \set{\emptyset}}}}$.
  2. Sean $x$ y $y$ conjuntos cualesquiera. Demuestra que si $s(x)=s(y)$, entonces $x=y$.
  3. Prueba que para cualquier natural $n$ se cumple que $\bigcup s(n)=n$.
  4. Sea $x$ un conjunto. Demuestra que $x$ y $s(x)$ son conjuntos distintos. ¿Será siempre cierto que $x$ y $s(s(x))$ son conjuntos disintos? En caso de que sí, da una prueba. En caso de que no, da un contraejemplo.

Más adelante…

En la siguiente entrada definiremos a los conjuntos inductivos. Tales conjuntos nos darán la base para definir al conjunto de los números naturales. Además hablaremos de un nuevo axioma: el axioma del infinito.

Entradas relacionadas

En los siguientes enlaces podrás repasar el contenido acerca de números naturales.

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

Teoría de los Conjuntos I: Números naturales

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada daremos la definición formal de qué es un número natural. Además probaremos algunos resultados sobre números naturales.

Número natural

Definición. Sea $n$ un conjunto. Decimos que $n$ es un número natural si satisface las siguientes tres condiciones:

  1. $n$ es un conjunto transitivo.
  2. $\in_n$ es un orden total estricto en $n$.
  3. Cualquier subconjunto no vacío $z$ de $n$ tiene elemento mínimo y máximo en el orden $\in_n$.

Ejemplo.

Afirmamos que el conjunto $0=\emptyset$ es un número natural. Veamos por qué. En la entrada anterior vimos que $\emptyset$ es un conjunto transitivo.

Además, $(\emptyset, \in_\emptyset)$ es un conjunto totalmente ordenado pues $\in_\emptyset= \emptyset$, por lo que se satisface por vacuidad (en $\emptyset$) que es una relación asimétrica y transitiva. Asimismo, los elementos de $\in_\emptyset$ son comparables por vacuidad (en $\emptyset$) y por lo tanto, $\in_\emptyset$ es un orden total.

Finalmente, se satisface por vacuidad que para cualquier $z\not=\emptyset$ (pues no hay tal) que cumple que $z\subseteq \emptyset$, se tiene que $z$ tiene elemento mínimo y máximo en el orden $\in_\emptyset$.

Por lo tanto, $\emptyset$ es un número natural.

$\square$

Elementos de números naturales son números naturales

En esta sección veremos que si $n$ es número natural y $z\in n$, entonces $z$ es número natural. Lo primero que es conveniente hacer es entender la relación $\in_z$ en términos de la relación $\in_n$.

Lema 1. Si $n$ es un conjunto transtivo, entonces para cualquier $z\in n$ se cumple que $\in_n\cap (z\times z)=\in_z$..

Demostración. En efecto, tenemos que

\begin{align*}
\in_n\cap(z\times z)&=\set{(x,y)\in n\times n:x\in y}\cap(z\times z)\\
&=\set{(x,y)\in z\times z:x\in y}\\
&=\in_z.
\end{align*}

$\square$

El siguiente lema será de ayuda para mostrar que cualquier elemento de un número natural resulta ser también un número natural.

Lema 2. Si $n$ es un conjunto transitivo, entonces, para cualquier $z\in n$ se satisface que $\in_z$ es un orden total estricto en $z$.

Demostración.

Veamos que $\in_z$ es una relación asimétrica, transitiva y sus elementos son $\in_z$-comparables.

  1. Asimetría.
    Procedamos por contradicción. Supongamos que $x,y\in z$ tales que $x\in_z y$ y $y\in_z x$. Por el Lema 1, tendríamos que $x\in_n y$ y $y\in_n x$, lo cual no puede ocurrir pues $\in_n$ es una relación asimétrica. Así, no hay tales $x$ y $y$. Esto muestra que $\in_z$ también es una relación asimétrica.
  2. Transitividad.
    Sean $x, y, w\in z$ tales que $x\in_z y$ y $y\in_z w$. Por el Lema 1, tenemos que $x\in_n y$ y $y\in_n w$, lo que implica que $x\in_n w$ con $x, w\in z$. De nuevo por el Lema 1, se tiene que $x\in_zw$. Por lo tanto, $\in_z$ es transitiva en $z$.
  3. $\in_z$-comparables.
    Sean $x,y\in z$. Dado que $z\in n$, entonces $x\in n$ y $y\in n$. Como $\in_n$ es total, tenemos que $x\in_n y$ o $y\in_n x$ o $y=x$. Por el Lema 1, estas posibilidades implican, respectivamente, que $x\in_z y$ o $y\in_z x$ o $y=x$, es decir, los elementos de $z$ son $\in_z$ comparables.

Por lo tanto, $\in_z$ es un orden total en $z$.

$\square$

Estamos listos para ver que elementos de naturales son naturales.

Teorema. Si $z\in n$ con $n$ número natural, entonces $z$ también es un número natural.

Demostración.

Supongamos que $n$ es un número natural y que $z\in n$. Veamos que en $z$ se verifican las condiciones 1, 2 y 3 de la definición de número natural.

  1. $z$ es un conjunto transitivo.
    En efecto, sea $y\in z$. Como $n$ es transitivo y $z\in n$, tenemos que $y\in n$. Si tomamos $w\in y$, se sigue nuevamente que $w\in n$ por la transitividad de $n$. Como $\in_n$ es transitiva, y $w,y,z$ están en $n$, tenemos entonces que $w\in z$. Así, $y\subseteq z$. Concluimos que para cualquier $y\in z$ se tiene que $y\subseteq z$ y, por lo tanto, $z$ es un conjunto transitivo.
  2. $\in_z$ es un orden total en $z$.
    Por el Lema 2 se tiene que $\in_z$ es un orden total estricto en $z$.
  3. Subconjuntos no vacíos de $z$ tienen máximo y mínimo con respecto a $\in_z$.
    Sea $B\subseteq z$ con $B$ no vacío. Dado que $n$ es un número natural y $z\in n$, tenemos que $z\subseteq n$. Así, por transitividad de la contención se sigue que $B\subseteq n$, por lo que $B$ tiene elemento mínimo y máximo con respecto a $\in_n$. Llamemos a estos elementos $b_1$ y $b_2$, respectivamente. Recordemos que $b_1,b_2$ son elementos de $B$ y, por lo tanto, de $z$ y de $n$.
    Veamos que $b_1$ y $b_2$ son los elementos mínimo y máximo de $B$ con respecto a $\in_z$. Tomemos $b\in B\setminus \{b_1\}$. Como $b\in B$, tenemos que $b\in z$ y por lo tanto $b\in n$. Como $b_1$ es mínimo de $\in_n$, tenemos que $b_1\in_n b$. Por el Lema 1, tenemos entonces que $b_1\in_z b$. Así, $b_1$ es mínimo de $\in_z$. Una demostración análoga muestra que $b_2$ es máximo de $\in_z$. Por lo tanto, $B$ tiene elemento mínimo y máximo con respecto a $\in_z$.

Todo lo anterior nos permite concluir que $z$ es número natural.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada, además de seguir trabajando el concepto de conjuntos transitivos.

  1. Muestra que los conjuntos $1,2,3,4$ que hemos definido previamente en efecto son conjuntos transitivos.
  2. Este ejercicio consiste en probar una versión más general del Lema 2. Muestra que si $(x,\lt)$ es un conjunto estrictamente y totalmente ordenado, entonces para cualquier subconjunto $y$ de $x$ se tiene que $(y, \lt \cap (y\times y))$ también es un conjunto estrictamente y totalmente ordenado.
  3. Prueba que si $x\not=\emptyset$ es un conjunto transitivo, entonces $\bigcap x$ es un conjunto transitivo.
  4. Prueba que si $x$ es un conjunto transitivo, entonces $\bigcup x$ es un conjunto transitivo
  5. Demuestra que si $n$ es un número natural, entonces $n\notin n$. Haz esto de dos formas distintas: 1) Usando la definición de número natural para llegar a una contradicción y 2) Usando el axioma de de buena fundación.
  6. Demuestra que si $n$ y $m$ son números naturales, entonces no puede ocurrir que $n\in m$ y $m\in n$ al mismo tiempo. Haz esto de dos formas distintas: 1) Usando la definición de número natural para llegar a una contradicción y 2) Usando el axioma de buena fundación.

Más adelante…

En la siguiente entrada definiremos al sucesor de un número natural. A partir de este nuevo concepto, probaremos propiedades adicionales para los números naturales.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

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

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

Hasta ahora solo hemos usado los conjuntos $0$, $1$, $2$, $3$ y $4$ que definimos en la entrada de axioma del par y axioma de unión, pero es momento de hablar de números naturales de manera más general y rigurosa. En esta entrada comenzaremos a hacer esto, enunciando algunas propiedades conjuntistas que esperamos que tengan los números naturales. Sin embargo, no dejaremos 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. A partir de ellos obtuvimos un conjunto $\emptyset$ que no tiene elementos, y además probamos que era el único conjunto con esta propiedad. Por comodidad, a este conjunto también le pusimos el «nombre» o «etiqueta» $0$. Después, aplicamos el axioma del par para a partir de $0$ conseguir al conjunto $\{\emptyset\}$ al que llamamos $1$. En los ejercicios, hablamos de cómo a partir de los axiomas se pueden construir también a $2:=1\cup \{1\}= \set{\emptyset, \set{\emptyset}}$, a $3:=2\cup \{2\}=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$, y también a $4:=3\cup \{3\}$.

Por supuesto, también se pueden construir otros conjuntos que no «siguien este patrón», por ejemplo, aplicando dos veces el axioma del par se puede construir al conjunto $\set{\set{\emptyset}}$.

Si nos fijamos en la cantidad de elementos que tienen los conjuntos $0,1,2,3,4$, notamos que las etiquetas son muy precisas y coinciden con nuestra intuición, pues por ejemplo el $0$ es el vacío que tiene cero elementos, el $1$ es $\{\emptyset\}$ que tiene un sólo elemento que es $\emptyset$, etc. De hecho, parte del ejercicio de la entrada mencionada pedía ver que $4=\{0,1,2,3\}$, que en efecto tiene cuatro elementos. Pero puede haber otros conjuntos distintos que también tengan la misma cantidad que estos conjuntos. Por ejemplo, el conjunto $\set{\set{\emptyset}}$ también tiene un elemento (tiene sólo a $\set{\emptyset}$), pero no es el mismo conjunto que $1$.

Parte de lo que queremos lograr al construir los números naturales formalmente es asociar a cada «número que usamos para contar» un conjunto con esa cantidad de elementos. Lo mencionado arriba debe dejarnos la idea de que puede haber muchas maneras de hacer esto. Por ejemplo, una posible manera sería formalizar la siguiente construcción:

\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 posible manera sería formalizar la siguiente construcción, que se parece más a cómo hemos estado utilizando las etiquetas $0,1,2,3,4$:

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

Debido a que hay muchas maneras de lograr nuestro objetivo, podemos poner algunas condiciones adicionales. Hablaremos de ellas en el transcurso de estas entradas. Estas propiedades adicionales que requeriremos nos llevarán a que la construcción apropiada es la segunda presentada aquí arriba.

Conjuntos transitivos

Para definir formalmente a los números naturales comenzaremos definiendo una de las características que tendrá cada uno de los números naturales.

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$.

Observa que si $x$ es transitivo en la definición que acabamos de dar, entonces si $z\in y$ y $y\in x$, entonces $z\in x$.

Ejemplo.

Nos gustaría que cada número natural sea transitivo y nos gustaría que $0$, como lo definimos, sea número natural. En efecto lo es pues, en este caso, $0=\emptyset$ y entonces por vacuidad se cumple que si $y\in \emptyset$, se tiene que $y\subseteq \emptyset$.

$\square$

Ejemplo.

También el conjunto que definimos como $1$ es transitivo. Recordemos que $1=\set{\emptyset}$. El único elemento de $1$ es $y=\emptyset$, así que para ver que $x$ es transitivo basta ver que $\emptyset\subseteq \set{\emptyset}$, lo cuál sabemos que es cierto. Por lo tanto, $1$ es un conjunto transitivo.

$\square$

Ejemplo.

Sea $x=\set{\emptyset, \set{\set{\emptyset}}}$. Tenemos que $x$ no es transitivo. En efecto, se tiene que $\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$

Equivalencias de conjuntos transitivos

A continuación veremos algunas equivalencias para que conjunto sea 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.

Comencemos suponiendo que $x$ es transitivo. Veremos que $x\subseteq \mathcal{P}(x)$. 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$

Otra equivalencia que tendrás que demostrar como parte de los ejercicios es la siguiente.

Proposición. Un conjunto $x$ es transitivo si y sólo si $\bigcup x\subseteq x$.

Otros resultados para conjuntos transitivos

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. Como $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 transitivo.

$\square$

Hay una segunda demostración de la proposición anterior, usando álgebra de conjuntos y la primera caracterización de la sección anterior.

Demostración. Como $x$ y $y$ son transitivos, tenemos que $x\subseteq \mathcal{P}(x)$ y $y\subseteq \mathcal{P}(y)$. Así, por propiedades que hemos demostrados de intersección, $$x\cap y \subseteq \mathcal{P}(x) \cap \mathcal{P}(y) \subseteq \mathcal{P}(x\cap y).$$

Así, $x\cap y \subseteq \mathcal{P}(x\cap y)$ y por lo tanto $x\cap y$ es transitivo.

$\square$

La transitividad también se preserva al unir conjuntos.

Proposición. Si $x$ y $y$ son conjuntos transitivos, entonces $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. Como $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$. Por lo tanto, $x\cup y$ es transitivo.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitira reforzar el concepto de conjunto transitivo.

  1. ¿Cuáles de los siguientes conjuntos son transitivos?
    1. $\set{\emptyset, \set{\emptyset}}$,
    2. $\set{\set{\emptyset}}$,
    3. $\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$.
  2. Verifica que, por definición, cada uno de los conjuntos $0,1,2,3,4$ que ya definimos son transitivos.
  3. Demuestra que $(\set{\emptyset, \set{\emptyset}, \set{\emptyset,\set{\emptyset}}}, \in)$ es un conjunto totalmente ordenado.
  4. Demuestra que $x=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ tiene elemento máximo y elemento mínimo en el orden $\in_x$.
  5. Demuestra la segunda equivalencia de la sección de conjuntos transitivos, es decir, que $x$ es transitivo si y sólo si $\bigcup x\subseteq x$.
  6. Si $x$ y $y$ son conjuntos transitivos, ¿será cierto que $x\setminus y$ siempre es un conjunto transitivo?, ¿será cierto que $x\triangle y$ siempre es un conjunto transitivo? Da una demostración o encuentra un contraejemplo en cada caso.

Más adelante…

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

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»