Wanneer gebruik ik een bewijs uit het ongerijmde?

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.

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

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.

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

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.

Leermiddelen

Bewijs uit het ongerijmde

Leer een bewering te bewijzen door aan te nemen dat ze onwaar is en te laten zien dat dit tot iets onmogelijks leidt, met klassieke bewijzen zoals de irrationaliteit van de wortel uit 2.

Gevorderd30 minLes

Werkblad om te printen

Definitie

Een bewijs uit het ongerijmde (ook indirect bewijs genoemd) bewijst een bewering

P

via een omweg: je neemt aan dat

P

onwaar is en laat zien dat die aanname tot iets onmogelijks leidt. Omdat correct redeneren uit een ware aanname nooit iets onmogelijks kan opleveren, moet de aanname fout zijn, dus is

P

waar.

De methode heeft vier stappen:

1.Neem de negatie aan: de eerste regel is "Stel, uit het ongerijmde, dat $\neg P$ ."
2.Redeneer met definities en bekende feiten, precies zoals in een direct bewijs.
3.Bereik een tegenspraak: een bewering $Q$ en haar tegendeel $\neg Q$ gelden allebei (bijvoorbeeld " $a/b$ is volledig vereenvoudigd" en " $a$ en $b$ zijn allebei even"), of een bekend feit wordt geschonden (zoals $1 = 0$ ).
4.Concludeer: de aanname $\neg P$ was onwaar, dus $P$ is waar.

In symbolen: als

\neg P \Rightarrow (Q \land \neg Q)

, dan geldt

P

. Dit werkt omdat

Q \land \neg Q

altijd onwaar is. Kies in de interactieve waarheidstabel verderop op deze pagina NIET om te zien dat

\neg P

altijd het tegendeel van

P

is, en kies dan EN: in de twee rijen waarin

Q

het tegendeel van

P

is (O, W en W, O), is

P \land Q

gelijk aan O. Dus

P \land \neg P

is O in elke rij (W = waar, O = onwaar).

De negatie goed opschrijven is de belangrijkste regel van het bewijs:

" $\sqrt{2}$ is irrationaal" wordt " $\sqrt{2}$ is rationaal"
"Er zijn oneindig veel priemgetallen" wordt "Er zijn maar eindig veel priemgetallen"
"Er is geen grootste even getal" wordt "Er is een grootste even getal"
" $x > 5$ " wordt " $x \le 5$ "
"Elk ... heeft de eigenschap" wordt "Minstens één ... heeft de eigenschap niet"

Uit het ongerijmde of via contrapositie? Een bewijs via contrapositie (vorige les) bewijst "als

p

, dan

q

" door alleen

\neg q

aan te nemen en naar één vast doel toe te werken:

\neg p

. Een bewijs uit het ongerijmde neemt aan dat de hele bewering onwaar is (bij een als-dan-bewering:

p

\neg q

samen) en mag bij elke onmogelijkheid eindigen.

Probeer het meteen

Je wilt uit het ongerijmde bewijzen dat

\sqrt{3}

irrationaal is. Wat is de juiste eerste regel?

Uitgewerkte voorbeelden

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

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

Veelgemaakte fouten

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

Waarom het fout is: 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".

$x > 5$ ontkennen als $x < 5$

Waarom het fout is: 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$ .

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

Waarom het fout is: 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.

Een verrassend resultaat voor een tegenspraak houden

Waarom het fout is: 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.

Interactieve visualisatie

Waarheidstabel

Operator selecteren

P ∧ Q

P	Q	P ∧ Q
O	O	O
O	W	O
W	O	O
W	W	W

W= WaarO= Onwaar

Interactieve sandbox

Expressiecalculator

Probeer deze:

Geschiedenis

Nog geen berekeningen

Oefenproblemen

18 opgaven

Opgave 1 van 18

Makkelijk

Je wilt uit het ongerijmde bewijzen dat $\sqrt{3}$ irrationaal is. Wat is de juiste eerste regel?

Waarom het belangrijk is

Sommige van de beroemdste resultaten uit de wiskunde zijn het makkelijkst te bewijzen uit het ongerijmde:

Irrationale getallen: de Grieken bewezen zo'n 2500 jaar geleden dat $\sqrt{2}$ geen breuk is, en dat veranderde hoe mensen over getallen dachten
Priemgetallen: het bewijs van Euclides dat de priemgetallen nooit opraken, wordt nog in elke cursus getaltheorie gebruikt
Informatica: het ladenprincipe verklaart waarom twee bestanden dezelfde korte vingerafdruk kunnen krijgen (een hash-botsing) en waarom geen compressie elk bestand kleiner kan maken
Puzzels: een sudoku oplossen betekent vaak zeggen "als in dit vakje een 5 stond, kwamen er twee 5'en in dezelfde rij, dus het is geen 5"
Alledaags redeneren: detectives en artsen sluiten mogelijkheden uit door te laten zien dat ze tot iets onmogelijks leiden

