TU/e
Mike Boldy en Hans Cuypers

Samengestelde quantoren

Vrije en gebonden variabelen

Als een predicaat met meer dan één variabele wordt gequantificeerd, is het resultaat geen propositie. De bewering

\exists_x[x>y]
is afhankelijk van y. We zeggen dat y een vrije variabele is.

Je zou het predicaat p als volgt kunnen definiëren:

p(y)\Leftrightarrow\exists_x[x>y].
Dit predicaat hangt niet van x af. De variabele x heeft alleen betekenis binnen de quantificatie, daarbuiten niet. We zeggen dat x een gebonden variabele is.

Een gebonden variabele kun je probleemloos vervangen door een andere letter.

\exists_u[u>y]
betekent hetzelfde als \exists_{x}[x>y]. Je kunt vrijwel iedere letter gebruiken. Kies echter geen letters die al in gebruik zijn:
\exists_y[y>y]
betekent echt iets heel anders als \exists_{x}[x>y]!

In de uitdrukking

\exists_x[p(x)]\rightarrow\forall_x[q(x)]
zijn alle x-en gebonden, maar door verschillende quantoren. Je zou de eerste x kunnen vervangen zonder de betekenis te veranderen:
\exists_y[p(y)]\rightarrow\forall_x[q(x)].
Hieraan kun je goed zien dat iedere quantor een bereik heeft. Het bereik van \exists_x of \forall_x is dat deel van de expressie waarin eventuele x-en worden gebonden. Het bereik kan gaten hebben:
\exists_x[p(x)\wedge\forall_x[q(x)]\wedge r(x)].
Het bereik van \exists_x bestaat uit p(x) en r(x). De x in q(x) wordt niet gebonden door \exists_x, maar door de \forall_x quantor die er vlak voor staat!

Meerdere quantoren

Omdat \exists_{x}[x>y] een predicaat is kun je hem op zijn beurt ook weer quantificeren, bijvoorbeeld:

\forall_y\left[\exists_x[x>y]\right].
Om deze uitdrukking beter leesbaar te maken laten we het buitenste paar blokhaken gewoonlijk weg:
\forall_y\exists_x[x>y].
Uiteraard kun je dit proces herhalen als er meer variabelen een rol spelen:
\forall_x\forall_y\forall_z[x>y\wedge y>z\rightarrow x>z].

Quantoren verwisselen

De propositie

\forall_y\exists_x[x>y]
drukt uit dat er bij ieder getal y een ander getal x bestaat dat groter is dan y. Je kunt bijvoorbeeld x=y+1 nemen. Als je de quantoren van plaats verwisselt krijg je
\exists_x\forall_y[x>y].
Deze bewering zegt dat er een getal x bestaat dat groter is dan ieder getal y. Dit is uiteraard niet waar.

Uit dit voorbeeld blijkt dat je niet zomaar twee quantoren kunt verwisselen. Verwisselen is toegestaan in de volgende gevallen:

Je kunt deze regels ook in formulevorm weergeven: Let op de pijl in de laatste regel. De andere kant op geldt de regel niet, zoals we aan het voorbeeld zagen.

Voorbeeld

Beweringen met samengestelde quantoren kunnen behoorlijk ingewikkeld worden:

\exists_{L}\forall_{\varepsilon>0}\exists_{N\in\mathbb N}\forall_{n\in\mathbb N} [n>N\rightarrow|x_n-L|<\varepsilon]
Hier staat dat de rij x_n een limiet heeft als n naar oneindig gaat. Voor de ongeoefende lezer zijn dergelijke predicaten nauwelijks te lezen. Toch blijkt het handig te zijn om dergelijke notaties te gebruiken. De predicatenlogica kent namelijk allerelei regels, die je pas goed kunt toepassen als je alles netjes hebt gequantificeerd.

Merk op dat ondank de vier quantoren er nog steeds een vrije variabele is, namelijk x.

Voorbeeld

Naast de \forall en \exists quantor bestaat er nog een quantor, namelijk \exists!. De propositie \exists!x[p(x)] is waar als er precies één x is waarvoor p(x) geldt. Je kunt deze quantor ook als volgt beschrijven:

\exists!_x[p(x)]\Leftrightarrow \exists_x[p(x)\wedge\forall y[p(y)\rightarrow y=x]].
Je kunt deze quantor gebruiken bij de definitie van het begrip ``functie''. Voor iedere functie f geldt namelijk
\forall_x\exists!_y[y=f(x)].