¿Cómo aplicar el teorema de recursión en la práctica?

Question

El teorema de la recursión

En teoría de conjuntos, se trata de un teorema que garantiza que existen funciones definidas recursivamente. Dado un conjunto $X$ , $a \in X$ y una función $f \colon X \to X$ el teorema afirma que existe una función única $F:\mathbb{N} \to X$ (donde $\mathbb{N}$ denota el conjunto de números naturales incluido el cero) tal que

$$F(0) = a$$

$$F(n + 1) = f(F(n))$$

para cualquier número natural $n$ .

¿Cómo se aplica esto en la práctica? ¿Cómo se aplica, por ejemplo, para demostrar la existencia de la función factorial?

Answer 1

El teorema de la recursión expresa simplemente el hecho de que las definiciones por recursión son válidas desde el punto de vista matemático, es decir, que podemos definir correctamente y con éxito funciones por recursión. Los matemáticos utilizan implícitamente este hecho cada vez que definen una función por recursión.

Una versión más general del Teorema de Recursión permitiría que la función $f$ para utilizar el argumento $n$ así como $F(n)$ . Una versión aún más general del Teorema de la Recursión, llamada recursión de curso de valores, permite $f$ para utilizar como argumento la restricción completa de la función $F\mid n$ a valores anteriores. (Estas versiones más complejas del teorema de la Recursión pueden derivarse únicamente del teorema del valor único que has enunciado, utilizando una función $f$ que toma una función parcial $F\mid n$ (un objeto finito) y devuelve $F\mid (n+1)$ la función parcial con un valor adicional en el dominio).

En el caso de la función factorial, definimos $0!=1$ y $(n+1)!=(n+1)\cdot n!$ . Esto define el factorial de forma recursiva, una vez que se ha definido la mulitplicación. El hecho de que esto defina efectivamente una función se debe al Teorema de la Recursión.

Si se quiere empezar un poco antes, se puede considerar cómo se construye la jerarquía de las funciones recursivas primitivas. Empezando por la función sucesora $s(n)=n+1$ se puede definir la suma por recursión: $a+0=a$ , $a+(n+1)=s(a+n)$ . Entonces se obtiene la multiplicación: $a\cdot 0=0$ , $a\cdot(n+1)=(a\cdot n)+a$ . A continuación, la exponenciación, el factorial, etc., todo de la manera habitual.

Los teóricos de conjuntos tienden a insistir en el teorema de la recursividad en parte debido a la versión del mismo que se aplica a la recursividad transfinita.

Answer 2

En la forma que has indicado, no puedes obtener la función factorial sin un poco de trabajo extra. No obstante, se puede hacer.

Dejemos que $X = \mathbb{N} \times \mathbb{N}$ sea el conjunto de pares ordenados de números naturales. Conjunto $f(x, y) = (x + 1, (x + 1) y)$ . Establecer $F(0) = (0, 1)$ . Entonces, por el teorema de recursión, existe una función $F : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$ tal que $F(n + 1) = f(F(n))$ por cada $n$ . Un argumento de inducción estándar muestra que $F(n) = (n, n!)$ . Dejemos que $p_2 : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ sea el mapa de proyección $p(x, y) = y$ . Entonces $p_2 \circ F : \mathbb{N} \to \mathbb{N}$ es la función factorial que buscas.

Answer 3

Seguimiento: Con la ayuda de mi programa DC Proof, he podido demostrar formalmente que dado un conjunto X y un elemento a en X y una función g: N x X --> X, existe una función f: N --> X tal que

1. f(1)=a

2. Para todo k en N, f(k+1) = g(k+1, f(k))

donde N es el conjunto de números naturales {1, 2, 3... }

Ejemplo: Para la función factorial, tenemos X=N, a=1 y g(x,y) = x*y (multiplicación en N).

1. Factorial(1)=1

2. Para todo k en N, Factorial(k+1) = (k+1) * Factorial(k)

He podido construir f a partir de los conjuntos N y X utilizando únicamente el producto cartesiano, el conjunto de potencias y las reglas de subconjuntos.

Vea la versión HTML en http://www.dcproof.com/recursive.html (669 líneas)

Answer 4

Parece que F(n+1) = f(F(n)) debería haber sido F(n+1)=f _n+1 (F(n)). En el caso de la función factorial, a = 1 y f _n (x) = nx.

Este enfoque no cubre todas las funciones recursivas sobre N. Para los números de Fibonacci de Fibonacci:

 F(0) = F(1) =1

F(n+2) = (n+1) + n = f _n+2 (F(n+1)) + f _n+1 (F(n))

donde f _n (x) = x para cualquier número natural n.