Archivo del Autor: Gabriela Hernández Aguilar

Teoría de los Conjuntos I: Teorema de recursión

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

A lo largo de la historia, el ser humano tuvo la necesidad de contar sus pertenencias. Esta idea la podemos asociar con los números naturales. Dado que la cantidad de cosas que alguien puede aumentar o disminuir, se tuvo la necesidad de sumar y restar. Ya definimos a los números naturales. Ahora hablaremos de la operación de suma. Pero para ello, primero necesitamos enunciar y demostrar un teorema muy importante: el teorema de recursión.

Motivación del proceso recursivo

Definir una operación de forma recursiva es de los procesos más comunes que hay. La suma y el producto son operaciones que se definirán con este proceso. Veamos, de manera intuitiva cómo queremos definir a la suma en los naturales.

La operación $+:(\mathbb{N}\times \mathbb{N})\to \mathbb{N}$ queremos que cumpla lo siguiente:

\begin{align*}
+(n,0)&=n+0=n\\
+(n,s(0))&= n+s(0)=n+1=s(n)=s(n+0)\\
+(n, s(1))&=n+s(1)=n+2=s(n+1)\\
\vdots\\
\end{align*}

En vez de poner puntos suspensivos, podemos reescribir esto como sigue.

\begin{align*}
+(n,0)&=n\\
+(n,s(m))&=s(n+m)\ \text{para cualquier}\ m\in\mathbb{N}.
\end{align*}

Observa estas propiedades con cuidado. Pensemos en que el número $n$ es fijo y vemos qué está sucediendo con $m$. En primer lugar, estamos diciendo qué queremos que suceda cuando $m=0$: estamos pidendo que se cumpla que $n+0=n$. En segundo lugar, estamos diciendo qué queremos que suceda con el sucesor de $m$: queremos que $n+s(m)=s(n+m)$. Esto tiene sentido pues si vamos definiendo «en orden» la suma, ya sabremos cuál es el valor de $n+m$, y para calcular $n+s(m)$ basta aplicar la función sucesor al número ya conocido $n+m$.

A este procedimiento es al que le llamaremos recursión. Para definir una función $f:\mathbb{N}\to A$, estableceremos un «caso base» diciendo quién es $f(0)$ y luego daremos una manera de obtener $f(n+1)$ a partir de $f(n)$. Antes de enunciar y demostrar esto formalmente, veremos un concepto que nos será de utilidad.

Cálculos de longitud $m$

Definición. Sea $A$ un conjunto y $a\in A$. Sea $g:A\to A$ una función. Sea $m\in \mathbb{N}$. Decimos que $t$ es un cálculo de longitud $m$ basado en $g$ si y sólo si $t$ es una función que satisface:

\begin{align*}
t&:s(m)\to A\\
t(0)&=a\\
t(s(k))&=g(t(k))\ \text{para cualquier}\ k\in\mathbb{N}\ \text{tal que}\ 0\leq k< m.
\end{align*}

Ejemplo.

¿Cómo se ve un cálculo de longitud $0$?

Sea $A$ un conjunto y $a\in A$ y sea $g:A\to A$. Un cálculo de longitud $0$ es una función $t: s(0)\to A$ tal que $t(0)=a$. (La segunda propiedad de la definición se satisface por vacuidad).

Y, ¿cómo se ve un cálculo de longitud $1$?

Sea $A$ un conjunto y $a\in A$ y sea $g:A\to A$. Un cálculo de longitud $1$ es una función

\begin{align*}
t&: s(1)\to A\\
t(0)&=a\\
t(s(0))&=g(t(0))= g(a).
\end{align*}

El $dom(t)=s(1)=\set{0,1}$ por lo que para saber quién es $t$ basta con saber a dónde envía al $0$ y al $1$, lo cuál sabemos: $0\to a$ y $1\to g(a)$, donde $g(a)\in A$.

$\square$

