Kwantyfikator rozgałęziony

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

$\{Q_{1}x_{1},Q_{2}x_{2},\dots Q_{n}x_{n}\},$

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

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

$Q_{1}x_{1}Q_{2}x_{2}\dots Q_{n}x_{n}\phi (x_{1},x_{2},\dots ,x_{n})$

wartość zmiennej $x_{i}$ wiązanej przez kwantyfikator $Q_{i}$ zależy od wartości zmiennych $x_{1},\dots ,x_{i-1}$ wiązanych przez kwantyfikatory $Q_{1},Q_{2},\dots ,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_{H}x_{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 {\big (}x_{1},x_{2},f(x_{1}),g(x_{2}){\big )}.$

$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_{H}x_{1},x_{2},y_{1},y_{2}){\bigg [}\phi (a)\land (x_{1}=x_{2}\leftrightarrow y_{1}=y_{2})\land {\Big (}\phi (x_{1})\to {\big (}\phi (y_{1})\land y_{1}\neq a{\big )}{\Big )}{\bigg ]}.$

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 $\phi$ jest mniejsza lub równa mocy zbioru elementów spełniających $\psi$”

$(Q_{L}x)(\phi x,\psi x)\equiv \operatorname {Card} {\big (}\{x\colon \phi x\}{\big )}\leqslant \operatorname {Card} {\big (}\{x\colon \psi x\}{\big )}\equiv (Q_{H}x_{1}x_{2}y_{1}y_{2}){\big [}(x_{1}=x_{2}\leftrightarrow y_{1}=y_{2})\land (\phi x_{1}\to \psi y_{1}){\big ]}.$

• Kwantyfikator Härtiga: „Zbiór elementów spełniających φ jest równoliczny ze zbiorem elementów spełniających $\psi$”

$(Q_{I}x)(\phi x,\psi x)\equiv (Q_{L}x)(\phi x,\psi x)\land (Q_{L}x)(\phi x,\psi x).$

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

$(Q_{C}x)(\phi x)\equiv (Q_{L}x)(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.