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}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/208230f1164d0d6c97fda8a45c0539b862672ef3)
gdzie
dla
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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d22aae95db9e3ec7d75b3c570b97e0a8268e30ab)
wartość zmiennej
wiązanej przez kwantyfikator
zależy od wartości zmiennych
wiązanych przez kwantyfikatory
W formule z kwantyfikatorem rozgałęzionym może być inaczej.
Przykłady kwantyfikatorów rozgałęzionych[edytuj | edytuj kod]
Najprostszym kwantyfikatorem Henkina jest
![{\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}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b6f9dfd91d64fa7cc4e151095fbdbea561d455d)
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 )}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5c20720e73179c308f5b6e995be84098313550a)
jest wystarczająco silny, żeby wyrazić kwantyfikator
(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 ]}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/60c444b77e1e69f6c0db57f9a890d56b1242e889)
Wynika z tego m.in. że logika pierwszego rzędu z dodanym
jest równoważna fragmentowi
[1] logiki drugiego rzędu.
Za pomocą
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
”
![{\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 ]}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85aad73c77d7e26f49019e769002b3b7c89f73d4)
- Kwantyfikator Härtiga: „Zbiór elementów spełniających φ jest równoliczny ze zbiorem elementów spełniających
”
![{\displaystyle (Q_{I}x)(\phi x,\psi x)\equiv (Q_{L}x)(\phi x,\psi x)\land (Q_{L}x)(\phi x,\psi x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46068315c40737e924e8358d08f9552fb32506b8)
- 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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95bf4eb994a4c92873b2252b5352721f162d114f)
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.
- ↑ Patrz Hierachia analityczna.
- ↑ Leon Henkin „Some Remarks on Infinitely Long Formulas”, Infinitistic Methods, Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 1959.