Ahora que tenemos ejemplos de cálculos de longitud $0$ y $1$, vamos a proceder a enunciar el teorema de recursión. En la demostración notaremos que será de gran importancia conocer el concepto de cálculo de longitud $m$.

Teorema de recursión

Teorema. Sean $A$ un conjunto cualquiera, $a\in A$ y $g:A\to A$ una función. Existe una única función $f: \mathbb{N}\to A$ que satisface:

a) $f(0)=a$,

b) $f(s(n))=g(f(n))$ para todo $n\in \mathbb{N}$.

Demostración.

Para hacer la demostración primero vamos a ver que para cada número natural $m$ existe un único cálculo de longitud $m$ basado en $g$. Este hecho lo vamos a probar por inducción.

Base de inducción. En el ejemplo anterior vimos que existe el cálculo de longitud $0$, por lo que basta ver que esta función es única. Supongamos que existe $l: s(0)\to A$ tal que $l(0)=a$. Como $t=\set{(0,a)}$ y $l=\set{(0,a)}$, entonces $s=t$, y por lo tanto el cálculo de longitud $0$ es único.

Hipótesis de inducción. Supongamos que existe un único cálculo de longitud $n$ basado en $g$, es decir, existe una única función $t:s(n)\to A$ que satisface:

\begin{align*}
t&: s(n)\to A\\
t(0)&=a\\
t(s(k))&=g(t(k))\ \text{con}\ 0\leq k< n
\end{align*}

Paso inductivo. Veamos que existe un único cálculo de longitud $s(n)$.

Proponemos $t^{*}:s(s(n))\to A$ dada por $t^{*}=t\cup \set{(s(n), g(t(n)))}$. Se tiene que $t^{*}$ es un cálculo de longitud $s(n)$. Para comprobarlo, notemos primero que $t\cap\{(s(n),g(t(n)))\}=\emptyset$, pues $s(n)\notin s(n)=dom(t)$, de modo que la pareja $(s(n),g(t(n)))$ no está en $t$. Por tanto, $t$ y $\{(s(n),g(t(n)))\}$ son funciones compatibles y, en consecuencia, $t^{*}$ es una función. Además, $domt^{*}=dom(t)\cup\{s(n)\}=s(n)\cup\{s(n)\}=s(s(n))$, por lo que $t^{*}$ es una función de $s(s(n))$ en $A$. Notemos ahora que $t^{*}(0)=t(0)=a$; por otro lado, si $k\in\mathbb{N}$ es tal que $0\leq k<n$, entonces, $t^{*}(s(k))=t(s(k))=g(t(k))=g(t^{*}(k))$ y, además, $t^{*}(s(n))=g(t(n))=g(t^{*}(n))$. Por tanto, $t^{*}$ es un cálculo de longitud $s(n)$. Resta ver que $t^{*}$ es el único cálculo de longitud $s(n)$.

En efecto, supongamos que $t_1$ y $t_2$ son dos cálculos de longitud $s(n)$. Veamos que $t_1=t_2$. Sean $p_1=t_1\setminus \set{(s(n), t_1(s(n)))}$ y $p_2=t_2\setminus \set{(s(n), t_2(s(n)))}$. Veamos que $p_1$ y $p_2$ son cálculos de longitud $n$. Notemos que $dom(p_1)=dom(t_1)\setminus\set{s(n)}=s(s(n))\setminus\{s(n)\}=s(n)$ y $dom(p_2)=dom(t_2)\setminus\set{s(n)}=s(s(n))\setminus\set{s(n)}=s(n)$. Por otro lado, $p_1(0)=t_1(0)=a=t_2(0)=p_2(0)$ y, para cada $k\in s(n)$ tal que $0\leq k<n$ tenemos $p_1(s(k))=t_1(s(k))=g(t_1(k))=g(p_1(k))$ y $p_2(s(k))=t_2(s(k))=g(t_2(k))=g(p_2(k))$. Esto muestra que $p_1$ y $p_2$ son cálculos de longitud $n$ y, por hipótesis de inducción, tenemos que $p_1=p_2$ y, por tanto, $t_1\setminus\set{(s(n),t_1(s(n)))}=t_2\setminus\set{(s(n),t_2(s(n)))}$. Resta mostrar que $t_1(s(n))=t_2(s(n))$, lo cual ocurre debido a lo siguiente

