Kwantyfikator rozgałęziony

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łęzionychEdytuj

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 zastosowanieEdytuj

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.

PrzypisyEdytuj

  1. Patrz Hierachia analityczna.
  2. Leon Henkin „Some Remarks on Infinitely Long Formulas”, Infinitistic Methods, Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 1959.