Kwantyfikator rozgałęziony

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

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

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

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

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

wartość zmiennej ${\displaystyle x_{i}}$ wiązanej przez kwantyfikator ${\displaystyle Q_{i}}$ zależy od wartości zmiennych ${\displaystyle x_{1},\dots ,x_{i-1}}$ wiązanych przez kwantyfikatory ${\displaystyle 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 ${\displaystyle Q_{H}{:}}$

${\displaystyle (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ć

${\displaystyle \exists f\exists g\forall x_{1}\forall x_{2}\phi {\big (}x_{1},x_{2},f(x_{1}),g(x_{2}){\big )}.}$

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

${\displaystyle (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 ${\displaystyle Q_{H}}$ jest równoważna fragmentowi ${\displaystyle \Sigma _{1}^{1}}$^[1] logiki drugiego rzędu.

Za pomocą ${\displaystyle Q_{H}}$ można też zdefiniować:

• Kwantyfikator Reschera: „Moc zbioru elementów spełniających ${\displaystyle \phi }$ jest mniejsza lub równa mocy zbioru elementów spełniających ${\displaystyle \psi }$”

${\displaystyle (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 ${\displaystyle \psi }$”

${\displaystyle (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”

${\displaystyle (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^[2].

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.

Przypisy