$t_1(s(n))= g(t_1(n))=g(t_2(n))=t_2(s(n))$.

Por lo tanto, $t_1=t_2$. Esto prueba la unicidad del cálculo de longitud $s(n)$. Llamemos entonces $t_m$ al único cálculo de longitud $m$ para cada $m\in \mathbb{N}$.

Ahora consideremos $\mathcal{F}=\set{t_m: m\in \mathbb{N}}$ y sea $f=\bigcup\mathcal{F}$. Afirmamos que $f$ es función. Por lo que se discutió en la entrada anterior, basta ver que $\mathcal{F}$ es un sistema compatible de funciones.

Sean $t_n,t_m\in \mathcal{F}$ cualesquiera funciones. Veamos que $t_n:s(n)\to A$ y $t_m:s(m)\to A$ son funciones compatibles. Para ello, mostraremos que para cualquier $x\in dom(t_n)\cap dom(t_m)$, se tiene que $t_n(x)=t_m(x)$.

Primero, tenemos que $dom(t_n)=s(n)$ y $dom(t_m)= s(m)$. Supongamos, sin pérdida de generalidad, que $s(n)\leq s(m)$, por lo que $s(n)\subseteq s(m)$ y así, $dom(t_n)\cap dom(t_m)= s(n)\cap s(m)= s(n)$. Así, debemos ver que para cualquier $x\in s(n)$, se tiene que $t_n(x)=t_m(x)$. Notemos que $t_m\upharpoonright_{s(n)}$ es un cálculo de longitud $s(n)$, pues $t_m\upharpoonright_{s(n)}(0)=t_m(0)=a$ y $t_m\upharpoonright_{s(n)}(s(k))=t_m(s(k))=g(t_m(k))=g(t_m\upharpoonright_{s(n)}(k))$ para cada $k\in\mathbb{N}$ tal que $0\leq k<n$. Por tanto, $t_n=t_m\upharpoonright_{s(n)}$, es decir, $t_n(x)=t_m(x)$ para cada $x\in s(n)$. Por tanto, $t_n$ y $t_m$ son funciones compatibles.

Tenemos entonces que $f=\bigcup\mathcal{F}$ es función y además, es tal que $dom(f)=\mathbb{N}$ y $Im(f)\subseteq A$ (en los ejercicios mostrarás que $\bigcup \mathbb{N}=\mathbb{N}$).

Esto prueba que existe $f:\mathbb{N}\to A$ que satisface las condiciones enunciadas en el teorema.

Nos resta ver que $f$ es única. Para ello, supongamos que existe $h:\mathbb{N}\to A$, tal que:

  1. $h(0)=a$,
  2. $h(s(n))= g(h(n))$ para cualquier $n\in \mathbb{N}$.

Veremos por inducción que $h(n)=f(n)$ para cada $n\in\mathbb{N}$. Primero, $h(0)=a=f(0)$. Ahora supongamos que $h(n)=f(n)$ para algún $n\in\mathbb{N}$. Para el paso inductivo, tenemos que:

$h(s(n))= g(h(n))=g(f(n))=f(s(n))$.

