Zomercursus Wiskunde. Katholieke Universiteit Leuven Groep Wetenschap & Technologie. September 2008

Zomercursus Wiskunde Katholieke Universiteit Leuven Groep Wetenschap & Technologie September 2008

Logica, verzamelingenleer, functies en bewijstechnieken (versie 9 juli 2008)

Inleiding Omdat de behandelde topics niet of nauwelijks meer aan bod komen in het secundair onderwijs is deze module opgevat als een naslagwerk en bevat dus veel meer informatie dan in de zomercursus aan bod zal komen. De nieuwe begrippen worden dan ook uitgebreid ingevoerd met veel voorbeelden en oefeningen zodat deze module gemakkelijk kan dienen voor zelfstudie. De module wordt in Zomercursus B gespreid over drie lessen. Les 1: De formele logica, verzamelingenleer, functies(enkel de pijlennotatie) en gebruik van kwantoren. Les 2 en 3: Bewijzen van uitspraken met kwantoren, bewijstechnieken met de nadruk op bewijs uit het ongerijmde en bewijs door contrapositie. Voor eigenschappen van natuurlijke getallen: het bewijs door volledige inductie. In de tekst zijn veel oefeningen opgenomen, de oefeningen aangeduid met een (∗) zijn iets moeilijker. Om wiskundige definities en redeneringen te kunnen opschrijven hebben we een taal nodig, een communicatiemiddel waarin we onze ideeën exact kunnen formuleren. De meest voor de hand liggende keuze is onze moedertaal (of een andere levende taal), deze voldoet perfect zolang ze maar goed begrepen wordt door onze toehoorders. Maar verder moeten we ook gebruik maken van symbolen en notaties die universeel gekend zijn in de wetenschappelijke wereld. Daartoe voeren we de symbolische logica en de verzamelingenleer in. In de logica maken we duidelijke afspraken over de betekenis van de zo belangrijke logische connectieven en, of, niet, als . . . dan . . . We overlopen hoe we de waarheidswaarden van uitspraken kunnen natrekken en formaliseren. We bekijken ook de redeneervormen die gebruik maken van universele stellingen uit de logica, zoals bijvoorbeeld de negatiewetten of de wet van contrapositie. Om uitspraken te kunnen doen over objecten die behoren tot een geheel moeten we het begrip verzameling invoeren en ook de symbolen vastleggen die in de context van verzamelingen onontbeerlijk

2

Logica, verzamelingenleer, functies en bewijstechnieken

zijn. Uitspraken als deze eigenschap geldt voor alle elementen uit de verzameling of deze eigenschap geldt voor minstens één element uit de verzameling kunnen we steeds ondubbelzinnig noteren met behulp van kwantoren. Hierdoor krijgen we een krachtige formele wiskundige taal waar de exactheid en ´ e´ enduidigheid van de gevormde uitspraken de grootste troef is. Helaas is er een nadeel aan die formele taal: indien we wiskundige uitspraken en bijbehorende redeneringen consequent volledig in symbolen zouden neerschrijven, d.w.z. zonder gewone woorden te gebruiken, vervallen we in een puur formalisme met nog moeilijk ontcijferbare teksten tot gevolg. Dit kan natuurlijk niet de bedoeling zijn: ook een wiskundige tekst is bij voorkeur vlot leesbaar. Daarom pleiten we voor een gezond evenwicht in gebruik tussen enerzijds de gewone taal en anderzijds de formele en universele taal van de symbolische logica. We zullen in de wiskunde eigenlijk zelden op zo’n extreem formele wijze communiceren, maar eerder kiezen voor een zinvol, complementair gebruik van gewone taal en formules, op zodanige wijze dat beide elkaar goed ondersteunen. We gebruiken de formele taal als aanvulling en hulpmiddel omdat ze nu eenmaal onze ideeën exacter en compacter kan weergeven. Maar onze teksten moeten in eerst instantie goed leesbaar zijn en bestaan uit goed gevormde en grammaticaal correcte zinnen en moeten de voorleestest moeiteloos doorstaan. Kortom wiskundige teksten mogen nooit verworden tot een wirwar van pijltjes en kwantoren! Anderzijds mag het belang en de kracht van formeel wiskundig taalgebruik niet onderschat worden, het neemt een centrale plaats in in wiskundige logica en is zeer zinvol als kernachtige herformulering van definities, eigenschappen, stellingen en eventueel korte bewijzen. In het voorlaatste deel van de tekst bekijken we enkele veel gebruikte bewijsvormen uit de wiskunde, zoals een bewijs uit het ongerijmde of een bewijs door contrapositie. Voor eigenschappen die gelden voor alle natuurlijke getallen geven we voorbeelden van bewijzen door volledige inductie. Onnodig te zeggen dat we hierbij de nadruk leggen op de manier waarop de bewijzen worden neergeschreven. Tot slot voeren we in het laatste hoofdstuk op een pragmatische manier het functiebegrip in, als een grootheid die afhangt van een andere grootheid. Wat de notaties betreft introduceren we de enige wiskundig verantwoorde notatie m.n. de pijlennotatie waarin het definitiegebied en de doelverzameling intrinsiek deel uitmaken van de notatie, terwijl het functievoorschrift – dat nota bene bij de meeste functies niet eens bestaat (denk bijvoorbeeld aan een functie die de tijdsafhankelijkheid van de temperatuur weergeeft) – een eerder ondergeschikte rol speelt.

1

De symbolische logica

Wanneer wij een redenering willen meedelen in de wiskunde, dan gebruiken wij daarvoor een taal, in ons geval het Nederlands. Soms echter is het moeilijk de juiste bewoordingen te vinden om deze redenering exact uit te drukken. Bovendien heeft Zomercursus Wiskunde Groep Wetenschap & Technologie

1. De symbolische logica

3

ieder een eigen taalgevoel, wat tot gevolg kan hebben dat degene die een zin uitzendt en degene die de zin ontvangt, deze zin soms op verschillende wijze interpreteren. Doe je bijvoorbeeld aan een kleuter de belofte “Als je braaf bent, krijg je een zuurtje of een reep chocolade”, wat mag die kleuter dan verwachten? Kan hij mits hij braaf is, ook een zuurtje én een reep chocolade krijgen? En wat gebeurt er als hij niet braaf is? Krijgt hij dan niets, of werd er in de belofte niets over gezegd? Om deze mogelijkheid tot verwarring te vermijden onttrekt men de redeneervormen soms aan de gewone taal. Men gaat ze symboliseren. Dit gebeurt in een nieuwe wetenschap: de symbolische of formele logica. We beperken ons hier tot een kleine selectie van notaties uit de logica die soms gebruikt worden voor het formuleren van wiskundige definities, eigenschappen, stellingen en redeneringen.

1.1

Wiskundige beweringen

In de logica werken we met zogenaamde proposities. Het begrip propositie is een grondbegrip en wordt dus niet gedefinieerd. Het wordt iets duidelijker als we zeggen dat het taalkundig wordt weergegeven door een zinvolle mededelende volzin. Let op, zinnen met eenzelfde betekenis, al dan niet in een andere taal, bepalen dezelfde propositie. Voorbeelden 1.1 • “De aarde is een planeet”: een ware propositie. • “1 + 1 = 3”: een onware propositie • “De vakantie is voorbij”: een ware of onware propositie naargelang het tijdstip waarop de uitspraak gedaan wordt. Van een propositie wordt geëist dat ze waar is of onwaar.1 We spreken hier van tweewaardige logica. Er bestaan ook meerwaardige logica’s. Volgende volzinnen zijn dus geen proposities. Tegenvoorbeelden 1.2 • “Lag ik nu maar in de zon.” • “Bestaan er buitenaardse wezens?” • “Laten we gaan zitten.” • “n is een priemgetal.” De eerste drie zijn geen constaterende volzinnen; we kunnen ook niet nagaan of ze waar zijn of niet. Zij stellen dus geen proposities voor. De laatste zin is ook geen propositie 1

In plaats van te zeggen dat een bewering waar resp. onwaar is, zegt men ook wel dat een bewering waar resp. niet waar is, waar resp. vals is, voldaan resp. niet voldaan is, of dat een bewering geldt resp. niet geldt.

Zomercursus Wiskunde Groep Wetenschap & Technologie

4


omdat we de waarheidswaarde enkel kunnen nagaan als we aan n een waarde toekennen. Zo een zin heet een predikaat. De symbolen in het predikaat die een waarde moeten krijgen om tot een propositie te komen heten vrije variabelen. Het geheel van proposities en predikaten noemen we beweringen of uitspraken. Wij gebruiken letters als p en q om proposities aan te geven en schrijven bijvoorbeeld p(m, n) om een predikaat aan te geven met m en n als vrije variabelen.

1.2

Logische connectieven

In de wiskunde moeten we vaak bepalen of een gegeven propositie waar is of niet. Beweringen kunnen soms ingewikkeld zijn en opgebouwd zijn uit een aantal componenten die verbonden worden door ‘logische connectieven’. Het waar of onwaar zijn van een samengestelde bewering hangt af van het waar of onwaar zijn van haar componenten. Voorbeeld 1.3 Denken we terug aan de brave kleuter die een zuurtje krijgt of een reep chocolade. In de omgangstaal wordt hier vaak bedoeld dat de kleuter moet kiezen; hij krijgt het ene ofwel het andere, niet beide samen. In de logica is dit echter niet zo: met het connectief ‘of’, bedoelen we ofwel het ene, ofwel het andere, ofwel beide. Het symbool voor ‘of’ is ∨ en is afkomstig van het Latijnse woord vel met deze betekenis.2 We vinden dit terug in volgende definitie.

Definitie 1.4 (De disjunctie ‘of’) Als p en q beweringen zijn, dan noteren we de bewering ‘p of q’ met p ∨ q. De betekenis van p ∨ q kan het best verduidelijkt worden door middel van een waarheidstabel. Een bewering is ofwel waar ofwel niet waar (onwaar). De waarheid van p ∨ q hangt af van de waarheidswaarden van p en q zoals gegeven door de volgende tabel. Hierbij duidt ‘w’aan dat de bewering waar is en ‘o’dat de bewering onwaar is. p q p∨q w w w w o w o w w o o o

Links in de tabel staan de vier mogelijke ‘waarheidscombinaties’ van de beweringen p en q. Rechts in de tabel staat de daaruit volgende waarheidswaarde van p∨q. De derde regel van de tabel drukt dan bijvoorbeeld uit dat indien p niet waar en q wel waar is, dat dan p ∨ q waar is. 2

In het Latijn bestaat ook nog het woord aut, dat ‘ofwel’betekent maar dan in de exclusieve betekenis: ofwel het ene ofwel het andere, maar niet beide.



5

Voorbeeld 1.5 Als we de kleuter een zuurtje en een reep chocolade beloven, zal er groot protest ontstaan indien we hem niet beide lekkernijen geven. Hier komt de logica van de kleuter wel overeen met de wiskundige logica.

Definitie 1.6 (De conjunctie ‘en’) We gebruiken ‘en’ als we willen uitdrukken dat twee beweringen allebei waar zijn. Als p en q beweringen zijn, dan is ‘p en q’ de bewering die waar is als p en q allebei waar zijn en anders niet waar is. We schrijven p ∧ q. De waarheidstabel voor p ∧ q is de volgende. p q p∧q w w w w o o o w o o o o

Definitie 1.7 (De negatie ‘niet’) Als p een bewering is dan is ‘niet p’ de tegengestelde bewering, die waar is als p het niet is, en omgekeerd. We noteren dit met ¬p. Dit heet ook wel de negatie van p. De waarheidstabel voor ¬p is de volgende. p ¬p w o o w

Oefeningen 1.8 1. Welke van de volgende proposities zijn waar, welke zijn onwaar? (a) 5 > 0 ∧ 1 + 1 = 2

(b) 5 < 0 ∧ 1 + 1 = 2 (c) 5 < 0 ∨ 1 + 1 = 2

(d) 5 > 0 ∨ 1 + 1 = 2 (e) 3 < 2 ∨ 4 < 1 (f) 3 6 5

(g) 3 6 3 (h) 2 6 3 6 4 2. Stel de waarheidstabellen op voor de volgende beweringen. Zomercursus Wiskunde Groep Wetenschap & Technologie

6


(a) ¬(p ∧ q)

(b) (¬p) ∨ (¬q) (c) p ∧ (¬q)

(d) p ∧ (¬p) (e) p ∨ (¬p)

Dit doe je bijvoorbeeld voor oefening (a) door volgende tabel aan te vullen: p q w w w o o w o o

1.3

p∧q

¬(p ∧ q)

Implicaties

De wiskunde en ook het dagelijkse taalgebruik lopen over van beweringen van het type “Als . . . , dan . . . ”. We stellen vast dat de kloof tussen wat we ermee bedoelen in de omgangstaal en in de wiskunde, hier het grootst is, we nemen die beweringen dan ook zeer uitgebreid onder de loupe. Voorbeelden 1.9 (1) Veronderstel dat n een natuurlijk getal is. Beschouw volgende bewering: “Als n een viervoud is, dan is n even.” (2) Veronderstel dat n een natuurlijk getal is. Beschouw volgende bewering: “Als n een drievoud is, dan is n even.” (3) Beschouw volgende bewering: “Als een mus een reptiel is, dan is 1 + 1 = 3.” (4) Beschouw volgende bewering: “Als een mus een reptiel is, dan is 1 + 1 = 2.” (5) Een bezorgde vader zegt tegen zijn ‘studerende’ zoon: “Als jij kan slagen zonder te studeren, dan ben ik Napoleon.” (6) Zelfde context als hierboven maar nu met een andere strategie: “Als je er door bent in juni, dan krijg je een brommer.” Dergelijke beweringen kunnen waar zijn of onwaar. Maar ze hebben hoe dan ook alle zes dezelfde structuur: Als p, dan q, Zomercursus Wiskunde Groep Wetenschap & Technologie

7


waarbij p en q staan voor beweringen (die op hun beurt waar of onwaar kunnen zijn). In de logica gebruikt men volgende notatie voor dergelijke beweringen: p⇒q en men leest dit als “p impliceert q” of gewoonweg als“als p, dan q” of nog als “q volgt uit p”. Oefening 1.10 Doe een gok naar de waarheidswaarde van elk van de bovenstaande beweringen. Vooreerst moeten we opmerken dat de Beweringen (3) en (4) ons nogal vreemd doen opkijken. Wat heeft die valse bewering over een mus te maken met de daaropvolgende som? Misschien verwachtte je het niet, maar volgens de logica zijn beide implicaties waar. In het dagelijks leven suggereert de uitspraak ‘p impliceert q’ dat er een causaal verband bestaat tussen p en q. Dat wil zeggen dat het waar zijn van q een gevolg is van het waar zijn van p. In de wiskundige betekenis van implicatie wordt geen causaal verband gesuggereerd. In de logica is een implicatie p ⇒ q altijd waar als p niet waar is, onafhankelijk van het al dan niet waar zijn van q. Dit laatste is misschien moeilijker te begrijpen maar werd door de Romeinen al vertaald in de spreuk “Ex falso sequitur quod libet” (Uit een foute bewering kun je alles concluderen.) Of vrij vertaald: “Als je de valse bewering p gelooft, moet je alles geloven.” Om die waarheidswaarden nog aannemelijker te maken zoemen we even in op de belofte in Bewering (6) die er in deze notatie als volgt uitziet: (je bent er door in juni) ⇒ (je krijgt een brommer) Bekijk alle mogelijke scenario’s voor Bewering (6). Elke studerende zoon (of dochter) voelt feilloos aan in welke scenario’s zijn (haar) vader zijn belofte “Als . . . , dan . . . ” houdt (de belofte is dus waar) en in welke scenario’s hij ze niet houdt (de belofte is dus onwaar). Enkel in het tweede scenario zal de student reden hebben om boos te zijn omwille van een gebroken belofte. scenario p is waar, q is waar, je bent er door in juni je krijgt een brommer p is waar, q is onwaar, je bent er door in juni je krijgt geen brommer p is onwaar, q is waar, je bent er niet door in je krijgt een brommer juni p is onwaar, q is onwaar, je bent er niet door in je krijgt geen bromjuni mer Zomercursus Wiskunde Groep Wetenschap & Technologie

belofte is waar onwaar

waar

waar

8


We kunnen dus besluiten met volgende definitie.

Definitie 1.11 (De implicatie “⇒”) Een implicatie is de bewering dat als een bepaalde bewering waar is dat dan ook een andere bewering waar is. We duiden dit aan met het symbool p ⇒ q (ook andere notaties worden wel gebruikt, zoals p → q) en we zeggen: ‘p impliceert q’ of ‘q volgt uit p’, of ‘als p, dan q’. p wordt wel eens het antecedens of de hypothese en q het consequens of de conclusie genoemd. De waarheidstabel voor p ⇒ q is de volgende. p q p⇒q w w w w o o o w w o o w Dus de enige manier waarop p ⇒ q niet waar is, is als p waar is en q niet.

De negatie van de implicatie p ⇒ q komt dus neer op zeggen dat p voldaan is en dat toch q niet voldaan is. De ontkenning van Bewering (6) is dus: “Je bent er door in juni en toch krijg je geen brommer.” Hier komen we later op terug. Overlopen we de waarheidswaarden van de overige beweringen. • Vermits een implicatie p ⇒ q altijd waar is als p onwaar is, is Bewering (5) een ware bewering, zelfs als die niet door Napoleon uitgesproken wordt. Inderdaad, het is een feit dat de eerste nog moet geboren worden die slaagt zonder te studeren, m.a.w. bij (5) is p niet waar. • Bewering (1) is wat de waarde van n ook moge zijn, altijd een ware bewering. Inderdaad, als p waar is, d.w.z. als n een veelvoud van 4 is, dan kan men gemakkelijk argumenteren dat n deelbaar moet zijn door 2 en dus even moet zijn; m.a.w. als p waar is, zal q waar zijn. Indien p niet waar is, d.w.z. indien n geen veelvoud is van 4; dan is de implicatie p ⇒ q sowieso waar. • De waarheidwaarde van (2) hangt af van de keuze van n. Als je bijvoorbeeld n = 5 had gekozen wordt Bewering (2): “als 5 een drievoud is, dan is 5 even”. Dit is een ware bewering om de eenvoudige reden dat 5 geen drievoud is, waardoor de p in deze bewering vals is, en dus de implicatie p ⇒ q waar is, zelfs als in dit geval (met n = 5) q manifest vals is.3 Voor andere keuzes van n kan (2) evenwel 3

