Archivo del Autor: Gabriela Hernández Aguilar

Teoría de los Conjuntos I: Equipotencia y dominancia

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta unidad daremos un par de definiciones que formalizarán la idea de que un conjunto sea más grande que otro, es decir, vamos a definir y formalizar la noción de que un conjunto tenga más elementos o la misma cantidad que otro, aún cuando no definamos formalmente qué es lo que entenderemos por cantidad de elementos de un conjunto.

Equipotencia

Definición. Sean $A$ y $B$ conjuntos. Decimos que $A$ es equipotente a $B$ si existe una función biyectiva $f:A\to B$. Denotaremos $A$ es equipotente a $B$ como $A\sim B$ o bien como $|A|=|B|$.

Si podemos establecer una función biyectiva entre $A$ y $B$, diremos que tienen la misma cantidad de elementos.

Ejemplo.

Sea $A=\mathbb{N}$ y $B=\set{2k:\ k\in\mathbb{N}}$.

Afirmación. $A$ y $B$ son equipotentes.

Demostración de la afirmación.

Sea $f:\mathbb{N}\to B$ la función dada por $f(n)=2n$. Veamos que $f$ es biyectiva.

  1. Inyectividad.
    Sean $x,y\in \mathbb{N}$ tales que $f(x)= f(y)$, esto es $2x=2y$. Luego, por ley de la cancelación para el producto tenemos que $x=y$ y, por lo tanto, $f$ es inyectiva.
  2. Suprayectividad.
    Si $y\in B$, entonces $y=2k$ para algún $k\in \mathbb{N}$. Así, existe $k\in \mathbb{N}$ tal que $f(k)=2k=y$ y, por consiguiente, $f$ es suprayectiva.

Por lo tanto, $f$ es biyectiva, de modo que $A\sim B$.

$\square$

El siguiente teorema seguro te recordará algunas cosas que discutimos cuando hablamos acerca de relaciones de equivalencia.

Teorema. Sean $A$, $B$ y $C$ conjuntos. Entonces se satisfacen los siguientes enunciados:

  1. $A$ es equipotente a $A$.
  2. Si $A$ es equipotente a $B$, entonces $B$ es equipotente a $A$.
  3. Si $A$ es equipotente a $B$ y $B$ es equipotente a $C$, entonces $A$ es equipotente a $C$.

Demostración.

  1. La función $Id_A$ es una función biyectiva, por lo que podemos concluir que $A\sim A$.
  2. Supongamos que $A\sim B$, entonces existe $f:A\to B$ biyectiva. Luego, $f^{-1}:B\to A$ es una función biyectiva y por lo tanto, $B\sim A$.
  3. Supongamos que $A\sim B$ y $B\sim C$, esto es, existe $f:A\to B$ biyectiva y $g:B\to C$ biyectiva. Luego, consideremos $g\circ f: A\to C$, como $f$ y $g$ son biyectivas, entonces $g\circ f$ es biyectiva.
    Así, $A\sim C$.

$\square$

De esta manera, la equipotencia se comporta «como una relación de equivalencia». Pero, estrictamente hablando, no es una relación de equivalencia, pues dicha relación tendría que darse en la colección de todos los conjuntos, pero ya sabemos que esta colección no es un conjunto.

Por la simetría, en vez de decir «$A$ es equipontente a $B$» podemos simplemente decir que $A$ y $B$ son equipotentes.

Dominancia

Hemos visto que para que un conjunto sea equipotente a otro se requiere que exista una función biyectiva. Esto «se comporta» como una relación de equivalencia. ¿Hay una noción que se comporte como un orden parcial o un orden estricto? Sí. La siguiente definición establece esta idea.

Definición. Sean $A$ y $B$ conjuntos. Decimos que $B$ domina a $A$ si existe $f: A\to B$ tal que $f$ es inyectiva, pero no existe una función biyectiva de $A$ en $B$. Lo denotaremos como $|A|\preceq|B|$.

Ejemplo.

Sean $A=\set{1,2,3}$ y $B=\mathbb{N}$. Tenemos que $|A|\preceq|B|$ pues $f=\set{(1,1), (2,2), (3,3)}$ es iuna función inyectiva. Sin embargo, no existe $h:A\to B$ tal que $h$ sea suprayectiva.

$\square$

El siguiente teorema formaliza la idea de que $\preceq$ «se comporta» como un orden parcial.

Teorema. Sean $A$, $B$ y $C$ conjuntos. Entonces, se satisfacen los siguientes enunciados:

  1. $A\preceq A$.
  2. Si $A\preceq B$ y $B\preceq C$, entonces $A\preceq C$.

Demostración.

  1. La función $Id_A$ es una función biyectiva, en paticular es una función inyectiva por lo que podemos concluir que $A\preceq A$.
  2. Supongamos que $A\preceq B$ y $B\preceq C$, esto es, existe $f:A\to B$ inyectiva y $g:B\to C$ inyectiva. Luego, consideremos $g\circ f: A\to C$, como $f$ y $g$ son inyectivas, entonces $g\circ f$ es inyectiva. Así, $A\preceq C$.

$\square$

A continuación probaremos un teorema importante en este curso. Dicho resultado muestra que, dado un conjunto $A$, no existe una función biyectiva de $A$ en el conjunto potencia de $A$, $\mathcal{P}(A)$. Como consecuencia de este teorema, obtenemos que existen conjuntos infinitos que no son equipotentes. Es cierto que no hemos dicho qué es un conjunto infinito, pero de momento puedes entenderlo (de manera informal) como un conjunto que tiene un subconjunto con $n$ elementos para cada $n\in\mathbb{N}$.

Teorema de Cantor. Sea $A$ un conjunto, entonces $A\preceq \mathcal{P}(A)$ pero $A\not\sim \mathcal{P}(A)$.

Demostración.

Sea $A$ un conjunto. Si $A=\emptyset$, entonces, $\emptyset$ es una función inyectiva de $A$ en $\mathcal{P}(A)$, por lo que $A\preceq\mathcal{P}(A)$. Supongamos ahora que $A\not=\emptyset$. Luego, $f:A\to \mathcal{P}(A)$ dada por $f(a)=\set{a}$ es una función inyectiva y, por tanto, $A\preceq\mathcal{P}(A)$.

Veamos ahora que no existe una biyección entre $A$ y $\mathcal{P}(A)$. Sea $f:A\to\mathcal{P}(A)$ una función. Para mostrar que $f$ no es una biyección, veamos que no es sobreyectiva. Sea $B=\{x\in A: x\notin f(x)\}$. El conjunto $B$ es un elemento en $\mathcal{P}(A)$, pero no es un elemento en la imagen de $f$. En efecto, supongamos que existe $y\in A$ tal que $f(y)=B$. Dado que $y\in A=B\cup(A\setminus B)$, entonces, $y\in B$ o $y\in A\setminus B$. Si $y\in B$, entonces, $y\notin f(y)=B$, de modo que $y\in B$ y $y\notin B$, lo cual es imposible. Ahora bien, si $y\in A\setminus B$, entonces, $y\notin B=f(y)$ y por consiguiente $y\in B$, lo cual, nuevamente, es imposible. Por lo tanto, $B$ no está en la imagen de $f$ y, en consecuencia, $f$ no es sobreyectiva.

$\square$

Lo siguiente que podemos probar es que si $A$ y $B$ son conjuntos tales que $A\preceq B$ y $B\preceq A$, entonces $A\sim B$. Este resultado corresponde al teorema de Cantor-Schröder-Bernstein que demostraremos en la próxima entrada.  

Tarea moral

Los siguientes ejercicios te permitirán aprender más resultados acerca de equipotencia y dominancia.

  1. Sean $n$ y $m$ números naturales. Muestra que $n\leq m$ si y sólo si $n \preceq m$.
  2. Demuestra que si $n$ y $m$ son números naturales distintos, entonces, o bien $n$ domina a $m$ o bien $m$ domina a $n$.
  3. Demuestra que si $A\subseteq B$, entonces $A\preceq B$.
  4. Enuncia formalmente un resultado que diga por qué la noción de «domina a» se comporta como un orden estricto.
  5. De entre las siguientes afirmaciones, decide cuáles son siempre verdaderas y para cuáles hay contraejemplos.
    • Si $|A|=|B|$ y $|C|=|D|$, entonces $|A\cup B|=|C\cup D|$.
    • Si $|A|=|B|$ y $|C|=|D|$, entonces $|A\cap B|=|C\cap D|$.
    • Si $|A|=|B|$ y $|C|=|D|$, entonces $|A\times B|=|C\times D|$.

Más adelante…

En la siguiente entrada probaremos el teorema de Cantor-Schröder-Bernstein. Este teorema nos será de gran utilidad para averiguar si dos conjuntos tienen la misma cantidad de elementos sin tener que exhibir una función biyectiva, tan sólo bastará con dar dos funciones inyectivas.

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: Producto en los naturales