Por lo tanto, para cualquier $n\in \mathbb{N}$ se cumple que $h(n)=f(n)$. Esto prueba la unicidad de $f$ y concluye la prueba del teorema de recursión.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido de esta entrada.

  1. Demuestra que $\bigcup \mathbb{N} = \mathbb{N}$.
  2. Sea $A$ un conjunto y $f : A\to A$ una función. Definimos:
    \begin{align*}
    f_0 &= Id_A,\\
    &\vdots\\
    f_{n+1} &= f_n\circ f.
    \end{align*}
    Demuestra que para cada $n \in \mathbb {N}$, $f_n$ es un elemento unívocamente determinado de $A^A$.
  3. Demuestra la siguiente versión más general del teorema de recursión, en donde en cada «paso» se permite aplicar una función distinta. Sean $A$ un conjunto cualquiera y $a\in A$. Sea $\mathcal{G}=\{g_i\}_{i\in \mathbb{N}}$ una familia de funciones de $A$ en $A$. Entonces, existe una única función $f: \mathbb{N}\to A$ que satisface:
    a) $f(0)=a$,
    b) $f(s(n))=g_n(f(n))$ para todo $n\in \mathbb{N}$.
  4. Sean $A$ un conjunto y $g:\mathcal{S}=\cup_{n\in\mathbb{N}}A^n\to A$ una función, donde $A^n$ es el conjunto de funciones de $n$ en $A$ para cada $n\in\mathbb{N}$. Demuestra que existe una única función $f:\mathbb{N}\to A$ tal que $f(n)=g(f\upharpoonright_n)$ para cada $n\in\mathbb{N}$.
    Sugerencia: Considera la función $F:\mathcal{S}\to\mathcal{S}$ definida por medio de $F(x)=x\cup\{(n,g(x))\}$ si $x\in A^n$, para cada $x\in\mathcal{S}$. Por el teorema de recursión, existe una única función $h:\mathbb{N}\to\mathcal{S}$ tal que $h(0)=\emptyset$ y $h(s(n))=F(h(n))$ para cada $n\in\mathbb{N}$. Concluye que $f:=\bigcup h[\mathbb{N}]$ es una función de $\mathbb{N}$ en $A$ con las propiedades deseadas.

Más adelante…

Ahora que hemos enunciado y demostrado el teorema de recursión, podemos definir la suma en el conjunto de los números naturales. En la siguiente entrada definiremos esta operación y a su vez probaremos algunas de sus propiedades haciendo uso del principio de inducción.

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: Funciones compatibles

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

Esta entrada nos permitirá dar un breve espacio a las funciones compatibles. Será de gran importancia hacer una parada en este concepto pues será de gran utilidad en la demostración de nuestro siguiente teorema: el teorema de recursión.

Funciones compatibles

En esta entrada exploraremos la pregunta de cuándo y en qué sentido la unión de dos o más funciones es una función. La definición que nos ayudará a explorar esto es la siguiente.

Definición. Sean $f$ y $g$ funciones. Decimos que $f$ y $g$ son funciones compatibles si y sólo si $f(x)=g(x)$ para cualquier $x\in dom(f)\cap dom(g)$.

Como consecuencia de la definición, si $f$ y $g$ son funciones tales que $dom(f)\cap dom(g)=\emptyset$, entonces por vacuidad $f$ y $g$ son compatibles.

Ejemplo.

Consideremos las funciones $f:\{1,2,3\}\to\{1,2\}$ y $g:\{0,4\}\to \{1,2,3\}$ dadas por $f(1)=f(2)=1$, $f(3)=2$, $g(0)=1$, $g(4)=3$. Como $dom(f)\cap dom(g)=\emptyset$, entoces $f$ y $g$ son compatibles.

$\square$

Ejemplo.

Consideremos las funciones $h:\{1,3\}\to \{0,1\}$ y $k:\{0,1,2\}\to \{0,1,2,3,4\}$ dadas como sigue:

\begin{align*}
h&=\{(1,0), (3,1)\}\\
k&=\{(0,3),(1,0),(2,2)\}
\end{align*}

Para ver que $h$ y $k$ son funciones compatibles, basta ver que para cada elemento $x$ en $dom(h)\cap dom(k)=\{1\}$ se cumple que $h(x)=k(x)$. Como el único elemento en la intersección es el $1$, basta ver que $h(1)=k(1)$. Y en efecto, $h(1)=0=k(1)$. Por lo tanto, $f$ y $g$ son funciones compatibles.

