Archivo de la etiqueta: teorema de recursión

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

Entradas relacionadas

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

Álgebra Superior I: Principio de recursión en los números naturales

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Introducción

En esta entrada revisaremos el concepto de recursión en un sentido matemático y revisaremos algunos ejemplos. Probablemente ya hayas escuchado el término, pues verás que es una herramienta útil para definir funciones en términos de las evaluaciones pasadas.

La suma de los primeros n números naturales

Carl Friedrich Gauss fue un matemático alemán del siglo XVIII el cual es uno de los más importantes en distintas disciplinas matemáticas como la teoría de números, la geometría y estadística. Sus aportes son varios en estas y más áreas por lo que nos tomaría varios años de estudio para llegar a muchos de sus resultados. En esta ocasión veremos uno de sus razonamientos más famosos el cual muchos le atribuyen cuando este solo estaba en el colegio cuando aún era niño.

Se dice que el profesor de su clase de matemáticas había castigado a todo el salón haciéndoles sumar los números naturales del $1$ al $100$. La historia dice que no pasó mucho tiempo (y mucho menos del esperado por el profesor) hasta que Gauss llegó con la respuesta «5050». El razonamiento que tuvo fue el siguiente: Para llegar a la suma, pondremos los números del $1$ al $100$ en una lista, y debajo los mismos números pero al revés, es decir, del $100$ al $1$, y notemos que sumando uno a uno los números de las dos listas como los hemos acomodado, queda un mismo número:

$$\begin{array}{cccccc}
&1 & 2 & \dots &99 & 100 \\
+&100 & 99 & \dots &2 & 1 \\
=&101 & 101 & \dots &101 & 101\\
\end{array}$$

De manera que si tenemos los primeros $100$ números, entonces el número resultante de la suma es $101$, de manera que si sumamos estos números, estaríamos sumando $100$ veces el número $101$, pero como hemos sumado dos veces la lista, entonces deberemos dividir entre $2$ para obtener la suma real. Dicho de otra forma: $$ \sum_{i=0}^{100} i = \frac{100(100+1)}{2} .$$
Si recuerdas, esta es la fórmula que probamos en la entrada pasada, pues en el caso general: $$ \sum_{i=0}^{n} i = \frac{n(n+1)}{2} $$

Viendo la suma como recursión

Sigamos pensando en el ejemplo. Para cada $n \in \mathbb{N}$, llamemos $$S_n = \sum_{i=0}^{n} i = \frac{n(n+1)}{2} .$$ Y nota que para cada número natural $n$ se cumple que:

  1. $S_0=0$
  2. Si $n>0$ entonces $S_n = S_{n-1}+n$

Nota ahora que podemos definir a $S_n$ únicamente en términos de la suma de su antecesor con el número. Esto quiere decir que si nos pidieran calcular $S_{51},S_{52},S_{53}$, primero podemos calcular $S_{51}$ sumando todos los números del $0$ al $51$, pero una vez tengamos ese resultado, no es necesario volver a sumar todos los números para $S_{52}$, sino que basta saber quién es $S_{51}$ y sumarle $52$ para obtener el término deseado, lo mismo para el siguiente número de la sucesión $S_{53}=S_{52}+53$. A $S$ se le puede ver como una función $S:\mathbb{N} \rightarrow \mathbb{N} $ donde $S_n$ hace referencia a la función $S$ valuada en $n$, esto quiere decir que $S(n)=S_n$. A esta función se le llamará una función recursiva.

Definición. Una función $\phi: \mathbb{N} \rightarrow \mathbb{N} $ se dice tener la propiedad de recursión si existe $a \in \mathbb{N} $ y una función $f : \mathbb{N} \rightarrow \mathbb{N} $ tal que:

  1. $\phi(0)=a$
  2. Si $n>0$ entonces $\phi(\sigma(n)) = f(\phi(n))$

