Branching quantifier

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

$\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 y_m bound by a quantifier Q_m depends on the value of the variables

y₁,...,y_m-1

bound by quantifiers

Qy₁,...,Qy_m-1

preceding Q_m. 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

$(Q_Hx_1,x_2,y_1,y_2)\phi(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}\phi(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.

$\exists f \exists g \forall x_1 \forall x_2\phi (x_1,x_2,f(x_1),g(x_2))$.

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

$(Q_{\geq\mathbb{N}}x)\phi (x)\equiv\exists a(Q_Hx_1,x_2,y_1,y_2)[\phi a\land (x_1=x_2 \leftrightarrow y_1=y_2) \land (\phi (x_1)\rightarrow (\phi (y_1)\land y_1\neq 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 \colon\phi x\} )\leq Card(\{ x \colon\psi x\} ) \equiv (Q_Hx_1x_2y_1y_2)[(x_1=x_2 \leftrightarrow y_1=y_2) \land (\phi x_1 \rightarrow \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)(\psi x,\phi x)$

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

$(Q_Cx)(\phi x)\equiv (Q_Lx)(x=x,\phi x)$

See also

• Game Semantics
• Dependence Logic
• IF logic
• Mostowksi quantifier
• Lindström quantifier

External links

• Game-theoretical quantifier at PlanetMath.