Por Gabriela Hernández Aguilar

3 respuestas

Introducción

Ahora que hemos definido a la suma en el conjunto de los naturales, podemos definir el producto, pues éste se refiere a sumar cierta cantidad de veces un mismo número. De este modo, el producto se definirá recursivamente en términos de la suma, así como la suma fue definida recursivamente en términos de la función sucesor.

Producto de naturales

Utilizando el teorema de recursión se puede mostrar, al igual que con la operación suma, que existe una única función $\cdot: \mathbb{N}\times\mathbb{N}\to \mathbb{N}$, denotada por $\cdot(m,n)=m\cdot n$, que satisface las siguientes condiciones:

  1. $0\cdot n=0$ para cualquier $n\in \mathbb{N}$,
  2. $s(m)\cdot n= (m\cdot n)+n$.

Dado que seguimos trabajando con conjuntos y hemos definido una nueva operación binaria, podemos preguntarnos si esta operación conmuta, es asociativa o si cumple alguna otra propiedad tal como lo hace el producto cartesiano y la suma en los naturales. Además veremos que esta operación se distribuye con la suma.

Distributividad del producto sobre la suma

Teorema. Para cualesquiera $m,n,k\in \mathbb{N}$, se tiene que $m\cdot(n+k)=m\cdot n+ m\cdot k$.

Demostración. Procederemos por inducción sobre $m$ y dejaremos fijos a $n$ y $k$.

Base de inducción. Si $m=0$, $0\cdot(n+k)=0=0+0=(0\cdot n)+(0\cdot k)$.

Hipótesis de inducción. Supongamos que se cumple para $m$, es decir, $m\cdot(n+k)= (m\cdot n)+(m\cdot k)$.

Paso inductivo. Veamos que se cumple para $m+1$, es decir, $(m+1)\cdot(n+k)=(m+1)\cdot n+(m+1)\cdot k$.

\begin{align*}
(m+1)\cdot (n+ k)&=m\cdot (n+ k)+(n+ k) \tag{Definición $\cdot$}\\
&= (m\cdot n+m\cdot k)+(n+ k) \tag{Hipótesis de inducción}\\
&= ((m\cdot n)+n)+((m\cdot k)+k)\tag{Conmutatividad y asociatividad de $+$}\\
&= (m+1)\cdot n+(m+1)\cdot k \tag{Definición $\cdot$}.
\end{align*}

Por lo tanto, $m\cdot(n+k)=m\cdot n+m\cdot k$ para cualesquiera $m, n, k\in \mathbb{N}$.

$\square$

Conmutatividad del producto

Para demostrar que el producto es conmutativo primero vamos a demostrar los siguientes lemas:

Lema 1. Para cualquier $n\in \mathbb{N}$, se tiene que $n\cdot 0=0$.

Demostración.

Procederemos por inducción sobre $n$.

Base de inducción. Si $n=0$, tenemos que $0\cdot 0=0$.

Hipótesis de inducción. Supongamos que para algún $k\in \mathbb{N}$ se satisface que $k\cdot 0=0$.

Paso de inductivo. Veamos que se cumple para $k+1$, es decir, $(k+1)\cdot 0=0$.

\begin{align*}
(k+1)\cdot 0 &=(k\cdot 0)+0\tag{Definición $\cdot$}\\
&= 0+0\tag{Hipótesis de inducción}\\
&= 0\tag{Propiedad $+$}.
\end{align*}

Por lo tanto, $n\cdot 0=0$, para cualquier $n\in \mathbb{N}$.

$\square$

Lema 2. Para cualquier $n\in \mathbb{N}$, se tiene que $n\cdot 1=n$.

Demostración.

Procederemos por inducción sobre $n$.

Base de inducción. Si $n=0$, tenemos que $0\cdot 1= 0$ por la definición de $\cdot$.

Hipótesis de inducción. Supongamos que para algún $k\in \mathbb{N}$ se satisface que $k\cdot 1=k$.

Paso de inductivo. Veamos que se cumple para $k+1$, es decir, $(k+1)\cdot 1=k+1$.

\begin{align*}
(k+1)\cdot 1&=(k\cdot 1)+1\tag{Definición $\cdot$}\\
&= k+1. \tag{Hipótesis de Inducción}
\end{align*}

Por lo tanto, para cualquier $n\in \mathbb{N}$, $n\cdot 1=n$.

$\square$

Teorema. Para cualesquiera $m,n\in \mathbb{N}$, $n\cdot m=m\cdot n$.

