Er is geen grootste even getal

Bewijs dat er geen grootste even getal bestaat.

Schrijf de negatie als eerste regel: Stel, uit het ongerijmde, dat er een grootste even getal $N$ bestaat = Aanname: $N$ is even en $N \ge$ elk even getal

Gebruik de definitie van even: $N = 2k$ voor een geheel getal $k$, dus $N + 2 = 2k + 2 = 2(k + 1)$ = $N + 2$ is even

Vergelijk de twee getallen: $N + 2 > N$ = Er bestaat een even getal groter dan $N$

Wijs de tegenspraak aan en concludeer: $N$ is het grootste even getal, maar $N + 2$ is een groter even getal = De aanname is onwaar

Answer: De aanname leidt tot een tegenspraak, dus er is geen grootste even getal. QED

Twee van de 13 mensen zijn in dezelfde maand jarig

Bewijs dat in elke groep van 13 mensen er minstens twee in dezelfde maand geboren zijn.

Schrijf de negatie: Stel, uit het ongerijmde, dat alle 13 mensen in verschillende maanden geboren zijn = Aanname: 13 verschillende maanden

Tel wat de aanname nodig heeft: 13 mensen zonder herhaalde maand hebben minstens 13 verschillende maanden nodig = Minstens $13$ maanden nodig

Vergelijk met de feiten: Een jaar heeft maar $12$ maanden, en $13 > 12$ = Onmogelijk

Concludeer: De aanname is onwaar = Twee mensen delen een maand

Answer: Minstens twee van de 13 mensen zijn in dezelfde maand geboren. Dit is het ladenprincipe: 13 voorwerpen, 12 laden. QED

Er is geen kleinste positief rationaal getal

Bewijs dat er geen kleinste positief rationaal getal bestaat.

Schrijf de negatie: Stel, uit het ongerijmde, dat $r$ het kleinste positieve rationale getal is = Aanname: $r > 0$, $r$ rationaal, niets is kleiner

Maak een nieuw getal: Als $r = \frac{a}{b}$, dan is $\frac{r}{2} = \frac{a}{2b}$ een breuk van gehele getallen = $\frac{r}{2}$ is rationaal

Controleer de grootte: $r > 0$, dus $0 < \frac{r}{2} < r$ = $\frac{r}{2}$ is positief en kleiner dan $r$

Wijs de tegenspraak aan en concludeer: $r$ was het kleinste, maar $\frac{r}{2}$ is kleiner = De aanname is onwaar

Answer: Er is geen kleinste positief rationaal getal. Noemt iemand bijvoorbeeld $\frac{1}{1000}$, dan is $\frac{1}{2000}$ kleiner. QED

De wortel uit 2 is irrationaal

Bewijs dat $\sqrt{2}$ irrationaal is.

Schrijf de negatie: Stel, uit het ongerijmde, dat $\sqrt{2}$ rationaal is: $\sqrt{2} = \frac{a}{b}$ met gehele getallen $a, b$, $b \neq 0$, en de breuk volledig vereenvoudigd = $a$ en $b$ hebben geen gemeenschappelijke deler

Kwadrateer beide kanten: $2 = \frac{a^2}{b^2}$, dus $a^2 = 2b^2$ = $a^2$ is even

Concludeer dat a even is: Als $a$ oneven was, zou $a^2$ oneven zijn (bewezen in de les over het directe bewijs) = $a = 2k$ voor een geheel getal $k$

Vul in: $(2k)^2 = 2b^2$, dus $4k^2 = 2b^2$, dus $b^2 = 2k^2$ = $b^2$ is even, dus $b$ is even

Wijs de tegenspraak aan: $a$ en $b$ zijn allebei even, dus allebei deelbaar door $2$ = Dit is in strijd met "volledig vereenvoudigd"

Answer: De aanname dat $\sqrt{2}$ rationaal is, leidt tot een tegenspraak, dus $\sqrt{2}$ is irrationaal. QED

Er zijn oneindig veel priemgetallen (Euclides)

Bewijs dat er oneindig veel priemgetallen zijn.

Schrijf de negatie: Stel, uit het ongerijmde, dat er maar eindig veel priemgetallen zijn: $p_1, p_2, \ldots, p_n$ = De lijst bevat elk priemgetal

Maak een nieuw getal: $N = p_1 \cdot p_2 \cdots p_n + 1$ = $N > 1$

Deel N door elk priemgetal van de lijst: $N$ is één meer dan een veelvoud van elke $p_i$ = De rest is altijd $1$, dus geen enkele $p_i$ deelt $N$

Gebruik een bekend feit: Elk geheel getal groter dan $1$ heeft minstens één priemfactor = $N$ heeft een priemfactor die niet op de lijst staat

Wijs de tegenspraak aan: De lijst zou elk priemgetal bevatten = De aanname is onwaar

