Archivo de la etiqueta: conjuntos transitivos

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»

Álgebra Superior II: La relación de orden en los naturales

Por Roberto Manríquez Castillo

Deja un comentario

Introducción

Seguramente desde que construimos de forma intuitiva el conjunto de números naturales, te diste cuenta de que nuestra forma de generar nuevos números a través de la función sucesor, nos daba una jerarquía de qué número natural iba primero, y quien era el que inmediatamente le seguía. Así, el primer natural debería de ser el $0$, el cual debería ser menor a todos los demás. Después, seguiría $\sigma(0)=1$ el cual debería ser menor al sucesor de cualquier otro número. Este razonamiento podría seguir de forma inductiva para los demás números.

En esta entrada abordaremos el problema de cómo organizar el conjunto de naturales. Hay varias formas de definir esta relación. Pero el trabajo que realizamos en las dos entradas pasadas nos permitirá atacar dos problemas de manera sencilla: el de definir el orden en $\mathbb{N}$ y el de demostrar sus propiedades.

El orden parcial en $\mathbb{N}$

Recordemos que si $n$ es un número natural distinto de cero, entonces $n=\{0,1,…,n-1\}$. Entonces de forma intuitiva podemos afirmar que cada número natural tienen por elementos a todos los naturales «menores» a él. Usando esta idea, podemos dar las siguientes dos definiciones.

Definición. Si $n,m\in \mathbb{N}$, decimos que $n$ es menor que $m$, en símbolos, $n<m$ si $n\in m$.

Definición. Si $n,m\in \mathbb{N}$, decimos que $n$ es menor o igual que $m$, en símbolos $n\leq m$ si $n\in m$ o $n=m$.

Antes de lanzarnos a probar propiedades de estas relaciones, comenzaremos con verificar la segunda de ellas define un orden parcial.

Teorema. La relación $\leq$ es un orden parcial en $\mathbb{N}$.

Demostración. Recordemos que según la definición de orden parcial, debemos probar que $\leq$ es reflexiva, transitiva y antisimétrica, hagamos esto por pasos.

$\leq$ es reflexiva: Si $m$ es un natural, tenemos que $m=m$, por lo que por nuestra definición, podemos escribir que $m\leq m$.

$\leq$ es transitiva: Sean $n,m,l$ naturales tales que $n\leq m$ y $m\leq l$. Debemos demostrar que $n\leq l$. Si $n=m$ o $m=l$ la conclusión es inmediata de las hipótesis. En otro caso, tenemos que que $n\in m$ y $m\in l$. Como $l$ es un número natural, es un conjunto transitivo, entonces $n\in l$, por lo que $n\leq l$.

$\leq$ es antisimétrica: Si $n,m$ son naturales tales que $n\leq m$ y $m\leq n$, debemos demostrar que $n=m$. Para ver esto, procedamos por contradicción. Supongamos que no son iguales, entonces $n\in m$ y $m\in n$. Pero como ya hemos mencionado anteriormente, el hecho de que dos conjuntos pertenezcan mutuamente al otro es contradictorio con el axioma de regularidad. Entonces debe suceder que $n=m$ como queríamos.

$\square$

Propiedades del orden en los naturales

Ya mostramos que $\leq$ es un orden parcial en $\mathbb{N}$. Probemos otras propiedades que esperamos que satisfaga. Empezamos con la que mencionamos en la introducción de la entrada.

Teorema. $0\leq n$ para todo natural $n$

Demostración. Si $n=0$, el resultado se sigue de manera automática. Si $n\neq 0$, el resultado se sigue de que ya demostramos que $0$ está en cada natural distinto de $0$.

$\square$

La siguiente propiedad que probaremos es que la función sucesor sí preserva el orden que definimos.

Teorema. Si $n,m\in\mathbb{N}$ y $n<m$, entonces $\sigma(n)<\sigma(m)$