Demostración.

Por inducción sobre $m$.

Base de inducción. Si $m=0$, entonces $0\cdot n=0=n\cdot 0$, por el Lema 1.

Hipótesis de inducción. Supongamos que para $k$ se cumple que $n\cdot k=k\cdot n$.

Paso inductivo. Veamos que para $k+1$ se satisface que $n\cdot (k+1)= (k+1)\cdot n$.

\begin{align*}
(k+1)\cdot n&= (k\cdot n)+n\tag{Definición $+$}\\
&= (n\cdot k)+n\tag{Hipótesis de Inducción}\\
&= (n\cdot k)+(n\cdot 1) \tag{Lema 2}\\
&= n\cdot (k+1) \tag{Distributividad}.
\end{align*}

Por lo tanto, $\cdot$ es conmutativo.

$\square$

Asociatividad del producto

Teorema. Para cualesquiera $m,n,k\in \mathbb{N}$, se tiene que $m\cdot(n\cdot k)=(m\cdot n)\cdot k$.

Demostración. Procederemos por inducción sobre $m$ y dejaremos fijos a $n$ y $k$.

Base de inducción. Si $m=0$, $0\cdot(n\cdot k)=0=0\cdot k = (0\cdot n)\cdot k$.

Hipótesis de inducción. Supongamos que se cumple para $m$, es decir, $m\cdot(n\cdot k)= (m\cdot n)\cdot k$.

Paso inductivo. Veamos que se cumple para $m+1$, es decir, $(m+1)\cdot(n\cdot k)=((m+1)\cdot n)\cdot k$.

\begin{align*}
(m+1)\cdot (n\cdot k)&=(m\cdot (n\cdot k))+(n\cdot k) \tag{Definición $\cdot$}\\
&= ((m\cdot n)\cdot k)+(n\cdot k) \tag{Hipótesis de inducción}\\
&=(k\cdot(m\cdot n))+(k\cdot n) \tag{Conmutatividad del producto}\\
&=k\cdot(m\cdot n+n) \tag{Distributividad}\\
&= (m\cdot n+n)\cdot k\tag{Conmutatividad del producto}\\
&= ((m+1)\cdot n)\cdot k\tag{Definición $\cdot$}.
\end{align*}

Por lo tanto, $\cdot$ es asociativa.

$\square$

Ley de cancelación

En álgebra, cuando tenemos una ecuación como la siguiente #$x\cdot z=y\cdot z,$$ siempre que $z\not=0$, concluimos que $x=y$. Esto tiene una justificación y la llamaremos ley de cancelación para el producto. En los naturales se cumple esta ley.

Teorema. Sean $n, m, k\in \mathbb{N}$ con $k\not=0$. Si $n\cdot k=m\cdot k$, entonces $n=m$.

Para probar dicho teorema, utilizaremos la siguiente serie de resultados.

Proposición. Si $n,m\in\mathbb{N}$ son tales que $n\leq m$, entonces, existe $t\in\mathbb{N}$ tal que $n+t=m$.

Demostración (Proposición).

Mostraremos por inducción sobre $m$ que para todo $n\leq m$, existe $t_n\in \mathbb{N}$ tal que $n+t_n=m$.

Base de inducción. $k=0$. Si $n\leq 0$, entonces $n=0$, pues recordemos que dos números naturales $n$ y $m$ satisfacen $n\leq m$ si, y sólo si, $n\in m$ o $n=m$. Así, si $n\leq 0$, entonces $n\in 0$ o $n=0$, pero dado que el enunciado $n\in 0$ no puede ser cierto pues $0=\emptyset$ no tiene elementos, se sigue que $n=0$ tiene que ser verdadero. De este modo, si $n\leq 0$, entonces $n=0$ y tomando $t=0$ se tiene que $n+t=0+0=0$. Por lo tanto, para todo $n\leq 0$ existe $t_n\in\mathbb{N}$ tal que $n+t_n=0$. Por lo tanto, la proposición es cierta para $k=0$.

Hipótesis de inducción. Supongamos que para algún $k\in\mathbb{N}$ se satisface que para todo $n\leq k$, existe $t_n\in\mathbb{N}$ tal que $n+t_n=k$.

Paso inductivo. Veamos que se cumple para $s(k)$. Sea $n\leq s(k)$. Luego, $n\in s(k)$ o $n=s(k)$. Si $n=s(k)$, entonces tomamos $t=0$ y se tiene que $n+t=s(k)+0=s(k)$. Supongamos ahora que $n\in s(k)$.

