Rincón Matemático
Matemática => Lógica, Conjuntos, Lenguajes Formales => Lógica => Mensaje iniciado por: alexpglez en 12 Agosto, 2017, 04:19 am
-
Para la demostración de que en una teoría semirrecursiva sobre L_a, tal que el modelo natural sea un modelo para tal teoría, tenga una sentencia verdadera en el modelo natural y no demostrable, se usa una relación:
[texx] R (n,d) [/texx] syss [texx] N \models \vdash^{(0^{(d)})}_T \phi (0^{(n)}) [/texx]
Carlos Ivorra, Lógica, pag 300.
Diciéndose que es recursiva, y la razón creo que está relacionada con que para todo n natural [texx] \vdash_T \phi(0^{(n)}) [/texx] o se refutaba la fórmula, y que la teoría es semirrecursiva. Debido a eso creo que se puede escribir un algoritmo y por lo tanto R es recursiva.
¿Cuál algoritmo sería?
Por otra parte, recién escrito el mensaje, me doy cuenta de un teorema anterior, que dice que toda teoría semirrecursiva es equivalente a uno demostrablemente recursivo. No sé si esto se puede utilizar como parte de la prueba, utilizando que "demostrar en T" es recursivo.
-
Sí, por el teorema 8.18 podemos suponer que T es demostrablemente recursiva, y si \( \mathbb N\vDash T \), esto implica que es recursiva, por lo que la relación "\( d \) es una demostración de la fórmula \( \alpha \)" es recursiva. Pero \( \mathbb N \models \vdash^{(0^{(d)})}_T \phi (0^{(n)}) \) es justo esa relación compuesta con la función que a cada \( n \) le hace corresponder la fórmula \( \phi (0^{(n)}) \) (considerada como un número natural), que es claramente recursiva (pues \( \phi(x) \) es una fórmula en concreto (es decir, un número natural en concreto), y tanto la función que a \( n \) le asigna el numeral \( 0^{(n)} \) como la sustitución de una variable por un término en una fórmula son funciones recursivas).
De todos modos, voy a aclarar en el libro el hecho de que podemos suponer que T es recursiva.
-
Muchas gracias