Demostración. Procedamos por inducción sobre $m$. Para el caso base debemos probar que la afirmación $n<0\Rightarrow\sigma(n)<0$, es verdadera. Sin embargo, el antecedente siempre es falso, ya que $n<0$ quiere decir que $n\in\emptyset$ lo cual es absurdo. Como el antecedente siempre es falso, entonces la base de inducción es verdadera.

Supongamos que para alguna $m$ se tiene que si $n<m$, entonces $\sigma(n)< \sigma(m)$. Debemos probar que el resultado es cierto para $\sigma(m)$. Supongamos entonces que $n<\sigma(m)$. Debemos probar que $\sigma(n)<\sigma( \sigma(m))$.

Como $n<\sigma(m)$, tenemos que $n\in \sigma(m)=m\cup \{m\}$, así que tenemos dos casos: $n\in m$ o $n\in\{m\}$.

Si $n\in m$, por hipótesis inductiva $\sigma(n)\in \sigma(m)$. Como $\sigma(m)\in \sigma(\sigma(m))$ y los naturales son transitivos, tenemos $\sigma(n)\in \sigma(\sigma(m))$, es decir, $\sigma(n)< \sigma(\sigma(m))$, como queríamos.

Finalmente, si $n\in \{m\}$, entonces $n=m$, pero así $\sigma(n)=\sigma(n)\in \sigma(\sigma(m))$, de modo que $\sigma(n)<\sigma(\sigma(m))$, como queríamos.

$\square$

El orden en los naturales es total

De entre los órdenes parciales hay un tipo de órdenes especiales: aquellos en los que cualesquiera dos elementos se pueden comparar. A estos se les conoce como órdenes totales. Los resultados de esta sección muestran que la relación $\leq$ en $\mathbb{N}$ es un orden total.

Un paso intermedio para demostrar esto es ver que si un número natural es menor que otro, entonces la función sucesor «no nos puede llevar muy lejos».

Teorema. Si $n,m$ son naturales tales que $m<n$, entonces se tiene que $\sigma(m)\leq n$.

Demostración. La hipótesis es imposible cuando $n=0$, pues no hay ningún natural menor a cero. Así, $n$ debe ser sucesor de algún otro natural, digamos $n=\sigma(k)$.

De $m<\sigma(k)$ tenemos que $m\in k\cup \{k\}$, así que $m\in k$, o $m=k$. Si $m\in k$, entonces $m<k$ y por el teorema anterior tenemos que $\sigma(m)<\sigma(k)=n$. Si $m=k$, entonces $\sigma(m)=\sigma(k)=n$. En cualquier caso tenemos $\sigma(m)\leq n$.

$\square$

El anterior teorema es equivalente a la afirmación siguiente.

Corolario. Si $n,m\in\mathbb{N}$, son tales que $m<n$ pero es falso que $\sigma(m)< n$, entonces $\sigma(m)=n$.

En estos momentos es conveniente regresar a leer las dos pruebas de los teoremas anteriores, y notar que en las demostraciones, cuando suponíamos que era falso que $n<m$ nunca supusimos que $n\geq m$. Sólo apelábamos directamente a la negación de la definición. Haber usado $n\geq m$ hubiera sido un error. En primer lugar, porque aún no hemos definido el símbolo $\geq$. Y en segundo lugar, porque aún no hemos descartado una cuarta posibilidad: que $n$ y $m$ no sean comparables. En realidad esto es imposible, pero hay que demostrarlo. En $\mathbb{N}$ el orden es total y de hecho satisface la propiedad de tricotomía que enunciamos a continuación.

Teorema. Para cualesquiera $n$ y $m$ naturales se cumple una y sólo una de las siguientes afirmaciones

  • $n=m$
  • $n< m$
  • $m< n$

Demostración. Ya hemos demostrado mediante el axioma de regularidad que estas proposiciones son mutuamente excluyentes. Sólo queda demostrar que siempre sucede por lo menos una de ellas. Demostraremos esto por inducción sobre $n$.

