Cuantificador de ramificación

En lógica , un cuantificador de ramificación , ^[1] también llamado cuantificador de Henkin , cuantificador parcialmente ordenado finito o incluso cuantificador no lineal , es un cuantificador de ordenación parcial ^[2]

${\displaystyle \langle Qx_{1}\dots Qx_{n}\rangle }$

de cuantificadores para Q  ∈ {∀,∃}. Es un caso especial de cuantificador generalizado . En lógica clásica , los prefijos de cuantificadores están ordenados linealmente de tal manera que el valor de una variable y _m limitada por un cuantificador Q _m depende del valor de las variables

y ₁ , ..., y _{m −1}

limitado por cuantificadores

Qy ₁ , ..., Qy _{m −1}

precedente Q _m . En una lógica con cuantificación parcialmente ordenada (finita) este no es en general el caso.

La cuantificación ramificada apareció por primera vez en un artículo de 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 utilizan 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 ${\displaystyle Q_{H}}$

${\displaystyle (Q_{H}x_{1},x_{2},y_{1},y_{2})\varphi (x_{1},x_{2},y_{1},y_{2})\equiv {\begin{pmatrix}\forall x_{1}\,\exists y_{1}\\\forall x_{2}\,\exists y_{2}\end{pmatrix}}\varphi (x_{1},x_{2},y_{1},y_{2}).}$

Es equivalente (de hecho, cada fórmula con un prefijo Henkin, no solo la más simple) a su Skolemización de segundo orden , es decir

${\displaystyle \exists f\,\exists g\,\forall x_{1}\forall x_{2}\,\varphi (x_{1},x_{2},f(x_{1}),g(x_{2})).}$

También es lo suficientemente potente como para definir el cuantificador (es decir, "hay infinitos") definido como ${\displaystyle Q_{\geq \mathbb {N} }}$

${\displaystyle (Q_{\geq \mathbb {N} }x)\varphi (x)\equiv (\exists a)(Q_{H}x_{1},x_{2},y_{1},y_{2})[\varphi (a)\land (x_{1}=x_{2}\leftrightarrow y_{1}=y_{2})\land (\varphi (x_{1})\rightarrow (\varphi (y_{1})\land y_{1}\neq a))].}$

De esto se desprenden varias cosas, incluida la no axiomatizabilidad de la lógica de primer orden con (observada por primera vez por Ehrenfeucht ), y su equivalencia con el fragmento de la lógica de segundo orden ( lógica existencial de segundo orden ), resultado este último publicado independientemente en 1970 por Herbert Enderton ^[4] y W. Walkoe. ^[5] ${\displaystyle Q_{H}}$ ${\displaystyle \Sigma _{1}^{1}}$

Los siguientes cuantificadores también se pueden definir mediante . ^[2] ${\displaystyle Q_{H}}$

• Rescher: "El número de φ s es menor o igual que el número de ψ s"

${\displaystyle (Q_{L}x)(\varphi x,\psi x)\equiv \operatorname {Card} (\{x\colon \varphi x\})\leq \operatorname {Card} (\{x\colon \psi x\})\equiv (Q_{H}x_{1}x_{2}y_{1}y_{2})[(x_{1}=x_{2}\leftrightarrow y_{1}=y_{2})\land (\varphi x_{1}\rightarrow \psi y_{1})]}$

• Härtig: "Los φ s son equinumerosos con los ψ s"

${\displaystyle (Q_{I}x)(\varphi x,\psi x)\equiv (Q_{L}x)(\varphi x,\psi x)\land (Q_{L}x)(\psi x,\varphi x)}$

• Chang: “El número de φ s es equinumeroso con el dominio del modelo”

${\displaystyle (Q_{C}x)(\varphi x)\equiv (Q_{L}x)(x=x,\varphi x)}$

El cuantificador de Henkin puede expresarse como un cuantificador de Lindström de tipo (4) . ^[2] ${\displaystyle Q_{H}}$

Relación con los lenguajes naturales

Hintikka en un artículo de 1973 ^[6] planteó 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]}

${\displaystyle {\begin{pmatrix}\forall x_{1}\,\exists y_{1}\\\forall x_{2}\,\exists y_{2}\end{pmatrix}}[(V(x_{1})\wedge T(x_{2}))\rightarrow (R(x_{1},y_{1})\wedge R(x_{2},y_{2})\wedge H(y_{1},y_{2})\wedge H(y_{2},y_{1}))].}$

que se sabe que no tiene equivalente lógico de primer orden. ^[7]

