TU/e
Mike Boldy en Hans Cuypers

Predicatenlogica en verzamelingen

De predicatenlogica is nauw verweven met de verzamelingenleer. We zagen dit al toen we verzamelingen gingen beschrijven met behulp van predicaten:

A=\{x|p(x)\}.
Omgekeerd kun je quantoren ook beschrijven in verzamelingentaal: stel U is het universum, dan geldt
\forall_x[p(x)]\Leftrightarrow A=U
en
\exists_x[p(x)]\Leftrightarrow A\neq\emptyset.

Met predicatenlogica kun je bewerkingen als doorsnede, vereniging en complement beschrijven, bijvoorbeeld (met A=\{x|p(x)\} en B=\{x|q(x)\}):

A\cap B=\{x|p(x)\wedge q(x)\}.
Door gebruik te maken van quantoren kun je nog meer bewerkingen bechrijven. Een goed voorbeeld is de inclusie:
A\subset B\Leftrightarrow \forall_x[x\in A\rightarrow x\in B].
De gelijkheid van twee verzamelingen kun je beschrijven met twee inclusies, maar het kan ook zo:
A=B\Leftrightarrow \forall_x[x\in A\leftrightarrow x\in B].

Het universum

Dit is een manier om het universum U in een quantor aan te geven:

\forall_{x\in U}[p(x)].
Je kunt deze bewering ook anders formuleren:
\forall_x[x\in U\rightarrow p(x)].
Met behulp van dit principe kan je de inclusie ook als volgt beschrijven:
A\subset B\Leftrightarrow \forall_{x\in A}[x\in B].

Universele doorsnede en vereniging

De doorsnede van vier verzamelingen A_1, A_2, A_3 en A_4 kun je als volgt aangeven:

A_1\cap A_2\cap A_3\cap A_4.
Haakjes zijn niet nodig volgens regel~2. Als je een heleboel verzamelingen hebt, of zelfs oneindig veel is deze manier van noteren niet handig meer. Hier brengen quantoren uitkomst.

Definitie

Stel je hebt een oneindige rij verzamelingen A_1, A_2,\ldots. Dan definiëren we de doorsnede van alle A_i als

\bigcap_{i=1}^\infty A_i=\{x|\forall_i[x\in A_i]\},
en de vereniging van alle A_i definiëren we als
\bigcup_{i=1}^\infty A_i=\{x|\exists_i[x\in A_i]\}.
Als de rij eindig is, dus A_1, A_2,\ldots,A_n, dan schrijf je
\bigcap_{i=1}^n A_i=\{x|\forall_i[x\in A_i]\},
en
\bigcup_{i=1}^n A_i=\{x|\exists_i[x\in A_i]\}.

Voorbeeld

Definieer de intervallen A_i=[0,\frac{1}{i})\subset\mathbb R. Dan

\bigcap_{i=1}^\infty A_i=\{0\}
en
\bigcup_{i=1}^\infty A_i=[0,1).

We bewijzen alleen de eerste gelijkheid. Dit is een gelijkheid van twee verzamelingen, dus we moeten twee inclusies bewijzen:

\{0\}\subset\bigcap_{i=1}^\infty A_i
en
\bigcap_{i=1}^\infty A_i\subset\{0\}.
Voor de eerste inclusie merk je op dat 0\in [0,\frac{1}{i}) voor iedere i, dus volgens de definitie geldt 0\in\bigcap_{i=1}^\infty A_i.

De tweede inclusie vergt iets meer werk. Stel x\in\bigcap_{i=1}^\infty A_i. Dit betekent

(\ast)\quad 0\leq x<\frac{1}{i} voor alle i.
Eerst merken we op dat x\geq0, want x\in A_1=[0,1). We bewijzen nu uit het ongerijmde dat x=0. Stel x>0, dan definiëren we m als volgt:
Bereken 1/x en rond het resultaat naar boven af op een geheel getal. Noem dit getal m.
Er geldt nu: m\geq\frac{1}{x}, dus x\geq\frac{1}{m}. Maar volgens (\ast) geldt 0\leq x<\frac{1}{m}. Tegenspraak.