Branching quantifier

The simplest Henkin quantifier $Q\_H$ is

:$(Q\_Hx\_1,x\_2,y\_1,y\_2)\backslash varphi(x\_1,x\_2,y\_1,y\_2)\backslash equiv\backslash begin\{pmatrix\}\backslash forall\; x\_1\; \backslash ,\; \backslash exists\; y\_1\backslash \backslash \; \backslash forall\; x\_2\; \backslash ,\; \backslash exists\; y\_2\backslash end\{pmatrix\}\backslash varphi(x\_1,x\_2,y\_1,y\_2).$

It (in fact every formula with a Henkin prefix, not just the simplest one) is equivalent to its second-order Skolemization, i.e.

: $\backslash exists\; f\; \backslash ,\; \backslash exists\; g\; \backslash ,\; \backslash forall\; x\_1\; \backslash forall\; x\_2\; \backslash ,\; \backslash varphi\; (x\_1,\; x\_2,\; f(x\_1),\; g(x\_2)).$

It is also powerful enough to define the quantifier $Q\_\{\backslash geq\backslash mathbb\{N\}\}$ (i.e. "there are infinitely many") defined as

:$(Q\_\{\backslash geq\backslash mathbb\{N\}\}x)\backslash varphi\; (x)\backslash equiv(\backslash exists\; a)(Q\_Hx\_1,x\_2,y\_1,y\_2)[\backslash varphi(a)\backslash land\; (x\_1=x\_2\; \backslash leftrightarrow\; y\_1=y\_2)\; \backslash land\; (\backslash varphi\; (x\_1)\backslash rightarrow\; (\backslash varphi\; (y\_1)\backslash land\; y\_1\backslash neq\; a))].$

