cuantificador de ramificación

En lógica, un cuantificador ramificado , ^{[ 1 ]} también llamado cuantificador de Henkin , cuantificador parcialmente ordenado finito o incluso cuantificador no lineal , es un orden 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 ligada por un cuantificador Q _m depende del valor de las variables.

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

limitados por cuantificadores

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

precedente Q _m . En una lógica con cuantificación parcialmente ordenada (finita), esto no suele ser así.

La cuantificación ramificada apareció por primera vez en un artículo de conferencia de Leon Henkin en 1959. ^{[ 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 compatible con la independencia de Hintikka y Gabriel Sandu .

El cuantificador de Henkin más simple${\displaystyle Q_{H}}$es

${\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 (de hecho, toda fórmula con un prefijo Henkin, no solo la más simple) equivalente 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.${\displaystyle Q_{\geq \mathbb {N} }}$(es decir, "hay infinitos") definido como

${\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 derivan varias cosas, incluida la no axiomatizabilidad de la lógica de primer orden con${\displaystyle Q_{H}}$(observado por primera vez por Ehrenfeucht ), y su equivalencia con la${\displaystyle \Sigma _{1}^{1}}$-fragmento de lógica de segundo orden ( lógica existencial de segundo orden ) — este último resultado fue publicado independientemente en 1970 por Herbert Enderton ^{[ 4 ]} y W. Walkoe. ^{[ 5 ]}

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

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

${\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: "Las φ son iguales en número a las ψ "

${\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 φ es igual al dominio del modelo".

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

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

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 habitante de la ciudad 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 un 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 oraciones Hintikka (como a veces se denomina a lo anterior) en las que los cuantificadores internos son en sí mismos cuantificadores generalizados , por ejemplo: "La mayoría de los aldeanos y la mayoría de los habitantes de la ciudad se odian entre sí". ^{[ 7 ]} Observando que${\displaystyle \Sigma _{1}^{1}}$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, a saber, probar si su negación en lenguaje natural implica cuantificación universal sobre una variable de conjunto (un${\displaystyle \Pi _{1}^{1}}$oración). ^{[ 10 ]}

La propuesta de Hintikka fue recibida con escepticismo por varios lógicos porque algunas oraciones de primer orden, como la que aparece 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 generó un amplio debate puramente teórico, no fue hasta 2009 que algunas pruebas empíricas con estudiantes formados en lógica revelaron que estos tienden a asignar modelos que coinciden con la oración de primer orden "bidireccional" en lugar de la oración con cuantificador ramificado a varias construcciones del lenguaje natural derivadas de la oración Hintikka. Por ejemplo, se les mostraron a los estudiantes grafos bipartitos no dirigidos —con cuadrados y círculos como vértices— y se les pidió que indicaran 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 ]}

• semántica de juegos
• Lógica de dependencia
• Lógica compatible con la independencia (lógica IF)
• cuantificador de Mostowski
• cuantificador de Lindström
• no ordenabilidad

• Cuantificador de teoría de juegos en PlanetMath.