Branching quantifier

From Wikipedia, the free encyclopedia

In logic a branching quantifier is a partial ordering

$\langle Qx_1\dots Qx_n\rangle$

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.

[edit] 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

1. $(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 other following quantifiers are 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)]$