Kwantyfikator rozgałęziony

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

$\{Q_1{x}_1,Q_2{x}_2,\dots Q_n{x}_n\},$

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

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

$Q_1{x}_1{Q}_2{x}_2\dots Q_n{x}_n\varphi (x_1,x_2,\dots ,x_n)$

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

$(Q_H{x}_1,x_2,y_1,y_2)\varphi (x_1,x_2,y_1,y_2)\equiv \left(\begin{array}{c}\mathrm{\forall }{x}_1\mathrm{\exists }{y}_1\\ \mathrm{\forall }{x}_2\mathrm{\exists }{y}_2\end{array}\right)\varphi (x_1,x_2,y_1,y_2).$

Po zastosowaniu skolemizacji ma on postać

$\mathrm{\exists }f\mathrm{\exists }g\mathrm{\forall }{x}_1\mathrm{\forall }{x}_2\varphi (x_1,x_2,f(x_1),g(x_2)).$

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

$(Q_{⩾\mathbb{N}}x)\varphi (x)\equiv \mathrm{\exists }a(Q_H{x}_1,x_2,y_1,y_2)[\varphi (a)\wedge (x_1=x_2\leftrightarrow y_1=y_2)\wedge (\varphi (x_1)\to (\varphi (y_1)\wedge y_1\ne a)\left)\right].$

Wynika z tego m.in. że logika pierwszego rzędu z dodanym $Q_H$ jest równoważna fragmentowi ${\mathrm{\Sigma }}_1^1$ logiki drugiego rzędu.

Za pomocą $Q_H$ można też zdefiniować:

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

$(Q_{L}x)(\varphi x,\psi x)\equiv \mathrm{Card}(\{x:\varphi x\})⩽\mathrm{Card}(\{x:\psi x\})\equiv (Q_H{x}_1{x}_2{y}_1{y}_2)[(x_1=x_2\leftrightarrow y_1=y_2)\wedge (\varphi x_1\to \psi y_1)].$

• Kwantyfikator Härtiga: „Zbiór elementów spełniających φ jest równoliczny ze zbiorem elementów spełniających $\psi$”

$(Q_{I}x)(\varphi x,\psi x)\equiv (Q_{L}x)(\varphi x,\psi x)\wedge (Q_{L}x)(\varphi x,\psi x).$

• Kwantyfikator Changa: „Moc zbioru elementów spełniających φ jest równoliczny z uniwersum modelu”

$(Q_{C}x)(\varphi x)\equiv (Q_{L}x)(x=x,\varphi x).$

Historia i zastosowanie

Kwantyfikator rozgałęziony pojawił się po raz pierwszy w „Some Remarks on Infinitely Long Formulas” Leona Henkina.

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.