TU/e
Mike Boldy en Hans Cuypers

Predicatenlogica en wiskunde

In het hoofdstuk over propositielogica en wiskunde hebben we gezien dat er altijd twee aspecten zijn waar je rekening mee moet houden:

Dit onderscheid heeft gevolgen voor de manier waarop je in de wiskunde met predicaten en quantoren omgaat.

De \forall quantor bewijzen

Als je een uitspraak in de vorm \forall_x[p(x)] moet bewijzen betekent dit dat je alle beweringen p(x) moet bewijzen. Dat is saai en bovendien kan het vaak niet eens. Daarom hebben wiskundigen iets slims bedacht: in plaats van een heleboel bewijzen geef je er maar één. Dit doe je dan voor een willekeurige x. Met willekeurig bedoelen we: je weet niet meer van x dan dat het tot het universum behoort. Verder mag je over x geen aannames maken.

Voorbeeld

Stel je wilt aantonen

voor ieder geheel getal n geldt: n(n+1) is even.
Met een quantor ziet dat er zo uit:
\forall_n[\mbox{n(n+1) is even}]
Je begint je bewijs met ``stel n is een geheel getal''. Je weet van n dus dat het een geheel getal is, maar verder niets.

Hoe je in het algemeen het bewijs afmaakt hangt helemaal van de situatie af. Je zou met gevalsonderscheiding verder kunnen gaan. Je kan ook als volgt te werk gaan: deel n door 2 met rest. Je kunt dus schrijven: n=2k+r voor zekere quotiënt k en rest~r. Voor r zijn er slechts twee mogelijkheden: r=0 of r=1. Herleid nu n(n+1):

\begin{array}{lll} n(n+1) & = & (2k+r)(2k+r+1) \\ & = & 4k^2+2rk+2k+2rk+r^2+r \\ & = & 2(2k^2+2rk+k)+r^2+r. \end{array}
Merk nu op dat r^2+r=0 of r^2+r=2, dus r^2+r is even.

Je hebt nu bewezen dat n(n+1) even is voor een willekeurig geheel getal n, en dus is n(n+1) even voor ieder geheel getal~n.

De \forall quantor toepassen

Als je weet dat de bewering \forall_x[p(x)] waar is kun je iedere x kiezen, en deze in p invullen. Je weet dan dat p(x) waar is. Je weet zelfs dat p(x) waar is als je niet weet wat x is. Dit kun je handig gebruiken om nieuwe proposities af te leiden.

Voorbeeld

Gebruik de optelformule voor de sinus om de verdubbelingsformule af te leiden. De optelformule kun je met quantoren als volgt opschrijven:

\forall_\alpha\forall_\beta[\sin(\alpha+\beta)=\sin(\alpha)\cos(\beta)+\cos(\alpha)\sin(\beta)].
Dit geldt voor alle getallen \alpha en \beta. Kies nu \beta=\alpha, dan volgt uit de optelformule:
\sin(\alpha+\alpha) & = & \sin(\alpha)\cos(\alpha)+\cos(\alpha)\sin(\alpha), \\ \sin(2\alpha) & = & 2\sin(\alpha)\cos(\alpha).
Merk op dat we \beta hebben gekozen, maar \alpha niet. De gelijkheid geldt voor willekeurige \alpha, dus voor iedere \alpha:
\forall_\alpha[\sin(2\alpha)=2\sin(\alpha)\cos(\alpha)].

De \exists quantor bewijzen

Bewijzen van de vorm \exists_x[p(x)] noemt men existentiebewijzen. Een existentiebewijs bestaat in principe uit het bepalen van één speciale x_0 zodat dat p(x_0) waar is. Verder worden er geen eisen aan x_0 opgelegd. Ook doet het er niet toe hoe je aan x_0 komt. Als je bijvoorbeeld wilt aantonen dat er een even priemgetal bestaat, dus dat

\exists_p[\mbox{p is priem}\wedge\mbox{p is even}],
dan volstaat het om p=2 te kiezen.

Helaas is het niet altijd zo eenvoudig. Het probleem bij existentiebewijzen is dat het vaak een hele toer is om de speciale x_0 te vinden. Vaak is het zelfs onmogelijk om x_0 expliciet te beschrijven. Denk maar aan de hoofdstelling van de algebra:

Ieder polynoom met complexe coëfficiënten heeft tenminste één nulpunt.
Probleem is dat in deze bewering een \forall quantor voorkomt
\forall_f\exists_{x\in\mathbb C}[f(x)=0].
Als je de bewering wilt bewijzen begin je met een willekeurig polynoom f(x). Daar weet je verder niets van, dus hiervan een nulpunt vinden is een onmogelijke klus. Als je de hoofdstelling wilt bewijzen zul je iets slims moeten bedenken. Een mogelijkheid is om een bewijs uit het ongerijmde te geven. Je stelt dat een polynoom f(x) geen nulpunten heeft, en laat zien dat dit tot een tegenspraak leidt. Het bewijs is niet eenvoudig, we geven daarom een ander voorbeeld.

Voorbeeld

Stel je wilt de volgende bewering bewijzen:

