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

Por Gabriela Hernández Aguilar

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 poseer cambia, es decir, aumenta o disminuye se tuvo la necesidad de sumar y restar. En el curso de teoría de los conjuntos ya habiendo definido al conjunto de los naturales, definiremos a la operación suma, pero para ello ocuparemos 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 como 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\\
+(n,s(m))&=n+s(m)= s(n+m)\ \text{para cualquier}\ m\in\mathbb{N}
\end{align*}

O bien,

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

Si observamos con cuidado, podemos notar que definimos a la suma en términos del resultado anterior, a esto es a lo que llamaremos recursión.

Antes de enunciar y demostrar el teorema de recursión, veremos un concepto que ocuparemos en su demostración.

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}\ 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 1$ 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 y $a\in A$. Si $g$ es una función 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(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 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 está 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$, es decir, existe $t:s(n)\to A$ una única función que satisface:

\begin{align*}
t&: s(n)\to A\\
t(0)&=a\\
t(s(k))&=g(t(k))\ \text{con}\ $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))}$, $t*$ satisface ser un cálculo de longitud $s(n)$. Resta ver que $t*$ es única.

En efecto, supongamos que $t_1$ y $t_2$ son dos cálculos de longitud $s(n)$. Veamos que $t_1=t_2$. Procederemos con el principio de inducción:

Base de inducción: Dado que $t_1(0)=a$ y $t_2(0)=a$, entonces $t_1(0)=t_2(0)$.

Hipótesis de inducción: Supongamos ahora que para algún $k\in s(s(n))$, $t_1(k)=t_2(k)$.

Paso inductivo: Bajo la hipótesis anterior, veamos que si $s(k)\in s(s(n))$, entonces $t_1(s(k))=t_2(s(k))$.
Tenemos que

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

Por lo tanto, $t_1=t_2$ para cualquier $k<s(n)$. Lo que prueba la unicidad del cálculo de longitud $s(n)$.

Ahora consideremos $\mathcal{F}=\set{t: t\ \text{es un cálculo de longitud}\ m}$ y sea $f=\bigcup\mathcal{F}$. Veamos que $f$ es función, para ello basta ver que $\mathcal{F}$ es un sistema compatible de funciones.

Sean $f,g\in \mathcal{F}$ cualesquiera funciones, veamos que $f_1:s(n)\to A$ y $f_2:s(m)m\to A$ son funciones compatibles. Veamos que para cualquier $x\in dom(f_1)\cap dom(f_2)$, $f_1(x)=f_2(x)$.

Primero, tenemos que $dom(f_1)=s(n)$ y $dom(f_2)= s(m)$. Supongamos sin pérdida de la generalidad que $s(n)\leq s(m)$, por lo que $s(n)\subseteq s(m)$ y así, $dom(f_1)\cap dom(f_2)= s(n)\cap s(m)= s(n)$. Así, debemos ver que para cualquier $x\in s(n)$, $f_1(x)=f_2(x)$, procederemos por inducción:

Base de inducción: Dado que $f_1$ y $f_2$ son funciones de cálculo, tenemos que $f_1(0)=f_2(0)$.

Hipótesis de inducción: Supongamos que para algún $k\in s(n)$, entonces $f_1(k)=f_2(k)$.

Paso inductivo: Bajo la hipótesis anterior, veamos que si $s(k)\in s(n)$, entonces $f_1(s(k))= f_2(s(k))$.

Tenemos que:

$f_1(s(k))= g(f_1(k))= g(f_2(k))= f_2(s(k))$.

Por lo tanto, $f_1$ y $f_2$ son funciones compatibles y así, $\mathcal{F}$ es un sistema compatible de funciones. Por lo tanto, $f=\bigcup\mathcal{F}$ es función y es tal que $dom(f)=\mathbb{N}$ y $Im(f)\subseteq A$.

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

Tenemos que $h=f$. Procederemos a demostrarlo por el principio de inducción.

Primero, $h(0)=a=f(0)$, por lo que para $0$ se satisface que $h=f$.

Ahora supongamos que $h(n)=f(n)$ para algún $n\in\mathbb{N}$. 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=f$. 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 sección

  • Demuestra que si A es un conjunto, $S =\bigcup\set{A^n :n \in \mathbb{N}}$ y $g : S\to A$ una función. Entonces existe una única función $h : \mathbb{N} \to A$ tal que, para cada $n \in \mathbb{N}$ se cumple que: $f (n) = g (f \upharpoonright n)$.
  • 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$.

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 suma y a su vez probaremos haciendo uso del principio de inducción algunas de sus propiedades.

Enlaces

Entrada anterior: Funciones compatibles

Siguiente entrada: Suma en los naturales

Deja una respuesta

Tu dirección de correo electrónico no será publicada.

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.