El caso base se reduce a probar que para cualquier $m$, se tiene que $0=m$, $0\in m$ o $m\in 0$. El primer teorema que probamos muestra que siempre se da la primera o la segunda opción.

Supongamos ahora que el resultado es cierto para alguna $n$. Debemos probarlo para $\sigma(n)$. Entonces sea $m\in\mathbb{N}$ arbitrario. Por hipótesis de inducción, $m$ es comparable con $n$, entonces podemos considerar tres casos:

$m=n$. Este caso es trivial porque entonces $m\in\sigma(n)$.

$m< n$. De nuevo tenemos que $m\in n\in \sigma(n)$, y por transitividad (del orden o de los conjuntos), tenemos que $m\in\sigma(n)$.

$n< m$. Por el teorema anterior, tenemos que en este caso, $\sigma(n)<m$ ó $\sigma(n)=m$.

De cualquier forma $\sigma(n)$ y $m$ son comparables. Esto termina la demostración.

$\square$

Para finalizar, hacemos la observación de que definir los símbolos $>$ y $\geq$ en $\mathbb{N}$ es sencillo. Simplemente, diremos que $n\geq m$ cuando $m\leq n$. Así mismo, diremos que $n>m$ cuando $m<n$.

Más adelante…

Ya empezamos a probar las propiedades del orden en $\mathbb{N}$. Sin embargo, falta ver una de las más importantes: el principio del buen orden. Esta lo veremos en la entrada siguiente. También veremos que, en cierto sentido, es equivalente al principio de inducción.

Otra cosa más que falta es ver que el orden que definimos «se comporta bien» con las operaciones de suma y producto en $\mathbb{N}$. Esto resultará de suma importancia para entradas posteriores.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Demuestra que si $n\leq m$, entonces $n<\sigma(m)$.
  2. Prueba que $n\leq m$ si y sólo si $n\subseteq m$.
  3. Generaliza el teorema de que $\in$ define un orden en $\mathbb{N}$, a que $\in$ define un orden en cualquier conjunto transitivo.
  4. Demuestra que $\leq$, restringido a $n \times n$ es un orden total en el conjunto $n$.
  5. Encuentra un conjunto $A$ con tantos elementos como números naturales y una forma de ordenarlo linealmente, tal que $A$ tiene elemento máximo.

Entradas relacionadas

Agradecimientos

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

Álgebra Superior II: Conjuntos transitivos

Por Roberto Manríquez Castillo

Deja un comentario

Introducción

En las últimas cuatro entradas hemos visto al conjunto de números naturales como elementos del conjunto $\mathbb{N}$. Sin embargo, no debemos olvidar que los números naturales son también conjuntos. Y al ser conjuntos, cada uno de los naturales tiene unos ciertos elementos que los caracterizan de forma unívoca.

Pensando en esto, recordemos el ejercicio 5 de la Tarea moral de las notas sobre la Construcción de los naturales:

Problema. Muestra que si $n\neq 0$, entonces $n=\{0,1,2,…,n-1\}$.

En otras palabras, como conjunto, cada natural consiste exactamente de los números naturales anteriores. Antes de empezar a leer esta entrada, y si aún no lo has hecho, te invitamos a intentar este problema. Aunque comenzaremos la siguiente sección dando una prueba, es bueno que intentes familiarizarte por tu cuenta con lo que será necesario hacer pues dicho resultado será importante para la teoría que veremos en esta entrada.

Dos propiedades de los números naturales

Para empezar, y por la importancia de la aseveración, probamos justo el ejercicio comentado en la introducción. Primero, notemos que como en la hipótesis se pide que $n\neq0$, entonces tiene sentido hablar del número $n-1$. Aunque no hemos definido a la resta en los números naturales, podemos definir a esta expresión como el único número $m$ tal que $\sigma(m)=n$

Teorema. Si $n\neq 0$, entonces $n=\{0,1,2,…,n-1\}$.

