Kwantyfikator rozgałęziony

Kwantyfikator rozgałęziony (inaczej kwantyfikator Henkina) to zbiór częściowo uporządkowany

$\{Q_1x_1, Q_2x_2,\dots Q_nx_n\}$

gdzie $Q_i\in {\{ \forall,\exists \}}$ dla $i\in\{1,2,3,..,n\}$.

W rachunku predykatów prefiks kwantyfikatorowy jest liniowym porządkiem tzn. w formule

$Q_1x_1Q_2x_2\dots Q_nx_n \phi(x_1, x_2, ..., x_n)$

wartość zmiennej $x_i$ wiązanej przez kwantyfikator $Q_i$ zależy od wartości zmiennych $x_1,...,x_{i-1}$ wiązanych przez kwantyfikatory $Q_1, Q_2,...,Q_{i-1}$. W formule z kwantyfikatorem rozgałęzionym może być inaczej.

Przykłady kwantyfikatorów rozgałęzionych

Najprostszym kwantyfikatorem Henkina jest $Q_H$:

$(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)$.

Po zastosowaniu skolemizacji ma on postać

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

$Q_h$ jest wystarczająco silny, żeby wyrazić kwantyfikator $Q_{\geqslant\mathbb{N}}$ (tzn. "istnieje nieskończenie wiele") :

$(Q_{\geqslant\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))]$.

Wynika z tego m.in. że logika pierwszego rzędu z dodanym $Q_H$ jest równoważna fragmentowi $\Sigma_1^1$ logiki drugiego rzędu.

Za pomocą $Q_H$ można też zdefiniować:

• Kwantyfikator Reschera: "Moc zbioru elementów spełniających φ jest mniejsza lub równa mocy zbioru elementów spełniających ψ"

$(Q_Lx)(\phi x,\psi x)\equiv Card(\{ x \colon\phi x\} )\leqslant 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)]$

• Kwantyfikator Härtiga: "Zbiór elementów spełniających φ jest równoliczny ze zbiorem elementów spełniających ψ"

$(Q_Ix)(\phi x,\psi x)\equiv (Q_Lx)(\phi x,\psi x) \land (Q_Lx)(\phi x,\psi x)$

• Kwantyfikator Changa: "Moc zbioru elementów spełniających φ jest równoliczny z uniwersum modelu"

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

Historia i zastosowanie

Kwantyfikator rozgałęziony pojawił się po raz pierwszy w "Some Remarks on Infinitely Long Formulas" Leona Henkina.

Jest to podstawowe pojęcie w IF-logice (ang. IF-logic, independence-friendly logic, informational-independence logic) Jaakko Hintikki i Gabriela Sandu.

Siła rachunku predykatów z kwantyfikatorami rozgałęzionymi jest większa niż logiki pierwszego rzędu, ale mniejsza niż logiki drugiego rzędu.