Answer: Er zijn oneindig veel priemgetallen. Let op: $N$ zelf hoeft geen priemgetal te zijn. Met de priemgetallen tot en met 13 is $N = 30031 = 59 \times 509$, en 59 en 509 zijn priemgetallen die op de lijst ontbreken. QED

Mistake: "Er zijn oneindig veel priemgetallen" ontkennen als "Er zijn geen priemgetallen"

Why: Het tegendeel van "oneindig veel" is niet "geen". De negatie moet elk geval dekken waarin de bewering niet klopt, en dat is "maar eindig veel".

Correct: Neem aan: "Er zijn maar eindig veel priemgetallen". Zo is ook de negatie van "elk priemgetal is oneven" de bewering "minstens één priemgetal is niet oneven", niet "elk priemgetal is even".

Mistake: $x > 5$ ontkennen als $x < 5$

Why: Het geval $x = 5$ wordt vergeten. Als het bewijs alleen $x < 5$ uitsluit, is het getal $5$ nog mogelijk.

Correct: De negatie van $x > 5$ is $x \le 5$, en de negatie van $x \ge 5$ is $x < 5$.

Mistake: "Volledig vereenvoudigd" vergeten in het bewijs dat $\sqrt{2}$ irrationaal is

Why: Zonder die voorwaarde is het helemaal geen tegenspraak dat $a$ en $b$ allebei even zijn: $\frac{4}{2}$ heeft een even teller en noemer.

Correct: Schrijf $\sqrt{2} = \frac{a}{b}$ volledig vereenvoudigd. Elke breuk kan vereenvoudigd worden, dus dat kost niets, en het is precies het feit dat het bewijs later schendt.

Mistake: Een verrassend resultaat voor een tegenspraak houden

Why: Een resultaat dat vreemd lijkt (een heel groot getal, een onverwachte breuk) is niet onmogelijk. Een tegenspraak moet botsen met de aanname of met een bekend feit.

Correct: Noem de twee beweringen die botsen, bijvoorbeeld "$r$ is het kleinste" en "$\frac{r}{2} < r$", en schrijf daarna de conclusie op.

Bij elkaar passende sokken in het donker

Het ladenprincipe, bewezen uit het ongerijmde, vertelt je hoeveel voorwerpen je minstens nodig hebt om zeker een herhaling te krijgen.

In een la liggen zwarte, witte en grijze sokken. Als je 4 sokken van allemaal verschillende kleuren kon pakken, had je 4 kleuren nodig, maar er zijn er maar 3. Dus 4 sokken bevatten altijd een passend paar.

Hash-botsingen in de informatica

Computers geven bestanden korte codes, hashes genoemd. Omdat er meer mogelijke bestanden dan codes zijn, moeten twee verschillende bestanden soms dezelfde code delen.

Een systeem geeft elk bestand een code van 00 tot en met 99. Bij 101 bestanden zou aannemen dat alle codes verschillend zijn 101 codes vragen, maar er zijn er maar 100, dus twee bestanden delen een code.

Waarom een rekenmachine nooit de exacte wortel uit 2 toont

Omdat $\sqrt{2}$ irrationaal is, houdt de decimale ontwikkeling nooit op en herhaalt ze zich nooit. Elk decimaal getal op het scherm is maar een benadering, en daar moeten ingenieurs rekening mee houden als ze diagonalen berekenen.

Een vierkante tegel met zijde 1 m heeft een diagonaal van $\sqrt{2} \approx 1{,}4142$ m. De waarde 1,4142 komt dichtbij, maar is niet exact.

Q: Waarom is het genoeg om een tegenspraak te bereiken?

A: Correct redeneren vanuit ware beweringen levert altijd alleen ware beweringen op. Als we iets onmogelijks bereiken, was minstens één startpunt onwaar, en het enige startpunt dat we zelf hebben toegevoegd, is de aanname $\neg P$. Dus $\neg P$ is onwaar en $P$ is waar.

Q: Wanneer gebruik ik een bewijs uit het ongerijmde?

A: Het is een goede keuze als de bewering zegt dat iets niet bestaat (geen grootste getal, geen breuk gelijk aan $\sqrt{2}$) of dat er oneindig veel van iets zijn. Dan geeft het tegendeel aannemen je een concreet object om mee te werken.

Q: Is een bewijs uit het ongerijmde hetzelfde als een bewijs via contrapositie?

A: Nee. Een bewijs via contrapositie bewijst rechtstreeks "als niet q, dan niet p" en eindigt bij "niet p". Een bewijs uit het ongerijmde neemt aan dat de bewering onwaar is en mag bij elke onmogelijkheid eindigen. Elk bewijs via contrapositie kun je herschrijven als bewijs uit het ongerijmde, maar niet elk bewijs uit het ongerijmde is een bewijs via contrapositie.

Q: Wat betekent QED, en wat is "reductio ad absurdum"?

A: QED (quod erat demonstrandum, "wat bewezen moest worden") markeert het einde van een bewijs. Reductio ad absurdum, "herleiding tot het ongerijmde", is de Latijnse naam van het bewijs uit het ongerijmde.