Branching quantifier

In logic a branching quantifier is a partial ordering

:$langle\; Qx\_1dots\; Qx\_n\; angle$

of quantifiers for Q∈{∀,∃}. In classical logic, quantifier prefixes are linearly ordered such that the value of a variable "x" bound by a quantifier "Q" depends on the value of the variables

:y₁,...,y_n

bound by quantifiers

:Qy₁,...,Qy_n

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

Branching quantification first appeared in Leon Henkin's "Some Remarks on Infinitely Long Formulas", "Infinitistic Methods", Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 1959. 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 (also known as informational-independence logic) which are claimed to be the most natural logics as a foundations for mathematics (e.g. set theory) or for capturing certain features of natural language and epistemology.

Definable Quantifiers

The simplest Henkin quantifier $Q\_H$ is

:.

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

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

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

:$(Q\_\{geqmathbb\{Nx)phi\; (x)equivexists\; a(Q\_Hx\_1,x\_2,y\_1,y\_2)\; [phi\; aland\; (x\_1=x\_2\; leftrightarrow\; y\_1=y\_2)\; land\; (phi\; (x\_1)\; ightarrow\; (phi\; (y\_1)land\; y\_1\; eq\; a))]$.

Several things follow from this, including the nonaxiomatizability of first-order logic with $Q\_H$ and its equivalence to the $Sigma\_1^1$-fragment of second-order logic.

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)(phi\; x,psi\; x)equiv\; Card(\{\; x\; colonphi\; x\}\; )leq\; Card(\{\; x\; colonpsi\; x\}\; )\; equiv\; (Q\_Hx\_1x\_2y\_1y\_2)\; [(x\_1=x\_2\; leftrightarrow\; y\_1=y\_2)\; land\; (phi\; x\_1\; ightarrow\; psi\; y\_1)]$

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

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

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

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

External links

* [http://planetmath.org/encyclopedia/Branching.html Game-theoretical quantifier] at PlanetMath.