cuantificador de Lindström

En lógica matemática , un cuantificador de Lindström es un cuantificador poliádico generalizado . Los cuantificadores de Lindström generalizan los cuantificadores de primer orden, como el cuantificador existencial , el cuantificador universal y los cuantificadores de conteo . Fueron introducidos por Per Lindström en 1966. Posteriormente, se estudiaron sus aplicaciones en lógica aplicada a la informática y en lenguajes de consulta de bases de datos .

Para facilitar la discusión, es necesario explicar algunas convenciones de notación. La expresión

${\displaystyle \phi ^{A,x,{\bar {a}}}=\{x\in A\colon A\models \phi [x,{\bar {a}}]\}}$

para A una L -estructura (o L -modelo) en un lenguaje L , φ una L -fórmula, y${\displaystyle {\bar {a}}}$una tupla de elementos del dominio dom( A ) de A. En otras palabras , ${\displaystyle \phi ^{A,x,{\bar {a}}}}$denota una propiedad ( monádica ) definida en dom(A). En general, donde x se reemplaza por una n -tupla${\displaystyle {\bar {x}}}$de variables libres,${\displaystyle \phi ^{A,{\bar {x}},{\bar {a}}}}$denota una relación n -aria definida en dom( A ). Cada cuantificador${\displaystyle Q_{A}}$se relativiza a una estructura, ya que cada cuantificador se considera una familia de relaciones (entre relaciones) en esa estructura. Como ejemplo concreto, tomemos los cuantificadores universal y existencial ∀ y ∃ , respectivamente. Sus condiciones de verdad se pueden especificar como

${\displaystyle A\models \forall x\phi [x,{\bar {a}}]\iff \phi ^{A,x,{\bar {a}}}\in \forall _{A}}$

${\displaystyle A\models \exists x\phi [x,{\bar {a}}]\iff \phi ^{A,x,{\bar {a}}}\in \exists _{A},}$

dónde${\displaystyle \forall _{A}}$es el singleton cuyo único miembro es dom( A ), y${\displaystyle \exists _{A}}$es el conjunto de todos los subconjuntos no vacíos de dom( A ) (es decir, el conjunto potencia de dom( A ) menos el conjunto vacío ). En otras palabras, cada cuantificador es una familia de propiedades en dom( A ), por lo que cada uno se llama cuantificador monádico . Cualquier cuantificador definido como una relación n  >  0-aria entre propiedades en dom( A ) se llama monádico . Lindström introdujo los poliádicos, que son relaciones n  >  0-arias entre relaciones en dominios de estructuras.

Antes de pasar a la generalización de Lindström, observe que cualquier familia de propiedades en dom( A ) puede considerarse un cuantificador generalizado monádico. Por ejemplo, el cuantificador "hay exactamente n cosas tales que..." es una familia de subconjuntos del dominio de una estructura, cada uno de los cuales tiene una cardinalidad de tamaño n . Entonces, "hay exactamente 2 cosas tales que φ " es verdadero en A si y solo si el conjunto de cosas tales que φ es un miembro del conjunto de todos los subconjuntos de dom( A ) de tamaño 2.  

Un cuantificador de Lindström es un cuantificador generalizado poliádico, por lo que en lugar de ser una relación entre subconjuntos del dominio, es una relación entre relaciones definidas en el dominio. Por ejemplo, el cuantificador${\displaystyle Q_{A}x_{1}x_{2}y_{1}z_{1}z_{2}z_{3}(\phi (x_{1}x_{2}),\psi (y_{1}),\theta (z_{1}z_{2}z_{3}))}$se define semánticamente como

${\displaystyle A\models Q_{A}x_{1}x_{2}y_{1}z_{1}z_{2}z_{3}(\phi ,\psi ,\theta )[a]\iff (\phi ^{A,x_{1}x_{2},{\bar {a}}},\psi ^{A,y_{1},{\bar {a}}},\theta ^{A,z_{1}z_{2}z_{3},{\bar {a}}})\in Q_{A}}$

dónde

