Kwantyfikator rozgałęziony (inaczej kwantyfikator Henkina) – zbiór częściowo uporządkowany
gdzie dla
W rachunku predykatów prefiks kwantyfikatorowy jest liniowym porządkiem, tzn. w formule
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
Najprostszym kwantyfikatorem Henkina jest
Po zastosowaniu skolemizacji ma on postać
jest wystarczająco silny, żeby wyrazić kwantyfikator (tzn. „istnieje nieskończenie wiele”)
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 ”
- Kwantyfikator Härtiga: „Zbiór elementów spełniających φ jest równoliczny ze zbiorem elementów spełniających ”
- Kwantyfikator Changa: „Moc zbioru elementów spełniających φ jest równoliczny z uniwersum modelu”
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
- ↑ Patrz Hierachia analityczna.
- ↑ Leon Henkin „Some Remarks on Infinitely Long Formulas”, Infinitistic Methods, Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 1959.