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:
- $h(0)=a$,
- $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.
- Demuestra que $\bigcup \mathbb{N} = \mathbb{N}$.
- 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$. - 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}$. - 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
- Ir a Teoría de los Conjuntos I
- Entrada anterior: Funciones compatibles
- Siguiente entrada: Suma en los naturales
Agradecimientos
Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»