Como $n\in s(k)$, entonces $n=k$ o $n\in k$, es decir, $n\leq k$. Luego, por hipótesis de inducción, existe $t_n\in\mathbb{N}$ tal que $n+t_n=k$. De este modo, si tomamos $s(t_n)\in\mathbb{N}$ se tiene que $n+s(t_n)=s(t_n)+n=s(t_n+n)=s(k)$.

En cualquier caso para $n$ hemos concluido que existe $t_n\in\mathbb{N}$ tal que $n+t_n=s(k)$.

Por lo tanto, la proposición es verdadera.

$\square$

Proposición. Si $n\in\mathbb{N}$, entonces $n\leq n+t$ para todo $t\in\mathbb{N}$.

Demostración (Proposición).

Sea $n\in\mathbb{N}$. Probaremos por inducción sobre $t$ que $n\leq n+t$ para todo $t\in\mathbb{N}$.

Base. $t=0$. Para $t=0$ tenemos que $n+t=n+0=n$, por lo que es verdad que $n\leq n+t$.

Hipótesis de inducción. Supongamos que para algún $t\in\mathbb{N}$, $n\leq n+t$.

Bajo esta hipótesis veamos que $n\leq n+s(t)$. Primero, notemos que $n+s(t)=s(t)+n$ por la conmutatividad de la suma. Luego, por definición de la suma, $s(t)+n=s(t+n)$. Dado que $s(t+n)=(t+n)\cup\set{t+n}$, entonces $n+t\in s(t+n)$. Ahora bien, por hipótesis de inducción, $n\leq n+t$, es decir, $n=n+t$ o $n\in n+t$. Si $n=n+t$, entonces $n\in s(n+t)$, ya que $n+t\in s(n+t)$, por lo que $n\leq s(n+t)=n+s(t)$.

Ahora, si $n\in n+t$, entonces, $n\in s(n+t)$ por transitividad de la pertenencia en los naturales, por lo que también se cumple que $n\leq n+s(t)$.

En cualquier caso concluimos que $n\leq n+s(t)$, lo que concluye la prueba de la proposición.

$\square$

El último resultado que veremos, antes de iniciar con la demostración de la ley de la cancelación del producto, dice lo siguiente:

Corolario. Si $n\in\mathbb{N}$ es distinto de $0$, entonces $n+t$ es distinto de $0$ para todo $t\in\mathbb{N}$.

Demostración (Corolario).

Sea $n\in\mathbb{N}$ distinto de $0$ y supongamos que $t\in\mathbb{N}$ es arbitrario. Por la proposición anterior, $n\leq n+t$, es decir, $n=n+t$ o $n\in n+t$. Si $n=n+t$, entonces $n+t$ es distinto de $0$ por la hipótesis sobre $n$. Si ahora $n\in n+t$, entonces $n+t$ es distinto de $0$, pues $n+t$ tiene un elemento, el cual es $n$, mientras que el $0$ no tiene elementos. Esto concluye la prueba.

$\square$

Ya que contamos con esta serie de resultados previos podemos dar la demostración de la ley de cancelación del producto.

Demostración (Ley de cancelación del producto).

Supongamos que $n\cdot k = m\cdot k$ con $k \neq 0$. Como el orden $\leq$ es un buen orden en $\mathbb{N}$, entonces es total. Así, $n\leq m$ o $m\leq n$. Haremos el caso $n\leq m$ pues el otro caso es análogo. Como $n\leq m$, existe un natural $t$ tal que $n+t=m$. Como $k\neq 0$, existe un natural $s$ tal que $k=s+1$. De esta manera,

\begin{align*}
ns+n &= n(s+1)\\
&=nk\\
&=mk\\
&=(n+t)(s+1)\\
&=ns+n+ts+t.
\end{align*}