$\square$

Hay una definición más general, para cuando se tienen varias funciones.

Definición. Sea $\mathcal{F}$ un conjunto de funciones. Diremos que $\mathcal{F}$ es un sistema compatible de funciones si para cualesquiera $f,g\in \mathcal{F}$, se tiene que $f$ y $g$ son compatibles.

Ejemplo.

Si consideramos a $\mathcal{F}=\set{h,k}$ con $h$ y $k$ como en el ejemplo anterior, tenemos que $\mathcal{F}$ es un sistema compatible de funciones pues $h$ y $k$ son funciones compatibles.

$\square$

Ejemplo.

Para cada $n\in\mathbb{N}\setminus\set{0}$ definamos $f_n:n\to\mathbb{N}$ por medio de $f_n(k)=s(k)$ para cada $k\in n$, donde $s(k)$ es el sucesor de $k$. Veamos que $\mathcal{F}=\set{f_n:n\in\mathbb{N}\setminus\set{0}}$ es un sistema de funciones compatibles. Si $n,m\in\mathbb{N}\setminus\set{0}$, entonces, $n\leq m$ o $m\leq n$ y, por consiguiente, $dom(f_n)\subseteq dom(f_m)$ o $dom(f_m)\subseteq dom(f_n)$; más aún, $f_n\subseteq f_m$ o $f_m\subseteq f_n$ y, por tanto, $f_n$ y $f_m$ son funciones compatibles. Por tanto, $\mathcal{F}$ es un sistema de funciones compatibles.

$\square$

Cuándo la unión de funciones es función

Teorema. Sean $f:X\to Y$ y $g:X’\to Y’$ funciones compatibles. Entonces $f\cup g$ es una función de $X\cup X’$ en $Y\cup Y’$.

Demostración.

Sean $f:X\to Y$ y $g:X’\to Y’$ funciones compatibles. Consideremos $f\cup g$. Debemos ver que $f\cup g$ tiene el dominio y codominio correctos, que es total y que es funcional.

La unión de $f$ y $g$ tiene el dominio y codominio correctos

Veamos que $f\cup g$ es una relación de $X\cup X’$ en $Y\cup Y’$. En efecto, cada pareja en $f\cup g$ es de la forma $(x,y)$ con $(x,y)$ en $X\times Y$, o $(x,y)$ en $X’\times Y’$. Si $(x,y)\in X\times Y$, entonces $x\in X \subseteq X\cup X’$ y $y\in Y\subseteq Y\times Y’$, y así $(x,y)\in (X\cup X’)\times (Y \cup Y’)$. De manera análoga, si $(x,y)\in X’\times Y’$, entonces $(x,y)\in (X\cup X’)\times (Y \cup Y’)$.

$f\cup g$ es total

Consideremos $x\in X\times X’$. Si $x\in X$, como $f$ es función, entonces es total y por lo tanto existe $y\in Y$ tal que $(x,y)\in f$. Así, $(x,y)\in f\cup g$. Si $x\in X’$, como $g$ es función, entonces es total y por lo tanto existe $y\in Y’$ tal que $(x,y)\in g$. Así, $(x,y)\in f\cup g$. En cualquier caso, existe $y\in Y\cup Y’$ para el cual $(x,y)\in f\cup g$. Esto muestra que $f\cup g$ es total.

$f\cup g$ es funcional

Supongamos que $(x,y) \in f\cup g$ y $(x,y’)\in f\cup g$. Debemos mostrar que $y=y’$.

Caso 1. $(x,y)\in f$ y $(x,y’)\in f$. En este caso, como $f$ es función, entonces es funcional y así $y=y’$.

Caso 2. $(x,y)\in g$ y $(x,y’)\in g$. Análogamente al caso anterior, $y=y’$.