Veamos esta definición por partes. Retomemos nuestro ejemplo de la suma de los primeros números naturales. La función que es recursiva es $\phi$, esta función debe satisfacer dos condiciones. La primera condición es que se defina a dónde «manda» el $0$, es decir, hace falta saber cómo empezar la definición recursiva, en este caso, se trata de cómo definimos el comportamiento de la función en el primer número del conjunto de los números naturales. La segunda condición se pone más interesante, pues lo que nos dice es que existe una función $f$ tal que la función $\phi$ evaluada en el sucesor de $n$ ($\sigma(n)=n+1$) es la función $f$ valuada en $\phi (n)$. Lo que quiere decir esta oración es que «Si quieres saber quién es $\phi(n+1)$ y ya sabes quién es $\phi (n)$, entonces basta hacerle algo a ese resultado (valuar ese resultado en $f$) para obtener lo querido».

En nuestro ejemplo de la función $S$ (en la definición, esta sería la función $\phi$), la función $f$ es aquella que a cada suma parcial le agrega el número correspondiente. Esto quiere decir que $f$ es la función: $$\begin{align*} f(S(n)) &= S(n)+n \\&= S(n+1)=S(\sigma(n))\end{align*}.$$

Teorema de recursión débil

El siguiente teorema nos garantiza no solo la existencia de funciones recursivas, sino que además nos garantiza que esta es una herramienta para conjuntos distintos al de los números naturales:

Teorema (Recursión Débil): Sea $X$ un conjunto y $x_{0}\in X$. Supongamos que tenemos una función $f:X\to X$. Entonces existe una única función $\phi:\mathbb{N}\to X$ tal que:

  • $\phi(0)=x_{0}$
  • $\phi(\sigma(n))=f(\phi(n)).$

La demostración de este teorema se verá en el curso de Álgebra Superior II. Y a grandes rasgos nos garantiza el hecho de que las definiciones de las funciones por recursión son matemáticamente válidas. En otras palabras, muestra que somos capaces de definir y usar funciones recursivas.

Algunos ejemplos

Veamos otro ejemplo de este tipo de funciones. Sea $n \in \mathbb{N}$ Definamos $$ n! = n*(n-1)*(n-2)*\dots*2*1.$$ Por ejemplo, $3!=3*2*1=6$. Nota que esta es una función que podemos describir como recursiva al establecer las siguientes condiciones:

  1. $0!=1$
  2. $n!=(n-1)!*n.$

Como veremos en siguientes entradas, esta función llamada factorial se utilizará mucho en conteo y combinatoria, pues nos hablará de el número de formas de combinar un conjunto con algún número de elementos.

El siguiente ejemplo requiere de una pequeña definición:

Definición. Sea $a$ una función. La función $a$ es una sucesión si $a : \mathbb{N} \rightarrow \mathbb{N} $ es una función entre números naturales.

Esta definición nos indica que a las funciones entre números naturales también se les conoce como sucesiones, muchas veces este no será el nombre común al que se refieran a las funciones de $ \mathbb{N} $ en $ \mathbb{N} $ pero si en alguna ocasión ves el término, sabrás a qué se refiere. También es común, al estar hablando de sucesiones, de escribir las evaluaciones de $a$ en cada término $n$ simplemente como $a_n$ es decir $a_n=a(n)$.

Supongamos ahora que tenemos la sucesión definida como $$a_n=5n+2$$. Los cinco primeros términos de esta sucesión son:$$a_0=2$$ $$a_1=7$$ $$a_2=12$$ $$a_3=17$$ $$a_4=22$$ Notemos que podemos escribir esto de forma recursiva, para ello, notemos que únicamente en cada paso estamos sumando un 5, de manera que $$a_{n+1}=a_n+5.$$Adicionalmente, ya sabemos cuánto vale en el $0$, así la siguiente proposición demuestra este hecho:

Proposición $a_n$ puede definirse de forma recursiva como:

  1. $a_0=2$
  2. $a_{n+1}=a_n+5.$

