Ten artykuł od 2024-08 wymaga zweryfikowania podanych informacji.Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.
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 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[1].
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
- ↑ Leon Henkin „Some Remarks on Infinitely Long Formulas”, Infinitistic Methods, Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 1959.