Caso 3. $(x,y)\in f$ y $(x,y’)\in g$. Tenemos entonces que $x\in dom(f)\cap dom(g)$ y, por tanto, $f(x)=g(x)$, es decir, $y=y’$, ya que $f$ y $g$ son funciones compatibles.

Caso 4.$(x,y)\in g$ y $(x,y’)\in f$. Análogamente al caso anterior.

Por lo tanto $f\cup g$ es funcional.

Por lo tanto, $f\cup g$ es función de $X\cup X’$ en $Y\cup Y’$.

$\square$

El siguiente teorema generaliza el resultado anterior

Teorema. Sea $\mathcal{F}$ una familia de funciones compatibles. Entonces se cumple que $\bigcup \mathcal{F}$ es una función con dominio $\bigcup\set{dom(f):f\in \mathcal{F}}$ y codominio $\bigcup\set{cod(f):f\in \mathcal{F}}$.

Como parte de los ejercicios de esta entrada, deberás demostrar esta generalización.

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada.

  1. En esta entrada probamos que si $f$ y $g$ son funciones compatibles, entonces $f\cup g$ es función. ¿Será cierto que si $f\cup g$ es función, entonces $f$ y $g$ son funciones compatibles?
  2. ¿Qué se necesita para que si $f:X\to Y$ y $g:X’\to Y’$ son funciones, entonces $f\cap g$ sea función de $X\cap X’$ en $Y\cap Y’$?
  3. Muestra que la unión de funciones compatibles es función, en el sentido en el que lo enuncia la generalización de la sección anterior.
  4. Sea $\mathcal{F}=\{f_i\}_{i\in \mathbb{N}}$ una familia de funciones tal que $f_{i}\subseteq f_{i+1}$. Demuestra que $\bigcup \mathcal{F}$ es una función con dominio $\bigcup\set{dom(f):f\in \mathcal{F}}$ y codominio $\bigcup\set{cod(f):f\in \mathcal{F}}$.

Más adelante…

En la siguiente entrada enunciaremos y probaremos el teorema de recursión. Dicho teorema nos permitirá definir operaciones como la suma y el producto en el conjunto de 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: Buen orden en los naturales

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada demostraremos que el conjunto de los números naturales es un conjunto bien ordenado.

Resultados previos

A continuación demostraremos el siguiente lema que nos dice que la intersección de dos números naturales resulta ser un número natural.

Lema. Si $n,m\in \mathbb{N}$, entonces $n\cap m\in \mathbb{N}$.

Demostración.

Sean $n,m\in \mathbb{N}$.

$n\cap m$ es un conjunto transitivo: En la entrada de construcción de números naturales se demostró que intersección de conjuntos transitivos es transitivo. Como $n$ y $m$ son naturales, entonces son transitivos. Así, $n\cap m$ también lo es.

$n\cap m$ es un orden total con la pertenencia:

Notemos la relación de pertenencia en $n\cap m$ es la relación $\in_{n\cap m}=\in_n\cap((n\cap m)\times(n\cap m))$. En efecto, si $x\in_{n\cap m}y$, entonces, $x\in y$ y $x,y\in n\cap m$; en particular, $x\in y$ y $x,y\in n$, es decir, $x\in_ny$. Esto muestra que $\in_{n\cap m}\subseteq \in_n\cap((n\cap m)\times(n\cap m))$. Por otro lado, si $x\in_n y$ y $x,y\in n\cap m$, entonces, $x\in y$ y $x,y\in n\cap m$, es decir, $x\in_{n\cap m}y$. Esto demuestra la igualdad mencionada.

–Asimetría de $\in_{n\cap m}$.

Sean $z,w\in n\cap m$ tales que $z\in_{n\cap m} w$. Dado que $z\in_{n\cap m}w$, entonces $z\in_nw$. De este modo, $w\notin_{n\cap m} z$, ya que de lo contrario, $w\in_n z$, lo cual contradice que $\in_n$ sea una relación asimétrica. Por lo tanto, $\in_{n\cap m}$ es asimétrica.