Bewering (2) voor n = 5 is vanuit logisch standpunt eigenlijk helemaal analoog aan bewering (5)



9

een valse bewering zijn. Neem bijvoorbeeld n = 9, dan is n een drievoud (dus p is waar), maar n is natuurlijk niet even (dus q is hier vals). • Beweringen (3) en (4) zijn waar omdat de bewering p vals is. Definitie 1.12 In de context van implicaties hanteert men ook vaak de terminologie nodige voorwaarde en voldoende voorwaarde. Veronderstel dat de implicatie p ⇒ q geldt. Een alternatieve manier om dit uit te drukken is: q is een nodige voorwaarde voor p, of, anders gezegd, opdat p zou gelden, is het nodig dat q geldt. Immers, als q vals is, kan p onmogelijk waar zijn. Men kan hetzelfde nog anders zeggen: p is een voldoende voorwaarde voor q, of nog opdat q zou gelden, is het voldoende dat p geldt.

Beschouw bijvoorbeeld de (ware) implicatie (1) van hierboven: “als n een viervoud is, is n even.” Alternatieve manieren om precies hetzelfde te zeggen zijn: opdat n een viervoud zou zijn, is het nodig dat n even is, of opdat n even zou zijn, is het voldoende dat n een viervoud is. In dit voorbeeld is meteen duidelijk dat een nodige voorwaarde niet voldoende hoeft te zijn en omgekeerd. Opmerking 1.13 (Veel gemaakte redeneerfout) Veronderstel dat men een bewering heeft van de vorm p ⇒ q waarvan men weet dat ze waar is (bijvoorbeeld Bewering (1): “(n een viervoud) ⇒ (n even))”. Soms trekt men dan verkeerdelijk de conclusie dat als p niet waar is, dan ook q niet waar zal zijn. In de context van Bewering (1) zou dat betekenen dat men zou besluiten dat als een getal n geen viervoud is, het niet even is. Dit is uiteraard fout, zo is 6 geen viervoud, maar wel even! Als je weet dat de bewering p ⇒ q een ware bewering is, en je weet dat p niet geldt, dan kan je niets besluiten over de geldigheid van q ! Dit is eigenlijk een evidentie. Toch leert de ervaring dat daar in de praktijk al te vaak tegen gezondigd wordt. als die gezegd wordt door iemand die niet Napoleon is. In beide gevallen zijn immers zowel p en q vals.


10


Wellicht komt dat doordat men in het dagelijks taalgebruik dikwijls slordig omspringt met het gebruik van “als . . . , dan . . . ” en daarbij soms meer bedoelt dan men strikt genomen zegt. Beschouw bijvoorbeeld Bewering (6) hierboven die de vader tegen zijn zoon zegt. Wat de vader behalve Bewering (6) wellicht ook bedoelde, zonder het evenwel expliciet te zeggen, is: “als je er niet door bent in juni, kan je naar die brommer fluiten”, of wat op hetzelfde neerkomt, “als je die brommer wil krijgen, dan moet je er door zijn in juni”. Als we met p de bewering “je bent er door in juni” aanduiden en met q de bewering “je krijgt een brommer”, dan zegt de vader in (6) “p ⇒ q” maar daar bovenop bedoelt hij stilzwijgend eigenlijk ook “q ⇒ p”. In de wetenschap en in de wiskunde in het bijzonder kunnen we ons natuurlijk dergelijk slordig en dubbelzinnig taalgebruik niet veroorloven. Heel veel wiskundige resultaten (proposities, stellingen, . . . ) zijn geformuleerd in de vorm: “Als bepaalde voorwaarden voldaan zijn, dan geldt volgende conclusie.” En in tegenstelling met het soms onzorgvuldig dagdagelijks taalgebruik, wordt daar dan niets meer mee bedoeld dan wat er letterlijk staat. M.a.w. als de voorwaarden van de stelling niet vervuld zijn, dan wordt niets beweerd over de geldigheid van de conclusie. Oefeningen 1.14 1. Beschouw de bewering: Als het vandaag dinsdag is, dan is het morgen zondag. Bepaal de waarheidswaarde van deze implicatie, (a) als ze uitgesproken wordt op dinsdag, (b) als ze uitgesproken wordt op woensdag, (c) als ze uitgesproken wordt op zaterdag. Wat denk je van de bewering: Als het vandaag zaterdag is, dan is het morgen zondag, naargelang de dag dat dit wordt uitgesproken. 2. Beschouw volgende bewering uit een advertentie: Als je dagelijks deze vermageringspillen slikt dan vermager je per maand zeker drie kilo. Hoe kan je deze bewering ontkrachten? Zomercursus Wiskunde Groep Wetenschap & Technologie

11


1.4

Equivalenties

We keren nog even terug naar het vader-zoon-tafereeltje van (6) uit vorige paragraaf. Als we ondubbelzinnig willen formuleren wat de vader in (6) wellicht echt bedoelde, komen we tot de uitspraak: “Je krijgt een brommer als en slechts als je er door bent in juni.” (1) en dit is eigenlijk de combinatie van twee implicaties: “Als je er door bent in juni, dan krijg je een brommer” én “Als je een brommer krijgt, dan ben je er door in juni.” Met de notatie p en q zoals in de vorige paragraaf, kunnen we de uitspraak (1) weergeven als “q als en slechts als p”, (2) wat dus de combinatie is van twee implicaties: p⇒q én

q ⇒ p.

We noteren uitspraak (2) kortweg door q ⇔ p.

Definitie 1.15 (De equivalentie “⇔”) De implicatie q ⇒ p is de omkering van de implicatie p ⇒ q. Als beide implicaties gelden dan schrijven we p ⇔ q en we zeggen dat p en q equivalent zijn. Dus p⇔q

betekent

(p ⇒ q) ∧ (q ⇒ p).

De waarheidstabel voor p ⇔ q is de volgende. p q w w w o o w o o

p⇒q w o w w

q⇒p w w o w

p⇔q w o o w

In wiskundige bewijzen wordt p ⇔ q vaak uitgesproken als ‘p als en slechts als q’, of in het kort ‘p asa q’. Als p ⇔ q dan noemen we p ook wel een nodige en voldoende voorwaarde voor q en omgekeerd q een nodige en voldoende voorwaarde voor p. Uit de waarheidstabel zien we dat p ⇔ q waar is als p en q allebei waar zijn of allebei niet waar zijn. Als een van de twee waar is en de andere niet dan is p ⇔ q niet waar. Zomercursus Wiskunde Groep Wetenschap & Technologie

12

1.5


Voorrangsregels

In ingewikkelde beweringen kunnen een aantal connectieven gecombineerd worden. Hiervoor gelden de volgende voorrangsregels ()

¬

∧

∨

⇒/⇐/⇔

waarbij de haakjes ( ) de eerste voorrang hebben en de implicatie ⇒ (of de gelijkwaardige connectieven ⇐ en ⇔) de laatste. Als er verwarring dreigt over de volgorde dan is het altijd aan te raden om haakjes te zetten. Met bedoelen we dus

¬p ⇒ q ∨ r (¬p) ⇒ (q ∨ r)

en het kan hier ook geen kwaad om de haakjes te zetten. Als we iets anders zouden bedoelen dan moeten we zeker haakjes zetten.

1.6

Tautologie¨ en en contradicties

Voorbeeld 1.16 Stel dat p de propositie “het is mooi weer” voorstelt, dan betekent ¬(¬p) “het is niet zo dat het geen mooi weer is”. Wat, als we goed nadenken, precies op hetzelfde neerkomt als de eerste uitspraak. Als je tweemaal ontkent, heb je niets gedaan. M.a.w. geldt p ⇔ ¬(¬p). Stel de waarheidstabel op van deze logische formule. Wat stel je vast? Voorbeeld 1.17 We pikken het voorbeeld van de belofte in Bewering (6) uit Voorbeelden 1.9 terug op. (je bent er door in juni) ⇒ (je krijgt een brommer). We hebben reeds opgemerkt dat de negatie van de implicatie p ⇒ q gelijk staat met zeggen dat p voldaan is en dat toch q niet voldaan is. De ontkenning van Bewering (6) is dus: Je bent er door in juni en toch krijg je geen brommer. In logische formules vertaald, wordt dit: ¬(p ⇒ q) ⇔ (p ∧ ¬q).

Deze equivalentie heeft de waarheidswaarde waar, ongeacht de waarheidswaarden van de verschillende proposities die er in voorkomen. Zo’n formule noemt men een tautologie. Zomercursus Wiskunde Groep Wetenschap & Technologie

13


Oefening 1.18 Ga laatste bewering na, stel de waarheidstabel op voor ¬(p ⇒ q) ⇔ (p ∧ ¬q). Dit doe je door volgende tabel aan te vullen. p q ¬q p ⇒ q ¬(p ⇒ q) p ∧ ¬q ¬(p ⇒ q) ⇔ (p ∧ ¬q) w w w o o w o o Voorbeeld 1.19 Beschouw weer de (ware) implicatie (1) van hierboven: als n een viervoud is, is n even. Anders gezegd: opdat n een viervoud zou zijn, is het nodig dat n even is, Het is overduidelijk dat, als de nodige voorwaarde niet voldaan is, dus n niet even is, zeker niet kan gelden dat n een viervoud is. In logische formules vertaald met p de bewering (n is een viervoud) en q de bewering (n is even) voelen we aan dat p ⇒ q impliceert dat ¬q ⇒ ¬p. Maar je kan evengoed nagaan dat het omgekeerde ook geldt. Stel dat ¬q ⇒ ¬p d.w.z. als voor een getal het feit dat het “niet even” zijn, impliceert dat het “geen viervoud” kan zijn, is het “even” zijn een nodige voorwaarde om een “viervoud” te zijn of er geldt p ⇒ q. ¬q ⇒ ¬p impliceert dat p ⇒ q. Met andere woorden lijkt

(p ⇒ q) ⇔ (¬q ⇒ ¬p)

een tautologie te zijn. Dit is algemeen zo. Ga dit na met behulp van een waarheidstabel. Deze zeer belangrijke tautologie heet de wet van contrapositie. Voorbeeld 1.20 Door de definitie van de negatie is het makkelijk in te zien dat voor elke propositie p geldt dat als p waar is automatisch ¬p niet waar is en omgekeerd dat als p onwaar is ¬p wel waar is, m.a.w. de conjunctie p ∧ ¬p heeft als waarheidswaarde altijd onwaar, onafhankelijk of p waar is of niet. Zo’n bewering noemt men een contradictie of tegenspraak. Uiteraard is de negatie van een contradictie een tautologie. Ga na dat de negatie van de contradicitie (p ∧ ¬p) equivalent is met de tautologie (p ∨ ¬p). Deze tautologie noemt men de wet van de uitgesloten derde. Zomercursus Wiskunde Groep Wetenschap & Technologie

14


Definitie 1.21 Een bewering samengesteld uit verschillende proposities is een tautologie of logische stelling als haar waarheidswaarde altijd waar is onafhankelijk van de waarheidswaarde van de verschillende proposities waaruit ze bestaat. Een contradictie of tegenspraak is een samengestelde bewering die altijd onwaar is, voor alle mogelijke waarden van de voorkomende proposities.

Contradicties zullen een belangrijke rol spelen bij de bewijstechniek bewijzen uit het ongerijmde. We komen hier later op terug. De logica telt vele tautologieën, vooral de equivalenties zijn handig omdat ze ons toelaten beweringen te vervangen door equivalente beweringen die soms beter te begrijpen zijn. Wij beperken ons hier tot de belangrijkste.

Stelling 1.22 (Tautologi¨ en of logische stellingen)

¬(¬p) ⇔ p ¬(p ∧ q) ⇔ (¬p) ∨ (¬q) ¬(p ∨ q) ⇔ (¬p) ∧ (¬q) ¬(p ⇒ q) ⇔ (p ∧ ¬q) (p ⇒ q) ⇔ (¬p ∨ q) (p ⇒ q) ⇔ (¬q ⇒ ¬p) (p ⇒ q) ∧ (q ⇒ r) ⇒ (p ⇒ r) p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) q ⇔ (¬q ⇒ (p ∧ ¬p)) p ∨ ¬p

dubbele negatie negatiewet van De Morgan voor ∧ negatiewet van De Morgan voor ∨ negatie van ⇒ verband ⇒ en ∨ contrapositie transitiviteit van ⇒ distributiviteit van ∧ t.o.v. ∨ distributiviteit van ∨ t.o.v. ∧ redenering uit het ongerijmde de wet van de uitgesloten derde

Oefeningen 1.23 1. Controleer met waarheidstabellen dat al deze wetten tautologiën zijn. 2. Beschouw de uitspraak: “als het mooi weer is ga ik fietsen”. Definieer de nodige proposities en vertaal deze zin in een logische formule. Ontken de formule en vertaal de uitspraak terug in een betekenisvolle zin. Als ik mijn belofte houd en je komt mij fietsend tegen, kan je dan iets zeggen over het weer? Wanneer kan je zeker besluiten dat het slecht weer is? Wat moet ik doen als het slecht weer is? Zomercursus Wiskunde Groep Wetenschap & Technologie


15

3. Beschouw de uitspraak: “als je braaf bent, krijg je een zuurtje of een reep chocolade”. Definieer de nodige proposities en vertaal deze zin in een logische formule. Pas contrapositie toe en herformuleer de nieuwe formule in een betekenisvolle zin. Ontken de uitspraak en herformuleer in een betekenisvolle zin. 4. Beschouw de uitspraak: “als je goed werkt of steekpenningen geeft ben je erdoor in juli”. Pas contrapositie toe en herformuleer de nieuwe formule in een betekenisvolle zin. 5. Beschouw de uitspraak: “je bent slim of je slaagt mits je hard studeert”. Definieer de nodige proposities en vertaal deze zin in een logische formule. Ontken de uitspraak en herformuleer in het een betekenisvolle zin. 6. Beschouw de uitspraak: “als ik praat, dan word ik gestraft”. Welke van de volgende uitspraken zijn hiermee gelijkwaardig. (a) Als ik gestraft word, dan heb ik gepraat. (b) Als ik niet gestraft word, dan heb ik niet gepraat. (c) Als ik niet praat, dan word ik niet gestraft. (d) Ik praat niet of ik word gestraft. 7. Beschouw de uitspraak: “ben je jong of klein, dan kan je gratis naar het pretpark.” Welk van volgende uitspraken is hiermee equivalent. (a) Als je moet betalen voor het pretpark, dan ben je noch jong noch klein. (b) Als je moet betalen voor het pretpark, dan ben je geen jonge kleine. 8. Beschouw de uitspraak: “van sporten word je gezond en leef je lang.” Vertaal deze uitspraak in een logische formule en toon d.m.v. tautologieën aan dat hij equivalent is met “van sporten word je gezond en van sporten leef je lang.” 9. Bewijs de wet van gevalsonderscheid: ((p ∨ q) ⇒ r) ⇔ (p ⇒ r) ∧ (q ⇒ r). Illustreer met een uitspraak. 10. Zijn volgende redenering juist? (a) Als ik hard werk, gaat mijn inkomen omhoog. Mijn inkomen gaat omhoog, dus ik werk hard. (b) Sporten is gezond. Indien sporten gezond is, zijn ijsberen groen. Dus ijsberen zijn groen. (c) Investeren maakt managers gelukkig. Als managers gelukkig zijn, ben ik dat ook. Van inversteren word ik gelukkig. Zomercursus Wiskunde Groep Wetenschap & Technologie

16


(d) Als ik met de fiets naar de les ga, ben ik moe als ik aankom. Ik ben altijd moe als ik in de les aankom, dus ga ik steeds met de fiets naar de les. 11. Trek (indien mogelijk) uit de volgende uitspraken relevante conclusies: (a) Als ik zwem, ben ik nat. Ik ben niet nat. (b) Als de burgemeester heeft gelogen, dan krijgt hij rode oren. De burgemeester heeft rode oren. (c) Als mijn informaticaprogramma geen fouten bevat, trakteer ik. Als ik trakteer heeft iedereen slagroom rond zijn mond. Iedereen heeft een schone mond. (d) Als je veel sport ben je gezond. Ik sport niet veel. 12. Kan je zo meteen zien of volgende twee beweringen equivalent zijn? (a) Als je morgen les wiskunde hebt, dan is er vandaag les chemie, of, als je vandaag geen toets fysica hebt, dan heb je morgen geen les wiskunde. (b) Als je morgen les wiskunde hebt, dan heb je vandaag les chemie of een toets fysica. Vertaal beide beweringen in een logische formule, definieer zelf de proposities die je daarvoor nodig hebt. Toon dan aan dat de twee formules equivalent zijn met een waarheidstabel.

2 2.1

De taal van verzamelingen Basisbegrippen, symbolen en terminologie

In de wiskunde hebben we het vaak over een aantal dingen die een geheel vormen, denk maar de even getallen, de breuken, de rechten in een vlak, de punten op een rechte enz. Dit vage begrip willen eenduidiger formaliseren.