Demostración (por inducción)

Base inductiva. Es claro que $$a_0 = 2 = 0*5+2$$ De manera que se cumple la base de inducción.

Hipótesis inductiva. Supongamos que para $n\geq 0$ se cumple que $$a_n = a_{n-1}+5=5n+2.$$

Paso inductivo. Para demostrar que $$a_{n+1}=a_n+5$$ como dice la proposición, notemos que por definición de la sucesión, $$a_{n+1}=5(n+1)+2=5n+2+5.$$
Ahora, por hipótesis de inducción, $$a_n=5n+2.$$De esta forma, $$a_{n+1}=5(n+1)+2)+5=a_n+5. $$ tal como se quería demostrar.

$\square$

Tarea Moral

  1. Muestra que hay una única función $\phi$ entre número naturales tal que:
    1. $\phi(0)=10$
    2. $\phi(\sigma(n))=2\phi(n)$
  2. Da una definición explícita de la función del inciso anterior.
  3. Da una definición recursiva para las siguientes sucesiones:
    • $a_n=2n$
    • $a_n=2n+1$
    • $a_n=2^n$
    • $a_n=0$

Más adelante…

En esta entrada dimos la idea de lo que significa la recursión en las matemáticas, en la siguiente entrada usaremos esta idea para empezar a definir las operaciones básicas en los números naturales: la suma y el producto.

Entradas relacionadas

  • Ir a Álgebra Superior I
  • Entrada anterior del curso: Problemas de inducción
  • Siguiente entrada del curso: Suma y producto de naturales y sus propiedades

Agradecimientos

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

Álgebra Superior II: Principio de inducción y teoremas de recursión

Por Roberto Manríquez Castillo

Deja un comentario

Introducción

Inducción y recursión son dos conceptos similares con los que seguramente te has topado en tu formación matemática, e incluso tal vez antes. Muchas veces se llegan a confundir ambos conceptos, ya que ambos tienen una fuerte relación con el 5° axioma de Peano.

Aunque lo detallaremos a lo largo de la entrada, el principio de Inducción es una propiedad de los números naturales, que nos sirve para demostrar que todos los naturales satisfacen una propiedad. Es decir, es una estrategia de demostración. En contraste, la recursión es un resultado que justifica el hecho de poder dar una definición para todos los naturales, basándonos en la definición de su antecesor. En otras palabras, es una estrategia de definición.

Al final de la entrada demostraremos el teorema de recursión débil, en cuya prueba, podremos apreciar cómo es que depende directamente del Principio de inducción.

Pruebas por inducción

Recordemos el 5° axioma de Peano, el cual probamos en la entrada pasada que se satisface en nuestro modelo:

Si $S\subset \mathbb{N}$ satisface que

  • $0\in S$ y
  • si $n\in S$, implica que $\sigma(s)\in S$,

entonces $S=\mathbb{N}$.

Como hemos mencionado en entradas anteriores, esta proposición es muy similar al principio de Inducción que probablemente hayas ocupado desde el curso de Álgebra Superior I. Más aún, en la entrada pasada, seguimos la misma estrategia que en otros cursos, a la hora de ocupar el 5° axioma. Efectivamente, la equivalencia entre ambos resultados es casi inmediata, y como ejemplo ilustrativo, probaremos el Principio de Inducción a partir del 5° axioma de Peano.

Proposición (Principio de Inducción): Sea $P(n)$ una propiedad, es decir, una proposición matemática que depende de un entero $n$. Si se tiene que:

  1. $P(0)$ es verdadera y
  2. cada vez que $P(n)$ es cierto, también lo es $P(n+1)$,

entonces P(n) es cierta para todos los números naturales.

Demostración. Sea $P(n)$ una propiedad que satisface 1. y 2. y consideremos el conjunto $S:=\{n\in\mathbb{N}: P(n)\text{es verdadera}\}$.

Como $P(0)$ es verdadera, entonces $0\in S$.