–Transitividad de $\in_{n\cap m}$.

Sean $z,w,y\in n\cap m$ tales que $z\in_{n\cap m} w$ y $w\in_{n\cap m} y$. Entonces, $z\in_n w$ y $w\in_n y$, por lo que $z\in_n y$ por la transitividad de $\in_n$. Así pues $z\in_n y$ y $z,y\in n\cap m$, y en consecuencia $z\in_{n\cap m}y$.

– $\in_{n\cap m}$-comparables.

Sean $z,w\in n\cap m$. En particular, $z,w\in n$. Luego, por ser $(n, \in_n)$ un orden total, $z\in_n w$ o $w\in_n z$ o $z=w$. En consecuencia, $z\in_{n\cap m}w$ o $w\in_{n\cap m}z$ o $z=w$. Por lo tanto, los elementos de $n\cap m$ son $\in_{n\cap m}$-comparables.

Cualquier subconjunto $B$ no vacío de $n\cap m$ tiene elemento mínimo y máximo.

Veamos que $B$ tiene mínimo. Lo del máximo quedará como uno de los ejercicos. Dado que $B\subseteq n\cap m$, entonces, en particular, $B\subseteq n$. Dado que $n$ es un número natural y $B$ es un subconjunto no vacío de $n$, $B$ tiene mínimo con respecto a $\in_n$.

Sea $a=\min(B)$ con respecto a $\in_n$. Luego, $a\in_nx$ para todo $x\in B\setminus\set{a}$. Así pues, si $x\in B\setminus\set{a}$ es cualquier elemento, entonces, $a\in_n x$ y, como $a,x\in n\cap m$ pues $B\subseteq n\cap m$, se sigue, $a\in_{n\cap m}x$. Por lo tanto, $a=\min(B)$ en el orden $\in_{n\cap m}$.

Por lo tanto, si $n,m\in \mathbb{N}$, entonces $n\cap m\in \mathbb{N}$.

$\square$

En la tarea moral te corresponde probar que cualquier subconjunto no vacío de $n\cap m$ tiene elemento máximo.

Antes de demostrar nuestro resultado principal, probaremos otros dos resultados auxiliares.

Lema. Si $n, m$ son naturales distintos $n\subsetneq m$, entonces $n\in m$.

Demostración.

Sean $n,m\in \mathbb{N}$ distintos tales que $n\subsetneq m$. Como, $m\setminus n\subseteq m$ y $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$ tal que $y\in k$, pero esto es imposible pues $k=\min(m\setminus n)$. Por lo tanto, $y\in n$ y, por ende, $k\subseteq n$.

$\supseteq$) Sea $y\in n$. Como $n\subseteq m$, entonces $y\in m$. Ahora, por ser $m$ un natural, $m$ está ordenado totalmente por la pertenencia. Así que, $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. Así, tendríamos $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, 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\subsetneq$ 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$.

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$

Los naturales están bien ordenados

Estamos listos para probar el resultado principal de esta entrada.

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$. Como $n\leq m$, sabemos que $n\in m$ o $n=m$. El caso $n\in m$ lleva a una contradicción, pues como $m\leq n$ entonces o $m=n$ (y llegamos a la contradicción $n\in n$) o $m\in n$ (y llegamos a la contradicción $n\in m$ y $m\in n$). Así, $n=m$.

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 lo 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)$. Afirmamos que $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. Sea $X$ un subconjunto no vacío de $\mathbb{N}$, demuestra que $\bigcap X\in \mathbb{N}\cap X$. (Nota que esta es una generalización del primer lema que probamos en esta entrada).
  2. Muestra que cualquier subconjunto no vacío de $n\cap m$ tiene elemento máximo.

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. Dicho teorema será de utilidad para definir recursivamente a la suma y el producto en el conjunto de 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: 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»