Definitie 2.1 – Met het begrip verzameling is iedereen eigenlijk intu¨ıtief vertrouwd. Het is een grondbegrip en zullen we hier op dit beginnend niveau niet exact definiëren. Een eerste poging tot definitie zou kunnen zijn: een verzameling is een geheel van objecten zodanig dat men van ELK object ondubbelzinnig kan zeggen of het al dan niet tot dat geheel behoort. Men zegt ook wel: een verzameling is VOLLEDIG bepaald door de objecten die ertoe behoren. In regel wordt een verzameling aangeduid met een hoofdletter, maar je zal merken dat dit niet altijd kan.


17

2. De taal van verzamelingen

– De objecten die tot een verzameling behoren, noemt men de elementen van die verzameling. Ze worden ‘vaak’ aangeduid met een kleine letter. Als een object a tot een verzameling A behoort noteert men a ∈ A (lees: “a is een element van A”), als een object b niet tot A behoort, noteert men b ∈ / A. – Met A ∋ x bedoelen we dat de verzameling A het element x bevat en dit is dus equivalent met x ∈ A. Analoog gebruiken we A 6∋ x. – De lege verzameling, genoteerd met ∅, is de unieke verzameling zonder elementen. – Indien A en B verzamelingen zijn, dan hebben we dat A gelijk is aan B als en slechts als A en B dezelfde elementen hebben. Men noteert A = B. – Als A en B verzamelingen zijn en elk element van A ook tot B behoort, dan zegt men dat A een deelverzameling is van B; notatie: A ⊂ B. Dit betekent dat B ook een deelverzameling is van zichzelf, zodat B ⊂ B. In sommige teksten gebruikt men de notatie ‘⊆’ in plaats van ‘⊂’ om te benadrukken dat de verzamelingen ook gelijk mogen zijn.4 De relatie A ⊂ B heet de inclusie van A in B. – We schrijven A ⊂ 6 B of A * B om aan te duiden dat A geen deelverzameling van B is. We noteren A B als geldt dat A ⊂ B maar A 6= B – We noemen A een echte deelverzameling van B als A

B en A 6= ∅.

– Een verzameling A wordt eindig genoemd als ze slechts een eindig aantal elementen bevat; dat aantal noteert men dan met #A. – Een verzameling met één element noemt men een singleton. – Een verzameling met twee elementen noemt men een paar. – Sommige verzamelingen die vaak voorkomen hebben een standaardnotatie, zoals – N is de verzameling van natuurlijke getallen. – Z is de verzameling van gehele getallen. – Q is de verzameling van rationale getallen (breuken). – R is de verzameling van reële getallen. – C is de verzameling van complexe getallen.


18


Er zijn verschillende manieren om een verzameling te definiëren. Notaties 2.2 1. Door opsomming: De elementen worden opgesomd, om aan te geven dat ze samen een verzameling vormen worden ze tussen accolades geplaatst. De verzameling A van de arabische cijfers is A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. De verzameling B van de even getallen is B = {0, 2, 4, 6, 8, 10, 12, · · · }. waarbij de puntjes betekenen ‘enzovoorts’. De volgorde waarin de elementen worden opgesomd, heeft geen belang voor het bepalen van een verzameling. Hoe dikwijls je een ding ook opsomt, in een verzameling telt het maar voor één element. Dus de arabische cijfers kan ook gedefiniëerd worden als A = {7, 2, 2, 6, 5, 4, 9, 8, 3, 3, 0, 1} en toch is #A = 10. 2. Door omschrijving: elementen die aan een voorwaarde voldoen Vorige verzameling B van de even getallen, kan ook als volgt worden weergegeven B = {x| x is een natuurlijk getal deelbaar door 2}. Men leest dit als “B is de verzameling van de elementen x waarvoor geldt dat x een natuurlijk getal is deelbaar door 2.” 3. Constructieve definitie: Een derde manier om verzamelingen weer te geven is door middel van een formule zoals in het voorbeeld C = {n2 | n ∈ N}. Hierin is C de verzameling van alle kwadraten van natuurlijke getallen. Dus een getal behoort tot C als en slechts als het kan geschreven worden als n2 voor zeker natuurlijk getal n. 4. Door een Venndiagram5 : Het is soms praktisch een verzameling A voor te stellen door een Venndiagram. Dit is een gesloten kring, de naam van de verzameling wordt buiten de kring geplaatst. De elementen van A worden door stippen binnen de kring voorgesteld. De stippen buiten de kring zijn dingen, die geen elementen van A zijn. We tekenen geen stippen op de kring. Niet alle elementen van A moeten worden weergegeven door een stip. 4

Laat hier geen verwarring ontstaan met de verwante symbolen < en 6 bij reële getallen. Het symbool < betekent hier strikt kleiner dan, terwijl 6 kleiner dan of gelijk aan betekent, zodat voor een x ∈ R het niet waar is dat x < x, maar je wel x 6 x kan zeggen. Bij verzamelingen daarentegen heeft het symbool ⊂ precies dezelfde betekenis als ⊆. 5 De Engelse wiskundige John Venn(1834-1923) voerde deze voorstellingswijze in een artikel gepubliceerd in 1880.


19


Voorbeeld 2.3 A = {5, 3, 7}

A .5

.3 .7 . Jan

.9

Opmerkingen 2.4 1. Het is handig voor veel voorkomende verzamelingen een speciale notatie in te voeren (a) De verzameling van de natuurlijke getallen zonder 0. N0 = {1, 2, 3, 4, 5, 6, · · · } = {x ∈ N | x 6= 0}. Met analoge notaties voor de andere getallenverzamelingen zonder 0. (b) De verzameling van de positieve reële getallen, (0 is een positief getal). R+ = {x ∈ R| x > 0}. Met analoge notaties voor de andere getallenverzamelingen. (c) De verzameling van de natuurlijke delers van een natuurlijk getal a. del a = {n ∈ N| n is een deler van a }.

(d) De verzameling van de natuurlijke veelvouden van een natuurlijk getal a. aN = {an| n ∈ N}. (e) De verzameling van de even getallen. 2N = {2n| n ∈ N}.

(f) De verzameling van de oneven getallen. 2N + 1 = {2n + 1| n ∈ N}.

2. De lege verzameling is deelverzameling van elke andere verzameling A, want, aangezien de lege verzameling geen elementen bevat, kunnen we geen element vinden in de lege verzameling dat niet tot A behoort, m.a.w. ∅ 6⊂ A is NIET waar, dus equivalent hiermee: ∅ ⊂ A is waar. 3. Uit de definities volgt dat A = B ⇔ A ⊂ B en A ⊃ B, waarin A ⊃ B een andere notatie is voor B ⊂ A. Dit betekent dat we de gelijkheid van twee verzamelingen A en B ook kunnen aantonen door de twee inclusies A ⊂ B en A ⊃ B te bewijzen. Zomercursus Wiskunde Groep Wetenschap & Technologie

20


4. Het is belangrijk om goed onderscheid te maken tussen de symbolen ∈ en ⊂. Ze zijn wel nauw verwant omdat x ∈ A ⇔ {x} ⊂ A. Voorbeelden 2.5 1. De verzameling van de mogelijke uitkomsten van de worp met één dobbelsteen worden genoteerd als {1, 2, 3, 4, 5, 6}. 2. Zij B de verzameling van alle Belgen. De deelverzameling V van de Belgische vrouwen is dan V = {x ∈ B | x is een vrouw}. In woorden: V is de verzameling van alle x-en uit B die vrouw zijn. Oefeningen 2.6 1. Bepaal de volgende verzamelingen door opsomming. A = {x ∈ N| x is een vijfvoud, groter dan 1 en kleiner dan 14} B = {x ∈ N| x is een gehele deler van 6} C = {x ∈ N| x is een oneven getal} 2. Bepaal de volgende verzamelingen door omschrijving. A = {1, 2, 3, 4, · · · } B = { lente, herfst, winter, zomer} C = {1, 3, 5, 7, · · · , 35} 3. Vul de juiste symbolen in. Kies uit ⊂, 6⊂, =, ∈, 6∈, ∋, 6∋ . Soms zijn er verschillende mogelijkheden, geef alle mogelijkheden. (1) 5 . . . N (2) {1, 3, 5, 7, 9, 11, . . . } . . . {x| x is een oneven getal} (3) {x| x is een roos} . . . {x| x is een bloem}

(4) {1, 3, 5, 7, 9} . . . 2

(5) {1} . . . {1, 3, 5, 7, 9}

(6) {1} . . . {{1}, {3}, {5}, {7}, {9}}

(7) {1, 3} . . . {{1}, {3}, {5}, {7}, {9}}

(8) {1, 3} . . . {1, 3, 5, 7, 9}

(9) {1, 3, 5, 7, 9} . . . ∅

(10) ∅ . . . {∅}



21

(11) ∅ . . . ∅

(12) {1, 3, {5, 7, 9}} . . . 5

(13) {1, 3, 5, 7, 9} . . . {p ∈ N| p is een priemgetal } (14) 2N + 1 . . . 2N0 − 1 = {2n − 1| n ∈ N0 }

4. Zijn volgende uitspraken waar of onwaar? • {x ∈ R | x2 + 1 = 0} = ∅.

• A = {1, 2, {3, 4}} heeft als elementen 1, 2 en de verzameling {3, 4}

• Zij B = {1, {1}}. Dan is {1} zowel een element als een deelverzameling van B. • {{1}} een geen deelverzameling van vorige verzameling B. • C = {∅} is leeg.

• C = {{∅}} is een singleton.

• 2N + 1 = 2N0 − 1 = {2n − 1| n ∈ N} 5. Omschrijf het interval [a, b], waarbij a, b ∈ R, als een verzameling. 6. Definieer de verzameling Q van de breuken met een constructieve definitie. 7. Hoe zou je Venndiagrammen tekenen van twee verzamelingen A en B, geef twee mogelijkheden, één voor willekeurige verzamelingen en één in het geval dat A ⊂ B. Veralgemeen tot drie verzamelingen, geef enkel het algemeen geval, nl. dat geen enkele inclusie gekend is. 8. Stel de getallen verzamelingen N, Z, Q, R, C voor in Venndiagrammen, zorg dat de verschillende inclusies duidelijk blijken uit de tekening. Duid ook volgende √ getallen 0, −1, 2/3, − 3, 5 − 6i aan. 9. Teken een Venndiagram voor de verzamelingen A = del 8 en B = del 9, duid ook alle elementen aan. 10. Teken een Venndiagram voor de verzamelingen A = del 4 en B = del 8, duid ook alle elementen aan.

2.2

Bewerkingen met verzamelingen

Met twee gegeven verzamelingen A en B kun je op een aantal manieren nieuwe verzamelingen bouwen: 6

genoemd naar René Descartes, Frans filosoof en wiskundige (1596 – 1650)


22


Definitie 2.7 – de doorsnede van A en B; notatie: A ∩ B. Lees: A doorsnede B. Dit is de verzameling van de elementen die behoren tot A en B. Dus A ∩ B = {x | x ∈ A ∧ x ∈ B}. Twee verzamelingen A en B zijn disjunct als A ∩ B = ∅. – de unie, of vereninging van A en B; notatie: A ∪ B. Lees: A unie B. Dit is de verzameling van de elementen die behoren tot A of B. Dus A ∪ B = {x | x ∈ A ∨ x ∈ B}. Als C = A ∪ B waarbij A ∩ B = ∅, dan noemt men C de disjuncte unie van A en B. – het verschil van A en B; notatie: A \ B. Lees: A min B. Dit is de verzameling van de elementen die behoren tot A maar niet tot B. Dus A \ B = {x | x ∈ A ∧ x ∈ / B}. Merk op dat A \ B 6= B \ A. – het cartesiaans6 product, ook de productverzameling van A en B genoemd; notatie: A × B. Lees: A maal B. Dit is de verzameling van de koppels (= geordende tweetallen) (a, b) waarbij a ∈ A en b ∈ B. Dus A × B = (a, b) a ∈ A ∧ b ∈ B . Als A en B eindige verzamelingen zijn, is A × B ook eindig en #(A × B) = #A · #B. Als A = B dan schrijven we A × A = A2 .

Er geldt dat twee koppels (a1 , b1 ) en (a2 , b2 ) gelijk zijn als en slechts als a1 = a2 en b1 = b2 . Let op dat bij een koppel de volgorde van belang is. Als a 6= b dan geldt (a, b) 6= (b, a). Dit is in tegenstelling tot de situatie bij verzamelingen. Als we een verzameling weergeven door de elementen op te noemen, dan doet de volgorde er niet toe. Er geldt dus {a, b} = {b, a}.

Vorige definities kunnen best ge¨ıllustreerd worden met Venndiagrammen.

BA

A

A

B


BA

A

B

B

A\ B

23


Voorbeelden 2.8 1. N = 2N ∪ (2N + 1) is een disjuncte unie. 2. [ 2, 4 [ ∩ ] 3, 5 [ = ] 3, 4 [. 3. del 8\ del 4 = {8}. 4. Het meest bekende voorbeeld van een cartesiaans product is het reële vlak, na keuze van een rechthoekig coördinatensysteem. R2 = {(x, y) | x, y ∈ R}. 5. Als X = {a, b, c} en Y = {1, 2}, dan is X × Y = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)} en Y × X = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}. Volgend deel van hoofdstuk 2. maakt geen deel meer uit van Zomercurus B

Eigenschappen 2.9 Voor twee verzamelingen A en B geldt, (a) A ∩ A = A, A ∪ A = A, A ∪ ∅ = A en A ∩ ∅ = ∅, (b) A \ A = ∅ en A \ ∅ = A, (c) A ∪ B = (A ∩ B) ∪ (A \ B) ∪ (B \ A) is een disjuncte unie.

Het gebeurt vaak dat de verzamelingen die we beschouwen deelverzamelingen zijn van een vaste verzameling, zoals bijvoorbeeld de reële getallen. Dit noemen we dan een universele verzameling die we meestal noteren met U.

Definitie 2.10 Gegeven een universele verzameling U. Het complement van een deelverzameling A ⊂ U, notatie Ac , is het verschil van U en A. Dus Ac = U \ A = {x ∈ U | x 6∈ A}.


24


De doorsnede, unie en complement voor verzamelingen komen overeen met de logische bewerkingen ‘en’, ‘of’ en ‘niet’.

Eigenschappen 2.11 Neem aan dat A, B en C deelverzamelingen zijn van een universele verzameling U. Dan geldt (a) (associativiteit) A ∪ (B ∪ C) = (A ∪ B) ∪ C en A ∩ (B ∩ C) = (A ∩ B) ∩ C. (b) (commutativiteit) A ∪ B = B ∪ A en A ∩ B = B ∩ A. (c) (distributiviteit) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) en A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). (d) (de wetten van De Morgan) (A ∪ B)c = Ac ∩ B c en (A ∩ B)c = Ac ∪ B c . (e) (complementering) A ∪ Ac = U en A ∩ Ac = ∅. (f) (dubbel complement) (Ac )c = A. Bewijs We kunnen deze eigenschappen bewijzen met Venndiagrammen. Bij wijze van voorbeeld tonen we de tweede distributieviteitseigenschap met een zogeheten klaverbladdiagram

A

B

A

B

C

C

A ∩ (B ∪ C) is dubbel gearceerd

(A ∩ B) ∪ (A ∩ C) is gearceerd of dubbel gearceerd

Opmerking 2.12 Stel x een element uit een universele verzameling U beschouw volgende beweringen p:x∈A

en

q:x∈B

en

r : x ∈ C.

Dan kan je bovenstaande eigenschappen vertalen door logische stellingen. Zoek in Stelling1.22 bijpassende stellingen voor eigenschap(c). Zomercursus Wiskunde Groep Wetenschap & Technologie


25

Hoe vertaal je dan de beweringen x ∈ Ac , x ∈ B c , x ∈ (A ∪ B)c en x ∈ (A ∩ B)c ? Zie je in waarom de eigenschap 2.11(d) de naam van De Morgan meekrijgt? Zie je hier een verband met een logische stelling uit de logica? Oefeningen 2.13 1. Zijn volgende uitspraken waar of onwaar? (a) N \ 0 = N0

(b) B = {1, {1}} \ {1} = {1} (c) N \ 2N = 2N + 1