Tomemos $n\in S$, entonces $P(n)$ es verdadera, y por 2., tenemos que $P(n+1)$ es verdadera; es decir, $n+1\in S$. Por el 5° Axioma de Peano, se tiene que $S=\mathbb{N}$, por lo que por la definición de $S$, se tiene que $P(n)$ es cierta para cada $n\in \mathbb{N}$

$\square$

Definiciones por recursión

Una de nuestras primeras ideas para poder construir a $\mathbb{N}$, fue intentar construir a mano cada elemento. Para esto, dimos una definición de lo que significaba el $0$ y el sucesor de un número. Después empezamos a iterar una y otra vez la función sucesor para obtener el sucesor del último número encontrado. Discutimos por qué es que esta idea no sería el mejor camino (sólo nos permite llegar hasta una cantidad finita de naturales), por lo tuvimos que introducir el Axioma del Infinito para resolver el problema. Veamos la analogía entre esta idea y el siguiente ejemplo intuitivo.

Ejemplo: Definamos la función factorial de un número natural, como:

  • $0!=1$
  • $(n+1)!=(n!)(n+1)$

Entonces, $3!:=(2!)(3)=(1!)(2)(3)=(0!)(1)(2)(3)=(1)(1)(2)(3)=6$.

Recordemos que al definir a los naturales, necesitábamos conocer un número para poder definir su sucesor. Aquí sucede lo mismo: en la definición de factorial necesitamos conocer quién es el factorial de un número para poder definir el factorial de su sucesor. A este tipo de definiciones se les conoce como definiciones recursivas, ya que para definir algo para un número, necesitamos tener conocimiento del valor de la función en los números anteriores.

Queda una pregunta muy importante. Si a los naturales no los pudimos definir de manera recursiva, ¿por qué podemos afirmar que la función factorial sí existe? A continuación enunciaremos algunos teoremas que nos garantizarán que sí podemos hacer este tipo de definiciones recursivas en nuestro modelo. Daremos una versión fuerte y una versión débil. Demostraremos la versión débil, pues basta para mucho de lo que queremos definir en los naturales (sumas, productos, potencias).

Las siguientes secciones son un poquito técnicas. Si las puedes seguir por completo, es fantástico. Pero incluso si no es así, basta con que en el fondo te quedes con la idea importante detrás: sí se vale definir de manera recursiva. Más adelante podrás regresar a este tema y entenderlo por completo.

Los teoremas de la recursión

Antes de la demostración principal de esta entrada, enunciaremos los teoremas que nos importan y hablaremos de manera intuitiva de lo que dicen. Hay dos versiones que veremos: una fuerte y una débil. Aunque parece que dicen cosas diferentes, en realidad son equivalentes. Será muy claro que la versión fuerte «implica» a la débil. Pero luego, en los problemas de tarea moral, se esbozará cómo ver que la versión débil se puede utilizar para demostrar la fuerte.

Teorema (Recursión Fuerte): Sea $X$ un conjunto y $x_{0}\in X$. Supongamos que tenemos varias funciones (una por cada natural $i$)

$$\{f_i:X\to X\}_{i\in\mathbb{N}\setminus \{0\}}.$$

Entonces existe una única función $g:\mathbb{N}\to X$ tal que:

  • $g(0)=x_{0}$
  • $g(\sigma(n))=f_{\sigma(n)}(g(n))$.

¿Qué es lo que quiere decir este teorema? Para responder esta pregunta veamos el siguiente diagrama:

Nuestro diagrama empieza en $0$, el cual queremos que sea mandado a algún $x_{0}\in X$, para la definición de los demás números, ocupamos la segunda característica que esperamos que $g$ satisfaga. Por ejemplo $g(1)=g(\sigma(0))=f_{1}(g(0))=f_{1}(x_{0})$. Este análisis coincide con lo que nos presenta el primer cuadro de flechas del diagrama anterior, que nos presenta los dos caminos que debe satisfacer $g$, para que sea la función que queremos. Como da lo mismo si «primero aplicamos $\sigma$ y luego $g$», a que si «primero aplicamos $g$ y luego $f_1$», decimos que el primer cuadrado del diagrama conmuta.