Demostración. Procedamos por inducción sobre $n$. Como el resultado es a partir de $1$, la base inductiva corresponde al caso $n=1$. Este caso es claro, ya que por definición,
\begin{align*}
1&=\sigma(0)\\&=\sigma(\emptyset)\\&=\emptyset\cup\{\emptyset\}\\&=\{0\}.
\end{align*}

Supongamos que para alguna $n$, se tiene que $n=\{0,1,…,n-1\}$, y probemos que el resultado también es cierto para $\sigma(n)$. Para ello, se usa la siguiente cadena de igualdades, en la cual te invitamos a pensar por qué se da cada igualdad: $$\sigma(n)=n\cup\{n\}=\{0,1,…,n-1\}\cup\{n\}=\{0,1,…,n-1,n\}.$$

Esto termina el paso inductivo y por lo tanto la demostración.

$\square$

Consideremos un número natural y ocupemos este resultado para examinarlo como conjunto. Para no hacer la notación muy larga, veamos como ejemplo al $4$. Por el teorema anterior, tenemos que
\begin{align*}
4&=\{0,1,2,3\}\\&=\{\emptyset,\{0\},\{0,1\},\{0,1,2\}\}.
\end{align*}

Analizando cada elemento del conjunto $4$, podemos ver que cada uno de los elementos (ya expandidos) de nuestro conjunto, es a su vez un subconjunto del $4$. Por ejemplo, uno de los elementos de $4$ es el conjunto $2=\{0,1\}$, que claramente es un subconjunto de $4$. Pensando de forma similar, no debe ser difícil convencerse, al menos de forma intuitiva, que esta propiedad será satisfecha de manera más general en los naturales.

Motivados por lo anterior, enunciamos el teorema siguiente, y damos una prueba formal usando el principio de Inducción.

Teorema. Si $n$ es un número natural y se tiene que $y\in n$, entonces $y\subseteq n$.

En este punto es muy importante recordar que $y\in n$ significa que $y$ es un elemento de $n$, mientras que $y\subseteq n$ significa que $y$ es un subconjunto de $n$, es decir, que todo elemento de $y$ también es elemento de $n$. Pasemos a la demostración.

Demostración. De nuevo procedamos por inducción. Si $n=0$, la proposición $y\in0$ es falsa, ya que $0=\emptyset$. Como el antecedente es falso, la proposición $y\in0\Rightarrow y\subseteq0$, es verdadera, y así probamos el caso base (como $y=\emptyset$, a esto también se le conoce como una prueba por vacuidad).

Supongamos que el resultado es cierto para alguna $n$, es decir que si $y\in n$, entonces $y\subseteq n$. Probemos que también es cierta la afirmación al substituir $n$ por $\sigma(n)$.

Sea $y\in \sigma(n)=n\cup\{n\}$. Por la definición de la unión hay dos casos: o bien $y\in n$, o bien $y\in \{n\}$.

Tratemos el primer caso. Si $y\in n$, entonces por la hipótesis de inducción, tenemos que $y\subseteq n$, pero por definición de $\sigma(n)$ tenemos que $n\subseteq \sigma(n)$. Como la contención de conjuntos es transitiva, concluimos que $y\subseteq \sigma(n)$.

El caso restante es $y\in\{n\}$. En este caso, el único elemento en el conjunto del lado derecho es $n$, así que debe suceder que $y=n$. De aquí es inmediata la contención buscada, pues $y=n\subseteq \sigma(n)$. En cualquier caso, obtenemos lo que que queremos. Así la inducción y la prueba concluyen.

$\square$

Conjuntos transitivos y un ejemplo

Nota que la propiedad de un conjunto $X$ si $y\in X$ entonces $y\subseteq X$, es equivalente a la propiedad de que si $z\in y\in X$ entonces $z\in X$. En general, esta propiedad no se satisface para cualquier conjunto. Es así que motivamos la siguiente definición.

Definición. Se dice que un conjunto $X$ es transitivo, si $Z\in Y\in X$ implica que $Z\in X$.

