Semantica de primer orden

Sintaxis y sem´ntica para un lenguaje de primer orden a
Federico Marulanda Instituto de Investigaciones Filos´ficas, UMSNH o Noviembre 2010

1

Anotaciones y definiciones preliminares

En lo que sigue, suponemos que se entiende por qu´ es necesario en ciertos contextos emplear e las semicomillas (tambi´n conocidas como esquinas, o comillas de Quine), y que se entiende su e funcionamiento. Sesupondr´ tambi´n un conociemiento b´sico de la teor´ de conjuntos y su a e a ıa notaci´n est´ndar. No obstante, para clarificar, introduciremos algunas definiciones conjuntistas o a utiles. ´ Definici´n Una secuencia de longitud n es un n-tuple ordenado, r1 , . . . , rn . Un n-tuple ordeo nado cumple con las siguientes condiciones: 1. Los elementos que lo constituyen se suceden en un ordendeterminado. 2. Puede contener el mismo elemento varias veces. La primera condici´n es garantizada por la regla que gobierna la identidad de dos n-tuples: o r1 , . . . , rn = q1 , . . . , qn s´ y s´lo s´ (syss) ri = qi para i = 1, . . . , n. Los n-tuples pueden ser ı o ı representados en la teor´ de conjuntos de varias maneras. Una de ellas es la siguiente definici´n ıa o recursiva: 1. El 0-tuple (el tuplevac´ es el conjunto vac´ ∅. ıo) ıo, 2. Si r es un objeto cualquiera, el 1-tuple r = {r}. 3. Si r1 y r2 son dos objetos cualquiera, el 2-tuple o par ordenado r1 , r2 = {{r1 }, {r1 , r2 }} 4. Para todo n > 1, si x es un n-tuple y r es un objeto cualquiera, entonces x, r = {{x}, {x, r}} es un (n + 1)-tuple. As´ un n-tuple r1 , . . . , rn puede ser visto como el par ordenado ı, Definici´n o como r1 , .. . , rn−1 , rn .

Si X1 , X2 , . . . , Xn son conjuntos, el producto cartesiano de X1 , X2 , . . . , Xn , denotado X1 × X2 × . . . × Xn

es el conjunto de todos los n-tuples en los cuales el primer elemento es un miembro de X1 , el segundo elemento es un miembro de X2 , . . ., y el n-avo elemento es un miembro de Xn . Formalmente, para todo x, x ∈ X1 × . . . × Xn syss existen x1 , . . . , xntales que x = x1 , . . . , xn y x1 ∈ X1 , . . . , xn ∈ Xn . 1

Ejemplos {1, 2} × {0, 1, 2} = { 1, 0 , 1, 1 , 1, 2 , 2, 0 , 2, 1 , 2, 2 } {1, 2} × {1, 2} × {2, 3} = { 1, 1, 2 , 1, 1, 3 , 1, 2, 2 , 1, 2, 3 , 2, 1, 2 , 2, 1, 3 , 2, 2, 2 , 2, 2, 3 } Notaci´n o por El producto cartesiano de un conjunto X con si mismo tomado n veces es denotado Xn X n es el conjunto consistente de todos los n-tuplesde elementos de X (por convenci´n ponemos o X 1 = X). Por ejemplo, X 2 = X × X es el conjunto de todos los pares ordenados de elementos de X.

2

Sintaxis: el lenguaje L1
p x a f P ∗ ¬ → ∀ ( )

Los s´ ımbolos de L1 , con los cuales se construyen todas las expresiones del lenguaje, son:

Daremos los siguientes nombres a ciertas combinaciones de los anteriores s´ ımbolos: • Letras deenunciado: ‘p ’, ‘p ’, ‘p ’, . . . • Variables individuales: ‘x ’, ‘x ’, ‘x ’, . . . • Constantes individuales: ‘a ’, ‘a ’, ‘a ’, . . . • S´ ımbolos de predicado: ‘P ∗ ’, ‘P ∗ ’, ‘P ∗ ’, . . . , ‘P ∗∗ ’, ‘P ∗∗ ’, ‘P ∗∗ ’, . . . , ‘P ∗∗∗ ’, ‘P ∗∗∗ ’, ‘P ∗∗∗ ’, . . . Un s´ ımbolo de predicado con n asteriscos es un s´ ımbolo de predicado n-ario. • S´ ımbolos de funci´n: ‘f ∗ ’, ‘f ∗ ’, ‘f ∗ ’, . . . , ‘f∗∗ ’, ‘f ∗∗ ’, ‘f ∗∗ ’, . . . , ‘f ∗∗∗ ’, ‘f ∗∗∗ ’, ‘f ∗∗∗ ’, o ... Un s´ ımbolo de funci´n con n asteriscos es un s´ o ımbolo de funci´n de n argumentos o s´ o ımbolo de funci´n n-aria. o • Conectivas o constantes l´gicas (respectivamente: negador, condicional ): ‘¬’, ‘→’ o • Cuantificador universal : ‘∀’ • Par´ntesis: ‘(’, ‘)’ e El lenguaje L1 no contiene s´ ımbolos para algunas conectivasusuales (conjunci´n, disyunci´n, bio o condicional) ni para el cuantificador existencial pues estos operadores pueden ser definidos a partir de la negaci´n, el condicional y el cuantificador universal. Sin embargo, si la legibilidad lo exigiera, o puede acudirse a las siguientes

2

Abreviaciones

Donde A y B son f´rmulas de L1 y v es una variable de L1 , o

1. A ∧ B es una abreviaci´n de ¬(A →...