Análogamente, ya que conocemos la definición de $g(1)$ podemos fijarnos en el segundo cuadro, para poder definir $g(2)$ (de nuevo, conmuta) y seguir «recursivamente» para cualquier número natural.

Ejemplo: ¿Qué conjunto, y qué funciones necesitamos para definir el factorial?

Consideremos $X=\mathbb{N}$, definiremos intuitivamente (ya que aún no lo hemos definido formalmente), $f_{i}:\mathbb{N}\longrightarrow \mathbb{N}$, como $f_{i}(n)=i\cdot n$, es decir, el producto por $i$.

El teorema de Recursión Fuerte, nos dice que existe una única función $g$ tal que

  • $g(0)=1$
  • $g(\sigma(n))=f_{\sigma(n)}(g(n))=\sigma(n)\cdot g(n)$

Denotemos $n!:=g(n)$. Entonces tenemos que $\sigma(n)!=n!\cdot \sigma(n)$, justo como queremos.

$\square$

El teorema de Recursión Débil y su demostración

El teorema de Recursión Débil tiene un enunciado parecido al teorema de recursión fuerte y puede ser visto como una consecuencia directa del teorema anterior pues se obtiene de la versión fuerte tomando $f_{1}=f_{2}=\ldots=f_{n}=\ldots$

Teorema (Recursión Débil): Sea $X$ un conjunto y $x_{0}\in X$. Supongamos que tenemos una función $f:X\to X$. Entonces existe una única función $g:\mathbb{N}\to X$ tal que:

  • $g(0)=x_{0}$
  • $g(\sigma(n))=f(g(n))$.

Para concluir con esta entrada, probaremos el teorema de Recursión Débil. Antes de hacer esto introducimos un concepto auxiliar y una propiedad de los naturales.

Recordemos que como conjunto, $m=\{0,1,…,m-1\}$, lo que sugiere la siguiente definición.

Definición: Si $n,m\in \mathbb{N}$, decimos que $n<m$ si $n\in m$.

Puede probarse que esta relación en $\mathbb{N}$ es un orden total, y que sastisface la siguiente propiedad.

Teorema (Principio el Buen Orden): Sea $S\subset\mathbb{N}$ un conjunto no vacío, es decir $S\neq \emptyset$. Entonces $S$ tiene un elemento mínimo. Es decir, existe $n\in S$ tal que $n<m$ para todo $m\in S\setminus\{n\}$.

La prueba del Principio del Buen Orden y más propiedades de $<$ serán estudiadas con mayor detalle en entradas posteriores. Con esto en mente demostramos el teorema de Recursión Débil.

Demostración. Recordemos que por definición, toda función con dominio $A$ y codominio $B$, es un subconjunto de $A\times B$, por lo que una buena idea es analizar el conjunto $\wp(\mathbb{N}\times X)$, definamos

\[\Re:=\{R\in\wp(\mathbb{N}\times X)\mid (0,x_{0})\in R \text{ y si }(n,x)\in R\text{, entonces }(\sigma(n),f(x))\in R\}\]

Esta definición se ve terriblemente complicada. Pero la intuición es clara: $\Re$ tiene a todas las posibles colecciones de parejas de $\mathbb{N}\times X$ que cumplen lo que queremos. El problema es que muchas de ellas no son funciones y tenemos que «arreglar esto».

Probablemente, notarás alguna similitud entre el conjunto $\Re$ y el conjunto de los subconjuntos inductivos (que se menciona en La construcción de los naturales). Siguiendo esta analogía, definiremos $g:=\bigcap \Re$ (podemos hacer esta intersección ya que $\Re$ no es vacío pues $\mathbb{N}\times X$ está en $\Re$).

  • Demostremos que $g\in \Re$:

