Autor Tema: Teorema de Corrección

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

26 Febrero, 2023, 09:52 pm
Leído 990 veces

josel_bahia

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 8
  • País: ar
  • Karma: +0/-0
Hola a todos.
Estoy con el Teorema de Corrección de la Lógica de Primer Orden (es la ida del Teorema de Completitud), y debo demostrar que los axiomas que usamos en la Sintaxis son válidos en cualquier modelo. Tengo problemas en probarlo con los siguientes axiomas:
a) \(  (\forall x) \mathcal{A}(x) \rightarrow \mathcal{A}(t)  \), si \( t \) es libre para \( x \) en \( \mathcal{A}(x) \)
b) \(  x=y \rightarrow (\mathcal{A} \rightarrow \mathcal{A'})  \), si \( y \) es libre para \( x \) en \( \mathcal{A} \) y \( \mathcal{A'} \) se obtiene a partir de \( \mathcal{A} \) reemplazando alguna ocurrencia libre de \( x \) por \( y \)

Agradezco la ayuda

26 Febrero, 2023, 10:20 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Estoy con el Teorema de Corrección de la Lógica de Primer Orden (es la ida del Teorema de Completitud), y debo demostrar que los axiomas que usamos en la Sintaxis son válidos en cualquier modelo. Tengo problemas en probarlo con los siguientes axiomas:
a) \(  (\forall x) \mathcal{A}(x) \rightarrow \mathcal{A}(t)  \), si \( t \) es libre para \( x \) en \( \mathcal{A}(x) \)
b) \(  x=y \rightarrow (\mathcal{A} \rightarrow \mathcal{A'})  \), si \( y \) es libre para \( x \) en \( \mathcal{A} \) y \( \mathcal{A'} \) se obtiene a partir de \( \mathcal{A} \) reemplazando alguna ocurrencia libre de \( x \) por \( y \)

Los detalles dependerán de las definiciones concretas que manejes y de los resultados que tengas demostrados. Para el primero, si \( M \) es un modelo del lenguaje formal considerado, para probar que

\( M\vDash  (\forall x) \mathcal{A}(x) \rightarrow \mathcal{A}(t) \)

tendrás que tomar una valoración \( v \) (que asigne a cada variable un objeto del universo de \( M \)) y probar que

\( M\vDash ( (\forall x) \mathcal{A}(x) \rightarrow \mathcal{A}(t))[v] \)

No sé si usarás esta notación. Me refiero a que implicación debe cumplirse cuando las variables se interpretan según \( v \).

Para ello tienes que suponer

\( M\vDash (\forall x) \mathcal{A}(x)[v] \)

y demostrar

\( M\vDash \mathcal{A}(t)[v] \).

La hipótesis es que, para todo objeto \( a \) en el universo de \( M \), se cumple \( M\vDash  \mathcal{A}(x) [v_x^a] \), donde \( v_x^a \) es la valoración que coincide con \( v \) salvo que interpreta \( x \) como \( a \).

Aplica esto al caso en que \( a \) es el objeto denotado por \( t \) en \( M \). En tal caso,

\( M\vDash  \mathcal{A}(x) [v_x^a] \)

es equivalente a

\( M\vDash \mathcal{A}(t)[v] \).

Eso es la interpretación semántica de la sustitución de una variable por un término en una fórmula: \( \mathcal A(t) \) se satisface en un modelo respecto de una valoración \( v \) si y sólo si \( \mathcal A(x) \) se satisface respecto de \( v_x^a \). Si no es un resultado que tengas demostrado previamente, tendrías que demostrarlo (por inducción sobre la longitud de \( \mathcal A \)). La prueba dependerá de la forma en concreto como te hayan definido la sustitución.