Telkens wanneer een bewering zegt dat iets NIET bestaat (geen grootste getal, geen breuk gelijk aan

\sqrt{2}

), is bewijs uit het ongerijmde meestal het natuurlijke gereedschap.

Toepassingen in de echte wereld

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.

Voorbeeld:

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.

1Probeer het zelf

In een la liggen losse sokken in 5 verschillende kleuren, en het is te donker om ze te zien.

Hoeveel sokken moet je pakken om zeker twee van dezelfde kleur te hebben?

Stap 1: Schrijf de wiskundige uitdrukking

Aantal kleuren plus één:

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.

Voorbeeld:

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.

2Probeer het zelf

Een systeem geeft elk bestand een code van 3 cijfers, van 000 tot en met 999.

Hoeveel bestanden garanderen dat twee ervan dezelfde code hebben?

Stap 1: Schrijf de wiskundige uitdrukking

Aantal codes plus één:

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.

Voorbeeld:

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.

3Probeer het zelf

Een rekenmachine toont $\sqrt{2} \approx 1{,}4142$ .

Controleer dat 1,4142 niet precies de wortel uit 2 is.

Stap 1: Schrijf de wiskundige uitdrukking

Kwadrateer het decimale getal:

Belangrijke punten

1Een bewijs uit het ongerijmde neemt aan dat de bewering onwaar is en laat zien dat dit tot iets onmogelijks leidt
2De eerste regel is de juiste negatie: "oneindig veel" wordt "maar eindig veel", $x > 5$ wordt $x \le 5$ , "elk" wordt "minstens één ... niet"
3Een tegenspraak bestaat uit twee beweringen die niet allebei waar kunnen zijn, zoals $Q \land \neg Q$ , dat in elke rij van een waarheidstabel onwaar is
4Klassieke resultaten die zo bewezen worden: $\sqrt{2}$ is irrationaal, er zijn oneindig veel priemgetallen, er is geen grootste even getal en geen kleinste positief rationaal getal
5Het ladenprincipe: als meer dan $n$ voorwerpen in $n$ laden gaan, bevat een la minstens twee voorwerpen
6Een bewijs via contrapositie bewijst rechtstreeks "als niet q, dan niet p", terwijl een bewijs uit het ongerijmde aanneemt dat de hele bewering onwaar is en naar welke onmogelijkheid dan ook zoekt

Veelgestelde vragen

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.

Woordenlijst

Bewijs uit het ongerijmde: Een bewijs dat aanneemt dat de bewering onwaar is en daaruit iets onmogelijks afleidt, zodat de bewering waar moet zijn (ook indirect bewijs genoemd)
Tegenspraak: Twee beweringen die niet allebei waar kunnen zijn, zoals $Q$ en $\neg Q$ ; de bewering $Q \land \neg Q$ is altijd onwaar
Negatie: Het tegendeel van een bewering, geschreven als $\neg P$ ; ze is waar precies wanneer $P$ onwaar is
Irrationaal getal: Een reëel getal dat niet te schrijven is als een breuk $\frac{a}{b}$ van gehele getallen, bijvoorbeeld $\sqrt{2}$
Ladenprincipe: Als je meer dan $n$ voorwerpen in $n$ laden stopt, bevat minstens één la twee of meer voorwerpen (ook duivenhokprincipe genoemd)

Formulekaart

Bewijs uit het ongerijmde

\neg P \Rightarrow (Q \land \neg Q) \;\text{ dus }\; P

Als de aanname niet P tot een tegenspraak leidt, dan is P waar

Een tegenspraak is altijd onwaar

Q \land \neg Q = F

Een bewering en haar negatie kunnen nooit allebei waar zijn

Ladenprincipe

n + 1 \text{ voorwerpen in } n \text{ laden}

Minstens één la krijgt twee of meer voorwerpen

Meer over dit onderwerp

Definitie

Uitgewerkte voorbeelden

Veelgemaakte fouten

Interactieve visualisatie

Waarheidstabel

Interactieve sandbox

Expressiecalculator

Geschiedenis

Oefenproblemen

Waarom het belangrijk is

Toepassingen in de echte wereld

Bij elkaar passende sokken in het donker

Hash-botsingen in de informatica

Waarom een rekenmachine nooit de exacte wortel uit 2 toont

Belangrijke punten

Veelgestelde vragen

Woordenlijst

Formulekaart

Bewijs uit het ongerijmde

Een tegenspraak is altijd onwaar

Ladenprincipe

Meer over dit onderwerp

Introductie tot wiskundige bewijzen

Direct bewijs

Bewijzen in twee kolommen

Bewijzen in alineavorm