Por las propiedades de la intersección, tenemos que $g\subset\mathbb{N}\times X$, por lo que $g\in \wp(\mathbb{N}\times X)$. Veamos que $(0,x_{0})\in g$. Sea $R\in\Re$ arbitrario, entonces $(0,x_{0})\in R$, por lo que $(0,x_{0})\in\bigcap \Re=g$. Por último, si $(n,x)\in g$, demostremos que $(\sigma(n),f(x))\in g$, para esto, sea $R\in \Re$ arbitrario, como $(n,x)\in g$, entonces $(n,x)\in R$, por lo que $(\sigma(n),f(x))\in R$. Es decir, $(\sigma(n), f(x))\in\bigcap \Re=g$. Por todo lo anterior, $g\in\Re$.

  • Veamos ahora que $Dom(g)=\mathbb{N}$:

Usemos el quinto axioma de Peano, como $(0,x_{0})\in g$, entonces $0\in Dom(g)$. Supongamos ahora que $n\in Dom(g)$ y demostremos que $\sigma(n)\in Dom(g)$, por la hipótesis de inducción, existe $x\in X$ tal que $(n,x)\in g$, y como $g\in\Re$, tenemos que $(\sigma(n),f(x))\in g$, pero esto quiere decir que $\sigma(n)\in Dom(g)$. Entonces $Dom(g)$ es inductivo, entonces $Dom(g)=\mathbb{N}$.

  • Demostremos ahora que $g$ sí es función. Para esto, tenemos ver que «cada natural se va a un sólo elemento», en símbolos, si $(n,x),(n,y)\in g$ entonces $n=m$

Aquí es donde ocuparemos el Principio del Buen Orden. Consideremos $S:=\{n\in\mathbb{N}\mid (n,x),(n,y)\in g \text{ y } x\neq y \}$. Procedamos por contradicción, supongamos que $S\neq\emptyset$, entonces, $S$ tiene un elemento mínimo, denotémoslo por $n$.

Si $n=0$, entonces existe $x\in X$ tal que $(0,x)\in X$ y $x\neq x_{0}$. Entonces consideremos $g’=g\setminus\{(0,x)\}$. Notemos que $g’\in\Re$, ya que $(0,x_{0})\in g’$, ya que $(0,x_{0})\neq (0,x)$. Además si $(k,a)\in g’$, entonces $(k,a)\in g$, por lo que $(\sigma(k),f(a))\in g$, y como $0$ nunca es el sucesor de otro número, tenemos que $(\sigma(k),f(a))\neq(0,x)$, por lo tanto $(\sigma(k),f(a))\in g’$, es decir, $g’\in \Re$, lo que implica que $g=\bigcap \Re\subset g’=g\setminus\{(0,x)\}$ lo cual es absurdo, por lo que $n\neq 0$.

Como $n\neq 0$, debemos tener que existe $m$ tal que $\sigma(m)=n$ ¿Por qué?. Y como $n$ es el mínimo en $S$, tenemos que $m\not\in S$, es decir, existe un único $x\in X$ tal que $(m,x)\in g$, esto implica que $(\sigma(m),f(x))=(n,f(x))\in g$, y como $n\in S$, debe existir $y\in X$, $y\neq f(x)$ tal que $(n,y)\in g$. Análogamente a como lo hicimos antes, consideremos $g’=g\setminus (n,y)$ y veamos que $g’\in \Re$. Como $(n,y)\neq(0,x_{0})$, tenemos que $(0,x_{0})\in g’$. Más aún, si $(k,a)\in g’$, demostremos que $(\sigma(k),f(a))\in g’$, para esto supongamos que no.