Voor ieder positief reëel getal \varepsilon is er een positief natuurlijk getal n zodat 1/n<\varepsilon.
Met quantoren ziet dit er als volgt uit:
\forall_{\varepsilon>0}\exists_{n\in\mathbb N^\ast}[\frac{1}{n}<\varepsilon].
Hierbij is \mathbb N^\ast de verzameling van positieve natuurlijke getallen, dus \mathbb N^\ast=\{1,2,3,\ldots\}.

Stel \varepsilon>0. We moeten nu bewijzen dat

\exists_{n\in\mathbb N^\ast}[\frac{1}{n}<\varepsilon].
Stel dat dit niet waar is. Dan geldt
\forall_{n\in\mathbb N^\ast}[\frac{1}{n}\geq\varepsilon],
dus
\forall_{n\in\mathbb N^\ast}[1\geq n\varepsilon],
dus
\forall_{n\in\mathbb N^\ast}[n\leq\frac{1}{\varepsilon}],
Maar dit betekent dat \mathbb N^\ast\subset[0,1/\varepsilon], wat duidelijk onzin is.

De \exists quantor toepassen

Als je weet dat \exists_x[p(x)] waar is, dan weet je dat er één exemplaar x_0 bestaat zodat p(x) waar is. Er kunnen er meer zijn, maar dat weet je niet. Belangrijk is nu het dat je het volgende in de gaten houdt:

Van x_0 weet je dat hij in het universum zit, en dat p(x_0) waar is en verder niets.
Denk maar aan de tussenwaardestelling. De functie f(x)=x^3+x-1 is continu, en f(0)=-1 en f(1)=1. De tussenwaardestelling zegt nu dat er een getal a op het interval [0,1] bestaat zodat f(a)=0. Verder kun je uit de tussenwaardestelling geen conclusies meer trekken.

Een veel gemaakte fout is dat men meer aanneemt dan is toegestaan. Soms sluipt dit soort fouten er ongemerkt in. In het volgende voorbeeld laten we zien wat er allemaal mis kan gaan.

Voorbeeld

Stel je wilt de volgende stelling bewijzen:

Als a een deler is van b, en b is een deler van c, dan is a een deler van c.
De bewering ``a is een deler van b'' noteren we als a|b. Je kunt dit als volgt definiëren:
a|b\Leftrightarrow\exists_q[a\cdot q=b].
Zie ook het voorbeeld over priemgetallen. De gevraagde stelling kun je in predicatenlogica als volgt formuleren:
\forall_a\forall_b\forall_c[a|b\wedge b|c\Rightarrow a|c].
Je begint met willekeurige getallen a, b en c te nemen. Daarna stel je dat a een deler is van b en dat b een deler is van c, en ga je aantonen dat a een deler is van c.

Wat je soms ziet is dat men bij het bewijs expliciete getallen gebruikt:

Er geldt a|b, dus bijvoorbeeld a\cdot3=b. Er geldt b|c, bijvoorbeeld b\cdot5=c. Dan c=sb=3(5a)=15a, dus a|c. {\bf\textcolor{red}{FOUT!}}
Dit is niet toegestaan. Je hebt nu alleen iets bewezen voor speciale gevallen. In feite neem je aan dat 3 het quotiënt is van b en a, maar dat weet je niet. Wat als het quotiënt 7 is?

Als je het bewijs op de correcte manier wilt geven moet je letters gebruiken. De aanname a|b betekent: er is een getal q zodat a\cdot q=b. Behalve deze gelijkheid weet je niets van q. Nu ga je de aanname b|c uitschrijven:

er is een q zodat b\cdot q=c. {\bf\textcolor{red}{FOUT!}}
Wat gaat hier mis? Je had al opgeschreven dat a\cdot q=b, dus q is kennelijk ook het quotiënt van b en a. En dit quotiënt is doorgaans niet hetzelfde als het quotiënt van c en b. Met andere woorden: je hebt een extra aanname gemaakt over het quotiënt van c en b, namelijk dat deze gelijk is aan het quotiënt van b en a.

De oplossing is simpel: gebruik een andere letter voor het quotiënt van c en b:

er is een r zodat b\cdot r=c.
Nu kun je het bewijs afmaken:
c=rb=r(qa)=(rq)a.
Je hebt nu een expliciet getal s=rq zodat c=s\cdot a, en dus geldt a|c. Let op: je weet nog steeds niet hoe groot het getal s is, je weet alleen dat het bestaat.

Gevalsonderscheiding

We geven nu een alternatief bewijs van de bewering

\forall_n[\mbox{n(n+1) is even}]
Stel n is een geheel getal. Het getal n is willekeurig, je weet niets van n. Om toch een aanknopingspunt te krijgen onderscheiden we twee gevallen: Meer gevallen zijn er niet, dus als we deze twee gevallen aan kunnen zijn we klaar.

Als n even is, dan is n(n+1) ook even (een even getal vermenigvuldigen met n+1 levert een even getal).

Als n oneven is, dan is n+1 even, en dus is n(n+1) ook even (een even getal vermenigvuldigen met n levert een even getal).

Belangrijk is dat alle waarden door tenminste één geval gedekt worden. Ze hoeven elkaar niet uit te sluiten.

Voorbeeld

Bewijs dat

\forall_{x\in\mathbb R}[|x|\geq 0].
Stel x\in\mathbb R. We onderscheiden twee gevallen: x\geq0 en x\leq0. De beide gevallen overlappen elkaar (voor x=0), maar dat is niet erg.