En lógica, un cuantificador de ramificación , [1] también llamado cuantificador de Henkin , cuantificador finito parcialmente ordenado o incluso cuantificador no lineal , es un ordenamiento parcial [2]
de cuantificadores para Q ∈ {∀, ∃}. Es un caso especial de cuantificador generalizado . En la lógica clásica , los prefijos de cuantificador están ordenados linealmente de modo que el valor de una variable y m limitada por un cuantificador Q m depende del valor de las variables
- y 1 , ..., y m −1
ligado por cuantificadores
- Qy 1 , ..., Qy m −1
precedente a Q m . En una lógica con cuantificación (finita) parcialmente ordenada, este no es el caso en general.
La cuantificación de ramificaciones apareció por primera vez en un artículo de la conferencia de 1959 de Leon Henkin . [3] Los sistemas de cuantificación parcialmente ordenada tienen una fuerza intermedia entre la lógica de primer orden y la lógica de segundo orden . Se están utilizando como base para la lógica favorable a la independencia de Hintikka y Gabriel Sandu .
Definición y propiedades
El cuantificador de Henkin más simple es
(De hecho, cada fórmula con un prefijo de Henkin, no solo la más simple) es equivalente a su Skolemización de segundo orden , es decir
También es lo suficientemente potente como para definir el cuantificador. (es decir, "hay infinitos") definido como
Varias cosas se siguen de esto, incluida la no xomatizabilidad de la lógica de primer orden con (observado por primera vez por Ehrenfeucht ), y su equivalencia con el-fragmento de lógica de segundo orden ( lógica existencial de segundo orden ) - este último resultado publicado de forma independiente en 1970 por Herbert Enderton [4] y W. Walkoe. [5]
Los siguientes cuantificadores también se pueden definir mediante . [2]
- Rescher: "El número de φ s es menor o igual que el número de ψ s"
- Härtig: "Las φ s son equinumerables con las ψ s"
- Chang: "El número de φ s es equivalente al dominio del modelo"
El cuantificador de Henkin puede expresarse en sí mismo como un cuantificador de tipo (4) Lindström . [2]
Relación con los lenguajes naturales
Hintikka en un artículo de 1973 [6] adelantó la hipótesis de que algunas oraciones en lenguajes naturales se entienden mejor en términos de cuantificadores ramificados, por ejemplo: "algún pariente de cada aldeano y algún pariente de cada ciudadano se odian" se supone que debe interpretarse , según Hintikka, como: [7] [8]
que se sabe que no tiene equivalente lógico de primer orden. [7]
La idea de ramificación no se limita necesariamente a utilizar los cuantificadores clásicos como hojas. En un artículo de 1979, [9] Jon Barwise propuso variaciones de las oraciones Hintikka (como a veces se llama lo anterior) en las que los cuantificadores internos son cuantificadores generalizados , por ejemplo: "La mayoría de los aldeanos y la mayoría de los habitantes se odian entre sí". [7] Observando que no está cerrado bajo la negación, Barwise también propuso una prueba práctica para determinar si las oraciones del lenguaje natural realmente involucran cuantificadores ramificados, es decir, para probar si su negación del lenguaje natural implica una cuantificación universal sobre una variable de conjunto (un oración). [10]
La propuesta de Hintikka fue recibida con escepticismo por varios lógicos porque algunas oraciones de primer orden como la que se muestra a continuación parecen capturar bastante bien la oración de Hintikka en lenguaje natural.
dónde
denota
Aunque siguió mucho debate puramente teórico, no fue hasta 2009 que algunas pruebas empíricas con estudiantes entrenados en lógica encontraron que es más probable que asignen modelos que coincidan con la oración "bidireccional" de primer orden en lugar de la oración cuantificadora de ramificación con varias frases naturales. construcciones del lenguaje derivadas de la oración Hintikka. Por ejemplo, a los estudiantes se les mostraron gráficos bipartitos no dirigidos —con cuadrados y círculos como vértices— y se les pidió que dijeran si oraciones como "más de 3 círculos y más de 3 cuadrados están conectados por líneas" describían correctamente los diagramas. [7]
Ver también
- Semántica del juego
- Lógica de dependencia
- Lógica amigable con la independencia (lógica IF)
- Cuantificador de Mostowski
- Cuantificador de Lindström
- No primera ordenación
Referencias
- ^ Stanley Peters ; Dag Westerståhl (2006). Cuantificadores en lenguaje y lógica . Prensa de Clarendon. págs. 66–72. ISBN 978-0-19-929125-0.
- ^ a b c Antonio Badia (2009). Cuantificadores en acción: cuantificación generalizada en lenguajes de consulta, lógicos y naturales . Saltador. pag. 74–76. ISBN 978-0-387-09563-9.
- ^ Henkin, L. "Algunas observaciones sobre fórmulas infinitamente largas". Métodos infinitistas: Actas del Simposio sobre Fundamentos de las Matemáticas, Varsovia, 2-9 de septiembre de 1959 , Panstwowe Wydawnictwo Naukowe y Pergamon Press, Varsovia, 1961, págs. 167-183. OCLC 2277863
- ^ Jaakko Hintikka y Gabriel Sandu, "Semántica teórica del juego", en Manual de lógica y lenguaje , ed. J. van Benthem y A. ter Meulen , Elsevier 2011 (2ª ed.) Citando Enderton, HB, 1970. Cuantificadores finitos parcialmente ordenados. Z. Math. Logik Grundlag. Matemáticas. 16, 393–397 doi : 10.1002 / malq.19700160802 .
- ^ Blass, A .; Gurevich, Y. (1986). "Cuantificadores de Henkin y problemas completos" (PDF) . Anales de lógica pura y aplicada . 32 : 1-16. doi : 10.1016 / 0168-0072 (86) 90040-0 . hdl : 2027,42 / 26312 .citando a W. Walkoe, cuantificación finita parcialmente ordenada, Journal of Symbolic Logic 35 (1970) 535–555. JSTOR 2271440
- ^ Hintikka, J. (1973). "Cuantificadores vs Teoría de la Cuantificación". Dialectica . 27 (3–4): 329–358. doi : 10.1111 / j.1746-8361.1973.tb00624.x .
- ^ a b c d Gierasimczuk, N .; Szymanik, J. (2009). "Cuantificación de ramificación v. Cuantificación bidireccional" (PDF) . Revista de semántica . 26 (4): 367. doi : 10.1093 / jos / ffp008 .
- ^ Sher, G. (1990). "Formas de ramificar cuantificadores" (PDF) . Lingüística y Filosofía . 13 (4): 393–422. doi : 10.1007 / BF00630749 .
- ^ Barwise, J. (1979). "Sobre cuantificadores de ramificación en inglés". Revista de lógica filosófica . 8 : 47–80. doi : 10.1007 / BF00258419 .
- ^ Mano, Michael (1998). "El diario de la lógica simbólica". El diario de la lógica simbólica . 63 (4): 1611–1614. doi : 10.2307 / 2586678 . JSTOR 2586678 .
enlaces externos
- Cuantificador de teoría de juegos en PlanetMath.