Los conjuntos transitivos son de suma importancia en la teoría de conjuntos, y probablemente conocerás más de ellos si llevas algún curso de esa materia. Un estudio profundo de estos conjuntos se sale de los fines de nuestro curso, pero podemos decir unas pocas cosas más. Con esta nueva definición podemos reformular el teorema de la sección anterior como sigue.

Teorema. Cada uno de los números naturales es un conjunto transitivo.

Como mencionamos, los conjuntos transitivos parecen ser una clase muy particular de conjuntos. Sin embargo, podemos mencionar otro conjunto transitivo de suma importancia: el conjunto $\mathbb{N}$. Esperamos que así como hicimos con los números naturales, puedas formarte una intuición de por qué esta afirmación es cierta, usando el teorema inicial.

Antes de dar la prueba, consideramos pertinente hacer mención de los límites del principio de inducción. En el teorema anterior, probamos que cada número natural es transitivo, nunca se probó que $\mathbb{N}$, fuese transitivo. De la misma forma, si en algún momento pruebas que una afirmación es cierta para cualquier número natural, esa misma afirmación podría dejar de ser cierta al considerar el caso de todo el conjunto $\mathbb{N}$. Encontraremos ejemplos de esto en entradas posteriores. Ahora sí, enunciamos el teorema.

Teorema: El conjunto $\mathbb{N}$ de números naturales es transitivo.

Demostración. Debemos probar que si $n\in \mathbb{N}$, entonces $n\subseteq \mathbb{N}$. Es decir, que todo número natural es un subconjunto de $\mathbb{N}$. Para esto, usaremos inducción sobre $n$.

Evidentemente la base es cierta ya que $0=\emptyset$ es un subconjunto de todo conjunto, en particular del de los naturales.

Supongamos que para un natural fijo $n$ sucede que $n\subseteq\mathbb{N}$ y a partir de ello probemos que $\sigma(n)$ también es un subconjunto de los naturales.

Para ver que esto es cierto, usamos que $\sigma(n)=n\cup \{n\}$. Esta es una unión de conjuntos, así que basta ver que cada uno está contenido en $\mathbb{N}$. Por un lado, $\{n\}$ está contenido en los naturales, ya que su único elemento es el número $n$, que está en $\mathbb{N}$. Por otro lado, por hipótesis de inducción, $n\subseteq\mathbb{N}$. Concluimos entonces, como queríamos, que $\sigma(n)\subseteq \mathbb{N}$.

$\square$

Nota que el teorema inicial de la sección es un refinamiento de este teorema. No sólo nos dice que los números naturales están contenidos en $\mathbb{N}$. Además, también especifica quiénes son los elementos de $n$.

Más adelante…

El teorema que demostramos al inicio de la entrada tendrá de nuevo mucha importancia en el siguiente tema. Aunque demostramos que cada número $n$ es el conjunto de los $n$ elementos menores que el, necesitamos definir qué significa que un conjunto tenga $n$ elementos. Motivados por esta idea, y por las características de los números naturales, definiremos también la idea de que un conjunto tenga una cantidad infinita de elementos. Veremos que, como podrás intuir, el conjunto $\mathbb{N}$ de todos los números naturales es en verdad un conjunto infinito y que en cierto sentido formal es el «más pequeño» de todos estos conjuntos.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Demuestra que $\{2,3\} $ no es un conjunto transitivo ¿Quién es el mínimo conjunto transitivo que lo contiene?
  2. Prueba que si $X$ y $Y$ son transitivos, entonces $X\cap Y$ es transitivo.
  3. Demuestra que si $X$ es transitivo, entonces $\bigcup X$ también es un conjunto transitivo.
  4. Prueba que en general que si $X$ es transitivo, entonces $\sigma (X)$ también es transitivo.
  5. Demuestra que un conjunto es transitivo si y solo si $\bigcup X\subset X$.

Entradas relacionadas

Agradecimientos

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