Dos estilos de la semántica de primer orden lenguaje: ¿qué elegir?

Question

Los clásicos de la semántica de FOL se presenta en dos estilos. La supresión de detalles irrelevantes para el título de la pregunta, supongamos que el $L$-wff $\varphi(x)$ sólo ha $x$ libre, y deje $I$ se fija una interpretación de la lógica del vocabulario de $L$. A continuación, una historia que viene a este:

$\exists x\varphi x$ que es verdad en la interpretación $I$ si, para algunos de asignación de $s$ de un objeto en el dominio como el valor a $x$, $\varphi x$ es cierto en $I + s$.

La otra historia viene a este:

$\exists x\varphi x$ que es verdad en la interpretación $I$, si para algunos el nombre de $c$ en $L^+$ -- $L$ aumentada con un nombre para cada objeto en el dominio -- $\varphi c$ que es verdad en $I^+$ (la interpretación $I$ aumentada con las interpretaciones de todos los nuevos nombres).

O seguimos $L$ fijo, y girar los objetos asignados a las variables; o incrementamos $L$ con un nombre fijo para cada objeto. En la cara de ella no es poco (o nada?) para elegir. Diferentes textos estándar, ir en diferentes maneras. Pero hay sutiles techie o conceptual de las razones para preferir una línea a la otra?

[Hubo alguna discusión entre algunos de los filósofos más de 35 años, acerca de Tarskian vs Fregean estilos de la semántica: pero estoy interesado aquí en los puntos de vista de los matemáticos y científicos de la computación!).]

Answer 1

Algunas observaciones aleatorias a partir de (lo siento, no lo que usted solicitó) un equipo de la perspectiva de la ciencia:

El dichotomoy está estrechamente paralelo a una elección que se debe hacer a la hora de definir la semántica de los lenguajes de programación. Uno puede llevar alrededor de un entorno que asigna los nombres de las variables a los valores que actualmente están vinculadas, o aplicar ligaduras de variables mediante la sustitución de algunos sintáctico de la representación de los valores en la expresión en el ámbito de la unión operador.

Ambos estilos se encuentran en el equipo de la ciencia de la literatura, pero la primera (con el medio ambiente) parece ser el más popular por varias razones. O tal vez yo soy parcial; yo prefiero entorno basado en la semántica.

El principal atractivo de la sustitución basado en la semántica es que parece técnicamente más sencilla, porque depende de la maquinaria (por sustitución, etc) que por lo general uno tiene que desarrollar de todos modos con el fin de apoyar sintáctica razonamiento acerca de los programas y fragmentos de programa. Es también más cerca de la concepción clásica del cálculo lambda como puramente sintáctica de reescritura del sistema.

Por otro lado, también depende de tener una representación sintáctica para cada posible valor. Esto desdibuja la distinción entre sintaxis y semántica (en su lógica de configuración se siente poco elegante a tener que dejar incluso el idioma que trabajar con variar según el dominio de la interpretación; que hace es extraño si en el mismo aliento que usted necesita para comparar las diferentes interpretaciones de la misma lengua). Por otra parte, en una de lenguajes de programación contexto, a menudo se desea razón acerca de las propiedades que dependen fundamentalmente en el hecho de que algunos valores posibles no puede ser escrito como cerrado términos, que está en conflicto directo con lo que uno necesita para una sustitución basado en la semántica. Que problema puede ser solucionado con la suficiente técnica fiddlework, por supuesto, pero que realmente no se ven bien.

El medio ambiente basado en la semántica no tiene estos problemas, y provee una clara ruptura entre la sintaxis de las fórmulas y su semántica.

El medio ambiente basado en la semántica también tiene la ventaja de ser estrictamente compositivo en el que el significado de una expresión depende únicamente del significado de sus partes en lugar de en su sintaxis -- el significado de ser un mapeo de entornos (valores, acciones, valores de verdad, lo que sea) que puede ser cosificado como razonablemente natural semántica de objetos en el nivel meta.

Para alguien que viene al formalismo de un fondo de programación, el medio ambiente basado en la semántica se siente más cerca de lo que "realmente sucede" con una expresión que contiene las variables (véase también el de Brian comentario). Por otro lado, la sustitución parece ser la manera en que las variables se explica generalmente en la escuela primaria de matemáticas de la educación.

En cada caso, el hecho de que también se puede hacer de otra manera con resultados equivalentes, por supuesto, una relevante e interesante propiedad que merece la prueba y la discusión.

Answer 2

El enfoque que procede a través de un largo idioma a veces es más elegante. Con la otra variable de la interpretación de la función de" enfoque, no es cierto que una fórmula es verdadera o falsa en una estructura, sino que uno tiene que hablar de la verdad en una estructura en relación a una variable de interpretación. Uno tiene que probar por separado como teorema de que dos variables interpretaciones que de acuerdo a las variables libres de una fórmula de darle el mismo valor de verdad, y por lo tanto la verdad de una oración en una estructura es independiente de la variable de interpretación. Sin embargo, para comprobar la verdad de una oración, debemos comenzar con algunos arbitraria variable de interpretación. Que separan teorema, la necesidad de elegir una asignación arbitraria que no afecta en nada, y los métodos de representación de las complicaciones de la variable interpretación funciones son completamente eliminados con la aumentada enfoque de lenguaje.

También, la definición de la variable de interpretación de las funciones de falla por vacío estructuras (es decir, vacío de dominio de discurso), que no tienen ninguna variable de interpretación de funciones. A la luz del teorema mencionado antes, podemos definir una frase, por cierto en una estructura cuando está satisfecho por cada una de las variables de interpretación, pero, a continuación, cada frase es verdadera en el modelo vacío. Si decimos que un enunciado es verdadero cuando es satisfecho por alguna variable de interpretación, entonces no hay enunciado es verdadero. De cualquier manera, la semántica a través de la variable de interpretación funciones descompone en vacío estructuras. Por el contrario, la aumentada de la versión de idioma trata a los cuantificadores más disquotationally y no tiene ningún problema con el vacío de las estructuras.

El principal inconveniente de la aumentada de la versión de idioma es que los abusos de los ingenuos significado de "lenguaje". Cuando una estructura es incontable, aumentada su lenguaje también es incontable. Que no causa problemas matemáticos si tratamos el idioma de manera abstracta, pero si creemos que un aspecto clave de un lenguaje formal es que podemos escribir cada frase con un número finito de símbolos de un alfabeto finito, luego de incontables idiomas no son buenas.