Como $(k,a)\in g’$, tenemos que $(k,a)\in g$, por lo que $(\sigma(k),f(a))\in g$, esto implica que $(\sigma(k),f(a))=(n,y)$ ya que este es el único elemento de $g$ que no está en $g’$. Como $\sigma(k)=n=\sigma(m)$, concluimos, por la inyectividad de $\sigma$, que $k=m$. Esto quiere decir que $(k,a)=(m,a)\in g$, pero recordando que $x$ es el único elemento relacionado con $m$, concluimos que $x=a$, en síntesis, $(k,a)=(m,x)$, por lo que $(\sigma(k),f(a))=(\sigma(m),f(x))=(n,f(x))\neq(n,y)$. Esto implica que $(\sigma(k), f(a))\in g’$, contradiciendo nuestra suposición de que no lo estaba.

Entonces hemos probado que $(0,x_{0})\in g’$ y que cada vez que $(k,a)\in g’$, también lo está $(\sigma(k), f(a))$. Esto quiere decir que $g’\in\Re$, y como lo hicimos anteriormente, tendremos que $g=\bigcap \Re\subset g’=g\setminus\{(n,y)\}$, lo cual es una contradicción. Esto quiere decir, que suponer que $S$ tiene un elemento mínimo, es absurdo, por lo que $S=\emptyset$. Lo que traducido quiere decir que para todo $n\in\mathbb{N}$, existe un único $x\in X$ tal que $(n,x)\in g$. Es decir, que $g$ sí es una función.

  • Demostremos que $g$ satisface las dos propiedades del Teorema.

Ya vimos que $g\in \Re$, por lo que $g(0)=x_{0}$. Sea ahora $n\in \mathbb{N}$ y $x=g(n)$, de nuevo, como $g\in\Re$, tenemos que $g(\sigma(n))=f(x)=f(g(n))$.

  • Por último, demostremos la unicidad de $g$

Si $h:\mathbb{N}\longrightarrow X$ es otra función que satisface las características del Teorema, consideremos $A=\{n\in\mathbb{N}\mid h(n)=g(n)\}$, como $h(0)=x_{0}=g(0)$. Tenemos que $0\in A$. Supongamos que $n\in A$. Tendríamos entonces que $h(\sigma(n))=f(h(n))=f(g(n))=g(\sigma(n))$, es decir que $\sigma(n)\in A$, por lo que $A$ es inductivo, y por consiguiente, $A=\mathbb{N}$. En resumen, $h$ y $g$, coinciden en dominio, codominio y regla de correspondencia, entonces $h=g$, como debíamos probar.

$\square$

La demostración del teorema de Recursión Fuerte requiere de algunos detalles adicionales, pero puede deducirse del teorema de Recursión Débil. Dejamos esto como uno de los problemas de la tarea moral.

Más adelante…

El teorema de Recursión será la mayor herramienta que tendremos para poder darle una forma más familiar a los números naturales, ya que las operaciones de suma y multiplicación, que veremos en la siguiente entrada, tendrán una definición recursiva.

Y así como el teorema de la Recursión nos permitirá definir, usaremos continuamente el principio de Inducción para poder demostrar las numerosas propiedades que estas operaciones tienen.

Tarea moral

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

  1. Demuestra el 5° Axioma de Peano a partir del Principio de Inducción
  2. Demuestra que si $n\neq 0$ entonces existe $m$ tal que $\sigma(m)=n$.
  3. ¿Qué función $g$, satisface que $g(0)=1$ y $g(\sigma(n))=2\cdot g(n)$? ¿Qué función $f$ estamos ocupando?
  4. ¿Qué conjunto y que función nos permitiría definir la sucesión de Fibonacci $a_{n+2}=a_{n+1}+a_{n}$ usando el Teorema de Recursión?
  5. Demuestra el Teorema de Recursión Fuerte, usando el Débil. Sugerencia: Considera, $F(n,x):\mathbb{N}\times X\longrightarrow \mathbb{N}\times X$, como $F(n,x)=(\sigma(n),f_{\sigma(n)}(x))$

Entradas relacionadas

Agradecimientos

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