(d) R\ ] 2, 5 ] =] − ∞, 2 [ ∪ [ 5, +∞[

(e) R \ Q is de verzameling van de irrationale getallen.

2. Ga met behulp van een Venndiagram na dat A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). A, B, C zijn willekeurige verzamelingen. 3. Ga eigenschap 2.9 (c) na met een Venndiagram. 4. Ga eigenschap 2.11 (d) na met een Venndiagram.

Definitie 2.14 De machtsverzameling7 (powerset) P (A) van een verzameling A is de verzameling van alle deelverzamelingen van X. Dus P (A) = {X | X ⊂ A}.

Voorbeeld 2.15 Als bijvoorbeeld A = {a, b, c}, dan P (A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, A}. De lege verzameling ∅ is een element van de machtsverzameling van elke verzameling A omdat ∅ ⊂ A voor elke A. We begrijpen de naamgeving van de machtsverzameling beter als we volgende eigenschap aantonen. Omwille van eigenschap 2.16 wordt in sommige handboeken i.p.v. P (A) de notatie 2A gebruikt als notatie voor de machtsverzameling van de verzameling A. 7


26


Eigenschap 2.16 Als A een eindige verzameling is met #A = n dan is #P (A) = 2n . We geven een idee van hoe het bewijs kan verlopen. We berekenen het aantal deelverzamelingen van verzamelingen met 0,1,2, · · · elementen. deelverzameling van aantal ∅ = {} {} 1 = 20 {a} {} en {a} 2 = 21 {a, b} {}, {a} en {b}, {a, b} 4 = 22 {a, b, c} {}, {a} {b}, {a, b} en {c}, {a, c} {b, c}, {a, b, c} 8 = 23 .. .. .. . . . Telkens als we een element aan de verzameling toevoegen, verdubbelt het aantal deelverzamelingen, omdat we enerzijds de vorige deelverzamelingen behouden en anderzijds nieuwe deelverzamelingen verkrijgen door het nieuwe element aan die vroegere deelverzamelingen toe te voegen. We introduceerden de begrippen doorsnede en unie, telkens van twee verzamelingen. Het komt vrij vaak voor in de wiskunde dat we deze begrippen willen uitbreiden tot een willekeurig aantal verzamelingen. Definitie 2.17 Veronderstel dat I een verzameling is en dat Xi een verzameling is voor elke i ∈ I. De veranderlijke i dient hier als index en de verzameling I wordt kortweg een indexverzameling genoemd. T S Dan definieert men de doorsnede, i∈ I Xi , en de unie, i∈ I Xi , van deze verzamelingen als volgt: \ Xi = {x | x ∈ Xi voor elke i ∈ I} i∈ I

en

[

i∈ I

Xi = {x | er is een i ∈ I met x ∈ Xi }.

Deze nieuwe, algemenere, notaties voor doorsnede en unie zijn vaak bijzonder handig. De indexverzameling I kan eindig of oneindig zijn, en bijgevolg kan men op deze manier doorsnede en unie van een oneindige familie van verzamelingen gaan beschouwen. Zomercursus Wiskunde Groep Wetenschap & Technologie

27

3. Logica met kwantoren

Voorbeeld 2.18 1 1 Beschouw de intervallen Xn = ,1 + met n ∈ N0 . Probeer in te zien dat n n [ \ Xn = ] 0, 2 ] en Xn = {1}. n∈N0

n∈N0

Oefeningen 2.19 1. Probeer in te zien welke verzameling bepaald wordt door de volgende unies en/of doorsnedes. \ 1 (a) 0, n n∈ N0 \ 1 (b) 0, n n∈ N0 [ 1 1 (c) , ,··· ,1 n n − 1 n∈ N 0

3 3.1

Logica met kwantoren Definitie

Veronderstel dat je ergens een blad papier vindt waarop enkel het volgende staat: x2 − 4 = 0.

(3)

Dan is niet duidelijk wat de schrijver hiermee bedoelde. Vooreerst is niet duidelijk waarvoor x staat. Met wat goede wil kunnen we wel vermoeden dat er bedoeld wordt dat x een reëel getal is. De schrijver had die mogelijke twijfel weggenomen als hij bijvoorbeeld had geschreven: x2 − 4 = 0

(x ∈ R).

Maar nu is nog niet duidelijk wat er precies bedoeld wordt. We geven drie mogelijke interpretaties: (a) Zoek alle x ∈ R die voldoen aan x2 − 4 = 0. (b) Er bestaat een x ∈ R waarvoor x2 − 4 = 0. (c) Voor alle x ∈ R is x2 − 4 = 0. Elk van de drie bovenstaande uitspraken is nu ondubbelzinnig. In (a) krijgen we de opdracht alle reële oplossingen van een vierkantsvergelijking te zoeken. In (b) en (c) worden ondubbelzinnige beweringen gemaakt. Bewering (c) is weliswaar manifest Zomercursus Wiskunde Groep Wetenschap & Technologie

28


fout, maar het is wel een duidelijke en ondubbelzinnige uitspraak. De oorspronkelijke uitdrukking (3) daarentegen is helemaal waardeloos; ze is immers zo vaag dat je zelfs niet eens kan zeggen of ze waar of vals is. Wat leren we hieruit? Vooreerst moeten we altijd expliciet aangeven waarvoor de symbolen die we gebruiken, staan (wat is x?). Bovendien moeten we steeds voldoende woorden bij formules geven om tot een ondubbelzinnige uitspraak te komen (voor alle x?, voor sommige x?, . . . ). De zinsneden “er bestaat een” en “voor alle” in uitdrukkingen (b) en (c) hierboven geven aan voor “hoeveel” x-en (voor welke “kwantiteit” x-en) de uitspraak die volgt zou moeten gelden. Men noemt ze in de logica daarom kwantoren en men voert er notaties voor in:

Definitie 3.1 Als p(a) een predicaat is dat afhangt van een veranderlijke a ∈ A dan betekenen volgende verkorte notaties voluit in woorden: ∀a ∈ A : p(a)

voor elk element a van A geldt p(a)

∃a ∈ A : p(a)

er bestaat (minstens) een element a van A waarvoor p(a) geldt

∃!a ∈ A : p(a) er bestaat precies één element a van A waarvoor p(a) geldt ∀ ∃ ∃!

is de universele kwantor of alkwantor is de existenti¨ ele kwantor of bestaanskwantor is de uniciteitskwantor

We schrijven de kwantor altijd vóór het predicaat. De veranderlijke a is een dummy of gebonden veranderlijke. Ze kan veranderd worden zonder dat de betekenis verandert, indien de nieuwe veranderlijke nog geen andere betekenis heeft op die plaats. We spreken af dat een kwantor betrekking heeft op alles wat er na komt, tenzij het door haakjes anders bepaald wordt. Zo bedoelen we met ∀a ∈ A : p(a) ⇒ q dat p(a) ⇒ q waar is voor elke a ∈ A. Als we bedoelen dat ∀a ∈ A : p(a) impliceert dat q waar is, dan we moeten zeker wel haakjes zetten. Dat schrijven we dus (∀a ∈ A : p(a)) ⇒ q. In termen van deze notaties kunnen we (b) en (c) nu compact opschrijven als (b’) ∃x ∈ R : x2 − 4 = 0. (c’) ∀x ∈ R : x2 − 4 = 0. Zomercursus Wiskunde Groep Wetenschap & Technologie

29


Als je dergelijke uitdrukkingen met kwantoren ontmoet, is het voor een goed begrip ervan belangrijk dat je ze spontaan blijft lezen als een volwaardige zin (in de voorbeelden dus in hun oorspronkelijke verwoordingen zoals in (2) en (3)).

3.2

Negatie van kwantoren

Voorbeeld 3.2 Nemen we X de verzameling van alle studenten uit de zomercursus en zij p(x) met x ∈ X de bewering “student x is blond.” Dan lezen we de uitspraak ∀x ∈ X : p(x) als “alle studenten van de zomercursus zijn blond”. Deze uitspraak is uiteraard niet waar, en dit toon je aan door één student aan te wijzen die niet blond is, in symbolen uitgedrukt merken we dus dat ¬(∀x ∈ X : p(x)) ⇐⇒ ∃x ∈ X : ¬p(x) (Vertaal laatste uitdrukking in gewone spreektaal.) Stel anderzijds q(x) de bewering “student x heeft groen haar” dan zal, mits hier niemand groen haar heeft, de uitspraak ¬(∃x ∈ X : q(x)) waar zijn, wat je aantoont door na te gaan dat elke student een haarkleur heeft die niet groen is, in symbolen ¬(∃x ∈ X : q(x)) ⇐⇒ ∀x ∈ X : ¬q(x) (Vertaal laatste uitdrukking in gewone spreektaal.) Samengevat:

Eigenschap 3.3 (Negatie van kwantoren) Zij p(x) een predikaat, dan geldt 1. ¬(∀x ∈ X : p(x)) ⇐⇒ ∃x ∈ X : ¬p(x) 2. ¬(∃x ∈ X : p(x)) ⇐⇒ ∀x ∈ X : ¬p(x)


30

3.3


Combinaties van kwantoren

In veel wiskundige formules komen verschillende kwantoren voor, de volgorde waarin ze voorkomen blijkt enorm belangrijk te zijn, dit merk je in volgende oefening. Oefening 3.4 Zij P een verzameling potjes van verschillende formaten, D een verzameling van de bijhorende deksels. Stel dat x ∈ D en y ∈ P dan definiëren we een predikaat p(x, y) met als betekenis ‘x past op y’. Verwoord elk van volgende formules in een zo goed mogelijk klinkende Nederlandse zin en zeg of de bewering waar of onwaar is. Welke beweringen zijn equivalent? (a) ∀x ∈ D : ∀y ∈ P : p(x, y) (b) ∀y ∈ P : ∀x ∈ D : p(x, y) (c) ∃x ∈ D : ∃y ∈ P : p(x, y) (d) ∃y ∈ P : ∃x ∈ D : p(x, y) (e) ∃x ∈ D : ∀y ∈ P : p(x, y) (f) ∀y ∈ P : ∃x ∈ D : p(x, y) Is er een logisch verband tussen (e) en (f)? Wat we hier intu¨ıtief aanvoelen wordt uitgedrukt in volgende eigenschappen. Eigenschap 3.5 (Verwisselen van kwantoren) Zij p(x,y) een predicaat, dan geldt 1. ∀x ∈ X : ∀y ∈ Y : p(x, y) ⇐⇒ ∀y ∈ Y : ∀x ∈ X : p(x, y) 2. ∃x ∈ X : ∃y ∈ Y : p(x, y) ⇐⇒ ∃y ∈ Y : ∃x ∈ X : p(x, y) 3. ∃x ∈ X : ∀y ∈ Y : p(x, y) =⇒ ∀y ∈ Y : ∃x ∈ X : p(x, y) 4. ∃x ∈ X : ∀y ∈ Y : p(x, y) 6⇐= ∀y ∈ Y : ∃x ∈ X : p(x, y)

Bijgevolg mogen gelijksoortige kwantoren verwisseld worden.

In 1. zijn beide equivalente uitdrukkingen in feite ook op te schrijven als één bewering met maar één universele kwantor ∀(x, y) ∈ X × Y : p(x, y). Zomercursus Wiskunde Groep Wetenschap & Technologie

31


Als X = Y dan mag de uitdrukking, zonder mogelijkheid van verwarring, zelfs verkort worden tot ∀x, y ∈ X : p(x, y). Net zo zijn beide uitdrukkingen in 2. op te schrijven als volgende bewering met één existentiële kwantor ∃(x, y) ∈ X × Y : p(x, y). Ook hier geldt dat als X = Y , we mogen verkorten tot ∃x, y ∈ X : p(x, y). De twee beweringen in 3. zijn niet logisch equivalent. Als we een combinatie hebben van een universele en een existentiële kwantor dan is de volgorde van belang. De omgekeerde pijl geldt in ’t algemeen niet, zoals blijkt uit het volgende tegenvoorbeeld. (Denk eerst eens na, hoe je aantoont dat een uitspraak van de vorm p ⇐ q niet geldt, of dus dat ¬(p ⇐ q) wel geldt. We nemen voor p(m, n) het predikaat n > m en we vergelijken de twee beweringen ∀m ∈ N : ∃n ∈ N : n > m

(4)

∃n ∈ N : ∀m ∈ N : n > m.

(5)

en De bewering (4) zegt dat bij elk natuurlijk getal een groter natuurlijk getal te vinden is. Deze bewering is waar. De tweede bewering (5) zegt dat er een natuurlijk getal bestaat dat groter is dan elk natuurlijk getal. Deze bewering is niet waar. Opmerking 3.6 De ervaring leert dat sommigen die omwisselingsfout wel maken in een wiskundige context en zich daarbij van geen kwaad bewust zijn, terwijl ze die fout (hopelijk) nooit zouden maken in het gewone taalgebruik (denk aan de potjes en dekseltjes). Dit stemt tot nadenken. . . We vermoeden heel sterk dat dit vooral te wijten is aan het feit dat men de betekenis van formeel genoteerde uitspraken met kwantoren niet door heeft; alsof men naar een hiëroglyfen-opschrift op een Egyptische tempel staart. Vandaar dat we willen onderstrepen hoe belangrijk het is dat je dergelijke compact genoteerde uitspraken, en bij uitbreiding alle uitdrukkingen met wiskundige symbolen, spontaan voluit leest als normale betekenisvolle zinnen. Oefeningen 3.7 1. Elk kind heeft een moeder. Gebruiken we hierbij de notatie K voor de verzameling van de kinderen en V voor de verzameling van de vrouwen en het predikaat Zomercursus Wiskunde Groep Wetenschap & Technologie

32


p(v, k) met als betekenis v is moeder van k, dan kunnen we deze uitspraak schrijven in termen van kwantoren als ∀k ∈ K : ∃v ∈ V : p(v, k). Illustreer aan de hand van deze uitspraak dat de volgorde van de kwantoren zeer belangrijk is. 2. Schrijf elk van volgende uitspraken met behulp van de notatie van formele logica (d.w.z. kwantoren (∀ en ∃), implicatie (⇒), . . . ). Voer daarbij zelf notaties in voor bepaalde verzamelingen en predikaten die relevant zijn in de diverse uitspraken. (a) Elke mus is een vogel. (b) Er zijn vogels die geen mussen zijn. (c) Als iemand goed studeert, zal hij slagen. (d) Voor elk examen slaagt er minstens één student. (e) Er is een examen waarvoor elke student slaagt. (f) Er is een student die voor alle examens slaagt. 3. Ontken elk van de uitspraken in vorige oefening. Formuleer je resultaat zowel in gewone spreektaal als in de taal van de formele logica. 4. Formuleer volgende beweringen in een betekenisvolle zin. Onderzoek of de beweringen waar of onwaar zijn. (a) ∀m ∈ N0 : ∃n ∈ N0 : m is een deler van n

(b) ∃n ∈ N0 : ∀m ∈ N0 : m is een deler van n (c) ∀n ∈ N0 : ∃m ∈ N0 : m is een deler van n

(d) ∃m ∈ N0 : ∀n ∈ N0 : m is een deler van n (e) ∀m, n ∈ N0 : m is een deler van n (f) ∃m, n ∈ N0 : m is een deler van n

5. Ontken elk van de uitspraken in vorige oefening. Formuleer je resultaat in gewone spreektaal. 6. Schrijf elk van volgende uitspraken met behulp van de notatie van formele logica (d.w.z. kwantoren (∀ en ∃), implicatie (⇒), . . . ). Voer daarbij zelf notaties in voor bepaalde verzamelingen en predikaten die relevant zijn in de diverse uitspraken. (a) Alle meisjes zijn goed in wiskunde. (b) Alle meisjes zijn niet goed in wiskunde. Zomercursus Wiskunde Groep Wetenschap & Technologie


33

(c) Er is een meisje dat niet goed is in wiskunde. (d) Alle kinderen die goed zijn in wiskunde zijn meisjes. (e) Alle kinderen die niet goed zijn in wiskunde zijn jongens. Welk van de uitspraken is de ontkenning van uitspraak (a)? Zijn er uitspraken in de lijst die dezelfde betekenis hebben als de uitspraak (a)? 7. Zij U de verzameling van alle mensen. Beschouw het predikaat p(x): x drinkt water. Druk de volgende uitspraken uit met symbolen. (a) Alle mensen drinken water. (b) Geen enkele mens drinkt water. (c) Alle mensen drinken geen water. (d) Er is geen enkel mens die geen water drinkt. (e) Sommige mensen drinken geen water. (f) Sommige mensen drinken water. Welk van de uitspraken is de ontkenning van uitspraak (a)? Zijn er uitspraken in de lijst die dezelfde betekenis hebben als de uitspraak (a)? 8. Betekent “het is niet zo dat sommige mensen dat deden” hetzelfde als “sommigen deden dat niet”? 9. Betekent “sommige mensen zijn onverstandig” hetzelfde als “‘het is niet zo dat alle mensen verstandig zijn”? 10. Beschouw de uitspraak ∀x ∈ R : ∀y ∈ R : (x2 = y 2) ⇒ (x = y). (a) Formuleer deze uitspraak voluit in woorden. (b) Ontken deze uitspraak. Formuleer de ontkenning zowel formeel met kwantoren als voluit in gewone spreektaal. (c) Welk van beide uitspraken is waar, de gegeven uitspraak of de ontkenning ervan? 11. Schrijf een equivalente propositie waarin geen negatieteken voorkomt. Zijn de proposities waar of onwaar? (a) ¬(∀x ∈ R : x < 2 ∨ x > 5)

(b) ¬(∃x ∈ R : x + 5 = 5 ∧ 5x > 0) (c) ¬(∀x ∈ R : 2 < x ∧ x < 5)


34


(d) ¬(∃x ∈ R : −2 < x 6 0) (e) ¬(∀x ∈ R : x ∈ [2, 3])

12. Duid in volgende reeks de alternatieven aan waarbij Uitspraak (1) equivalent is met Uitspraak (2). Argumenteer. (a) (1) Niet alle jongeren sporten en fuiven graag. (2) Er zijn jongeren die niet graag sporten en niet graag fuiven. (b) (1) Niet alle domme jongeren zijn blonde meisjes. (2) Er bestaan domme meisjes die niet blond zijn. (c) (1) Het is niet zo dat sommige mensen ongezond eten. (2) Sommige mensen eten niet ongezond. (d) (1) Alle kinderen die niet goed zijn in wiskunde zijn jongens. (2) Alle meisjes zijn goed in wiskunde. (e) (1) Alle kinderen die goed zijn in wiskunde zijn meisjes. (2) Alle meisjes zijn goed in wiskunde.

4

Bewijstechnieken

4.1

Neerschrijven van wiskundige teksten

In vorige hoofdstukken hebben we een zeer formele wiskundige taal ingevoerd en hierbij ook steeds in de kanttekening meegegeven dat dit ook gevaren inhoudt. Wiskundige teksten die enkel gebruik maken van deze formele schrijfwijzen en die bol staan van een wirwar van pijltjes, haakjes en kwantoren zijn moeilijk ontcijferbaar — eerder een soort combinatie van rebussen en hiërogliefen, dus zeker niet geschikt voor vlotte communicatie. Vermits wiskunde vooral een zaak van denken is (meer nog dan van rekenen), wordt wiskunde bij voorkeur neergeschreven in de taal waarin we als mensen van nature denken, met name de gewone taal, onze moedertaal8 , met volledige, nauwkeurige en grammaticaal correcte zinnen. Niet dat we hier taalpurisme of literaire hoogstandjes willen nastreven, maar we formuleren definities, resultaten en redeneringen altijd in volwaardige zinnen. Onvermijdelijk bevatten dergelijke zinnen wel symbolen daar waar ze verwijzen naar wiskundige objecten. Maar die symbolen nemen steeds binnen de zin waarin ze optreden, een grammaticaal correct invulbare plaats in, d.w.z. je moet zo’n zin kunnen voorlezen als een normaal klinkende zin. Wanneer we het bijvoorbeeld hebben over twee reële getallen, a en b, is volgende zin een goede combinatie van gewone taal met symbolen: “Omdat a2 = b2 , moet a = ±b.” Deze zin laat zich immers perfect luidop voorlezen in de gewone taal als een onmiddellijk 8

of een andere levende taal


4. Bewijstechnieken

35

te begrijpen zin: “Omdat a kwadraat gelijk is aan b kwadraat, moet a gelijk zijn aan plus of min b.” Hoe vanzelfsprekend het ook moge lijken dat je met volwaardige en betekenisvolle zinnen moet communiceren, toch leert de ervaring dat vele studenten dit voor wiskunde schijnen te vergeten. Veel te vaak zie je in hun oplossingen van oefeningen bijna uitsluitend symbolen staan, hoogstens aangevuld met hier en daar wat pijltjes of dubbele pijltjes (waarvan er sommigen dan nog niet gelden als logische implicatie). Je hebt er dan het raden naar wat de schrijver bedoelde. We raden de lezer ten stelligste aan om zich een goede schrijf- en argumenteerstijl eigen te maken, a fortiori voor wetenschappelijke teksten. Je zal merken dat wiskundesyllabi bol staat van zinsneden als “omdat . . . , weten we dat . . . ”, “Veronderstel dat . . . . Dan mogen we besluiten dat . . . ”, “Uit . . . volgt dat . . . ”, “Om te bewijzen dat . . . , volstaat het te verifiëren dat . . . ”, enz. Dergelijke zinsneden zijn onontbeerlijk in een wiskundige tekst. Zij dragen immers de redenering, het verhaal. Niet alleen laten ze de lezer toe te begrijpen welke redenering de schrijver volgt, maar ook behoeden ze de schrijver zelf tegen het maken van redeneerfouten omdat hij via die zinsneden de redenering ook voor zichzelf duidelijk moet expliciteren. Vermits van jou zal verwacht worden zelf oefeningen of bewijzen neer te schrijven is het belangrijk zelf te controleren of je schrijfstijl de goede is. Dit is niet moeilijk: doe de “voorleestest”! Lees je oplossing luidop voor; als dit klinkt als normale betekenisvolle taal, zit je wellicht goed. Een bijkomende moeilijkheid bij het neerschrijven van een redenering is dat we ze meestal niet opschrijven op de manier waarop we ze vinden. Je zult meestal enige tijd bezig zijn om het bewijs te vinden voordat je kunt overgaan naar het opschrijven van het bewijs.

4.2

Directe bewijzen

Veel wiskundige stellingen zijn van de vorm p ⇒ q. Hierin is p de hypothese of de aanname van de stelling. Vermits p ⇒ q sowieso waar is als p onwaar is valt er in die situatie niets meer te bewijzen. Er blijft dus enkel aan te tonen dat, als p waar is, daaruit volgt dat ook q waar is. De eenvoudigste manier is door middel van een direct bewijs. Hier is een voorbeeld. We schetsen eerst het kader waarbinnen de redenering kan worden opgebouwd. We werken met reële getallen en bekijken meer specifiek de eigenschappen die daar gelden rond de ordening. Deze fundamentele eigenschappen zijn. Eigenschappen 4.1 (De orde in R) (1) Voor elk tweetal reële getallen a en b geldt precies één van de volgende mogelijkZomercursus Wiskunde Groep Wetenschap & Technologie

36


heden a < b,

a = b,

a > b.

(2) Voor reële getallen a, b en c geldt a < b ⇒ (a + c < b + c) (3) Voor reële getallen a, b en c geldt (a < b ∧ c > 0) ⇒ ac < bc (a < b ∧ c < 0) ⇒ ac > bc (4) Voor reële getallen a, b en c geldt (a < b ∧ b < c) ⇒ a < c. Deze eigenschap heet de transitiviteit van de ordening. Met deze eigenschappen willen we volgende eigenschap aantonen.

Voorbeeld 4.2 Schrijf een bewijs voor volgende eigenschap, Voor strikt positieve reële getallen a en b geldt a < b ⇒ a2 < b2 .

We kunnen hier samenvatten wat we moeten doen door onderscheid te maken tussen wat gegeven is en wat we moeten bewijzen. Gegeven: Strikt positieve reële getallen a en b. Te bewijzen: a < b ⇒ a2 < b2 . Het directe bewijs van een implicatie p ⇒ q is om de hypothese p toe te voegen aan de gegevens en om daarmee q te bewijzen. Dit leidt in dit voorbeeld tot. Gegeven: Strikt positieve reële getallen a en b met a < b. Te bewijzen: a2 < b2 . Zomercursus Wiskunde Groep Wetenschap & Technologie

37

4. Bewijstechnieken

Nu gaan we nadenken hoe het te bewijzen zou kunnen volgen uit het gegeven. Omdat we iets willen weten over a2 en b2 ligt het voor de hand om de gegeven ongelijkheid a < b met a en b te vermenigvuldigen. Omdat a en b strikt positief zijn blijven de ongelijkheden behouden wegens eigenschap (3) over de orde in R zodat a < b ⇒ a2 < ab

(6)

a < b ⇒ ab < b2 .

(7)

(a2 < ab) ∧ (ab < b2 ) ⇒ a2 < b2 .

(8)

en

Omdat we aangenomen hebben dat a < b waar is volgt nu dat a2 < ab en ab < b2 . Deze twee ongelijkheden bevatten beide ab en er geldt Omdat a < b weten we al dat a2 < ab en ab < b2 en daarom geldt vanwege (8) dat a2 < b2 waar is. De beweringen (6) en (7) volgen meteen uit (3) en (8) volgt uit (4). Het bovenstaande is NIET het bewijs zoals je het opschrijft. We doen enkele pogingen: Bewijs a
⇓a>0 b>0

eig. (3)

2

a < ab en ab < b

⇓ transitiviteit eig. (4) (a < ab) ∧ (ab < b2 ) ⇒ a2 < b2 2

FOUT: geen verhaal! Hoogstens bruikbaar als schets om het bewijs te visualiseren. Het volgende is ook geen acceptabel bewijs. Bewijs a < b ⇒ (a2 < ab ∧ ab < b2 ) ⇒ a2 < b2 . Beide manieren van opschrijven zondigen tegen alle regels die we formuleerden in het begin van dit hoofdstuk. Het is hoogstens de manier waarop we bondig in het KLAD onze gedachten vormden. Het uiteindelijke bewijs is een opeenvolging van Nederlandse zinnen met woorden zoals ‘volgt’, ‘dus’ en ‘omdat’ die aangeven hoe de verschillende zinnen met elkaar samenhangen. Enige wiskundige notatie wordt ook gebruikt maar het geheel moet een leesbaar verhaal opleveren. Let op dat we geen pijlen gebruiken om gevolgtrekkingen aan te geven. Een goed bewijs van de eigenschap kan er bijvoorbeeld zo uit zien. Bewijs Veronderstel dat a < b. Omdat a > 0 en b > 0 volgt hier, dankzij eigenschap 4.1(3) uit, dat a2 < ab en ab < b2 . Zodat a2 < b2 vanwege de transitiviteit van de ordening. Hiermee is bewezen dat a < b ⇒ a2 < b2 . Zomercursus Wiskunde Groep Wetenschap & Technologie

38

4.3


Bewijzen van beweringen met kwantoren

Enorm veel beweringen in de wiskunde hebben de vorm van een universele bewering of een existentiële bewering of een combinatie er van. Het is heel belangrijk om te weten hoe je dergelijke beweringen kunt bewijzen. De universele kwantor Een bewering ∀a ∈ A : p(a) wordt meestal bewezen vanuit de vorm a ∈ A ⇒ p(a).

Dat wil zeggen dat we aannemen dat a ∈ A en daaruit gaan we p(a) bewijzen. Zo’n bewijzen beginnen dan ook steevast met de uitdrukking “kies een a willekeurig in A, daarna volgt een goed opgebouwde redenering die p(a) aantoont. Het is belangrijk dat in die redenering de beschouwde a ook willekeurig blijft, dat we over a geen veronderstellingen maken, zoals (in geval a een reëel getal is) a is positief, of a > 1 e.a. We kunnen dit best vergelijken met een bewering die we doen over “alle mannelijke Belgen” en waar we iemand willen overtuigen van die bewering. Handigst is van de bewering na te gaan voor “Jan Modaal.” In het hele betoog, mogen we van Jan Modaal dan ook geen speciale eigenschappen veronderstellen, we mogen niets veronderstellen over zijn leeftijd , zijn beroep of zijn favoriete voetbalclub . . . Hij moet zo “Modaal” mogelijk blijven. Hebben we op het einde van ons betoog de bewering aangetoond voor “Jan Modaal” dan geldt hij “voor alle mannelijke Belgen”. Voorbeeld 4.3 Schrijf een bewijs voor volgende eigenschap, ∀a ∈ R0 : a2 > 0

(9)

Bewijs Kies a ∈ R0 willekeurig. Dan is a ∈ R met a 6= 0. Dan geldt door de totale orde in R ofwel a < 0 of a > 0. In het geval dat a > 0 volgt door beide zijden van de ongelijkheid a > 0 met het strikt positieve getal a te vermenigvuldigen dat a2 > 0. In het geval dat a < 0 krijgen we ook a2 > 0, omdat bij het vermenigvuldigen met het strikt negatieve getal a de ongelijkheid omdraait. In beide gevallen volgt dat a2 > 0. Omdat a ∈ R0 willekeurig gekozen was is (9) bewezen. De existenti¨ ele kwantor De eenvoudigste manier om een bewering ∃a ∈ A : p(a) te bewijzen is om een zeker element a ∈ A aan te geven waarvoor p(a) geldt. Dit noemen we wel een bewijs met een voorbeeld. Zomercursus Wiskunde Groep Wetenschap & Technologie

39

4. Bewijstechnieken

Voorbeeld 4.4 Schrijf een bewijs voor volgende eigenschap, ∃n ∈ Z : n2 = 9.

(10)

Bewijs Merk op dat 3 ∈ Z en 32 = 9. Dus n = 3 geeft een voorbeeld waaruit blijkt dat (10) juist is. De negatie van een stelling met een kwantor • Vermits er geldt

¬(∀x ∈ X : p(x)) ⇐⇒ ∃x ∈ X : ¬p(x)

zullen we zo’n negatie van de alkwantor bewijzen door een voorbeeld waarvoor p(x) niet opgaat, wat we in dit geval een tegenvoorbeeld noemen. • De negatie van een existentiële kwator komt omwille van ¬(∃x ∈ X : p(x)) ⇐⇒ ∀x ∈ X : ¬p(x) neer op een bewijs dat zal beginnen met “Kies een willekeurige x ∈ X · · · ” waarna we moeten aantonen dat p(x) niet geldt. Oefeningen 4.5 Let op dat het er bij deze oefeningen niet om gaat dat je voor jezelf de juistheid van de te bewijzen bewering inziet, maar dat het de bedoeling is dat je een goed neergeschreven bewijs geeft. 1. Welke uitspraak is waar, welke onwaar? Bewijs je antwoord. (a) ∃x ∈ R : x2 − 4 = 0.

(b) ∀x ∈ R : x2 − 4 = 0. 2. Formuleer volgende beweringen in een betekenisvolle zin. Onderzoek of de beweringen waar of onwaar zijn en geef een bewijs. (a) ∀m ∈ Z : ∀n ∈ Z : m 6 n

(b) ∃m ∈ Z : ∃n ∈ Z : m 6 n (c) ∀m ∈ Z : ∃n ∈ Z : m 6 n

(d) ∃m ∈ Z : ∀n ∈ Z : m 6 n (e) ∀n ∈ Z : ∃m ∈ Z : m 6 n


40


(f) ∃n ∈ Z : ∀m ∈ Z : m 6 n 3. Verwoord volgende eigenschappen in een betekenisvolle zin en bewijs ze als gevolg van Eigenschap 4.1 over de orde in R. (a) ∀x, y, z ∈ R : x + z < y ⇔ x < y − z

(b) ∀a, b, c, d ∈ R : (a < b ∧ c < d) ⇒ a + c < b + d

(c) Geldt volgende eigenschap ∀a, b, c, d ∈ R : (a < b ∧ c < d) ⇒ a − c < b − d ook? Argumenteer!

(d) Volgende eigenschap geldt niet algemeen in R. ∀a, b, c, d ∈ R : (a < b ∧ c < d) ⇒ ac < bd. Toon dit aan. Verander het nodige aan de hypothese opdat je wel een algemeen geldende uitspraak krijgt en bewijs deze. 4. Zij W ⊂ R een deelverzameling van reële getallen en M een reëel getal. Een bovengrens van een verzameling W is een reëel getal dat groter of gelijk is aan alle getallen uit W . M is een maximum van de verzameling W als M ∈ W en M een bovengrens is van W Geef een correcte formule uit de logica waaraan voldaan moet worden bij volgende uitspraken. Zorg dat het negatieteken ¬ niet voorkomt in de formule. (a) M is een bovengrens van de verzameling W . (b) M is geen bovengrens van de verzameling W . (c) M is een maximum van de verzameling W . (d) M is geen maximum van de verzameling W . (e) W is een naar boven begrensde verzameling. (f) W is geen naar boven begrensde verzameling. (g) M is de kleinste bovengrens van W . (h) M is een bovengrens van W en elke andere bovengrens is groter dan M. (i) M is een bovengrens van W en elk getal dat kleiner is dan M is geen bovengrens van W . Is er een logisch verband tussen (g), (h) en (i). 5. Zij W = { n1 | n ∈ N0 }. (a) Zoek of W een maximum heeft. Bewijs ook je bewering. (b) Zijn 0 en 2 een bovengrenzen ? Bewijs je antwoord. Zomercursus Wiskunde Groep Wetenschap & Technologie

41

4. Bewijstechnieken

6. Zij p(x) een willekeurige predikaat. ∅ de lege verzameling. Controleer dat de beweringen ∀a ∈ ∅ : p(a) en ∀a ∈ ∅ : ¬p(a) altijd WAAR zijn door aan te tonen dat de negatie ervan altijd onwaar is, en dat de beweringen ∃a ∈ ∅ : p(a) en ∃a ∈ ∅ : ¬p(a) altijd ONWAAR zijn.

4.4 4.4.1

Een bewijs uit het ongerijmde Bewijs van negatieve bewering

Een negatieve bewering is een bewering dat iets niet bestaat. Zo’n bewering is vaak moeilijk op een directe manier te bewijzen. Hier is een voorbeeld.

Voorbeeld 4.6 Bewijs volgende eigenschap. Er bestaan geen gehele getallen n en m met 8n − 6m = 101. Bij een bewijs uit het ongerijmde nemen we aan dat hetgene dat we moeten bewijzen niet waar is. Daaruit leiden we een bewering af waarvan we weten dat ze niet waar is. Dit is een tegenspraak waaruit we concluderen dat onze oorspronkelijke aanname dat de bewering niet waar is, onjuist is. Daarom is de bewering wel waar. De stelling in voorbeeld 4.6 kan nu als volgt uit het ongerijmde bewezen worden. Bewijs Neem aan dat n en m gehele getallen zijn met 8n − 6m = 101. Omdat 8 en 6 even getallen zijn is dan 101 = 8n − 6m = 2(4n − 3m) een even getal. Maar 101 is oneven, zodat we een tegenspraak hebben. Uit deze tegenspraak volgt dat er geen gehele getallen n en m bestaan met 8n − 6m = 101. De tegenspraak is hier van de vorm p ∧ ¬p. Hierin is p de propositie “101 is een even getal” zodat ¬p overeenkomt met “101 is een oneven getal” die allebei waar zouden zijn als de stelling waar was. Een bewijs uit het ongerijmde is gebaseerd op de tautologie q ⇔ (¬q ⇒ (p ∧ ¬p)). We geven nog een voorbeeld. Zomercursus Wiskunde Groep Wetenschap & Technologie

42


Voorbeeld 4.7 √ Bewijs volgende eigenschap uit het ongerijmde: 2 is een irrationaal getal m.a.w. √

2 ∈ R \ Q.

Bewijs √ √ Veronderstel dat 2 ∈ Q. Dan is 2 = a/b met a, b ∈ N0 , en a, b niet beiden even (anders kan je de breuk vereenvoudigen). Dus 2 = a2 /b2 of 2b2 = a2 . Dit impliceert dat a2 , en dus ook a even is (zie oefeningen 4.9 3.). Schrijf a = 2a′ . Dan is 2b2 = (2a′ )2 = 4a′ 2 , en b2 = 2a′ 2 . Dit impliceert dat b2 , en dus ook √ b, even is. Dit is in strijd met het feit dat a, b niet beiden even zijn, en bewijst dat 2 6∈ Q. 4.4.2

Bewijs van implicaties uit het ongerijmde

Soms is het directe bewijs van een implicatie p ⇒ q niet eenvoudig te geven, zoals in het volgende voorbeeld.

Voorbeeld 4.8 Bewijs volgende eigenschap. Als x, y en a reële getallen zijn met x > y, dan geldt ax ≤ ay ⇒ a ≤ 0.

Het is moeilijk om vanuit de fundamentele eigenschappen van ongelijkheden een direct bewijs te construeren, omdat die eigenschappen afhangen van het teken van a en dat is nu net datgene dat we willen bepalen. De eenvoudigste oplossing is een bewijs uit het ongerijmde. We onderstellen dus dat p ⇒ q niet waar is. Nu weten we van de negatiewet van de implicatie dat ¬(p ⇒ q) ⇔ p ∧ ¬q. p ⇒ q niet waar komt dus overeen met onderstellen dat p waar is en q niet waar. Dus we kunnen aantonen dat p ⇒ q geldt door te laten zien dat p waar en q niet waar samen leiden tot een tegenspraak. Zo vinden we een bewijs van de eigenschap uit voorbeeld 4.8. Bewijs Gegeven is dat x > y. Veronderstel uit het ongerijmde dat ax ≤ ay en a > 0. Dan volgt uit x > y en het feit dat a strikt positief is dat ax > ay, hetgeen in tegenspraak Zomercursus Wiskunde Groep Wetenschap & Technologie

43

4. Bewijstechnieken

is met de onderstelling dat ax ≤ ay. Dus ax ≤ ay en a > 0 zijn niet allebei waar en daarom geldt ax ≤ ay ⇒ a ≤ 0.

4.5

Bewijs door contrapositie

Nauw verwant, maar fundamenteel toch verschillend is volgende bewijstechniek voor het aantonen van een implicatie. De implicatie p ⇒ q is logisch equivalent met haar contrapositie ¬q ⇒ ¬p, zoals we vroeger hebben aangetoond. Dus als de ene implicatie waar is, dan is de andere het ook. De bewering ax ≤ ay ⇒ a ≤ 0

uit de vorige stelling is dus logisch equivalent met

a > 0 ⇒ ax > ay. Als we van contrapositie gebruik maken vinden we een alternatief bewijs voor de stelling in voorbeeld 4.8. Bewijs Gegeven is dat x > y. Als a > 0 dan volgt uit de eigenschappen voor ongelijkheden dat ax > ay. Dus a > 0 ⇒ ax > ay. Vanwege contrapositie is dan ook ax ≤ ay ⇒ a ≤ 0. Oefeningen 4.9 1. Stel dat bij de studenten die de zomercursus volgen, volgende beweringen waar zijn: (1) De aspirant wetenschappers die van wiskunde houden zijn cool. (2) Wie van wiskunde houdt is niet dom. (3) Alle aspirant wetenschappers houden van wiskunde. (4) De nerds uit de zomercursus zijn dom of niet cool. Toon aan dat aspirant wetenschappers uit de zomercursus geen nerds zijn, doe dit met een direct bewijs en met een bewijs uit het ongerijmde. 2. Geef een bewijs uit het ongerijmde voor de bewering dat er geen gehele getallen m en n zijn met 14m + 21n = 100. 3. Geef een bewijs uit het ongerijmde en door contrapositie voor volgende eigenschap. Voor elk natuurlijk getal n geldt: als n2 even is, dan is n ook even. Zomercursus Wiskunde Groep Wetenschap & Technologie

44


4. Bewijs volgende eigenschap uit het ongerijmde. Als W een verzameling reële getallen is en W heeft een maximum (zie Oefeningen 4.5 oefening 4). Dan is dit maximum uniek. Men mag dus spreken van het maximum. Merk op dat je ook een direct bewijs kan geven. 5. Beschouw volgende eigenschap. Zij a, x ∈ R twee willekeurige reële getallen dan geldt, (∀ε ∈ R+ 0 : |x − a| < ε) ⇒ x = a. In de meeste handboeken wordt dit ook geformuleerd als (∀ε > 0 : |x − a| < ε) ⇒ x = a. Formuleer deze eigenschap in een betekenisvolle Nederlandse zin, we geven je als hint dat |x − a| het best vertaald wordt als “de afstand tussen x en a” (verifieer deze betekenis, je vindt ze ook terug in het pakket “absolute waarde”). Bewijs nu de eigenschap met een bewijs uit het ongerijmde en met een bewijs door contrapositie.

4.6

Bewijzen van eigenschappen van de natuurlijke getallen: Het principe van volledige inductie

Nieuwsuitzendingen worden af en toe opgesmukt door recordpogingen waar men zo lang mogelijke ketens dominostenen wil laten omvallen. Het principe van volledige inductie kan je best vergelijken met zo’n competitie waar men nu een oneindige keten dominostenen wil laten omvallen. De hele keten zal pas vallen als aan twee voorwaarden voldaan is: 1. De eerste steen moet worden omgegooid. 2. Op elke plaats moeten de stenen zó staan dat als de k-de steen valt, ook de (k + 1)-ste steen omvalt. De natuurlijke getallen vormen ook zo’n oneindige keten die begint bij 0 en waar elk natuurlijk getal een unieke opvolger heeft. Wil je dat een eigenschap P (n) geldt voor alle natuurlijke getallen, dan moet hij gelden voor het kleinste natuurlijk getal. Dus P (0) moet gelden en indien je kan aantonen dat, als de eigenschap geldt voor een willekeurig natuurlijk getal k, hij ook geldt voor het volgende natuurlijk getal k + 1. Dan zal die eigenschap gelden voor alle natuurlijke getallen. Intu¨ıtief voel je immers dat omdat P (0) geldt, dan ook automatisch P (0 + 1) = P (1) geldt, maar dan ook P (1 + 1) = P (2), enz. Omdat dit proces nooit zal stoppen, zegt je intu¨ıtie dat de eigenschap dan geldt voor alle natuurlijke getallen. Exacter wordt dit alles geformuleerd in een echte wiskundige stelling, die we hier niet bewijzen. Zomercursus Wiskunde Groep Wetenschap & Technologie

4. Bewijstechnieken

45

Stelling 4.10 (Het principe van volledige inductie) De bewering P (n) geldt voor elke n ∈ N als geldt (1) P (0) is waar, en

(2) Voor elke k ∈ N geldt: P (k) ⇒ P (k + 1). Een bewijs met volledige inductie valt uiteen in drie delen. • Als eerste het bewijs dat P (0) waar is. Dit is de basisstap. • Ten tweede het bewijs dat P (k) ⇒ P (k + 1) waar is voor elke k ∈ N. Dit is de inductiestap. In de inductiestap zullen we aannemen dat P (k) waar is. Deze aanname heet de inductiehypothese. Gebruik makend van de inductiehypothese moeten we dan bewijzen dat P (k + 1) waar is. • De derde stap is de conclusie. Deze stap is steeds hetzelfde. Het houdt in dat we het principe van volledige inductie aanroepen om te concluderen dat P (n) waar is voor elke n ∈ N. Hier is een eenvoudig voorbeeld. Voorbeeld 4.11 Bewijs volgende eigenschap met volledige inductie9 . Voor elk natuurlijk getal n geldt dat n2 + n een even getal is.

Bewijs • Basisstap: Voor n = 0 is n2 + n = 02 + 0 = 0 en dit is even. • Inductiestap: Neem aan dat k een natuurlijk getal is en dat k 2 + k een even getal is (inductiehypothese). Er geldt (k + 1)2 + (k + 1) = k 2 + 2k + 1 + k + 1 = (k 2 + k) + 2(k + 1). Duidelijk is dat 2(k + 1) even is . Omdat door de inductiehypothese k 2 + k even is, is ook hun som even en bijgevolg is (k + 1)2 + (k + 1) even. Hiermee is de inductiestap bewezen. • Conclusie: Omdat de basisstap en de inductiestap bewezen zijn, volgt met het principe van volledige inductie dat n2 + n een even getal is voor elke n ∈ N. 9

Deze eigenschap kan ook op andere manieren bewezen worden. Het eenvoudigste bewijs maakt gebruik van gevalsonderscheid: n is even of n is oneven.


46


Vaak wordt het symbool n ook gebruikt in de inductiestap. Dan is de inductiestap dat P (n) ⇒ P (n + 1) geldt voor elke n ∈ N. Dit dubbel gebruik van het symbool n kan tot verwarring leiden en is pas aan te raden als je volledig vertrouwd bent met het principe van volledige inductie. Opmerking 4.12 Geldt de eigenschap P (n) enkel voor alle n ∈ N0 dan wordt de basisstap: P (1) is waar. Geldt de eigenschap P (n) enkel voor alle natuurlijke getallen strikt groter dan 5 dan wordt de basisstap: P (6) is waar, enz. Oefeningen 4.13 Bewijs volgende eigenschappen door volledige inductie. 1. Voor elk geheel getal n ∈ N geldt 1 + 2 + 3 + · · · + n =

n(n + 1) . 2

2. Voor elk geheel getal n ∈ N geldt 12 + 22 + 33 + · · · + n2 =

n(n + 1)(2n + 1) . 6

3. Voor elk geheel getal n ∈ N is n(n2 + 5) deelbaar door 6. 4. Zoek een formule voor de n-de afgeleide van een functie met voorschrift f (x) = 1 = (1 + x)−1 en bewijs deze per inductie. 1+x 5. Stel x ∈ R en x > −1 dan geldt voor elke n ∈ N0 (1 + x)n > (1 + nx) 6. Beschouw de eigenschap: Voor elk natuurlijk getal geldt n = n + 1 Toon de noodzaak van de basisstap aan door na te gaan dat voor deze foute eigenschap het bewijs van de inductiestap perfect kan aangetoond worden. 7. ∗ Voor elk geheel getal n ≥ 4 geldt n2 ≤ 2n . 8. ∗ Elke eindige niet lege verzameling heeft een maximum. 9. ∗ Wat schort er aan volgend bewijs door inductie van de eigenschap: Als in een groep eerste bachelorstudenten minstens één student slaagt, dan slagen ze allemaal in dat groepje. • Basisstap: De eigenschap geldt duidelijk bij een groep met één student.

• Inductiestap: We veronderstellen dat de eigenschap bewezen is voor elk groepje van k ∈ N0 studenten en tonen de eigenschap nu aan voor een groep met k + 1 studenten. Zij A een groep van k + 1 studenten waarvan minsten één student geslaagd is. We verwijderen uit die groep één student (niet diegene waarvan geweten is dat hij geslaagd is). De overblijvende groep A′ telt k studenten, waarvan minstens één geslaagd is. Passen we de inductiehypothese toe op deze groep Zomercursus Wiskunde Groep Wetenschap & Technologie

5. Het functiebegrip

11

47

A′ dan mogen we besluiten dat elke student uit A′ geslaagd is. Blijft natuurlijk nog aan te tonen dat de verwijderde student ook geslaagd is. Dit is echter eenvoudig: beschouw een nieuwe groep A′′ van k studenten die je maakt door de verwijderde student samen te nemen met k − 1 (geslaagde) studenten uit groep A′ . A′′ bevat k studenten waarvan er minstens één geslaagd is (er zijn er wel zeker k − 1 geslaagd!) A′′ voldoet aan de voorwaarden van de inductiehypothese, we mogen dus besluiten dat alle studenten uit groep A′′ geslaagd zijn. M.a.w alle studenten uit de oorspronkelijke groep A zijn geslaagd. Hiermee is de inductiestap bewezen.

• Conclusie: Omdat de basisstap en de inductiestap bewezen zijn, volgt met het principe van volledige inductie dat als in een groep eerste bachelorstudenten minstens één student slaagt, ze allemaal slagen in dat groepje.

5 5.1

Het functiebegrip

10

Notaties en terminologie

In heel wat disciplines worden we geconfronteerd met afhankelijkheden: grootheden blijken af te hangen van andere grootheden. We illustreren dit met enkele voorbeelden.

10

In de wiskunde geeft men een nauwkeurige definitie voor het begrip functie die enkel gebaseerd is op primaire noties uit de verzamelingenleer. Alhoewel dergelijke fundamentele abstracte definitie niet zo heel moeilijk is, verkiezen we toch ze hier niet te geven. Voor wie wiskunde in eerste instantie als hulpwetenschap wil gebruiken, blijkt deze definitie immers een beetje steriel over te komen omdat ze niet genoeg appelleert aan de intu¨ıtie. Daarom geven we hier in plaats van de formele wiskundige definitie een intu¨ıtievere omschrijving van het functiebegrip.


48


grootheid

hangt af van

grootheid

koers van een aandeel

tijd

vraag naar dvd-spelers

prijs van dvd-spelers én prijs van dvd-films

druk in een vat water

temperatuur

luchtdruk

hoogte boven aardoppervlak

positie van een raket in de ruimte

tijd verlopen sinds lancering

diepte van een vijver

plaats

aantal GSM-abonnees

tijd

De grootheden in de linker kolom worden in deze context de de afhankelijke grootheden of afhankelijke variabelen genoemd, die in de rechter kolom de onafhankelijke grootheden of onafhankelijke variabelen. Meestal, zoals ook in de voorbeelden hierboven, kunnen de betrokken grootheden gekwantificeerd worden en dus beschreven worden door (één of meerdere) getallen: – De koers van een aandeel uitgedrukt in bv. euro wordt gegeven door een reëel getal, dus door een element van R. – De tijd (eens men een gepaste eenheid en beginmoment gekozen heeft) wordt beschreven door een reëel getal, dus door een element van R. – De vraag naar dvd-spelers, bijvoorbeeld uitgedrukt in duizendtallen, wordt gegeven door een reëel getal, dus door een element van R. – De prijs van dvd-spelers én dvd-films wordt beschreven door een koppel reële getallen (waarvan het eerste de prijs van de spelers aangeeft en het tweede de prijs van de films), dus door een element van R2 . – De druk, temperatuur en de hoogte boven het aardoppervlak worden (na het kiezen van een schaal) gegeven door een reëel getal, dus door een element van R. – De positie van een raket in de drie-dimensionale ruimte wordt vastgelegd door drie reële getallen, dus door een element van R3 , – Diepte van een vijver uitgedrukt in meter wordt gegeven door een reëel getal, dus gegeven door een element van R. Zomercursus Wiskunde Groep Wetenschap & Technologie


12

49

– De plaats wordt beschreven door twee reële getallen (bv. lengte- en breedtegraad), dus door een element van R2 . – Het aantal GSM-abonnees wordt gegeven door een natuurlijk getal, dus door een element van N. – ... We zien dus dat er in elk van de afhankelijkheden twee verzamelingen in het spel zijn: – een verzameling A waartoe de onafhankelijke grootheid behoort (bv. A = R, A = R+ × R+ ⊆ R2 , A = Rn , . . . ), – een verzameling B waartoe de afhankelijke grootheid behoort (bv. B = R, B = R3 , B = N, . . . ). De afhankelijkheid zelf beschrijven we wiskundig met een functie van A naar B: f : A → B : x 7→ f (x).

(11)

Een functie f van A naar B laat met elk element x uit A juist ´ e´ en element uit B corresponderen dat we dan met f (x) noteren. We zeggen dat de functie f “x afbeeldt op f (x)” wat in de notatie (11) gesymboliseerd wordt door “x 7→ f (x)”. We lezen de notatie (11) voluit als f is een functie van A naar B die x (uit A) afbeeldt op f (x) (in B). Kortweg noteert men een functie f van A naar B ook met f : A → B. Als in een bepaalde context de verzamelingen A en B gekend zijn wordt de notatie f : x 7→ f (x) toegelaten.

In verband met functies f : A → B hanteert men nog de volgende terminologie: – De verzameling A wordt het definitiegebied of domein van de f genoemd (notatie: def(f ) of dom(f )). – B is de doelverzameling of codomein, – Als x ∈ A en y = f (x) dan noemt men y het beeld van x onder f , of (vermits B vaak een getallenverzameling is) de functiewaarde van x. Men leest “y = f (x)” vaak als “y is f van x”.


50


– De verzameling y ∈ B ∃x ∈ A : f (x) = y , m.a.w. de verzameling van alle functiewaarden van f , wordt de beeldenverzameling of kortweg het beeld van f genoemd en genoteerd met f (A), Bld(f ) soms ook Im(f ) (van het Engelse image). – Als A ⊆ R, zegt men dat f een functie van één (reële) variabele of veranderlijke is. Als A ⊆ Rn (met n ∈ N \ {0, 1}), zegt men dat f een functie van n (reële) veranderlijken of variabelen is. – Als B ⊆ R, noemt men f een reële (of scalaire) functie Als B ⊆ Rm (met m ∈ N \ {0, 1}), noemt men f een vectorfunctie. – Met één vectorfunctie f : A → Rm : x 7→ f (x) = (f1 (x), f2 (x), . . . , fm (x))

(12)

komen m scalaire functies fi : A → R : x 7→ fi (x) (i = 1, 2, . . . , m) overeen die men de componentsfuncties of co¨ ordinaatsfuncties van f noemt. Omgekeerd definiëren m scalaire functies fi : A → R (i = 1, 2, . . . , m) via (12) één vectorfunctie f : A → Rm . Opmerking 5.1 (functie versus afbeelding) Als synoniem van “functie” (function) gebruikt men soms ook het woord “afbeelding” (mapping). In sommige (oudere) wiskundehandboeken voor het secundair onderwijs maakt men echter een onderscheid tussen de begrippen functie en afbeelding. Volgens die conventie zou een functie f van A naar B niet in elk punt van A gedefinieerd hoeven te zijn; indien dat wel het geval is spreekt men in deze conventie van een afbeelding. Maar je kan eigenlijk geen functie eenduidig beschrijven zonder meteen te zeggen op welke verzameling ze gedefinieerd is. In de internationaal gangbare conventie zal men er daarom bij de notatie “f : A → B” steeds van uit gaan dat f op geheel A gedefinieerd is. Wij volgen deze laatste conventie. Wanneer we het bijvoorbeeld zullen hebben over een reële functie die niet op geheel R maar slechts op een of ander deel A van R van R gedefinieerd is, zullen we steeds schrijven f : A ⊆ R → R : x 7→ f (x) dus met expliciete vermelding van het definitiegebied A in plaats van f : R → R : x 7→ f (x).

De keuze van de letters (f voor de functie, x voor de onafhankelijke variabele) is eigenlijk arbitrair. Het zijn nu eenmaal de traditionele keuzes in een puur wiskundige contextloze situatie. Als men echter afhankelijkheden modelleert in een concrete context, zoals in de voorbeelden hierboven, zal men uiteraard andere — meer suggestieve — letters kiezen voor de functies en de variabelen. Als men bijvoorbeeld wil beschrijven hoe de concentratie van een chemisch product evolueert in de tijd, ligt het voor de hand om de letter c (van concentratie) te gebruiken voor de functie en de letter t (van tijd) voor de onafhankelijke variabele; de functie zal men dan voluit noteren met c : R+ → R : t 7→ c(t) Zomercursus Wiskunde Groep Wetenschap & Technologie


14

51

waarbij c(t) = de concentratie (bv. in mg/liter) op het ogenblik t (bv. gemeten in minuten vanaf het begin van het experiment). Een intu¨ıtief uitstekende metafoor voor een functie f : A → B is die van een “input-outputmachine”. in x -

f

uit

-

f (x)

De functie krijgt als input een object uit A, noem het bijvoorbeeld x, en “maakt” er een object uit B mee dat we dan f (x) noemen. Soms kennen we een expliciet recept of voorschrift waarmee zulk een machine werkt, bijvoorbeeld f : R → R : x 7→ x2 . (13) Hier luidt het recept: neem een reëel getal en kwadrateer het. Men noemt het recept “x 7→ x2 ” of “f (x) = x2 ” hier het functievoorschrift van f . Het is het “recept” volgens hetwelk het beeldpunt gemaakt wordt met het “ingrediënt” x. Een ander voorbeeld is g : R3 → R : (x, y, z) 7→ xy + z. Hier luidt het voorschrift: neem drie reële getallen, vermenigvuldig de eerste twee met elkaar en tel daar het derde bij op. Opmerking 5.2 (Verwar f niet met f (x)) Ten prooi aan de intrinsieke luiheid die in elke mens schuilt, komen velen in de verleiding om de functie f uit (13) kortweg te omschrijven als “de functie x2 ”. Dit is inderdaad een stuk korter dan de volledige notatie in (13). Maar het gebruik van dergelijke terminologie is gevaarlijk omdat het het correcte functiebegrip kan versluieren. Het risico bestaat immers dat men de functie zelf (de “machine”) gaat verwarren met de functiewaarde (de “output van de machine”). Al snel wordt het functiebegrip dan vervormd tot iets vaag als “een formule met een x”. Gegeven het feit dat de keuze van de letter x voor de variabele arbitrair is en het feit dat men in toepassingen meestal meer suggestieve letters voor de variabelen kiest, is deze opvatting over een functie nefast, niet in het minst voor wie wiskunde in de eerste plaats wil gaan toepassen. Louter afgaand op de symbolen blijken sommigen immers te denken dat “de functie x2 ” iets anders zou zijn dan “de functie t2 ” in zoverre dat ze bijvoorbeeld wel vlot de afgeleide kunnen berekenen van “de functie x2 ” terwijl ze blokkeren bij de afgeleide van “de functie t2 ”. Maar als we de volledige notatie voor een functie gebruiken, zou het duidelijk moeten zijn dat de functie g : R → R : t 7→ t2 precies dezelfde is als de functie f in (13). Beide “machines” doen immers hetzelfde: ze kwadrateren. Wil men toch een verkorte terminologie hanteren, dan is het veel beter te spreken over bv. “de kwadrateer-functie”, “de sinusfunctie”, “ de exponentiële functie”, . . . in plaats van “de functie x2 ”, “de functie sin x”, “de functie ex ”, . . . We spreken wel van de functie x 7→ x2 of de functie x 7→ ex .13 13

Zo zal het gebruik van “de functie x”i.p.v. de functie identieke functie x 7→ x en “de functie c”i.p.v. de constante functie x 7→ c aanleiding geven tot contradicties zoals bij het aangeven van hun afgeleide functies. In vele handboeken schrijft men c′ = 0 en x′ = 1, maar wat als x = c?


52


De wijdverbreide opvatting dat een functie iets zou zijn als “een formule met een x” heeft nog een bijkomend nadeel dat andermaal zeer kwalijk is voor wie wiskunde echt wil gaan toepassen. Ze verengt immers het functiebegrip tot dat soort afhankelijkheden waarvoor er per toeval een expliciet functievoorschrift bestaat. Het moge duidelijk zijn dat de luchtdruk op een bepaalde plaats afhangt (dus functie is) van de tijd, het is al even duidelijk dat we daar natuurlijk geen formuletje voor hebben. En zo is het met zeer vele afhankelijkheden (dus functies) in diverse disciplines. Vaak hebben we enkel informatie over de afhankelijkheid via een tabel van metingen die dan eventueel in een grafiekvorm wordt gepresenteerd. Of soms hebben we hooguit kwalitatieve informatie over de betrokken functie (bv. de functie is stijgend). In veel disciplines zal men wel proberen via (benaderende) modellen voor bepaalde (eenvoudige) afhankelijkheden (benaderende) functievoorschriften te vinden.

5.2 5.2.1

Grafische voorstellingen van functies Venndiagrammen

De functie f : A → B kan voorgesteld worden met een pijlendiagram. Deze voorstelling is eigenlijk alleen handig bij eindige verzamelingen. Voorbeeld:  1 7→ a    2 7→ c f : A = {1, 2, 3, 4} → B = {a, b, c, d, e} : 3 7→ a    4 7→ c A 1• 2• 3• 4•

5.2.2

B •a •b •c •d •e

Grafiek van een functie f : A ⊆ R → R

Een functie f : A ⊆ R → R : x 7→ f (x), dus een reële functie van één reële variable, kunnen we op een bijzonder handige manier visualiseren door zijn grafiek. Per definitie is de grafiek graf(f ) van een functie f : A ⊆ R → R : x 7→ f (x) een verzameling van koppels, namelijk graf(f ) = (x, y) ∈ R × R x ∈ A en y = f (x) .

De grafiek van f is dus een deel van R × R (= R2 ). We merkten reeds in Voorbeelden 2.8 op dat we R × R kunnen identificeren met een vlak waarin we een rechthoekig Zomercursus Wiskunde Groep Wetenschap & Technologie


15

53

coördinatensysteem hebben gekozen. Elk element (x, y) van R × R correspondeert dan met één punt in het vlak, namelijk het punt met coördinaten (x, y) t.o.v. dat coördinatensysteem. De grafiek van f kunnen we dan visualiseren als de verzameling van de punten van het vlak waarvan de coördinaten (x, y) voldoen aan x ∈ A en y = f (x). Deze verzameling ziet er uit als een “kromme” in het vlak. Men noemt de uitdrukking “y = f (x)” ook wel eens de vergelijking van de grafiek (of van die kromme).

Y y = f (x)

(x, y) •

x

X

Je kan gemakkelijk inzien dat een deelverzameling G van het vlak de grafiek van een functie f : A ⊆ R → R is, als en slechts als elke verticale rechte de verzameling G in hoogstens één punt snijdt.


54


Voorbeelden 5.3 (1) De grafiek van de functie f : R → R : x 7→ sin x is Y 1 π 1

−1

2

2π

3

4

5

6

X

−1

(2) Dit is niet de grafiek van een functie. Waarom niet? Y

X

 2 als x ≤ 1,  x √ (3)f : [0, 3] → R : x 7→ f (x) = 1 + 2 − x als 1 < x < 2, heeft als grafiek  2 als x ≥ 2. Y

5.3 5.3.1

2

◦

•

1

•

◦

1

2

3 X

Operaties op functies Samenstellen van functies

Veronderstel dat in een bepaalde situatie drie grootheden in het spel zijn waarbij de eerste afhangt van de tweede en de tweede afhangt van de derde. Als de derde grootheid wijzigt zal daardoor de tweede grootheid wijzigen wat dan weer leidt tot een verandering van de eerste grootheid. Aldus zien we dat de eerste grootheid afhangt van de derde grootheid. Dit geeft aanleiding tot de notie van samenstellen van functies. Zomercursus Wiskunde Groep Wetenschap & Technologie


16

55

Beschouw functies f : A → B en g : B0 → C. De samenstelling g ◦ f : A0 → C (lees :“g na f ”) wordt gedefinieerd door (

A0 = dom(g ◦ f ) = x ∈ A f (x) ∈ B0 (g ◦ f )(x) = g f (x) voor x ∈ dom(g ◦ f )

Merk op dat een samenstelling enkel zinvol kan zijn (d.w.z. niet op de lege verzameling gedefinieerd is) als B en B0 een niet-lege doorsnede hebben. De metafoor van de input-output machine geeft ook hier de juiste intu¨ıtie. Het vormen van de samenstelling g ◦ f (g na f ) correspondeert met het in serie schakelen van de “machines” van g en f zo dat de “machine” van g werkt na die van f .

x

-

-

f

f (x)

-

-

g

g f (x)

Voorbeelden 5.4 1. Beschouw f : R → R : x 7→ x2 en g : R → R : x 7→ sin x. Dan is g ◦ f : R → R : x 7→ sin(x2 )

x

-

f

-

x2

-

-

g

sin(x2 )

en f ◦ g : R → R : x 7→ (sin x)2

x

-

g

-

sin x

-

f

-

Merk op dat f ◦ g 6= g ◦ f . 2. Beschouw f : R → R : x 7→ x + 1 en g : R0 → R : x 7→ 1/x. Dan is dom(g ◦ f ) = {x ∈ R | f (x) ∈ R0 } = {x ∈ R | x + 1 6= 0} = R \ {−1}. Bijgevolg is g ◦ f : R \ {−1} → R : x 7→ Zomercursus Wiskunde Groep Wetenschap & Technologie

1 . x+1

(sin x)2 .

56


3. Veronderstel dat de prijs P (z) voor het behandelen van z mensen die lijden aan een bepaalde ziekte, gegeven is door P (z) = 100 000 + 10 000 z. Men voorziet dat het aantal zieken als volgt zal evolueren in de tijd: z(t) = 10 + t/10. Hoe zal de kostprijs voor het behandelen van de ziekte evolueren in de tijd? Hier zijn twee functies in het spel: x -

P

-

100 000 + 10 000 x

t -

z

-

10 + t/10.

Het gevraagde wordt beschreven door de functie P ◦ z, dus ttijd

z

-

10 + t/10 -

P

-

aantal zieken

100 000 + 10 000 (10 + t/10) = 200 000 + 1000t. kostprijs

4. Beschouw de functies f : R3 → R : (x, y, z) 7→ 3xz + y 2, s g : R → R : s 7→ , 1 + s2 h : R → R3 : t 7→ (t, cos t, 1 − 2t2 ).

Hier zijn de samenstellingen g ◦ f , f ◦ h, h ◦ f en h ◦ g zinvol (waarom zijn f ◦ g en g ◦ h hier niet zinvol?). Het is niet moeilijk de expliciete functievoorschriften voor de zinvolle samenstellingen te vinden, bijvoorbeeld: g ◦ f : R3 → R : (x, y, z) 7→

3xz + y 2 , 1 + (3xz + y 2)2

h ◦ f : R3 → R3 : (x, y, z) 7→ (3xz + y 2, cos(3xz + y 2), 1 − 2(3xz + y 2 )2 ).

f ◦ h : R → R : t 7→ 3t(1 − 2t2 ) + cos2 t, s 1 + s4 s 3 h ◦ g : R → R : s 7→ , cos , . 1 + s2 1 + s2 (1 + s2 )2 Vind zelf de voorschriften van de twee andere zinvolle samenstellingen. Merk op dat we hier met de drie gegeven functies ook een ketting met drie schakels kunnen maken, bv. g ◦ f ◦ h. Ga na dat g ◦ f ◦ h : R → R : t 7→ Zomercursus Wiskunde Groep Wetenschap & Technologie

3t(1 − 2t2 ) + cos2 t

2 . 1 + 3t(1 − 2t2 ) + cos2 t


5.3.2

17

57

Bewerkingen met functies f : A → R

Omdat er bewerkingen zijn in R, kan men ook puntsgewijze bewerkingen definiëren voor functies die waarden aannemen in R. Beschouw functies f : A1 → R en g : A2 → R gedefinieerd op verzamelingen A1 resp. A2 . Beschouw ook een λ ∈ R. We definiëren hiermee functies met waarden in R door • f + g door

(

dom(f + g) = A1 ∩ A2 (f + g)(x) = f (x) + g(x) voor x ∈ dom(f + g)

• λf door

(

dom(λf ) = A1

• f g door

(

dom(f g) = A1 ∩ A2

(λf )(x) = λ.f (x) voor x ∈ dom(λf )

(f g)(x) = f (x) g(x) voor x ∈ dom(f g)

 f   dom = x ∈ A1 ∩ A2 g(x) 6= 0  f g • door f f f (x)  g  voor x ∈ dom  (x) = g g(x) g We illustreren dit met een eenvoudig voorbeeld. Beschouw f : R → R : x 7→ x − 1 en g : R+ → R : x 7→

√

x.

√ f + g : R+ → R : x 7→ x − 1 + x, √ f g : R+ → R : x 7→ (x − 1) x, Dan is f x−1 : R+ , 0 → R : x 7→ √ g x √ g x + : R \ {1} → R : x 7→ . f x−1

Samen met het samenstellen van functies beschikken we nu over een heel arsenaal van middelen om met eenvoudige functies ingewikkelde functies op te bouwen. Omgekeerd is het vaak nuttig (onder meer bij het berekenen van afgeleiden) om ingewikkelde functies uiteen te rafelen in eenvoudige functies. Beschouw bijvoorbeeld de functie f : R → R : x 7→ 3x cos x + sin2 (2x + 5). Zomercursus Wiskunde Groep Wetenschap & Technologie

58


Dan is f = f1 .f2 + f6 ◦ f5 ◦ (f3 + f4 ) met f1 f2 f3 f4

: R → R : x 7→ 3x : R → R : x 7→ cos x : R → R : x 7→ 2x : R → R : x 7→ 5

f5 : R → R : x 7→ sin x f6 : R → R : x 7→ x2 .

De “machine” van f kan dan als volgt opgebouwd worden. x f1 -3x R

x-

- f2 - x cos x x f3 -2x R

- f4 - x 5

5.4

×-

-

3x cos x

N

++-2x +f5 5

- f6 -

sin(2x + 5)

3x cos x+ sin2 (2x + 5)

sin2 (2x + 5)

Inverteren van functies

5.4.1

Inleidend probleem

Veronderstel dat men gedurende het eerste levensjaar van een baby systematisch zijn lengte en gewicht heeft bijgehouden. Dit betekent dat we functies kennen ℓ : [0, 12] → R+ : t 7→ ℓ(t), g : [0, 12] → R+ : t 7→ g(t), waarbij ℓ(t) = lengte van de baby (gemeten in centimeter) op het ogenblik t (gemeten in maanden vanaf de geboorte), g(t) = gewicht van de baby (gemeten in kilogram) op het ogenblik t (gemeten in maanden vanaf de geboorte).

ℓ

tijd Zomercursus Wiskunde Groep Wetenschap & Technologie

gewicht

lengte

Typisch zien de grafieken van ℓ en g er als volgt uit. g

tijd


18

59

De lengte ℓ(t) neemt als maar toe als t toeneemt (want baby’s krimpen niet, zelfs niet als je ze wast in te warm water). Het gewicht kan wel enigszins op en neer gaan; baby’s vallen doorgaans wat af in hun eerste levensweek en een ziekte veroorzaakt ook vaak een significant gewichtsverlies. Jaren later, als de baby groot geworden is en de nostalgie de kop opsteekt, botst de moeder nog ergens op twee vergeten foto’s van de baby die moeten genomen zijn (op mogelijks verschillende momenten) tijdens het eerste levensjaar. Op de achterkant van de ene foto heeft ze destijds fier de lengte van haar baby op dat moment genoteerd, op de andere staat hoeveel de baby woog. Kan uit deze informatie altijd worden afgeleid wanneer de foto’s genomen werden?

ℓ ℓ0

t0

tijd

gewicht

lengte

Laten we dit probleem eerst bekijken voor de foto waarop de lengte genoteerd staat. Op de grafiek van ℓ hieronder is duidelijk dat er voor elke ℓ0 ∈ R+ er hoogstens één t0 ∈ [0, 12] bestaat waarvoor ℓ(t0 ) = ℓ0 . Bijgevolg is het inderdaad mogelijk eenduidig te bepalen wanneer de foto genomen is.

g g0

tijd

Voor de foto waarop het gewicht genoteerd staat, ligt dat anders. Op de grafiek van g hierboven is duidelijk dat bepaalde waarden van gewichten (bv. g0 op de tekening) meer dan één keer werden aangenomen. We zien dus dat het (afhankelijk van de waarde van g0 ) niet altijd mogelijk zal zijn de foto eenduidig te dateren. Het feit dat het eenduidig dateren altijd kan bij de foto met de lengte maar niet altijd lukt bij de foto met het gewicht, heeft alles te maken met het feit dat de functie ℓ een speciale eigenschap heeft die de functie g niet heeft: ℓ is injectief maar g niet.

Definitie 5.5 We noemen een functie f : A → B injectief als er voor elke y ∈ B hoogstens één x ∈ A bestaat waarvoor f (x) = y.

Bijvoorbeeld de functie, waarvan onderstaande figuur het pijlendiagram is, is NIET injectief. Zomercursus Wiskunde Groep Wetenschap & Technologie

60


. .

.

A

B

Twee verschillende x-en uit A moeten dus een verschillend beeld hebben of in symbolen f : A → B injectief is als en slechts als ∀x1 , x2 ∈ A : x1 6= x2 ⇒ f (x1 ) 6= f (x2 ) . Of door contrapositie geeft dit een handiger criterium.

f : A → B is injectief

asa

∀x1 , x2 ∈ A : f (x1 ) = f (x2 ) ⇒ x1 = x2 .

Een functie is dus niet injectief als en slechts als er x1 , x2 ∈ A bestaan met x1 6= x2 waarvoor f (x1 ) = f (x2 ). Voor een reële functie f van één reële variabele, f : A ⊆ R → R, is het zeer eenvoudig aan de hand van de grafiek na te gaan of f injectief is of niet: f is injectief als en slechts als elke horizontale rechte de grafiek in hoogstens één punt snijdt.

Het is ook gemakkelijk in te zien dat een functie f : A ⊆ R → R die strikt stijgend resp. strik dalend is (d.w.z. ∀x1 , x2 ∈ A : x1 < x2 ⇒ f (x1 ) < f (x2 ) (resp. f (x1 ) > f (x2 ))), injectief is. Het omgekeerde hoeft echter niet waar te zijn: er zijn functies f : A ⊆ R → R die wel injectief zijn, maar toch niet strikt stijgend of strikt dalend zijn. Geef hier zelf een voorbeeld van met behulp van een grafiek. Injectieve functies kunnen we inverteren. Definitie 5.6 Zij f : A → B een injectieve functie. Dan kunnen we een nieuwe functie invoeren als volgt g : f (A) ⊆ B → A : y 7→ g(y), waarbij g(y) het unieke element in A is waarvoor f (g(y)) = y. We noemen g de inverse functie van f . We noteren de inverse functie van f met f −1 . Merk op dat dom(f −1 ) = f (A) = Bld(f ).



20

61

Zij f : A → B een injectieve functie. Merk op dat dan (f −1 ◦ f )(x) = x voor elke x ∈ A, m.a.w. f −1 maakt de werking van f ongedaan (vandaar de naam inverse functie). Daarom wordt een injectieve functie soms ook een inverteerbare functie genoemd.

x

-

f

-

f (x)

-

f −1

-

x

Voor functie f van (een deel van) R naar (een deel van) R kunnen we, zoals reeds opgemerkt, onmiddellijk de injectiviteit ervan aan de grafiek aflezen. Bovendien is de grafiek van de inverse van zo’n injectieve functie ook meteen te vinden. Als a ∈ domf en f (a) = b, dan is (a, b) ∈ graf(f ), door de definitie van de inverse functie f −1 zal dan f −1 (b) = a zodat (b, a) ∈ graf(f −1). We hebben dus dat (a, b) ∈ graf (f )

asa

(b, a) ∈ graf (f −1 ).

Nu liggen (a, b) en (b, a) symmetrisch t.o.v. de eerste bissectrice19 . Bijgevolg geldt dat

Als f : A → B een injectieve functie is, dan is de grafiek van f −1 is het spiegelbeed van de grafiek van f t.o.v. de eerste bissectrice. Voorbeelden 5.7 1. Wanneer we teruggrijpen naar de situatie van 5.4.1, dan zien we dat de functie ℓ injectief en dus inverteerbaar is. De functie ℓ−1 beschrijft de leeftijd van de baby als functie van zijn lengte. Schets de grafiek van ℓ−1 . Daarentegen is het niet mogelijk de leeftijd van de baby te zien als functie van zijn gewicht. Waaraan zie je dat als je de grafiek van de functie g spiegelt door de eerste bissectrice? 2. We controleren dat de functie f : R → R : x 7→ 2x + 5 injectief is. Kies hiertoe x1 , x2 willekeurig in R, dan volgt uit f (x1 ) = f (x2 ) dat 2x1 + 5 = 2x2 + 5 waaruit we kunnen besluiten dat x1 = x2 . Het criterium voor injectieviteit is dus voldaan. Bovendien is f (R) = R (bewijs dit!). De inverse van f nl. f −1 : R → R heeft dus R als domein. Om het functievoorschrift te vinden, y−5 lossen we de vergelijking y = f (x) = 2x + 5 op naar x, dit geeft x = . De 2 y−5 inverse functie die de werking van f opheft is dus f −1 : R → R : y 7→ . 2 De naam van de onafhankelijk veranderlijke is hier y, willen we zoals gebruikelijk een x als naam voor de onafhankelijk veranderlijke dan wordt de inverse functie 19

Dit is de rechte met vergelijking y = x


62


x−5 . Vergewis je ervan dat f ◦ f −1 en f −1 ◦ f telkens 2 de identieke functie opleveren. Schets de grafieken van f en f −1 en vergewis je ervan dat hun de grafieken elkaars spiegelbeeld zijn t.o.v. de eerste bissectrice.

f −1 : R → R : x 7→

3. De functie f : R+ → R+ : x 7→ x + x2 + x3 + x4 + x5 is strikt stijgend (waarom?) en dus injectief. Bovendien is f (R+ ) = R+ .21 Er bestaat dus een inverse functie f −1 : R+ → R+ . Ook al heeft f een eenvoudig functievoorschrift, toch kan je het functievoorschrift van f −1 niet in formulevorm schrijven22 . Uit de laatste twee voorbeelden kunnen we dus besluiten.

Als f : A ⊂ R → B ⊂ R : x 7→ f (x) een injectieve functie is, dan kan het functievoorschrift van f −1 : f (A) ⊂ B → A : x 7→ f −1 (x) soms gevonden door de vergelijking y = f (x) op te lossen naar x (als dit kan!) en daarna de rollen van x en y om te wisselen.

Definitie 5.8 We noemen een functie f : A → B surjectief als f (A) = B, of nog als er voor elke y ∈ B minstens één x ∈ A bestaat waarvoor f (x) = y. Onderstaande figuur is de pijlendiagram van een functie die NIET surjectief is.

. .

. . .

A

B

In verband met inverteerbaarheid van functies ontmoeten we ook nog volgend begrip.

21

Om dit te argumenteren heb je eigenlijk resultaten over limieten en continu¨ıteit nodig. Dit heeft te maken met het feit dat er geen formules (kunnen) bestaan om in het algemeen de wortels van een vijfdegraadsveelterm neer te schrijven. 22



23

63

Definitie 5.9 We noemen een functie f : A → B een bijectie als f injectief én surjectief is, dus als er voor elke y ∈ B precies één x ∈ A bestaat waarvoor f (x) = y. Merk op dat als f : A → B een injectieve functie is, de inverse functie f −1 : f (A) → A een bijectie is. In het bijzonder,

Eigenschap 5.10 als f : A → B een bijectie is (en dus f (A) = B), dan is de inverse functie f −1 : B → A ook een bijectie en (f −1 )−1 = f. Voorbeelden 5.11 f : N −→ N : x 7→ 3x + 2 is injectief maar niet surjectief. f : R −→ R : x 7→ 3x + 2 is bijectief. f : N −→ N : x 7→ x3 is injectief maar niet surjectief. 3 f : R −→ R : x 7→ x is bijectief. f : R −→ R : x 7→ x2 is niet injectief en niet surjectief. + 2 f : R −→ R : x 7→ x is niet injectief en wel surjectief. + 2 f : R −→ R : x 7→ x is injectief maar niet surjectief. f : R+ −→ R+ : x 7→ x2 is bijectief. We merken hier nogmaals op hoe belangrijk het is om bij het opgeven van een functie het domein én het codomein aan te geven. Indien je zou spreken over de functie “x2 ” of “y = x2 ”, hoe zou je dan kunnen bepalen of die functie injectief, surjectief of bijectief is? Oefeningen 5.12 1. Welke van volgende uitspraken is waar voor de functie f : R → R : x 7→ f (x) = sin x. Argumenteer telkens je bewering. (a) ∀b ∈ R : ∃a ∈ R : f (a) = b

(b) ∃b ∈ R : ∀a ∈ R : f (a) = b (c) ∀a ∈ R : ∃b ∈ R : f (a) = b

(d) ∃a ∈ R : ∀b ∈ R : f (a) = b 2. Geef door middel van een grafiek of een expliciet functievoorschrift een voorbeeld van een overal gedefinieerde functie f : R → R : x 7→ f (x) die voldoet aan ∀ε > 0 : ∃x ∈ R : |f (x) − 2| < ε, Zomercursus Wiskunde Groep Wetenschap & Technologie

64


maar NIET voldoet aan ∃x ∈ R : ∀ε > 0 : |f (x) − 2| < ε. Hint: bekijk eerst oefening 5 uit Oefeningen 4.9 3. Zij f : A ⊂ R → R : x 7→ f (x) een functie met domein A. Stel dat 2 ∈ A. Zoek welke implicaties gelden tussen volgende uitspraken. Argumenteer telkens je bewering. Als een implicatie tussen twee uitspraken niet geldt, toon dit dan ook aan door het geven van een concreet tegenvoorbeeld. (a) ∀ε > 0 : ∃x ∈ A \ {2} : |f (x) − f (2)| < ε

(b) ∃x ∈ A \ {2} : ∀ε > 0 : |f (x) − f (2)| < ε (c) ∀ε > 0 : ∀x ∈ A \ {2} : |f (x) − f (2)| < ε

(d) ∃x ∈ A \ {2} : f (x) = f (2) (e) f is een constante functie.

Hint: bekijk eerst oefening 5 uit Oefeningen 4.9 4. Zoek een voorbeeld van een niet-constante functie f : R → R die voldoet aan ∀x ∈ R : f (x) = f (−x) én ∃y ∈ R, ∀x ≥ 3 : f (x) = y. Denk in eerste instantie zeker niet in termen van een concreet functievoorschrift, maar interpreteer wat beide uitspraken over f betekenen en probeer zo de grafiek van dergelijke functie te tekenen. 5. Geef het expliciet functievooschrift van drie functies van R naar R waarvan de grafiek een rechte is en die bovendien respectievelijk voldoen aan: (a) de punten (2, 1) en (3, −2) behoren tot de grafiek.

(b) de grafiek is een rechte door het punt (1,2) met richtingscoëfficient (helling) −3.

(c) de grafiek is een rechte met richtingscoëfficient 2 die de Y-as snijdt op hoogte −8.

6. *Een functie f : R → R noemt men lineair als voldaan is aan volgende twee voorwaarden. (a) ∀x1 , x2 ∈ R : f (x1 + x2 ) = f (x1 ) + f (x2 )

(b) ∀k, x ∈ R : f (kx) = kf (x)

Is de functie f : R → R : x 7→ 2x + 3 lineair? Kan je (nog?) een voorschrift geven van een functie f : R → R die lineair is. 7. Hieronder zie je de grafiek van een functie f : R → R. Zomercursus Wiskunde Groep Wetenschap & Technologie


24

65

Y 2

1

−5

−4

−3

−2

1

−1

2

3

4

X

−1

−2

Beschrijf in woorden hoe je de grafieken van onderstaande functies bekomt uit de grafiek van f (spiegelen, verschuiven, uitrekken, samendrukken, . . . ): (a) f1 : R → R : x 7→ f (−x) (c) f3 : R → R : x 7→ f (2 x) (e) f5 : R → R : x 7→ f (1/2 x) (g) f7 : R → R : x 7→ f (x − 2) (i) f9 : R → R : x 7→ f (x + 2)

(b) f2 : R → R : x 7→ −f (x) (d) f4 : R → R : x 7→ 2 f (x) (f) f6 : R → R : x 7→ 1/2f (x) (h) f8 : R → R : x 7→ f (x) − 2 (j) f10 : R → R : x 7→ f (x) + 2

8. Hieronder zie je de grafieken van twee functies van R naar R. Welke is inverteerbaar? Waarom? Schets de grafiek van de inverse van de inverteerbare functie. Y

Y

X

X

9. Ga voor elk van de volgende functies na of ze injectief en/of surjectief zijn. (a) R → R : x 7→ x3

(b) R → R : x 7→ |x|

(c) R → R : x 7→ sin2 x 1 (d) R0 → R : x 7→ x


66


(e) R → R : x 7→ ex 10. Zijn de volgende functies injectief? Indien ja, beschrijf dan hun inverse functie met behulp van een functievoorschrift. (a) R → R : x 7→ 2x3 + 5

(b) R → R : x 7→ 12x − 11

(c) R → R : x 7→ x2 − 4x + 1

11. De functie f : R → R : x 7→ x3 is een bijectie. Geldt dit ook voor de functie g : C → C : x 7→ x3 ? 12. Een strikt stijgende of strikt dalende functie is injectief. Het omgekeerde hoeft echter niet waar te zijn: er zijn functies f : A ⊆ R → R die wel injectief zijn, maar toch niet strikt stijgend of strikt dalend zijn. Geef hier zelf een voorbeeld van met behulp van een grafiek. 13. De functie f : R → R : x 7→ (x + 2)2 is noch injectief noch surjectief, kan je iets veranderen aan het definitiegebied en/of de doelverzameling om een nieuwe functie te bekomen die injectief is maar niet surjectief, ofwel niet injectief maar wel surjectief en tenslotte bijectief. 14. Hieronder zie je de grafieken van een aantal functies van R naar R.

1

f

1

−1

h1

1

−1 −1

1

−1

−1

1

g

1

−1

h2

h3

1

1

−1 −1

1

1

−1 −1

Schets de grafieken van de functies f ◦ g, g ◦ f , f ◦ hj en hj ◦ f (voor j = 1, 2, 3). Zomercursus Wiskunde Groep Wetenschap & Technologie


26

67

15. Men noemt een functie f : R → R evenals f (−x) = f (x) voor alle x ∈ R en oneven als f (−x) = −f (x) voor alle x ∈ R. (a) Hoe kan je aan de grafiek van een functie zien of ze even/oneven is? (b) Toon aan dat elke functie van R naar R te schrijven is als de som van een even en een oneven functie. 16. We beschouwen opnieuw de functie f uit oefening 7. Schets de grafiek van volgende nieuwe functies: (a) f+ : R → R : x 7→ max{f (x), 0}

(b) f− : R → R : x 7→ min{f (x), 0} (c) |f | : R → R : x 7→ |f (x)|

Wat is het product van f+ en f− ? Kan je een verband vinden tussen f , f+ en f− , alsook tussen |f |, f+ en f− ? 17. Beschouw functies f, g : R → R. Welke van onderstaande uitspraken zijn waar, welke zijn vals? Bewijs de ware uitspraken, ontkracht de valse met een tegenvoorbeeld. (a) Als f en g injectief zijn, dan is f ◦ g ook injectief.

(b) Als f ◦ g injectief is, dan is g injectief.

(c) Als f ◦ g injectief is, dan is f injectief.

18. Beschouw de functie f : R → R : x 7→

x 2 2 2 + sin (x + 2x) . 1 + x2

Schrijf f met behulp van samenstellingen en bewerkingen met functies in termen van constante functies, de identieke functie, de kwadratische functie en de sinusfunctie. Stel het geheel grafisch voor met een schakeldiagramma voor de input-outputmachines van de eenvoudige functies. 19. Vind een voorbeeld van twee niet-constante functies f, g : R → R zodat de samenstelling f ◦ g constant is. Toemaatje: het Griekse alfabet25 Om wiskundige objecten (zoals bv. getallen, functies, . . . ) te noteren heeft men letters nodig. Om de leesbaarheid te verhogen zal men vaak eenzelfde soort objecten met gelijkaardige letters noteren. Klassieke letters voor functies zijn bv. f , g en h; voor onbekenden of variabelen ziet men dikwijls x, y en z verschijnen. Anderzijds, als men met verschillende soorten wiskundige objecten tegelijk werkt, is het aangewezen 25

Kan ook nuttig zijn op vakantie. . .


68


letters te gebruiken die voldoende anders zijn om dat onderscheid ook notationeel te suggereren. Zo kan het gebeuren dat de voorraad gewone (d.w.z. Latijnse) letters min of meer uitgeput raakt. In dat geval kunnen we Griekse letters gaan gebruiken. Of soms gebruikt men om puur traditionele redenen in sommige contexten of voor bepaalde types objecten Griekse letters (bv. voor hoeken). Ook in dit handboek zullen we (een beperkte set van) Griekse letters gebruiken. Hieronder vind je het volledige Griekse alfabet (zowel kleine letters als hoofdletters). α β γ δ ε ζ η θ ι κ λ µ

A B Γ ∆ E Z H Θ I K Λ M

alfa bêta gamma delta epsilon zêta êta thêta iota kappa lambda mu

ν ξ o π ρ σ τ υ ϕ χ ψ ω

N Ξ O Π P Σ T Υ Φ X Ψ Ω

nu xi omikron pi rho sigma tau upsilon phi chi psi omega

Zijn geen Griekse letters maar komen ook voor in wiskundige teksten: ˜ A tilde. A: ℵ: aleph. ∂: voor partiële afgeleiden ∇: nabla. ∞: oneindig.

Referenties [1] P. Desmedt, K. Hoornaert, Zelfstudiepakket: Verzamelingen en de taal van de wiskunde (3de versie), 1ste Kandidatuur Wiskunde K.U.Leuven, Leuven 2003. [2] E. Jennekens, G. Deens, Wiskunde ’68 voor het vierde jaar secundair onderwijs, Deel A Logica en Beschrijvende Statistiek, De Sikkel, Kapellen, 1972. [3] A. Kuijlaars, Bewijzen en redeneren, syllabus 1ste Bachelor Wiskunde, K.U.Leuven, 2007-2008. Zomercursus Wiskunde Groep Wetenschap & Technologie

6. Oplossingen

69

[4] J. Quaegebeur, Hogere Wiskunde I en II, 1ste Bachelor HIR, K.U.Leuven, Alta, Leuven, 2007-2008. [5] R. Verhulst, M. Verwulgen, R. De Weerdt, F. Van Roey, A. Van der Spiegel, Exponent 1, Wiskunde voor het eerste jaar secundair onderwijs, Standaard Educatieve Uitgeverij, 1992.

6

Oplossingen


Zomercursus Wiskunde. Katholieke Universiteit Leuven Groep Wetenschap & Technologie. September 2008

Recommend Documents