Estaba leyendo algo que contenía la siguiente declaración:
Es un resultado matemático bien establecido que las teorías que consisten sólo en definiciones recursivas... son inherentemente consistentes.
¿Tiene nombre este resultado? ¿Podría alguien indicarme bibliografía al respecto?
No es cierto en el sentido más general, pero sí en cierto sentido.
Una forma de que sea cierto en el sentido del teorema de Knaster-Tarski:
Si $L$ es una red completa y $\phi\colon L \to L$ es una función que preserva el orden, entonces el conjunto de puntos fijos de $\phi$ es una subred completa de $L$ y, en particular, el conjunto de puntos fijos en no vacío.
Muchas construcciones recursivas corresponden a mapas que conservan el orden en una red completa, por lo que, según este teorema, las construcciones tienen puntos fijos. Esos puntos fijos corresponden a lo que la definición recursiva intenta construir.
Por ejemplo, para construir los conjuntos de Borel en un espacio topológico $X$ consideremos la red de todos los conjuntos de subconjuntos de $X$ . Se trata de una red de conjuntos de potencias, por lo que es completa. Sea $\phi$ sea el siguiente operador: dada una familia $F$ , $\phi(F)$ contiene todos los conjuntos que pueden obtenerse como unión contable de conjuntos de $F \cup F^c \cup O$ donde $F^c$ es el conjunto de complementos de conjuntos en $F$ y $O$ es el conjunto de conjuntos abiertos en $X$ . Entonces $\phi$ es un operador preservador del orden, y su punto fijo mínimo es la familia de conjuntos de Borel de $X$ .
Aquí hay un sentido en el que las definiciones recursivas no siempre definen algo. Está relacionado con el campo de las "funciones recursivas generales", que fue una de las primeras formas de estudiar la computabilidad. Supongamos que escribimos un conjunto de definiciones recursivas para una función: $$ f(0) = 5 \qquad f(x+1) = 2f(x)+x $$ Esta definición concreta define una función total $\mathbb{N} \to \mathbb{N}$ . Pero en general no hay razón para esperar que un conjunto arbitrario de normas funcione. Por ejemplo, $$ f(0) = 1 \qquad f(3x) = x + 2 \qquad f(x+1) = 2 $$ no define una función. La cuestión aquí es que estamos considerando definiciones arbitrarias, no sólo definiciones en la forma del primer ejemplo.
He aquí un ejemplo basado en la conjetura de Collatz; ¿da una función total? $$ f(0) = 0 \qquad f(1) = 1 \qquad f(2x) = f(x) \qquad f(2x+1) = f(6x+4)$$
Como puede ver, el problema de saber qué conjuntos de reglas definen realmente una función total no es nada sencillo, y sólo empeora si tiene un sistema de varias funciones definidas recursivamente entre sí.
Hay un tercer aspecto del problema, relacionado con la importancia fundacional de las definiciones inductivas. Por ejemplo, en las matemáticas no formalizadas, los números naturales son el conjunto más pequeño de objetos que contiene 0 y es cerrado bajo sucesión. Este tipo de definición inductiva concreta es una de las razones por las que la gente suele pensar que los números naturales son más directamente accesibles a la intuición que, por ejemplo, los conjuntos arbitrarios incontables.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