Several things follow from this, including the nonaxiomatizability of first-order logic with $Q\_H$ (first observed by Ehrenfeucht), and its equivalence to the $\backslash Sigma\_1^1$-fragment of second-order logic (existential second-order logic)—the latter result published independently in 1970 by Herbert EndertonJaakko Hintikka and Gabriel Sandu, "Game-theoretical semantics", in Handbook of logic and language, ed. J. van Benthem and A. ter Meulen, Elsevier 2011 (2nd ed.) citing Enderton, H.B., 1970. Finite {{Sic|hide=y|partially|-}}ordered quantifiers. Z. Math. Logik Grundlag. Math. 16, 393–397 {{doi|10.1002/malq.19700160802}}. and W. Walkoe.{{Cite journal | last1 = Blass | first1 = A. | last2 = Gurevich | first2 = Y. | doi = 10.1016/0168-0072(86)90040-0 | title = Henkin quantifiers and complete problems | journal = Annals of Pure and Applied Logic | volume = 32 | pages = 1–16 | year = 1986 | url = http://research.microsoft.com/en-us/um/people/gurevich/Opera/66.pdf| hdl = 2027.42/26312 | hdl-access = free }} citing W. Walkoe, Finite {{Sic|hide=y|partially|-}}ordered quantification, Journal of Symbolic Logic 35 (1970) 535–555. {{JSTOR|2271440}}

The following quantifiers are also definable by $Q\_H$.

• Rescher: "The number of φs is less than or equal to the number of ψs"

::$(Q\_Lx)(\backslash varphi\; x,\backslash psi\; x)\backslash equiv\; \backslash operatorname\{Card\}(\backslash \{\; x\; \backslash colon\backslash varphi\; x\backslash \}\; )\backslash leq\; \backslash operatorname\{Card\}(\backslash \{\; x\; \backslash colon\backslash psi\; x\backslash \}\; )\; \backslash equiv\; (Q\_Hx\_1x\_2y\_1y\_2)[(x\_1=x\_2\; \backslash leftrightarrow\; y\_1=y\_2)\; \backslash land\; (\backslash varphi\; x\_1\; \backslash rightarrow\; \backslash psi\; y\_1)]$

• Härtig: "The φs are equinumerous with the ψs"

::$(Q\_Ix)(\backslash varphi\; x,\backslash psi\; x)\backslash equiv\; (Q\_Lx)(\backslash varphi\; x,\backslash psi\; x)\; \backslash land\; (Q\_Lx)(\backslash psi\; x,\backslash varphi\; x)$

• Chang: "The number of φs is equinumerous with the domain of the model"

::$(Q\_Cx)(\backslash varphi\; x)\backslash equiv\; (Q\_Lx)(x=x,\backslash varphi\; x)$

The Henkin quantifier $Q\_H$ can itself be expressed as a type (4) Lindström quantifier.

Hintikka in a 1973 paper{{Cite journal | last1 = Hintikka | first1 = J. | title = Quantifiers vs. Quantification Theory | doi = 10.1111/j.1746-8361.1973.tb00624.x | journal = Dialectica | volume = 27 | issue = 3–4 | pages = 329–358 | year = 1973 }} advanced the hypothesis that some sentences in natural languages are best understood in terms of branching quantifiers, for example: "some relative of each villager and some relative of each townsman hate each other" is supposed to be interpreted, according to Hintikka, as:{{Cite journal | last1 = Gierasimczuk | first1 = N. | last2 = Szymanik | first2 = J. | doi = 10.1093/jos/ffp008 | title = Branching Quantification v. Two-way Quantification | journal = Journal of Semantics | volume = 26 | issue = 4 | pages = 367 | year = 2009 | url = http://www.jakubszymanik.com/papers/HTR.pdf}}{{Cite journal | last1 = Sher | first1 = G. | title = Ways of branching quantifers | doi = 10.1007/BF00630749 | journal = Linguistics and Philosophy | volume = 13 | issue = 4 | pages = 393–422 | year = 1990 | s2cid = 61362436 | url = https://escholarship.org/content/qt41g2927h/qt41g2927h.pdf?t=nww5sf }}

: $\backslash begin\{pmatrix\}\backslash forall\; x\_1\; \backslash ,\; \backslash exists\; y\_1\backslash \backslash \; \backslash forall\; x\_2\; \backslash ,\; \backslash exists\; y\_2\backslash end\{pmatrix\}\; [(V(x\_1)\; \backslash wedge\; T(x\_2))\; \backslash rightarrow\; (R(x\_1,y\_1)\; \backslash wedge\; R(x\_2,y\_2)\; \backslash wedge\; H(y\_1,\; y\_2)\; \backslash wedge\; H(y\_2,\; y\_1))].$

which is known to have no first-order logic equivalent.

The idea of branching is not necessarily restricted to using the classical quantifiers as leaves. In a 1979 paper,{{Cite journal | last1 = Barwise | first1 = J. | title = On branching quantifiers in English | doi = 10.1007/BF00258419 | journal = Journal of Philosophical Logic | volume = 8 | year = 1979 | pages = 47–80| s2cid = 31950692 }} Jon Barwise proposed variations of Hintikka sentences (as the above is sometimes called) in which the inner quantifiers are themselves generalized quantifiers, for example: "Most villagers and most townsmen hate each other." Observing that $\backslash Sigma\_1^1$ is not closed under negation, Barwise also proposed a practical test to determine whether natural language sentences really involve branching quantifiers, namely to test whether their natural-language negation involves universal quantification over a set variable (a $\backslash Pi\_1^1$ sentence).{{cite journal | first1 = Michael | last1 = Hand | title = Reviewed work: 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 | journal = The Journal of Symbolic Logic | volume = 63 | issue = 4 | year = 1998 | jstor = 2586678 | pages = 1611–1614 | doi = 10.2307/2586678 | s2cid = 117833401 }}

Hintikka's proposal was met with skepticism by a number of logicians because some first-order sentences like the one below appear to capture well enough the natural language Hintikka sentence.

: $[\backslash forall\; x\_1\; \backslash ,\; \backslash exists\; y\_1\; \backslash ,\; \backslash forall\; x\_2\; \backslash ,\; \backslash exists\; y\_2\backslash ,\; \backslash varphi\; (x\_1,\; x\_2,\; y\_1,\; y\_2)]\; \backslash wedge\; [\backslash forall\; x\_2\; \backslash ,\; \backslash exists\; y\_2\; \backslash ,\; \backslash forall\; x\_1\; \backslash ,\; \backslash exists\; y\_1\backslash ,\; \backslash varphi\; (x\_1,\; x\_2,\; y\_1,\; y\_2)]$

where

: $\backslash varphi\; (x\_1,\; x\_2,\; y\_1,\; y\_2)$

denotes

: $(V(x\_1)\; \backslash wedge\; T(x\_2))\; \backslash rightarrow\; (R(x\_1,y\_1)\; \backslash wedge\; R(x\_2,y\_2)\; \backslash wedge\; H(y\_1,\; y\_2)\; \backslash wedge\; H(y\_2,\; y\_1))$

Although much purely theoretical debate followed, it wasn't until 2009 that some empirical tests with students trained in logic found that they are more likely to assign models matching the "bidirectional" first-order sentence rather than branching-quantifier sentence to several natural-language constructs derived from the Hintikka sentence. For instance students were shown undirected bipartite graphs—with squares and circles as vertices—and asked to say whether sentences like "more than 3 circles and more than 3 squares are connected by lines" were correctly describing the diagrams.

• Game semantics
• Dependence logic
• Independence-friendly logic (IF logic)
• Mostowski quantifier
• Lindström quantifier
• Nonfirstorderizability

{{reflist}}

• [https://web.archive.org/web/20070930235518/http://planetmath.org/encyclopedia/Branching.html Game-theoretical quantifier] at PlanetMath.

Category:Quantifier (logic)