¿Realmente necesitamos el teorema de recursión si tratamos sólo con funciones específicas recursivamente definida?

Question

¿Cómo es posible definir de una forma totalmente rigurosa (es decir, a partir de los axiomas) fue de las funciones $$h:\mathbb{N}\rightarrow \mathbb{N}, \ n\mapsto 1\cdot\ldots \cdot n$$ or $$ g:\mathbb{N}\rightarrow \mathbb{R}, \ n\mapsto x^n \ $$

sin usar el teorema de recursión , que de inmediato nos dice que estas funciones existen y son únicos ?

De manera diferente, dijo: ¿realmente necesitamos una declaración general como el teorema de recursión para demostrar que estas dos funciones específicas existen y son únicos ? No hay una manera más fácil la prueba sólo para estas dos funciones (estoy pensando de alguna manera la construcción de los conjuntos de estas funciones corresponden directamente de $\mathbb{N}$ $\mathbb{R}$ a través de los axiomas de ZFC, sin recurrir al teorema de recursión. Mi enfoque ingenuo - nunca he tenido un curso en teoría de conjuntos, por lo que no sé si esto es correcto - sería, por ejemplo, para la segunda función, para construir el conjunto de $$ \{ (n,r)\in\mathbb{N}\times \mathbb{R} \mid r=x^n \},$$ where $x \in \mathbb{R}$ is some fixed number, via the "axiom schema of separation", which gives me my function $g$, ya que es su gráfica)

Lado de la pregunta: hasta donde yo tengo entendido el teorema de recursión, la importante declaración que hace es que estas funciones son únicas (puesto que la existencia me parece ya ser "dado", ya que uno siempre puede definir (usando la terminología de la Wikipedia) una función de $F(n):= (f\circ \ldots \circ f)(n)$, donde la composición fue tomada $n$ veces, aunque de nuevo, yo realmente no se que axiomas me deja hacerlo, ya que esto es sólo mi intuición).

Answer 1

Usted está en lo correcto, sin duda, que demuestren la existencia de la función es (casi trivialmente) equivalente a mostrar la existencia de la relación, pero ¿qué proponen para definir la relación '$r=x^n$' (podemos incluso suponer $r$ $x$ enteros aquí - el problema todavía no es fácil!) en la no-recursiva de la moda? Un excelente ejercicio (que me encontró por primera vez en Hofstadter del Gödel, Escher, Bach) es caracterizar el predicado '$n$ es una potencia de $2$' en explícito de la moda - tenga en cuenta que 'explícita' aquí significa sin el uso de la recursividad o iteración (que es, para estos fines, la recursividad en disfraz)! Si eres capaz de conseguir que uno, puede probar con el predicado '$n$ es una potencia de $10$' - que debe recorrer un largo camino hacia mostrando cuán poderosa es el teorema de recursión es como una herramienta.

En general, me gustaría mucho cuidado con el uso de 'intuición' para comprender estos conceptos, porque la lógica y la axiomatics son un área donde su intuición puede llevar fuertemente a la perdición (por ejemplo, ver el Axioma de Elección) y donde los argumentos formales son una necesidad. De hecho, probablemente sería útil sólo para encontrar el apropiado manera formal para demostrar la existencia de estas funciones con el teorema de recursión: en su forma más útil aquí el teorema formalmente indica que, para cualquier número $a$ y la función $f(x):\mathbb{N}\to\mathbb{N}$ hay una función de $F(x):\mathbb{N}\to\mathbb{N}$$F(0) = a$$F(n+1) = f(F(n))$.

Para entender lo que puede salir mal, puede ser digno de la comprensión de cómo el teorema de recursión puede fallar: imaginar un sistema abstracto donde nuestra noción de 'número' sigue siendo el mismo, y nos ha dado las operaciones básicas de la aritmética de la suma y la multiplicación, pero la noción de función se limita a exponencialmente delimitada funciones: para cada función $f$ existen constantes $k$ $C$ tal que para todo $n$, $|f(n)| \le \left|n\right|^k+C$ . Entonces podemos sumar y multiplicar estas funciones y aún así obtener totalmente legítimo, funciones, e incluso podemos componer estas funciones para obtener funciones legítimas: si $f(n)$ $g(n)$ son exponencialmente acotada, entonces la función de $h$ definido por $h(n) = f(g(n))$ es exponencialmente limitada. Pero el recurion teorema (en la forma que me dio) falla en este establecimiento se puede ver por qué?