${\displaystyle \phi ^{A,{\bar {x}},{\bar {a}}}=\{(x_{1},\dots ,x_{n})\in A^{n}\colon A\models \phi [{\bar {x}},{\bar {a}}]\}}$

para una n -tupla${\displaystyle {\bar {x}}}$de variables.

Los cuantificadores de Lindström se clasifican según la estructura numérica de sus parámetros. Por ejemplo:${\displaystyle Qxy\phi (x)\psi (y)}$es un cuantificador de tipo (1,1), mientras que${\displaystyle Qxy\phi (x,y)}$es un cuantificador de tipo (2). Un ejemplo de cuantificador de tipo (1,1) es el cuantificador de Hartig que prueba la equicardinalidad, es decir, la extensión de {A, B ⊆ M: |A| = |B|}. Un ejemplo de cuantificador de tipo (4) es el cuantificador de Henkin .

El primer resultado en esta dirección lo obtuvo Lindström (1966), quien demostró que un cuantificador de tipo (1,1) no se podía definir en términos de un cuantificador de tipo (1). Después de que Lauri Hella (1989) desarrollara una técnica general para probar la expresividad relativa de los cuantificadores, la jerarquía resultante resultó estar ordenada lexicográficamente por tipo de cuantificador:

(1) < (1, 1) < . . . < (2) < (2, 1) < (2, 1, 1) < . . . < (2, 2) < . . . (3) < . . .

Para cada tipo t , existe un cuantificador de ese tipo que no se puede definir en lógica de primer orden extendida con cuantificadores que son de tipos menores que t .

Aunque Lindström solo había desarrollado parcialmente la jerarquía de cuantificadores que ahora llevan su nombre, le bastó con observar que algunas propiedades interesantes de la lógica de primer orden se pierden al extenderla con ciertos cuantificadores generalizados. Por ejemplo, añadir un cuantificador del tipo "existen un número finito de elementos" conlleva una pérdida de compacidad , mientras que añadir un cuantificador del tipo "existen un número incontable de elementos" a la lógica de primer orden da como resultado una lógica que ya no satisface el teorema de Löwenheim-Skolem . En 1969, Lindström demostró un resultado mucho más contundente, conocido como el teorema de Lindström , que afirma intuitivamente que la lógica de primer orden es la lógica "más fuerte" que posee ambas propiedades.

• Lindstrom, P. (1966). "Lógica de predicados de primer orden con cuantificadores generalizados". Theoria . 32 (3): 186– 195. doi : 10.1111/j.1755-2567.1966.tb00600.x .
• L. Hella. "Jerarquías de definibilidad de cuantificadores generalizados", Annals of Pure and Applied Logic , 43(3):235–271, 1989, doi : 10.1016/0168-0072(89)90070-5 .
• L. Hella. "Jerarquías lógicas en PTIME". En Actas del 7º Simposio IEEE sobre Lógica en Ciencias de la Computación , 1992.
• L. Hella, K. Luosto y J. Vaananen . "El teorema de jerarquía para cuantificadores generalizados". Journal of Symbolic Logic , 61(3):802–817, 1996.
• Burtschick, Hans-Jörg; Vollmer, Heribert (1999), Cuantificadores de Lindström y definibilidad del lenguaje de hojas , ECCC TR96-005 
• Westerståhl, Dag (2001), "Cuantificadores", en Goble, Lou (ed.), The Blackwell Guide to Philosophical Logic , Blackwell Publishing, pp . 437–460 .
• Antonio Badia (2009). Cuantificadores en acción: Cuantificación generalizada en lenguajes de consulta, lógicos y naturales . Springer. ISBN 978-0-387-09563-9.

• Jouko Väänanen (ed.), Cuantificadores generalizados y computación. IX Escuela Europea de Verano en Lógica, Lenguaje e Información. Taller ESSLLI'97. Aix-en-Provence, Francia, 11-22 de agosto de 1997. Conferencias revisadas , Springer Lecture Notes in Computer Science 1754, ISBN 3-540-66993-0

• Dag Westerståhl, 2011. ' Cuantificadores generalizados '. Enciclopedia de filosofía de Stanford .