En esta cadena de igualdades hemos usado las propiedades que ya hemos probado de la suma y el producto. Usando ahora la ley de cancelación de la suma, obtenemos que $0=ts+t$. Como aquí hay una suma de naturales igualada a cero, cada sumando es igual a cero. En particular, $t=0$ y por lo tanto $m=n+0=n$, como queríamos.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta sección:

  1. Demuestra que existe una única función $\cdot: \mathbb{N}\times\mathbb{N}\to \mathbb{N}$, denotada por $\cdot(m,n)=m\cdot n$, que satisface las siguientes condiciones:
    – $0\cdot n=0$ para cualquier $n\in \mathbb{N}$,
    – $s(m)\cdot n= (m\cdot n)+n$.
  2. Demuestra que para cualesquiera $m,n,l\in \mathbb{N}$ tal que $l\not=0$, si $m<n$, entonces $l\cdot m<l\cdot n$.
  3. Demuestra que para cualesquiera $m,n\in \mathbb{N}$, si $m\cdot n=0$, entonces $m=0$ o $n=0$.
  4. Usa el teorema de recursión para probar la existencia y unicidad de una función $F:\mathbb{N}\to \mathbb{N}$ que satisfaga lo siguiente:
    $F(0)=1$,
    $F(1)=1$,
    $F(2)=2\cdot 1$,
    $\vdots$
    $F(n)=n\cdot (n-1)\cdots 2\cdot 1$.
    A la función $F$ se le llama el factorial y la denotamos por $F(n)=n!$.
  5. Usa el teorema de recursión y unicidad para probar para cada natural $n$ la existencia de una función $w_n:\mathbb{N}\to \mathbb{N}$ que cumple $w_n(0)=1$ y $w_n(m+1)=n\cdot w_n(m)$. Usa las funciones $w_n$ para definir la exponenciación en $\mathbb{N}$ como la operación binaria de $\mathbb{N}$ en $\mathbb{N}$ denotada por $n^m=w_n(m)$. Prueba que la exponenciación cumple las siguientes propiedades:
    • Para todo natural $m>0$, se cumple que $0^m=0$ y $1^m=1$.
    • Para cualesquiera naturales $l,m,n$, se cumple que $(m\cdot n)^l=m^l\cdot n^l$, que $l^{m+n}=l^m\cdot l^n$ y que $(l^m)^n=l^{m\cdot n}$.
  6. Encuentra todas las soluciones en los naturales a la ecuación $m^2+n=n^2+m$. ¡Ten cuidado! En $\mathbb{N}$ todavía no hemos definido la resta, así que como primer paso no puedes «pasar restando». Todos tus argumentos tendrán que permanecer en lo que hemos construido de $\mathbb{N}$.

Más adelante…

Con esta entrada concluimos el contenido acerca de números naturales. Es lo único que haremos en este curso sobre la construcción de sistemas numéricos, pero todos estos conocimientos sirven para constuir a los enteros y los racionales. Puedes hacer clic en los enlaces para consultar el contenido de la construcción de los números enteros y de los números racionales que se encuentra en el curso de Álgebra Superior II.

Nuestro enfoque continuará siendo conjuntista, y ahora nos enfocaremos en la noción de que dos conjuntos «tengan la misma cantidad de elementos». Así, en la siguiente unidad hablaremos acerca de equipotencia, finitud, infinitud, dominancia y aritmética cardinal. El conjunto de los números naturales jugará un papel clave para esta teoría.

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: Suma en los naturales

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

Como lo dijimos en la entrada anterior, buscamos la manera de definir a la suma en el conjunto de los naturales y esto nos lo permitirá el teorema de recursión. En esta nueva entrada presentaremos la definición formal de la suma y demostraremos algunas de las propiedades que satisface.

Suma de naturales

El teorema de recursión nos garantiza que la siguiente definición es correcta.

Definición. Dado $n\in \mathbb{N}$ fijo pero arbitrario, la función sumar $n$ es la una única función $f_n:\mathbb{N}\to \mathbb{N}$ tal que $f_n(0)=n$ y $f_n(s(m))=s(f_n(m))$ para cualquier $m\in \mathbb{N}$.

Está definición nos dice cómo sumar a un número natural con un $n$ fijo. Sin embargo, usualmente entendemos a la suma como una operación binaria, que toma dos sumandos y nos da un resultado. A continuación hacemos esto.

Definición. Definimos a la suma de los naturales como la función $+: \mathbb{N}\times \mathbb{N}\to \mathbb{N}$ tal que $+(m,n)=f_m(n)$ para cualesquiera $n,m\in \mathbb{N}$. Definimos también la notación $m+n:=+(m,n)$.

Como la función $+$ está basada en las funciones $f_n$, obtenemos de manera inmediata que se satisfacen las siguientes propiedades:

  1. $0+n=n$ para cualquier $n\in \mathbb{N}$,
  2. $s(m)+n=s(m+n)$ para cualesquiera $m,n\in \mathbb{N}$.

¿Habrá otra función que satisfaga esto?

Teorema. La función $+$ es la única función de $\mathbb{N}\times \mathbb{N}$ en $\mathbb{N}$ que satisface las propiedades 1) y 2) de arriba.

