Misplaced Pages

Branching quantifier

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Branching quantification)

In logic a branching quantifier, also called a Henkin quantifier, finite partially ordered quantifier or even nonlinear quantifier, is a partial ordering

⟨ Q x 1 … Q x n ⟩ {\displaystyle \langle Qx_{1}\dots Qx_{n}\rangle }

of quantifiers for Q ∈ {∀,∃}. It is a special case of generalized quantifier. In classical logic, quantifier prefixes are linearly ordered such that the value of a variable ym bound by a quantifier Qm depends on the value of the variables

y1, ..., ym−1

bound by quantifiers

Qy1, ..., Qym−1

preceding Qm. In a logic with (finite) partially ordered quantification this is not in general the case.

Branching quantification first appeared in a 1959 conference paper of Leon Henkin. Systems of partially ordered quantification are intermediate in strength between first-order logic and second-order logic. They are being used as a basis for Hintikka's and Gabriel Sandu's independence-friendly logic.

Definition and properties

The simplest Henkin quantifier Q H {\displaystyle Q_{H}} is

( Q H x 1 , x 2 , y 1 , y 2 ) φ ( x 1 , x 2 , y 1 , y 2 ) ≡ ( ∀ x 1 ∃ y 1 ∀ x 2 ∃ y 2 ) φ ( x 1 , x 2 , y 1 , y 2 ) . {\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}).}

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

∃ f ∃ g ∀ x 1 ∀ x 2 φ ( x 1 , x 2 , f ( x 1 ) , g ( x 2 ) ) . {\displaystyle \exists f\,\exists g\,\forall x_{1}\forall x_{2}\,\varphi (x_{1},x_{2},f(x_{1}),g(x_{2})).}

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

( Q ≥ N x ) φ ( x ) ≡ ( ∃ a ) ( Q H x 1 , x 2 , y 1 , y 2 ) [ φ ( a ) ∧ ( x 1 = x 2 ↔ y 1 = y 2 ) ∧ ( φ ( x 1 ) → ( φ ( y 1 ) ∧ y 1 ≠ a ) ) ] . {\displaystyle (Q_{\geq \mathbb {N} }x)\varphi (x)\equiv (\exists a)(Q_{H}x_{1},x_{2},y_{1},y_{2}).}

Several things follow from this, including the nonaxiomatizability of first-order logic with Q H {\displaystyle Q_{H}} (first observed by Ehrenfeucht), and its equivalence to the Σ 1 1 {\displaystyle \Sigma _{1}^{1}} -fragment of second-order logic (existential second-order logic)—the latter result published independently in 1970 by Herbert Enderton and W. Walkoe.

The following quantifiers are also definable by Q H {\displaystyle Q_{H}} .

  • Rescher: "The number of φs is less than or equal to the number of ψs"
( Q L x ) ( φ x , ψ x ) ≡ Card ⁡ ( { x : φ x } ) ≤ Card ⁡ ( { x : ψ x } ) ≡ ( Q H x 1 x 2 y 1 y 2 ) [ ( x 1 = x 2 ↔ y 1 = y 2 ) ∧ ( φ x 1 → ψ y 1 ) ] {\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})}
  • Härtig: "The φs are equinumerous with the ψs"
( Q I x ) ( φ x , ψ x ) ≡ ( Q L x ) ( φ x , ψ x ) ∧ ( Q L x ) ( ψ x , φ x ) {\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: "The number of φs is equinumerous with the domain of the model"
( Q C x ) ( φ x ) ≡ ( Q L x ) ( x = x , φ x ) {\displaystyle (Q_{C}x)(\varphi x)\equiv (Q_{L}x)(x=x,\varphi x)}

The Henkin quantifier Q H {\displaystyle Q_{H}} can itself be expressed as a type (4) Lindström quantifier.

Relation to natural languages

Hintikka in a 1973 paper 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:

( ∀ x 1 ∃ y 1 ∀ x 2 ∃ y 2 ) [ ( V ( x 1 ) ∧ T ( x 2 ) ) → ( R ( x 1 , y 1 ) ∧ R ( x 2 , y 2 ) ∧ H ( y 1 , y 2 ) ∧ H ( y 2 , y 1 ) ) ] . {\displaystyle {\begin{pmatrix}\forall x_{1}\,\exists y_{1}\\\forall x_{2}\,\exists y_{2}\end{pmatrix}}.}

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, 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 Σ 1 1 {\displaystyle \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 Π 1 1 {\displaystyle \Pi _{1}^{1}} sentence).

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.

[ ∀ x 1 ∃ y 1 ∀ x 2 ∃ y 2 φ ( x 1 , x 2 , y 1 , y 2 ) ] ∧ [ ∀ x 2 ∃ y 2 ∀ x 1 ∃ y 1 φ ( x 1 , x 2 , y 1 , y 2 ) ] {\displaystyle \wedge }

where

φ ( x 1 , x 2 , y 1 , y 2 ) {\displaystyle \varphi (x_{1},x_{2},y_{1},y_{2})}

denotes

( V ( x 1 ) ∧ T ( x 2 ) ) → ( R ( x 1 , y 1 ) ∧ R ( x 2 , y 2 ) ∧ H ( y 1 , y 2 ) ∧ H ( y 2 , y 1 ) ) {\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}))}

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.

See also

References

  1. Stanley Peters; Dag Westerståhl (2006). Quantifiers in language and logic. Clarendon Press. pp. 66–72. ISBN 978-0-19-929125-0.
  2. ^ Antonio Badia (2009). Quantifiers in Action: Generalized Quantification in Query, Logical and Natural Languages. Springer. p. 74–76. ISBN 978-0-387-09563-9.
  3. Henkin, L. "Some Remarks on Infinitely Long Formulas". Infinitistic Methods: Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 2–9 September 1959, Panstwowe Wydawnictwo Naukowe and Pergamon Press, Warsaw, 1961, pp. 167–183. OCLC 2277863
  4. Jaakko 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 partially-ordered quantifiers. Z. Math. Logik Grundlag. Math. 16, 393–397 doi:10.1002/malq.19700160802.
  5. Blass, A.; Gurevich, Y. (1986). "Henkin quantifiers and complete problems" (PDF). Annals of Pure and Applied Logic. 32: 1–16. doi:10.1016/0168-0072(86)90040-0. hdl:2027.42/26312. citing W. Walkoe, Finite partially-ordered quantification, Journal of Symbolic Logic 35 (1970) 535–555. JSTOR 2271440
  6. Hintikka, J. (1973). "Quantifiers vs. Quantification Theory". Dialectica. 27 (3–4): 329–358. doi:10.1111/j.1746-8361.1973.tb00624.x.
  7. ^ Gierasimczuk, N.; Szymanik, J. (2009). "Branching Quantification v. Two-way Quantification" (PDF). Journal of Semantics. 26 (4): 367. doi:10.1093/jos/ffp008.
  8. Sher, G. (1990). "Ways of branching quantifers" (PDF). Linguistics and Philosophy. 13 (4): 393–422. doi:10.1007/BF00630749. S2CID 61362436.
  9. Barwise, J. (1979). "On branching quantifiers in English". Journal of Philosophical Logic. 8: 47–80. doi:10.1007/BF00258419. S2CID 31950692.
  10. Hand, Michael (1998). "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". The Journal of Symbolic Logic. 63 (4): 1611–1614. doi:10.2307/2586678. JSTOR 2586678. S2CID 117833401.

External links

Category: