Foros de matemática
10/12/2017, 09:18:37 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Puedes practicar LATEX con el cómodo editor de Latex online
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: ¿Por qué esta relación recursiva?  (Leído 205 veces)
0 Usuarios y 1 Visitante están viendo este tema.
alexpglez
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 73


Ver Perfil
« : 11/08/2017, 11:19:36 pm »

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.
En línea
Carlos Ivorra
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.467


Ver Perfil WWW
« Respuesta #1 : 12/08/2017, 05:16:41 am »

Sí, por el teorema 8.18 podemos suponer que T es demostrablemente recursiva, y si [texx]\mathbb N\vDash T[/texx], esto implica que es recursiva, por lo que la relación "[texx]d[/texx] es una demostración de la fórmula [texx]\alpha[/texx]" es recursiva. Pero [texx]\mathbb N \models \vdash^{(0^{(d)})}_T \phi (0^{(n)})[/texx] es justo esa relación compuesta con la función que a cada [texx]n[/texx] le hace corresponder la fórmula [texx]\phi (0^{(n)})[/texx] (considerada como un número natural), que es claramente recursiva (pues [texx]\phi(x)[/texx] es una fórmula en concreto (es decir, un número natural en concreto), y tanto la función que a [texx]n[/texx] le asigna el numeral [texx]0^{(n)}[/texx] 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.
En línea
alexpglez
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 73


Ver Perfil
« Respuesta #2 : 12/08/2017, 03:23:36 pm »

Muchas gracias
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!