Demostración.

Sea $+$ la función que definimos arriba y supongamos que existe $h:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ que satisface $h(0,n)=n$ y $h(s(m), n)= s(h(m,n))$ para cualesquiera $m,n\in \mathbb{N}$. Veamos que $+=h$.

Definamos para cada $n\in\mathbb{N}$ la función $h_n:\mathbb{N}\to\mathbb{N}$ por medio de $h_n(0)=h(n,0)$ y $h_n(m)=h(n,m)$. Notemos que para todo $n\in\mathbb{N}$, $h_n(0)=n$ y $h_n(s(m))=h(n,s(m))=s(h(n,m))=s(h_{n}(m))$, y por el teorema de recursión se sigue que $h_n=f_n$.

Así, para $n,m\in\mathbb{N}$ arbitrarios, $+(m,n)=f_n(m)=h_n(m)=h(n,m)$ y en consecuencia, $+=h$.

$\square$

Dado que seguimos trabajando con conjuntos y hemos definido una nueva operación binaria, podemos preguntarnos si esta operación conmuta, es asociativa o si cumple alguna otra propiedad algebraica. Notaremos que para demostrar estas propiedades ocuparemos en todo momento el principio de inducción.

Asociatividad de la suma

Teorema. Para cualesquiera $m,n,k\in \mathbb{N}$, se tiene que $m+(n+k)=(m+n)+k$.

Demostración.

Procederemos por inducción sobre $m$ y dejaremos fijos a $n$ y $k$.

Base de inducción. Si $m=0$, $0+(n+k)=n+k=(0+n)+k$.

Hipótesis de inducción. Supongamos que se cumple para $m$, es decir, $m+(n+k)= (m+n)+k$.

Paso inductivo. Veamos que se cumple para $s(m)$, es decir, $s(m)+(n+k)=(s(m)+n)+k$.

\begin{align*}
s(m)+(n+k)&=s(m+(n+k)) \tag{Definición $+$}\\
&= s((m+n)+k) \tag{Hipótesis de inducción}\\
&= s(m+n)+k\tag{Definición $+$}\\
&= (s(m)+n)+k\tag{Definición $+$}.
\end{align*}

Por lo tanto, $+$ es asociativa.

$\square$

Conmutatividad de la suma

Ahora vamos a ver que la suma conmuta, para ello demostraremos los siguientes lemas:

Lema 1. Para cualquier $m\in \mathbb{N}$, se tiene que $0+m=m+0$.

Demostración.

Procederemos por inducción sobre $m$.

Base de inducción. Si $m=0$, tenemos que $0+0=0=0+0$.

Hipótesis de inducción. Supongamos que para algún $k\in \mathbb{N}$ se satisface que $0+k=k+0$.

Paso de inductivo. Veamos que se cumple para $s(k)$, es decir, $0+s(k)=s(k)+0$.

\begin{align*}
s(k)+0 &=s(k+0)\tag{Definición $+$}\\
&= s(0+k)\tag{Hipótesis de inducción}\\
&= s(k)\tag{Definición $+$}\\
&= 0+s(k)\tag{Definición $+$}.
\end{align*}

Por lo tanto, $0+m=m+0$, para cualquier $m\in \mathbb{N}$.

$\square$

Lema 2. Para cualesquiera $m,n\in \mathbb{N}$, se tiene que $s(n)+m=n+s(m)$.

Demostración.

Procederemos por inducción sobre $m$.

Base de inducción. Si $n=0$, tenemos que $s(0)+m=s(0+m)= s(m)=0+s(m)$.

Hipótesis de inducción. Supongamos que para algún $k\in \mathbb{N}$ se satisface que $s(k)+m=k+s(m)$.

Paso de inductivo. Veamos que se cumple para $s(k)$, es decir, $s(s(k))+m=s(k)+s(m)$.

\begin{align*}
s(s(k))+m &=s(s(k)+m) \tag{Definición $+$}\\
&= s(k+s(m)) \tag{Hipótesis de Inducción}\\
&= s(k)+s(m) \tag{Definición $+$}.
\end{align*}

Por lo tanto, para cualesquiera $m,n\in \mathbb{N}$, se tiene que $s(n)+m=n+s(m)$.

$\square$

Proposición. Para cualesquiera $m,n\in \mathbb{N}$, se tiened que $n+m=m+n$.

Demostración.

Por inducción sobre $m$.

Base de inducción. Si $m=0$, entonces $n+0=0+n$. (Lo probamos por inducción en el primer lema 1).

Hipótesis de inducción. Supongamos que para $k$ se cumple que $n+k=k+n$.

Paso inductivo. Veamos que para $s(k)$ se satisface que $n+s(k)= s(k)+n$.

\begin{align*}
s(k)+n&= s(k+n)\tag{Definición $+$}\\
&= s(n+k)\tag{Hipótesis de Inducción}\\
&= s(n)+k\tag{Definición $+$}\\
&= n+s(k)\tag{Lema 2}.
\end{align*}

Por lo tanto, $+$ es conmutativa.

$\square$

Ley de cancelación

En álgebra, cuando tenemos una ecuación como la siguiente:

$x+5=y+5$,

dado que $5=5$, entonces ponemos $x=y$. Esto tiene una justificación y la llamaremos ley de cancelación de la suma. El teorema dice lo siguiente:

Teorema. Si se tienen números naturales $n,m,k$ tales que $n+k=m+k$, entonces $n=m$.

Demostración.

Demostraremos que si $n\not=m$, entonces $n+k\not=m+k$. Procederemos por inducción sobre $k$.

Base de inducción. Supongamos que $n\not=m$. Luego, $n+0=0+n=n$ y $m+0=0+m=m$ y así, $n+0=n\not=m=m+0$.

Hipótesis de inducción. Supongamos que para algún $k\in \mathbb{N}$, se satisface que si $n\not=m$, entonces $n+k\not=m+k$.

Paso inductivo. Veamos que se cumple para $s(k)$, es decir, si $n\not=m$, entonces $n+s(k)\not=m+s(k)$.

Supongamos que $n\not=m$. Luego,

\begin{align*}
n+s(k)&= s(n)+k\tag{Lema 2}\\
&= s(n+k)\tag{Definición $+$}\\
&\not= s(m+k)\tag{Hipótesis de inducción e inyectividad de $s$}\\
&= s(m)+k\tag{Definición $+$}\\
&= m+s(k)\tag{Lema 2}.
\end{align*}

Por lo tanto, se cumple la ley de cancelación para la suma.

$\square$

Como último resultado de esta entrada, probaremos que $s(m)=m+1$ para cualquier $m\in \mathbb{N}$.

Teorema. Para cualquier $m\in \mathbb{N}$, se tiene que $s(m)=m+1$.

Demostración.

Procederemos por inducción sobre $m$.

Base de inducción. Si $m=0$, entonces $s(0)=1=0+1$.

Hipótesis de inducción. Supongamos que para $k\in \mathbb{N}$ se cumple que $s(k)=k+1$.

Paso inductivo. Veamos que la propiedad se satisface para $s(k)$, es decir, $s(s(k))= s(k)+1$.

\begin{align*}
s(k)+1&= s(k+1)\tag{Definición $+$}\\
&= s(s(k))\tag{Hipótesis de inducción}.
\end{align*}

Por lo tanto, $s(m)=m+1$ para cualquier $m\in \mathbb{N}$.

$\square$

A partir de este momento usaremos el hecho de que $s(m)=m+1$.

Tarea moral

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

  1. Verifica totalmente a partir de las definiciones que $2+2=4$.
  2. Reflexiona sobre por qué sí se tiene que usar inducción para demostrar que $n+0=n$ para todo número natural $n$, pero no es necesario usar inducción para demostrar que $0+n=n$ para todo número natural $n$.
  3. Demuestra que si $n,m\in \mathbb{N}$ tales que $n\not=m$, entonces $s(n)\not= s(m)$.
  4. Demuestra usando el principio de inducción que para cualesquiera $m, n \in \mathbb{N}$, se tiene que $m + n \geq n$.
  5. Prueba que para cualesquiera $m,n\in \mathbb{N}$ tales que $m+n=0$, se cumple que $m=0$ y $n=0$.
  6. Demuestra usando únicamente las definiciones dadas que no existe un entero $n$ tal que $4+n = 2$.

Más adelante…

En la siguiente entrada definiremos al producto en el conjunto de los números naturales. Al igual que en la definición de la suma, podremos notar que usaremos un proceso recursivo para definir esta operació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: 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<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)\ \text{con}\ 0<s(0)=1.
\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<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(f)$, de modo que la pareja $(s(n),g(t(n)))$ no está en $f$. 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<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<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 $s(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(k))$ para cada $k\in\mathbb{N}$ tal que $0<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:

$f_0 = Id_A$,
$\vdots$
$f_{n+1} = f_n\circ f$.

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

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»