La idea de ramificación no se limita necesariamente al uso de los cuantificadores clásicos como hojas. En un artículo de 1979, ^[9] Jon Barwise propuso variaciones de las oraciones Hintikka (como se denomina a veces a lo anterior) en las que los cuantificadores internos son en sí mismos cuantificadores generalizados , por ejemplo: "La mayoría de los habitantes de los pueblos y la mayoría de los habitantes de las ciudades se odian". ^[7] Al observar que no está cerrado bajo negación, Barwise también propuso una prueba práctica para determinar si las oraciones en lenguaje natural realmente involucran cuantificadores ramificados, es decir, para probar si su negación en lenguaje natural involucra una cuantificación universal sobre una variable establecida (una oración). ^[10] ${\displaystyle \Sigma _{1}^{1}}$ ${\displaystyle \Pi _{1}^{1}}$

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.

${\displaystyle [\forall x_{1}\,\exists y_{1}\,\forall x_{2}\,\exists y_{2}\,\varphi (x_{1},x_{2},y_{1},y_{2})]\wedge [\forall x_{2}\,\exists y_{2}\,\forall x_{1}\,\exists y_{1}\,\varphi (x_{1},x_{2},y_{1},y_{2})]}$

dónde

${\displaystyle \varphi (x_{1},x_{2},y_{1},y_{2})}$

denota

${\displaystyle (V(x_{1})\wedge T(x_{2}))\rightarrow (R(x_{1},y_{1})\wedge R(x_{2},y_{2})\wedge H(y_{1},y_{2})\wedge H(y_{2},y_{1}))}$

Aunque se desató un gran debate puramente teórico, no fue hasta 2009 que algunas pruebas empíricas con estudiantes formados en lógica revelaron que era más probable que asignaran modelos que coincidieran con la oración de primer orden "bidireccional" en lugar de la oración con cuantificador de ramificación a varias construcciones de lenguaje natural derivadas de la oración Hintikka. Por ejemplo, se mostraron a los estudiantes 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]

Véase también

• Semántica del juego
• Lógica de dependencia
• Lógica favorable a la independencia (lógica IF)
• Cuantificador de Mostowski
• Cuantificador de Lindström
• No primer ordenabilidad

Referencias

1. Stanley Peters; Dag Westerståhl (2006). Cuantificadores en lenguaje y lógica . Clarendon Press. pp. 66–72. ISBN 978-0-19-929125-0.
2. Antonio Badia (2009). Cuantificadores en acción: cuantificación generalizada en lenguajes de consulta, lógicos y naturales. Springer. pág. 74–76. ISBN 978-0-387-09563-9.
3. Henkin, L. "Algunas observaciones sobre fórmulas infinitamente largas". Métodos infinitistas: Actas del Simposio sobre fundamentos de las matemáticas, Varsovia, 2 a 9 de septiembre de 1959 , Panstwowe Wydawnictwo Naukowe y Pergamon Press, Varsovia, 1961, págs. OCLC  2277863
4. Jaakko Hintikka y Gabriel Sandu, "Semántica de teoría de juegos", en Handbook of logic and language , ed. J. van Benthem y A. ter Meulen , Elsevier 2011 (2.ª ed.) citando a Enderton, HB, 1970. Cuantificadores finitos parcialmente ordenados. Z. Math. Logik Grundlag. Math. 16, 393–397 doi :10.1002/malq.19700160802.
5. 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 parcialmente ordenada finita, Journal of Symbolic Logic 35 (1970) 535–555. JSTOR  2271440
6. Hintikka, J. (1973). "Cuantificadores frente a teoría de cuantificación". Dialectica . 27 (3–4): 329–358. doi :10.1111/j.1746-8361.1973.tb00624.x.
7. Gierasimczuk, N.; Szymanik, J. (2009). "Cuantificación de ramificación frente a cuantificación bidireccional" (PDF) . Journal of Semantics . 26 (4): 367. doi :10.1093/jos/ffp008.
8. Sher, G. (1990). "Formas de ramificar cuantificadores" (PDF) . Lingüística y filosofía . 13 (4): 393–422. doi :10.1007/BF00630749. S2CID  61362436.
9. Barwise, J. (1979). "Sobre cuantificadores de ramificación en inglés". Journal of Philosophical Logic . 8 : 47–80. doi :10.1007/BF00258419. S2CID  31950692.
10. Hand, Michael (1998). "Trabajo revisado: On Branching Quantifiers in English, Jon Barwise; Branching Generalized Quantifiers and Natural Language. Generalized Quantifiers, Linguistic and Logical Approaches, Dag Westerståhl, Peter Gärdenfors; Ways of Branching Quantifiers, Gila Sher". Revista de lógica simbólica . 63 (4): 1611–1614. doi :10.2307/2586678. JSTOR  2586678. S2CID  117833401.

Enlaces externos

• Cuantificador de teoría de juegos en PlanetMath.