Autor Tema: ¿Por qué esta relación recursiva?

0 Usuarios y 1 Visitante están viendo este tema.

12 Agosto, 2017, 04:19 am
Leído 945 veces

alexpglez

  • Novato
  • Mensajes: 119
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
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.

12 Agosto, 2017, 10:16 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 9,060
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
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.

12 Agosto, 2017, 08:23 pm
Respuesta #2

alexpglez

  • Novato
  • Mensajes: 119
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino