Kwantyfikator rozgałęziony (inaczej kwantyfikator Henkina ) – zbiór częściowo uporządkowany
{
Q
1
x
1
,
Q
2
x
2
,
…
Q
n
x
n
}
,
{\displaystyle \{Q_{1}x_{1},Q_{2}x_{2},\dots Q_{n}x_{n}\},}
gdzie
Q
i
∈
{
∀
,
∃
}
{\displaystyle Q_{i}\in {\{\forall ,\exists \}}\ {}}
i
∈
{
1
,
2
,
3
,
…
,
n
}
.
{\displaystyle 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
…
Q
n
x
n
ϕ
(
x
1
,
x
2
,
…
,
x
n
)
{\displaystyle Q_{1}x_{1}Q_{2}x_{2}\dots Q_{n}x_{n}\phi (x_{1},x_{2},\dots ,x_{n})}
wartość zmiennej
x
i
{\displaystyle x_{i}}
kwantyfikator
Q
i
{\displaystyle Q_{i}}
x
1
,
…
,
x
i
−
1
{\displaystyle x_{1},\dots ,x_{i-1}}
Q
1
,
Q
2
,
…
,
Q
i
−
1
.
{\displaystyle Q_{1},Q_{2},\dots ,Q_{i-1}.}
Przykłady kwantyfikatorów rozgałęzionych
edytuj
Najprostszym kwantyfikatorem Henkina jest
Q
H
:
{\displaystyle Q_{H}{:}}
(
Q
H
x
1
,
x
2
,
y
1
,
y
2
)
ϕ
(
x
1
,
x
2
,
y
1
,
y
2
)
≡
(
∀
x
1
∃
y
1
∀
x
2
∃
y
2
)
ϕ
(
x
1
,
x
2
,
y
1
,
y
2
)
.
{\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}).}
Po zastosowaniu skolemizacji ma on postać
∃
f
∃
g
∀
x
1
∀
x
2
ϕ
(
x
1
,
x
2
,
f
(
x
1
)
,
g
(
x
2
)
)
.
{\displaystyle \exists f\exists g\forall x_{1}\forall x_{2}\phi {\big (}x_{1},x_{2},f(x_{1}),g(x_{2}){\big )}.}
Q
h
{\displaystyle Q_{h}}
Q
⩾
N
{\displaystyle Q_{\geqslant \mathbb {N} }}
(
Q
⩾
N
x
)
ϕ
(
x
)
≡
∃
a
(
Q
H
x
1
,
x
2
,
y
1
,
y
2
)
[
ϕ
(
a
)
∧
(
x
1
=
x
2
↔
y
1
=
y
2
)
∧
(
ϕ
(
x
1
)
→
(
ϕ
(
y
1
)
∧
y
1
≠
a
)
)
]
.
{\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 ]}.}
Wynika z tego m.in. że logika pierwszego rzędu z dodanym
Q
H
{\displaystyle Q_{H}}
Σ
1
1
{\displaystyle \Sigma _{1}^{1}}
[1] logiki drugiego rzędu .
Za pomocą
Q
H
{\displaystyle Q_{H}}
Kwantyfikator Reschera : „Moc zbioru elementów spełniających
ϕ
{\displaystyle \phi }
ψ
{\displaystyle \psi }
(
Q
L
x
)
(
ϕ
x
,
ψ
x
)
≡
Card
(
{
x
:
ϕ
x
}
)
⩽
Card
(
{
x
:
ψ
x
}
)
≡
(
Q
H
x
1
x
2
y
1
y
2
)
[
(
x
1
=
x
2
↔
y
1
=
y
2
)
∧
(
ϕ
x
1
→
ψ
y
1
)
]
.
{\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 ]}.}
Kwantyfikator Härtiga : „Zbiór elementów spełniających φ jest równoliczny ze zbiorem elementów spełniających
ψ
{\displaystyle \psi }
(
Q
I
x
)
(
ϕ
x
,
ψ
x
)
≡
(
Q
L
x
)
(
ϕ
x
,
ψ
x
)
∧
(
Q
L
x
)
(
ϕ
x
,
ψ
x
)
.
{\displaystyle (Q_{I}x)(\phi x,\psi x)\equiv (Q_{L}x)(\phi x,\psi x)\land (Q_{L}x)(\phi x,\psi x).}
Kwantyfikator Changa : „Moc zbioru elementów spełniających φ jest równoliczny z uniwersum modelu ”
(
Q
C
x
)
(
ϕ
x
)
≡
(
Q
L
x
)
(
x
=
x
,
ϕ
x
)
.
{\displaystyle (Q_{C}x)(\phi x)\equiv (Q_{L}x)(x=x,\phi x).}
Historia i zastosowanie
edytuj
↑ Patrz Hierachia analityczna .
↑ Leon Henkin „Some Remarks on Infinitely Long Formulas”, Infinitistic Methods , Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 1959.
![{\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)
![{\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)
