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 fueron estudiados por sus aplicaciones en lógica en la informática y los lenguajes de consulta de bases de datos .
Generalización de cuantificadores de primer orden
Para facilitar la discusión, es necesario explicar algunas convenciones de notación. La expresion
para A una estructura L (o modelo L ) en un lenguaje L , φ una fórmula L , yuna tupla de elementos del dominio dom ( A ) de A . [ aclaración necesaria ] En otras palabras,denota una propiedad ( monádica ) definida en dom (A). En general, donde x se reemplaza por una n -tupla de variables libres, denota una relación n -aria definida en dom ( A ). Cada cuantificadorse relativiza a una estructura, ya que cada cuantificador es visto como una familia de relaciones (entre relaciones) en esa estructura. Para un ejemplo concreto, tome los cuantificadores universal y existencial ∀ y ∃, respectivamente. Sus condiciones de verdad se pueden especificar como
dónde es el singleton cuyo único miembro es dom ( A ), yes el conjunto de todos los subconjuntos no vacíos de dom ( A ) (es decir, el conjunto de potencias 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 denomina 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 como un cuantificador monádico generalizado. 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 cierto en A si el conjunto de cosas que son tales que φ es miembro del conjunto de todos los subconjuntos de dom ( A ) de tamaño 2.
Un cuantificador de Lindström es un cuantificador poliadico generalizado, 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 se define semánticamente como
- [ aclaración necesaria ]
dónde
para una n- tupla de variables.
Los cuantificadores de Lindström se clasifican según la estructura numérica de sus parámetros. Por ejemplo es un cuantificador de tipo (1,1), mientras que 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 |}. [ aclaración necesaria ] Un ejemplo de un cuantificador de tipo (4) es el cuantificador de Henkin .
Jerarquía de expresividad
El primer resultado en esta dirección fue obtenido por Lindström (1966) quien mostró que un cuantificador de tipo (1,1) no era definible 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 , hay un cuantificador de ese tipo que no es definible en lógica de primer orden extendido con cuantificadores que son de tipos menores que t .
Como precursores del teorema de Lindström
Aunque Lindström había desarrollado sólo parcialmente la jerarquía de cuantificadores que ahora llevan su nombre, le bastó observar que algunas propiedades agradables de la lógica de primer orden se pierden cuando se amplía con ciertos cuantificadores generalizados. Por ejemplo, agregar un cuantificador "existen finitos muchos" da como resultado una pérdida de compacidad , mientras que agregar un cuantificador "existen incontables veces" 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 sólido ahora conocido como teorema de Lindström , que establece intuitivamente que la lógica de primer orden es la lógica "más fuerte" que tiene ambas propiedades.
Caracterización algorítmica
Referencias
- 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 Proceedings of the 7th IEEE Symposium on Logic in Computer Science , 1992.
- L. Hella, K. Luosto y J. Vaananen . "El teorema de la 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 hoja , ECCC TR96-005
- Westerståhl, Dag (2001), "Quantifiers", en Goble, Lou (ed.), The Blackwell Guide to Philosophical Logic , Blackwell Publishing, págs. 437–460.
- Antonio Badia (2009). Cuantificadores en acción: cuantificación generalizada en lenguajes de consulta, lógicos y naturales . Saltador. ISBN 978-0-387-09563-9.
Otras lecturas
- Jouko Väänanen (ed.), Computación y cuantificadores generalizados. IX Escuela de Verano Europea en Lógica, Lenguaje e Información. Taller ESSLLI'97. Aix-en-Provence, Francia, 11 al 22 de agosto de 1997. Conferencias revisadas , Springer Lecture Notes in Computer Science 1754, ISBN 3-540-66993-0
enlaces externos
- Dag Westerståhl, 2011. ' Cuantificadores generalizados '. Enciclopedia de Filosofía de Stanford .