Syllabus Verzamelingen en Kansrekening cursus 2010/2011
W. Kager en M. van de Vel
Inhoudsopgave
1 1.1 1.2 1.3 1.4
Basisbegrippen Basisbegrippen van de verzamelingenleer Rol van verzamelingen in de kansrekening Operaties met verzamelingen Verzamelingenalgebra en redeneringen
2 2.1 2.2 2.3 2.4 2.5
Standaard uitkomstenruimtes Vier soorten trekkingen Zonder terugleggen/met volgorde Zonder terugleggen/zonder volgorde Met terugleggen/met volgorde Met terugleggen/zonder volgorde
12 12 13 16 17 19
3 3.1 3.2 3.3 3.4
Gevorderde verzamelingenleer Collecties van verzamelingen Productverzamelingen Functies en grafieken Grootte van verzamelingen
23 23 26 30 34
Antwoorden op opgaven
41
Index
43
1 1 4 6 8
1
Basisbegrippen
1.1 Basisbegrippen van de verzamelingenleer Een verzameling is in de wiskunde een (ongeordende) collectie van elementen, zoals de collectie van alle gehele getallen groter dan 0 en kleiner dan 10, of die van alle even getallen. Zo’n verzameling wordt vaak aangegeven door een opsomming van de elementen binnen accolades, waarbij de elementen worden gescheiden door komma’s. Zo kunnen we de twee genoemde verzamelingen noteren als {1, 2, 3, . . . , 9}
en
{2, 4, 6, . . . }.
Naar goed gebruik gebruiken we hier . . . om aan te duiden dat de opsomming van de voorafgaande elementen volgens hetzelfde patroon voortgezet dient te worden. We spreken af dat in zulke opsommingen de punten staan voor alle tussenliggende gehele getallen, tenzij de (gedeeltelijke) opsomming die aan de punten voorafgaat duidelijk maakt dat er een andere voortzetting bedoeld wordt. Met {1, . . . , 6} bedoelen we dus alle gehele getallen van 1 t/m 6, maar met {0, 2, 4, . . . , 12} uitsluitend de even getallen van 0 t/m 12. De volgende verzamelingen worden bekend verondersteld uit het VWO: • • • •
N = {1, 2, 3, . . . }, de verzameling van de natuurlijke getallen. Z = {. . . , −2, −1, 0, 1, 2, . . . }, de verzameling van de gehele getallen. Q, de verzameling van de rationale getallen (de breuken). R, de verzameling van de re¨ele getallen.
Merk op dat 0 niet tot de natuurlijke getallen wordt gerekend. Om de verzameling van de niet-negatieve gehele getallen {0, 1, 2, . . . } aan te geven, gebruiken we de notatie N0 of ook wel Z+ : • •
N0 := {0, 1, 2, . . . }, de verzameling van de niet-negatieve gehele getallen. Z+ := {0, 1, 2, . . . }, de verzameling van de niet-negatieve gehele getallen.
Het toekenningssymbool := geeft aan dat de uitdrukking links van het symbool (aan de kant van de dubbele punt) wordt gedefinieerd door de uitdrukking aan de rechterkant (de kant van het gelijkteken).
1
B
2
Een verzameling kun je zien als een (denkbeeldig) geheel van elementen. Dat a een element is van V drukken we uit met de notatie a ∈ V. Als a geen element is van V dan schrijven we a < V. Er geldt bijvoorbeeld 2 ∈ {1, 2, 3}
0
10 ∈ R
− 10 ∈ Z.
Als we een reeks gegevens hebben zoals a ∈ Z, b ∈ Z, c ∈ Z, dan wordt dit ook wel zuiniger weergegeven als a, b, c ∈ Z. Een tweede, veel gebruikte manier om een verzameling te noteren maakt gebruik van een omschrijving. Dat ziet er als volgt uit: {prototype : omschrijving}
of
{prototype| omschrijving}.
(1.1)
Je kunt zo’n uitdrukking lezen als “de verzameling van alle elementen van de vorm prototype, waarvoor geldt dat omschrijving”. Dit is het beste te verduidelijken met een paar voorbeelden. • • •
N0 = {z ∈ Z : z ≥ 0}. Het prototype is hier z ∈ Z en de omschrijving is “z ≥ 0”: het gaat om de verzameling van alle getallen z in Z, waarvoor geldt dat z ≥ 0. De verzameling van de even natuurlijke getallen is {n ∈ N : n is even}. Het prototype is een getal n ∈ N en de omschrijving is “n is even”: het gaat om de verzameling van alle getallen n in N, waarvoor geldt dat n even is. Een alternatieve weergave van de vorige verzameling is {2k : k ∈ N}. Het prototype is nu een getal van de vorm 2k met omschrijving “k ∈ N”: het betreft de verzameling van alle getallen van de vorm 2k waarvoor geldt dat k in N zit.
Twee verzamelingen V en W heten gelijk, notatie V = W, als ze precies dezelfde elementen bevatten, preciezer: als elk element van V ook in W zit, en elk element van W ook in V zit. Neem bijvoorbeeld V = {1, 1, 2, 3} en W = {3, 1, 2}. Dan zit elk element van V ook in W, en elk element van W zit ook in V (ga maar na), dus V = W. Kennelijk maakt het niet uit in welke volgorde de elementen van een verzameling worden opgesomd, of hoe vaak elk element in de opsomming voorkomt! Een verzameling W is een deelverzameling van V als ieder element van W ook in V zit. We noteren dit als W ⊂ V, hetgeen je kunt uitspreken als “W is bevat in V”. Een alternatieve schrijfwijze is V ⊃ W, spreek uit “V bevat W”. Er geldt bijvoorbeeld {1, 2, 3} ⊂ N
Q ⊃ Z.
Merk op: de uitspraak “V = W” is equivalent met de uitspraak “V ⊂ W en W ⊂ V”. Als W geen deelverzameling is van V, dan kunnen we dat noteren als W 1 V. De verzameling W heet een echte deelverzameling van V als W een deelverzameling is van V (W ⊂ V), maar V en W niet gelijk zijn (W , V). Zo is de verzameling {3, 1, 2, 3} bijvoorbeeld een echte deelverzameling van {1, 2, 3, 4}. Een verzameling met geen enkel element wordt een lege verzameling genoemd. Voor twee lege verzamelingen is de uitspraak “als x in de ene verzameling zit, dan zit x ook in de andere verzameling” waar, omdat de premisse altijd onwaar is. Twee lege verzamelingen zijn dus gelijk. Er is kennelijk maar e´ e´ n lege verzameling, die we de lege verzameling noemen en noteren met ∅. Merk op dat ∅ = {} (verzameling gevormd door een lege opsomming).
1.1
B
3
We sluiten deze paragraaf af met de in de wiskunde gebruikelijke notaties voor de intervallen op de re¨ele rechte: (a, b) := {x ∈ R : a < x < b}
(a, b] := {x ∈ R : a < x ≤ b} [a, b) := {x ∈ R : a ≤ x < b}
[a, b] := {x ∈ R : a ≤ x ≤ b}
(a, ∞) := {x ∈ R : x > a}
[a, ∞) := {x ∈ R : x ≥ a} (−∞, b) := {x ∈ R : x < b}
(−∞, b] := {x ∈ R : x ≤ b}
De verzameling bestaande uit de niet-negatieve re¨ele getallen noteren we ook als R+ := [0, ∞). Opgaven 1.
2.
We hebben twee re¨ele intervallen V := (1, 3) en W := [1, π). Ga na welke van de volgende uitspraken waar zijn en welke niet: (a) 1 ∈ V; (b) 1 ∈ W; (c) 0 < V; (d) π ∈ V; (e) π ∈ W; (f) V ⊂ W; (g) W ⊂ V. De verzameling V wordt als volgt gedefinieerd: V := {x ∈ Z : x is oneven of x is een drievoud}.
3.
4.
Verder hebben we de verzamelingen A := {x ∈ Z : x is even} en B := {x ∈ Z : x is een drievoud}. Ga na welke van de volgende uitspraken waar zijn en welke niet: (a) 0 ∈ V; (b) −111 ∈ V; (c) 110 ∈ V; (d) 13 ∈ V; (e) A ⊂ V; (f) B ⊂ V; (g) Z ⊂ V. Geef de volgende verzamelingen weer in de notatie met een prototype en een omschrijving zoals in formule (1.1): (a) De verzameling van alle negatieve gehele getallen; (b) De verzameling van alle irrationale (re¨ele) getallen; (c) De verzameling van alle gehele getallen die deelbaar zijn door 7; (d) De verzameling van alle positieve, irrationale getallen; (e) De verzameling van alle re¨ele nulpunten van het polynoom x3 −6x2 +11x−6. Zij A := (0, 10), B := {x ∈ R : x2 + x + 1 = 0} en C := {x ∈ R : x3 − 1 = 0}. Formuleer elk van de volgende uitspraken in gewoon Nederlands, en ga na of de uitspraak waar is of niet: (a) A ⊂ B; (b) B ⊂ C;
1
B
5.
6. 7.
4
(c) C ⊂ A. Voer voor elk van de volgende uitspraken geschikte verzamelingen A en B in, en formuleer de uitspraak dan in de vorm “A ⊂ B”: (a) Elk geheel getal dat deelbaar is door 21, is ook deelbaar door 7. (b) Alle oplossingen van de vergelijking x2 − x + 3 = 0 liggen tussen 0 en 10. (c) Het polynoom x3 − 6x2 + 11x − 6 heeft geen positieve nulpunten. Schrijf alle deelverzamelingen op van de verzamelingen V := {1} en W := {1, 2}. Bepaal het totale aantal deelverzamelingen van V := {1, 2, 3, 4}.
1.2 Rol van verzamelingen in de kansrekening Het voornaamste doel van dit vak is dat je leert een wiskundig model op te stellen voor een experiment waarin toeval een rol speelt, en hoe je vervolgens met behulp van dit model kansen op gebeurtenissen kunt uitrekenen. Het model zal voor elke mogelijke uitkomst van het experiment de kans moeten geven dat het experiment die uitkomst heeft. Het is daarom in de eerste plaats van belang te weten wat de verzameling van alle mogelijke uitkomsten van het experiment is. Die verzameling noemen we de uitkomstenruimte, en we geven hem consequent weer met S. De uitkomstenruimte S speelt bij ons de rol van wat in de verzamelingenleer het universum wordt genoemd. Met die term geven we aan dat we in het vervolg met een verzameling altijd een deelverzameling van S bedoelen, en met een uitkomst altijd een element van S. Een deelverzameling A van S noemen we in de kansrekening een gebeurtenis. Als de uitkomst van het experiment in A ligt, dan zeggen we dat de gebeurtenis A optreedt. Ons doel is de kans te bepalen dat dit gebeurt. Deze kans is de som van de kansen op elk van de uitkomsten die in A ligt. Daarom is het van belang om precies te weten welke uitkomsten er in A zitten, d.w.z., om een gebeurtenis te kunnen uitdrukken als deelverzameling van S. Dit alles klinkt misschien heel abstract. Laten we daarom eens naar een paar concrete voorbeelden van kansexperimenten kijken, en uitleggen hoe we voor deze experimenten de uitkomstenruimte S kunnen opstellen en hoe we dan een gebeurtenis als deelverzameling van S kunnen beschrijven. Voorbeeld 1 (Werpen met een dobbelsteen). Stel dat het experiment bestaat uit het e´ e´ n keer gooien met een gewone, zeszijdige dobbelsteen. Dan zijn er 6 mogelijke uitkomsten van het experiment, en het ligt voor de hand die te nummeren van 1 t/m 6, waarbij het nummer van de uitkomst overeenkomt met het aantal ogen dat is gegooid. Onze uitkomstenruimte wordt dan S = {1, . . . , 6}. Misschien ben je niet ge¨ınteresseerd in de precieze uitkomst van de worp met de dobbelsteen, maar wil je alleen maar weten of het aantal gegooide ogen even is. Deze gebeurtenis duiden we in de kansrekening aan met {er is een even aantal ogen gegooid}, d.w.z. door de omschrijving van de gebeurtenis te geven tussen accolades. Als de uitkomstenruimte S bekend is, dan staat deze uitdrukking voor de deelverzameling
1.2
R
5
van elementen van S die aan de omschrijving voldoen. In ons voorbeeld geldt {er is een even aantal ogen gegooid} = {x ∈ S : x is even}. We zeggen dat de rechterkant in bovenstaande gelijkheid de gebeurtenis aan de linkerkant “uitdrukt als deelverzameling van de uitkomstenruimte S”. De abstracte notatie aan de linkerkant heeft een belangrijk voordeel: het duidt de gebeurtenis aan op een manier die niet afhangt van de keuze van de uitkomstenruimte S en de interpretatie van de elementen van S. Dit is belangrijk, omdat er altijd meerdere keuzes voor S mogelijk zijn. Zo hadden we in dit voorbeeld ook kunnen nemen S = {0, 1, . . . , 5}, waarbij elke uitkomst staat voor het aantal gegooide ogen min 1. Dan zou juist gelden {er is een even aantal ogen gegooid} = {x ∈ S : x is oneven}. Dit lijkt misschien onnatuurlijk, maar wiskundig gezien zijn de twee keuzes volkomen equivalent. ⊳ Voorbeeld 2 (Werpen met 5 dobbelstenen). Bij Yahtzee gooi je met 5 dobbelstenen tegelijk. Hoe kunnen we voor dit experiment een uitkomstenruimte opstellen? Wel, stel je voor dat de dobbelstenen genummerd zijn van 1 t/m 5. De uitkomst van de worp met de dobbelstenen kun je dan noteren door eerst het aantal ogen van dobbelsteen 1 op te schrijven, dan die van dobbelsteen 2, enz., tot en met dobbelsteen 5. Je krijgt dus een rijtje van 5 getallen, met elk getal tussen 1 en 6. In de wiskunde noteren we zo’n geordend rijtje door de getallen, gescheiden door komma’s, tussen twee ronde haakjes te schrijven, bijvoorbeeld (1, 5, 5, 2, 6). Let erop dat dit heel iets anders is dan {1, 5, 5, 2, 6} (een verzameling die bestaat uit 4 elementen)! Wiskundig kunnen we de uitkomstenruimte voor het gooien met 5 dobbelstenen dus noteren als S = {(x1 , x2 , . . . , x5 ) : x1 , x2 , . . . , x5 ∈ {1, . . . , 6}}. Dit is de verzameling van alle rijtjes van 5 getallen, waarvoor geldt dat elk getal tussen 1 en 6 zit. Beschouw nu bijvoorbeeld de gebeurtenis {er zijn 5 verschillende aantallen ogen gegooid}. Deze gebeurtenis kunnen we als deelverzameling van S uitdrukken als {(x1 , . . . , x5 ) ∈ S : xi , x j voor alle i , j}. Het prototype bestaat hier uit alle rijtjes van lengte 5 die in S zitten, de omschrijving specificeert dat alle getallen in het rijtje verschillend moeten zijn. In de omschrijving zeggen we niet expliciet dat i en j zelf in {1, . . . , 5} moeten zitten, omdat dat hier uit de context al voldoende duidelijk is. ⊳ Het kan soms een hele kunst zijn om voor een kansexperiment een geschikte uitkomstenruimte te vinden. Gelukkig is het in veel gevallen mogelijk om gebruik te maken van een van de zogenaamde standaard uitkomstenruimtes (of een kleine variatie daarop), die we in hoofdstuk 2 zullen introduceren. Die standaard uitkomstenruimtes maken allemaal, zoals we zullen zien, gebruik van geordende rijtjes zoals in het voorafgaande voorbeeld.
1
B
111111 000000 000000 111111 000000 111111 000000 111111 A B 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111
6
11 00 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11
A11 00 00 B 11
111111 000000 000000 111111 A B 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111 000000 111111
Vereniging
Doorsnede
Verschil
Symmetrisch verschil
Complement
(A ∪ B) = A ∩ B
000000000111111111 111111111 000000000 000000000111111111 111111111 000000000 11111 00000 00000 11111 000000000 111111111 000000000 A 11111 B A A B 00000 11111 00000 000000000111111111 000000000 111111111 00000 11111 00000111111111 11111 000000000 111111111 000000000 111111111 00000 11111 00000111111111 11111 000000000 000000000 00000 11111 00000 11111 000000000111111111 000000000 111111111 00000 11111 00000111111111 11111 000000000111111111 000000000 00000 11111 00000111111111 11111 000000000 111111111 000000000 00000 11111 00000 11111 000000000111111111 000000000 111111111 00000 11111 00000111111111 11111 000000000 111111111 000000000 111111111 00000 11111 00000 11111 c c c 1.3 Operaties met verzamelingen In het vervolg beschouwen we het universum, oftewel de uitkomstenruimte S, als gegeven. Alle verzamelingen waar we over spreken zijn vanaf nu deelverzamelingen van S, oftewel gebeurtenissen in de taal van de kansrekening. Gegeven twee verzamelingen A en B kunnen we op eenvoudige wijze nieuwe verzamelingen construeren: A ∩ B := {x ∈ S : x ∈ A en x ∈ B} A ∪ B := {x ∈ S : x ∈ A of x ∈ B} A \ B := {x ∈ S : x ∈ A en x < B}
de doorsnede van A en B; de vereniging van A en B; het verschil van A met B.
In woorden: • • •
A ∩ B is de verzameling van alle elementen van S die zowel in A als in B zitten. A ∪ B is de verzameling van alle elementen van S die in tenminste e´ e´ n van de verzamelingen A en B zitten. A \ B is de verzameling van alle elementen van S die in A zitten maar niet in B.
Om je deze verzamelingen voor te kunnen stellen is het vaak handig gebruik te maken van zogenaamde Venn-diagrammen1 . Hierin geven we het universum aan als een rechthoekig kader, en deelverzamelingen daarvan als gedeeltes van de rechthoek omlijnd door een ellips (naar goed gebruik). Allerlei elementaire eigenschappen van verzamelingen kunnen met zo’n diagram op zicht duidelijk worden gemaakt. Zie de afbeelding hierboven. De bovengenoemde elementaire operaties met verzamelingen hebben een eenvoudige overeenkomstige interpretatie binnen de kansrekening: • •
De gebeurtenis A ∩ B treedt op dan en slechts dan als A en B allebei optreden. De gebeurtenis A ∪ B treedt op dan en slechts dan als tenminste e´ e´ n van de twee gebeurtenissen A en B optreedt.
1
John Venn, Engels wiskundige, 1834–1923.
1.3
O
•
7
De gebeurtenis A \ B treedt op dan en slechts dan als A optreedt, maar B niet.
In vraagstukken is het handig om deze constructies te herkennen, omdat ze het mogelijk maken om een gebeurtenis met een complex ogende omschrijving uit te drukken in gebeurtenissen waarvan de kansen eenvoudiger zijn uit te rekenen. De basisrekenregels van de kansrekening vertellen je vervolgens hoe je de kans op de complexere gebeurtenis kunt uitrekenen met behulp van de kansen op de eenvoudiger gebeurtenissen. Dit komt uitgebreid aan bod in de colleges.
Voorbeeld 3 (Gooien met een dobbelsteen). Beschouw voor het experiment waarin je met e´ e´ n dobbelsteen gooit de twee gebeurtenissen A := {er wordt een even aantal ogen gegooid}; B := {er worden meer dan 4 ogen gegooid}.
Dan geldt A ∩ B := {het gegooide aantal ogen is even en groter dan 4};
A ∪ B := {het gegooide aantal ogen is even of groter dan 4 (of beide)}; A \ B := {het gegooide aantal ogen is even maar niet groter dan 4}; B \ A := {het gegooide aantal ogen is groter dan 4 en oneven}.
⊳
Wanneer geldt A ∩ B = ∅, dan noemen we A en B disjunct. In woorden: A en B zijn disjunct als ze geen enkel element gemeenschappelijk hebben. Verder defini¨eren we Ac := S \ A = {x ∈ S : x < A}
het complement van A.
De interpretatie hiervan in de kansrekening is als volgt: •
De gebeurtenis Ac treedt op dan en slechts dan als A niet optreedt.
Merk op dat de afhankelijkheid van S niet in de notatie Ac tot uitdrukking wordt gebracht. Er wordt impliciet verondersteld dat het complement wordt genomen ten opzichte van de verzameling S van alle mogelijke uitkomsten van het experiment. Merk op dat we het verschil A \ B nu ook kunnen schrijven als A \ B = A ∩ Bc . Het is niet moeilijk om in te zien dat in het algemeen A \ B , B \ A (zie voorbeeld 3). Met andere woorden, de operatie \ is niet commutatief. Daarom gebruikt men soms het symmetrisch verschil A △ B van twee verzamelingen A en B: A △ B := (A \ B) ∪ (B \ A)
het symmetrisch verschil van A en B.
Er geldt wel altijd A △ B = B △ A. We laten het aan de lezer om de interpretatie van A △ B in de kansrekening te formuleren (opgave 1). Opgaven 1.
Geef de interpretatie van A △ B in de kansrekening.
1
B
2.
3.
4.
8
Controleer met Venn-diagrammen dat de volgende gelijkheden juist zijn. (a) A △ B = B △ A. (b) A △ B = (A ∪ B) \ (A ∩ B). Controleer met Venn-diagrammen of de volgende uitspraken correct zijn. NB: de mogelijke antwoorden zijn “ja”, “nee” of “hangt af van A en B”. (a) S = A ∪ Ac . (b) A = (B ∩ A) ∪ (Bc ∩ A). (c) S = (B \ A) ∪ (A \ B). Voor vraagstukken met re¨ele getallen zijn Venn-diagrammen vaak minder aangewezen als hulpmiddel. In deze opgave gebruiken we een voorstelling m.b.v. een assenstelsel. Gegeven zijn de volgende verzamelingen: A = {(x, y) : x, y ∈ R, x + y ≤ 1};
B = {(x, y) : x, y ∈ R, x2 + y2 ≤ 1}.
5.
6.
7.
(a) Teken de verzamelingen A en B in een (x, y)-assenstelsel. (b) Geef in de tekening de verzamelingen A ∪ B, A ∩ B, A \ B en B \ A aan. Schrijf de gegeven verzameling als een doorsnede, vereniging of verschil van de twee aangegeven verzamelingen A en B: (a) De verzameling van alle x ∈ R met 0 ≤ x ≤ 1 of 2 ≤ x ≤ 3 (neem A = [0, 1], B = [2, 3]). (b) De verzameling van alle gehele getallen die deelbaar zijn door 7, maar niet door 11 (neem A = {7n : n ∈ Z}, B = {11n : n ∈ Z}). √ (c) De verzameling van alle x ∈ R met x2 > 2 (neem A = {x ∈ R : x > 2}, √ B = {x ∈ R : x < − 2}). (d) De verzameling van alle niet-negatieve, irrationale getallen (A = R+ , B = Q). (e) De verzameling van alle negatieve, rationale getallen (A = R+ , B = Q). Ga met behulp van Venn-diagrammen na of de uitspraak waar of onwaar is: (a) A ∩ (B \ C) = (A ∩ B) \ C. (b) A ∪ (B \ C) = (A ∪ B) \ C. (c) (A \ B) ∪ (A \ C) ⊃ A \ (B ∪ C). (d) (A \ B) ∪ (A \ C) ⊂ A \ (B ∪ C). Controleer met behulp van Venn-diagrammen dat in het algemeen: (a) A \ B , B \ A. (b) (A \ B) \ C , A \ (B \ C). (c) A \ (B \ C) , (A ∪ C) \ B.
1.4 Verzamelingenalgebra en redeneringen In de vorige paragraaf hebben we Venn-diagrammen gebruikt om formules met verzamelingen te controleren. In deze paragraaf geven we meer gerichte methodes om met dergelijke formules om te gaan. De eerste methode is een algebra¨ısche methode, waarbij een complexe formule wordt ontleedt in een beperkt aantal fundamentele subformules. We kunnen de fundamentele subformules onderverdelen in een aantal groepen:
1.4
V
∅c = S Sc = ∅ A ∩ Ac = ∅ A ∪ Ac = S
S is complement van ∅ ∅ is complement van S (vgl: logische contradictie) (vgl: logische tautologie)
(Ac )c = A (A ∩ B)c = Ac ∪ Bc (A ∪ B)c = Ac ∩ Bc
involutie van complement wet van De Morgan voor ∩ wet van De Morgan voor ∪
A∩A=A A∪A=A A∩B=B∩A A∪B=B∪A
idempotentie van ∩ idempotentie van ∪ commutativiteit van ∩ commutativiteit van ∪
A ∩ (B ∩ C) = (A ∩ B) ∩ C A ∪ (B ∪ C) = (A ∪ B) ∪ C A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
associativiteit van ∩ associativiteit van ∪ distributiviteit van ∩ over ∪ distributiviteit van ∪ over ∩
A \ B = A ∩ Bc A △ B = (A ∪ B) ∩ (A ∩ B)c
omzetting via definitie van \ omzetting via definitie van △
9
Opmerking: Omdat ∩ en ∪ associatief zijn, kunnen we in het vervolg simpelweg schrijven A ∩ B ∩ C en A ∪ B ∪ C (dus zonder haakjes te gebruiken), zonder dat er verwarring kan ontstaan over wat we bedoelen. Echter, in een formule waarin zowel ∩ als ∪ voorkomt is het natuurlijk wel noodzakelijk haakjes te gebruiken! We beschouwen de bovenstaande gelijkheden nu als axioma’s van waaruit we nieuwe formules kunnen ontdekken door te rekenen. Dit leidt tot een heuse verzamelingenalgebra. Het volgende voorbeeld lijkt op de “bananenformule” voor het product (a + b)(c + d): (A ∪ B) ∩ (C ∪ D) = (A ∪ B) ∩ C ∪ (A ∪ B) ∩ D = (A ∩ C) ∪ (B ∩ C) ∪ (A ∩ D) ∪ (B ∩ D) = (A ∩ C) ∪ (B ∩ C) ∪ (A ∩ D) ∪ (B ∩ D).
Op de tweede regel werden de onderdelen (A ∪ B) ∩ C en (A ∪ B) ∩ D vervangen door gelijkwaardige onderdelen volgens de distributieve wetten. Op de derde regel hebben we de associativiteit van ∪ gebruikt om de buitenste haakjes weg te laten. Voorbeeld 4. Toon aan dat A \ (B ∩ C) = (A \ B) ∪ (A \ C). Bewijs. Volgens de definitie van \ en de eerste wet van De Morgan geldt dat A \ (B ∩ C) = A ∩ (B ∩ C)c = A ∩ (Bc ∪ Cc ).
Vervolgens gebruiken we de distributiviteit van ∩ over ∪ om te zien dat A ∩ (Bc ∪ Cc ) = (A ∩ Bc ) ∪ (A ∩ Cc ) = (A \ B) ∪ (A \ C).
⊳
1
B
10
We komen nu op de tweede manier om verzamelingenformules te bewijzen: logisch redeneren. Vooral in meer complexe gevallen is dit eigenlijk de enige goed begaanbare weg. Als je bijvoorbeeld aan moet tonen dat A ⊂ B, dan kun je een willekeurig element x van A beschouwen, en beredeneren dat x dan noodzakelijk ook in B moet zitten. Om te bewijzen dat A = B moet je zo’n redenering in beide richtingen houden. Immers, aantonen dat A = B is hetzelfde als aantonen dat A ⊂ B en B ⊂ A. We illustreren dit met een aantal voorbeelden. Voorbeeld 5. Toon aan dat {x ∈ R : x2 < 4} ⊂ [−3, 3]. Bewijs. Stel dat x een element is van R met de eigenschap x2 < 4. Dan volgt daaruit dat −2 < x < 2 en dus −3 ≤ x ≤ 3. We concluderen dat x ∈ [−3, 3]. ⊳ Voorbeeld 6. Als A ⊂ B, dan Ac ⊃ Bc . Bewijs. Neem aan A ⊂ B, en laat x een element zijn van Bc . Dan geldt dus x < B. Maar de aanname A ⊂ B zegt dat elk element van A ook in B zit, waaruit volgt dat x niet in A kan zitten: x ∈ Ac . Daarom geldt Bc ⊂ Ac . ⊳ Voorbeeld 7 (Alternatief voor voorbeeld 4). Toon aan dat A \ (B ∩ C) = (A \ B) ∪ (A \ C). Bewijs. Het bewijs gaat in twee stappen: 1.
Stel x ∈ A \ (B ∩ C). Dan zit x in A maar niet in zowel B als C. Dus zijn er twee mogelijkheden: x zit in A maar niet in B, of anders moet x wel in A en B zitten, maar niet in C. In het eerste geval zit x in A \ B, en in het tweede geval in A \ C. Daaruit concluderen we A \ (B ∩ C) ⊂ (A \ B) ∪ (A \ C).
2.
Stel x ∈ (A \ B) ∪ (A \ C). Dan kan het zo zijn dat x in A \ B zit, en zo niet, dan zit x wel in A \ C. In het eerste geval zit x wel in A maar niet in B, en dus zit x wel in A maar niet in B ∩ C. En in het tweede geval zit x wel in A maar niet in C, en dus zit x wel in A maar niet in B ∩ C. In beide gevallen geldt dus x ∈ A \ (B ∩ C), waaruit we concluderen (A \ B) ∪ (A \ C) ⊂ A \ (B ∩ C).
⊳
Voorbeeld 8 (Eerste wet van De Morgan). Toon aan dat (A ∩ B)c = Ac ∪ Bc . Bewijs. Dit bewijs gaat weer in twee stappen: 1.
2.
Neem aan dat x ∈ (A ∩ B)c . Dan zit x dus niet in zowel A als B. Daaruit volgt x < A of x < B. Maar dan geldt x ∈ Ac of x ∈ Bc , dus x ∈ Ac ∪ Bc . Hieruit concluderen we: (A ∩ B)c ⊂ Ac ∪ Bc . Stel nu x ∈ Ac ∪ Bc . Dan zit x dus in Ac of in Bc , en dus x < A of x < B. Met andere woorden, als x in A zit, dan zit x niet in B, waaruit volgt dat x niet zowel in A als in B kan zitten. Dus x ∈ (A ∩ B)c , waaruit we concluderen Ac ∪ Bc ⊂ (A ∩ B)c . ⊳
1.4
V
11
Opgaven 1.
2.
3.
4.
5.
Controleer de gegevens met behulp van Venn-diagrammen: (a) De distributieve wet A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). (b) De distributieve wet A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). (c) De wet van De Morgan (A ∩ B)c = Ac ∪ Bc . (d) De wet van De Morgan (A ∪ B)c = Ac ∩ Bc . Controleer met verzamelingenalgebra: (a) (A ∩ B) \ C = (A \ C) ∩ (B \ C). (b) (A ∪ B) \ C = (A \ C) ∪ (B \ C). (c) A \ (B ∪ C) = (A \ B) ∩ (A \ C). Bewijs of weerleg de inclusie A ⊂ B met een redenering: (a) A := {21n : n ∈ N}, B := {3n : n ∈ N}. (b) A := {1, 2, 3}, B := {x ∈ R : x3 − 6x2 + 11x − 6 = 0}. (c) A := {x ∈ R : |x| > 1}, B := {x ∈ R : x2 − x > 0}. Verifieer eerst de uitspraak met een Venn-diagram, en geef vervolgens een formeel bewijs: (a) Als A ⊂ B, dan A ∪ B = B. (b) Als A ⊂ B, dan A ∩ B = A. (c) A ∩ B ⊂ A en A ∩ B ⊂ B. (d) Als A ⊂ B, dan A \ B = ∅. Bewijs (S is uiteraard het universum): (a) Ac △ Bc = A △ B. (b) (A △ B) ∪ (A △ Bc ) = S. (c) (lastig) De associatieve eigenschap van het symmetrisch verschil: (A △ B) △ C = A △ (B △ C).
6.
(lastig) Laat A, B en C de volgende deelverzamelingen van R2 zijn: A := {(x, y) : x, y ∈ R, x2 + y2 ≤ 1}
B := {(x, y) : x, y ∈ R, |x| + |y| ≤ 1} C := {(x, y) : x, y ∈ R, |x| ≤ 1, |y| ≤ 1}
Bewijs of weerleg de volgende uitspraken: (a) A ⊂ B, A ⊂ C, B ⊂ A. (b) B ⊂ C, C ⊂ A, C ⊂ B. Aanwijzing: Maak eerst een schets, waaruit meetkundig blijkt welke inclusies gelden en welke niet. Geef daarna formele redeneringen om de correcte inclusies te bewijzen, en geef concrete punten aan in het vlak die de foute inclusies weerleggen.
2
Standaard uitkomstenruimtes
2.1 Vier soorten trekkingen Veel kansexperimenten zijn te vergelijken met het trekken van (genummerde) ballen uit een vaas. In dit hoofdstuk bekijken we de verschillende manieren waarop je ballen uit een vaas kunt trekken. Dit leidt tot de formulering van een aantal standaard uitkomstenruimtes, die niet alleen toepasbaar zijn op het trekken van ballen uit een vaas, maar ook op tal van andere kansexperimenten. Voorbeeld 9. Welke mogelijke resultaten zijn er bij drie worpen met een dobbelsteen? Je kan elk resultaat precies nabootsen door drie maal een bal te nemen uit een voorraad van 6 genummerde ballen. Omdat hetzelfde aantal ogen meerdere keren kan voorkomen, moet je elke getrokken bal terugleggen voordat je de volgende bal trekt. ⊳ Voorbeeld 10. Welke mogelijkheden zijn er bij bridge om de 52 speelkaarten te verdelen over de 4 spelers? Je kunt dit precies nabootsen door e´ e´ n voor e´ e´ n een bal te trekken uit een voorraad van 52 genummerde ballen. Elke bal staat voor een van de 52 speelkaarten. De eerste 13 getrokken ballen bepalen de kaarten die uitgedeeld worden aan speler 1, de volgende 13 horen bij speler 2, enz. In dit voorbeeld moet je elke getrokken bal niet terugleggen voordat je de volgende bal pakt. ⊳ We spreken van trekkingen met terugleggen en trekkingen zonder terugleggen. Verder moeten we afspreken of we al dan niet letten op de volgorde waarin de ballen worden getrokken. Bij het delen van speelkaarten maakt het gewoonlijk niet uit in welke volgorde de spelers de kaarten gekregen hebben, maar gaat het er alleen maar om welke kaarten ze gekregen hebben. En bij de meeste spellen met dobbelstenen gooi je de dobbelstenen tegelijkertijd en let je ook niet op de volgorde. Er zijn echter best spellen te bedenken waarin de volgorde wel uitmaakt. We onderscheiden daarom ook trekkingen met en trekkingen zonder (inachtneming van de) volgorde. Er zijn dus vier soorten trekkingen. Voor elk daarvan zullen we een standaard manier geven om de uitkomstenruimte op te stellen. We zullen hierbij uitgaan van een vaas met daarin m ballen, die genummerd zijn van 1 t/m m, waaruit we in
2.2
Z /
13
totaal n ballen trekken. We bepalen ook het precieze aantal elementen van elke uitkomstenruimte, en illustreren met voorbeelden hoe je gebeurtenissen uit kunt drukken als deelverzamelingen van de uitkomstenruimte. We illustreren ook hoe je de kansen op deze gebeurtenissen kunt uitrekenen. Daartoe maken we gebruik van het feit dat (in de meeste gevallen) elke mogelijke uitkomst van het experiment even waarschijnlijk is—we spreken dan van een homogeen kansmodel. We proberen in dit hoofdstuk zo intu¨ıtief mogelijk te werk te gaan. In hoofdstuk 3 zullen we zien dat de uitkomstenruimtes die we hier construeren in feite (deelverzamelingen van) zogenaamde productverzamelingen zijn. Ook zullen we in dat hoofdstuk formele telregels formuleren waarmee je de grootte van verzamelingen kunt bepalen. De intu¨ıtieve aanpak in dit hoofdstuk wijst daar alvast naar vooruit.
Opgaven 1.
2.
Bij Amerikaanse roulette zijn er 18 genummerde zwarte vakjes, 18 genummerde rode vakjes, en 2 groene vakjes waarin het balletje kan landen. Wat voor soort trekking komt overeen met het spelen van Amerikaanse roulette? Van een groep van 20 mensen wil je modelleren op welke dagen in het jaar zij jarig zijn. Je gaat er daarbij van uit dat iedereen op een volstrekt willekeurige dag jarig is, en je negeert schrikkeljaren. (a) Met wat voor soort trekking kun je de mogelijke verjaardagen van de 20 mensen modelleren? (b) Stel dat je weet dat alle 20 mensen op verschillende dagen jarig zijn. Met wat voor soort trekking kun je dan een mogelijke realisatie van hun verjaardagen modelleren?
2.2 Zonder terugleggen/met volgorde Trekken zonder terugleggen en met inachtneming van de volgorde is wellicht de meest voor de hand liggende methode om een trekking uit te voeren. Bij deze methode trek je een willekeurige bal uit de vaas, en noteert het nummer dat op de bal staat. Vervolgens pak je opnieuw een willekeurige bal uit de vaas, en noteert zijn nummer achter dat van de vorige getrokken bal. Zo ga je door tot je in totaal n ballen hebt getrokken. Als resultaat krijg je een rijtje van n getrokken nummers. Merk op dat noodzakelijkerwijs moet gelden n ≤ m, met m het totale aantal ballen. Een trekking zonder terugleggen/met volgorde resulteert dus in een (geordend) rijtje van n verschillende getallen. Wiskundig geformuleerd geeft dit ons de volgende standaard uitkomstenruimte voor dit experiment: S = {(x1 , x2 , . . . , xn ) : x1 , x2 , . . . , xn ∈ {1, 2, . . . , m}, xi , x j als i , j}. Hier staat xi voor het nummer op de i-de getrokken bal. Wat is nu het aantal elementen van S? In paragraaf 3.4 zullen we telregels introduceren waarmee je de grootte van verzamelingen op een formele manier kunt bepalen, maar hier geven
2
S
14
we eerst een meer intu¨ıtieve, grafische manier om in te zien wat het aantal elementen van S is. Beschouw het interval (0, 1] en bekijk de eerste trekking. Er zijn m mogelijke ballen die je kunt trekken. Verdeel het interval (0, 1] in m gelijke stukken, en associeer elk stuk met e´ e´ n van de m mogelijke trekkingen. Dit is stap 1. Bekijk vervolgens de tweede trekking. Bij elk van de voorgaande m mogelijke trekkingen zijn er nog m−1 ballen over in de vaas. Verdeel dus elk interval uit de vorige stap in m − 1 gelijke stukken, en associeer elk stuk met e´ e´ n van de mogelijke m − 1 trekkingen voor de tweede bal. Dit is stap 2. Het is duidelijk dat we na deze tweede stap m · (m − 1) intervallen hebben, omdat elk van de m intervallen uit stap 1 in m − 1 stukken werd opgedeeld. Elk van deze intervallen correspondeert met een unieke manier om twee ballen uit de vaas te trekken. Ga nu op dezelfde manier verder voor de derde trekking, de vierde trekking, enz. Voorbeeld 11. Voor een trekking zonder terugleggen/met volgorde van 3 ballen uit een vaas met in totaal 4 ballen krijgen we de volgende representatie, waarbij het nummer boven elk interval correspondeert met de bal die getrokken wordt: stap 1:
0
stap 2:
0
stap 3:
0
1 2
3
2 4
1
3
3 4
1
2
4 4
1
2
1 3
3 4 2 4 2 3 3 4 1 2 1 3 2 4 1 4 1 2 2 3 1 3 1 2
1 1
(3, 1, 4)
De gestippelde pijl in dit plaatje loopt door het interval dat correspondeert met de trekking (3, 1, 4). Merk op dat elke trekking met een uniek interval overeenkomt. ⊳ Uit de grafische constructie volgt dat na stap k het aantal verkregen intervallen gegeven wordt door m · (m − 1) · (m − 2) · · · (m − k + 1). Aangezien de intervallen na stap k precies overeenkomen met alle manieren om de eerste k ballen te pakken, volgt hieruit (door k = n te nemen) dat het totale aantal elementen van de uitkomstenruimte S gelijk is aan #S = m · (m − 1) · · · (m − n + 1). We kunnen dit ook schrijven als #S =
m! (m − n)!
waarbij m! (spreek uit “m faculteit”) gedefinieerd is door m · (m − 1) · (m − 2) · · · 1 voor m ∈ N; m! := 1 voor m = 0.
Merk in het bijzonder op dat #S = m! als we alle ballen e´ e´ n voor e´ e´ n uit de vaas trekken, d.w.z., als we n = m nemen. Het aantal volgordes waarin je m ballen kunt neerleggen is dus m!. Dit noemen we ook het aantal permutaties van m elementen.
2.2
Z /
15
Normaal gesproken is elke mogelijke uitkomst voor een trekking zonder terugleggen/met volgorde even waarschijnlijk. We kunnen dan werken met het homogene kansmodel waarbij elke uitkomst in S de kans 1/#S = (m − n)!/m! heeft. Voorbeeld 12. Neem een vaas met m = 20 ballen, en trek daaruit n = 5 ballen zonder terugleggen en met inachtneming van de volgorde. Bekijk de gebeurtenissen A = {alleen ballen met een nummer kleiner dan 11 worden getrokken}; B = {de nummers worden in oplopende volgorde getrokken}. De gebeurtenis A treedt op als de 5 getrokken ballen uit de 10 ballen met nummers 1 t/m 10 gekozen worden. Als deelverzameling van S wordt A dus beschreven door A = {(x1 , x2 , . . . , x5 ) ∈ S : x1 , x2 , . . . , x5 ∈ {1, 2, . . . , 10}} met S = {(x1 , x2 , . . . , x5 ) : x1 , x2 , . . . , x5 ∈ {1, 2, . . . , 20}, xi , x j als i , j}. Merk op dat we in de omschrijving van gebeurtenis A niet meer hoeven te vermelden dat xi , x j moet zijn voor i , j, omdat dit al volgt uit het feit dat de elementen van A uit de verzameling S komen. Om P(A) te berekenen moeten we #A bepalen. Maar dit komt precies overeen met het aantal manieren waarop je zonder terugleggen/met volgorde 5 ballen uit een vaas met in totaal 10 ballen kunt trekken. Dus #A = 10! 5! en daaruit volgt (in het homogene kansmodel) dat P(A) =
#A = #S
10! 5! 20! 15!
=
21 15! · 10! = . 20! · 5! 1292
Bekijk vervolgens de gebeurtenis A ∩ B. Nu ligt de volgorde waarin de ballen getrokken worden vast. We hebben hierboven uitgelegd dat er 5! volgordes zijn waarin je 5 verschillende ballen kunt neerleggen. Dat betekent dat er voor elke trekking zonder terugleggen/met volgorde van 5 ballen uit een vaas met in totaal 10 ballen, 5! − 1 andere trekkingen zijn waarbij dezelfde ballen betrokken zijn. Precies 10! , e´ e´ n van die 5! trekkingen is in oplopende volgorde. Hieruit volgt dat #(A∩B) = 5!·5! en dus P(A ∩ B) =
#(A ∩ B) = #S
10! 5!·5! 20! 15!
=
7 10! 15! · = . 5!5! 20! 51 680
Opgaven 1.
Druk de gebeurtenis A ∩ B uit voorbeeld 12 uit als deelverzameling van S.
⊳
2
S
16
2.3 Zonder terugleggen/zonder volgorde Soms ben je bij het trekken zonder terugleggen niet ge¨ınteresseerd in de volgorde waarin de ballen worden getrokken, maar wil je alleen weten welke ballen er getrokken worden (zoals bij gebeurtenis A in voorbeeld 12 hierboven). In dat geval zou je net zo goed in e´ e´ n greep n ballen uit de vaas kunnen trekken. We spreken dan van trekken zonder terugleggen/zonder volgorde. Om de uitkomst van zo’n trekking te noteren, zou je het volgende kunnen doen: van tevoren schrijf je de nummers 1 t/m m op een rij, en na de trekking kruis je dan de nummers door van de getrokken ballen. Achteraf kun je uit dit resultaat dan alleen achterhalen welke ballen er getrokken zijn, maar je weet niets over de volgorde, ongeacht of de ballen e´ e´ n voor e´ e´ n werden getrokken of in e´ e´ n greep. Wiskundig zou je de uitkomst kunnen noteren als een rijtje van de getrokken nummers, waarbij je de getrokken nummers altijd in oplopende volgorde noteert: S = {(x1 , x2 , . . . , xn ) : x1 , x2 , . . . , xn ∈ {1, 2, . . . , m}, x1 < x2 < · · · < xn }. In de vorige paragraaf hebben we gezien dat het aantal mogelijke uitkomsten voor een trekking van n uit m ballen zonder terugleggen/met volgorde wordt gegeven door m!/(m − n)!. Bovendien hebben we gezien dat het aantal volgordes waarin je n ballen kunt neerleggen wordt gegeven door n!. Hieruit volgt dat precies 1 op de n! volgordes waarin je n verschillende getallen kunt noteren een oplopende volgorde is. Daarom wordt het aantal elementen van S gegeven door ! m m! = , #S = n n! · (n − m)! waarbij de binomiaalco¨effici¨ent mn is gedefinieerd door ! m! als n ∈ {0, 1, . . . , m}; m n! · (n − m)! := n 0 anders. De binomiaalco¨effici¨ent mn geeft het aantal manieren waarop je n objecten kunt kiezen uit een verzameling van m objecten. We spreken ook wel van het aantal combinaties van n uit m objecten. Opnieuw zal voor het hier beschouwde type trekking het homogene kansmodel de natuurlijke keuze zijn, omdat elke greep van n ballen uit de vaas normaal gesproken dezelfde kans heeft. In dit geval heeft elke uitkomst dus de kans 1/#S = 1/ mn . Voorbeeld 13. Bekijk opnieuw een vaas met m = 20 ballen, trek nu n = 5 ballen in e´ e´ n greep, en beschouw weer de gebeurtenis A uit voorbeeld 12: A = {alleen ballen met een nummer kleiner dan 11 worden getrokken}. Gebeurtenis A treedt op als de 5 ballen uit de ballen met nummers 1 t/m 10 worden gekozen. Deze gebeurtenis is nu als deelverzameling van S te schrijven als A = {(x1 , x2 , . . . , x5 ) ∈ S : x1 , x2 , . . . , x5 ∈ {1, 2, . . . , 10}}
2.4
M /
17
waarbij S = {(x1 , x2 , . . . , x5 ) : x1 , x2 , . . . , x5 ∈ {1, 2, . . . , 20}, x1 < x2 < · · · < x5 }. Omdat er
10 5
mogelijke keuzes zijn voor de 5 getrokken ballen, krijgen we
#A P(A) = = #S
10 5 20 5
=
10! 5!·5! 20! 15!·5!
=
21 10! · 15! = . 20! · 5! 1292
Vergelijk dit met de situatie bij het trekken zonder terugleggen/met volgorde: het gevonden antwoord is hetzelfde, maar de beschrijving van A en de berekening zijn net even anders. ⊳ Er is nog een voor de hand liggende alternatieve manier om de uitkomstenruimte voor een trekking zonder terugleggen/zonder volgorde wiskundig te formuleren. Als je de trekking nabootst door de getrokken nummers door te kruisen, zoals we hierboven beschreven, dan komt dit wiskundig gezien op een natuurlijke manier overeen met de uitkomstenruimte S′ = {(y1 , y2 , . . . , ym ) : y1 , y2 , . . . , ym ∈ {0, 1}, y1 + y2 + · · · + ym = n}, waarbij yi = 0 betekent dat bal i niet werd getrokken (niet doorgekruist) en yi = 1 dat bal i wel werd getrokken (doorgekruist). Omdat er in totaal n ballen worden getrokken moet gelden y1 + y2 + · · · + ym = n, waarbij uiteraard n ≤ m moet zijn. Merk op dat het verschil tussen S en S′ slechts een kwestie is van hoe je een uitkomst wilt noteren; met elke uitkomst in S komt op een natuurlijke wijze precies e´ e´ n uitkomst in S′ overeen (opgave 1). In het bijzonder is dus #S = #S′ .
Opgaven 1.
2. 3.
Leg uit op welke wijze de twee representaties S en S′ met elkaar overeenkomen, dat wil zeggen, let uit hoe een element van S genoteerd zou worden als element van S′ en andersom. Druk de gebeurtenis A uit voorbeeld 13 uit als deelverzameling van S′ , en bereken P(A) in deze representatie. (lastig) Geef een alternatieve uitkomstenruimte S′ voor trekken zonder terugleggen/met volgorde die van dezelfde vorm is als de hierboven gegeven uitkomstenruimte S′ voor trekken zonder terugleggen/zonder volgorde.
2.4 Met terugleggen/met volgorde Bij trekken met terugleggen wordt elke getrokken bal teruggestopt in de vaas voordat de volgende bal wordt getrokken. Er zijn dan twee belangrijke verschillen met trekken zonder terugleggen: dezelfde bal kan meerdere keren worden getrokken en het aantal getrokken ballen n kan groter zijn dan het totale aantal ballen m in de vaas. Net als bij het trekken zonder terugleggen ligt het weer voor de hand de ballen
2
S
18
e´ e´ n voor e´ e´ n te trekken, en de nummers op de getrokken ballen te noteren in de volgorde waarin ze getrokken werden. Dat leidt tot de standaard uitkomstenruimte
S = {(x1 , x2 , . . . , xn ) : x1 , x2 , . . . , xn ∈ {1, 2, . . . , m}}. Vergelijk dit met de uitkomstenruimte voor trekken zonder terugleggen/met volgorde: de restrictie dat de xi ’s verschillend moeten zijn vervalt nu! Bovendien kan n nu ook groter zijn dan m. Omdat er in dit experiment voor elke getrokken bal m mogelijkheden zijn, wordt het aantal mogelijke uitkomsten gegeven door #S = m · m · · · m = mn . | {z } n factoren
Dit is opnieuw niet moeilijk in te zien met een grafische methode zoals uitgelegd in paragraaf 2.2 (opgave 1). Weer is het zo dat normaal gesproken elke mogelijke uitkomst voor deze manier van trekken even waarschijnlijk is, zodat we met het homogene kansmodel met uitkomstenruimte S kunnen werken; elke uitkomst heeft dan kans 1/#S = m−n . Voorbeeld 14. Neem opnieuw m = 20, n = 5 en de gebeurtenissen A = {alleen ballen met een nummer kleiner dan 11 worden getrokken}; B = {de nummers worden in oplopende volgorde getrokken}. Op gebeurtenis A heeft elke getrokken bal een nummer tussen 1 en 10. Deze gebeurtenis wordt als deelverzameling van S beschreven door A = {(x1 , x2 , . . . , x5 ) ∈ S : x1 , x2 , . . . , x5 ∈ {1, 2, . . . , 10}} met S = {(x2 , x2 , . . . , x5 ) : x1 , x2 , . . . , x5 ∈ {1, 2, . . . , 20}}. Het is direct duidelijk dat #A = 105 en dus P(A) =
5 1 1 #A 105 = 5 = . = #S 2 32 20
Op de gebeurtenis A ∩ B moeten de getrokken ballen 5 verschillende nummers tussen 1 en 10 hebben, en deze nummers moeten bovendien in oplopende volgorde worden getrokken. Als deelverzameling van S wordt dit A ∩ B = {(x1 , x2 , . . . , x5 ) ∈ S : x1 , x2 , . . . , x5 ∈ {1, 2, . . . , 10}, x1 < x2 < · · · < x5 }. Zoals we eerder hebben gezien heeft deze verzameling 10 5 elementen. Daarom geldt 10 #(A ∩ B) 10! 63 = = 55 = . ⊳ P(A ∩ B) = #S 800 000 20 5! · 5! · 205
2.5
M /
19
Opgaven 1.
2.
3.
Bekijk de trekking uit voorbeeld 11. Stel nu dat je in dat voorbeeld met terugleggen zou trekken in plaats van zonder terugleggen. Maak de grafische representatie voor die situatie en verifieer daarmee dat het aantal elementen van de uitkomstenruimte inderdaad gegeven wordt door mn . In voorbeelden 12, 13 en 14 keken we telkens naar dezelfde gebeurtenis A, maar voor verschillende manieren van trekken. We kregen twee verschillende uitkomsten voor de kans P(A). Verklaar waarom we twee keer dezelfde uitkomst kregen, en we de derde keer een grotere kans op A kregen. Vergelijk de uitkomsten voor de kans P(A ∩ B) uit voorbeelden 12 en 14 met elkaar en geef een verklaring voor het verschil.
2.5 Met terugleggen/zonder volgorde⋆ Ook bij het trekken met terugleggen kun je wel of geen acht slaan op de volgorde waarin je de ballen trekt. Als je niet ge¨ınteresseerd bent in de volgorde, dan zou je als volgt te werk kunnen gaan. Je maakt van tevoren een lijstje van de nummers 1 t/m m. Daarna trek je e´ e´ n voor e´ e´ n de ballen met terugleggen, waarbij je telkens een turfje zet achter het nummer van de getrokken bal. Zodoende turf je dus hoe vaak je elke bal hebt getrokken. De volgorde waarin je de ballen trok is bij deze werkwijze achteraf niet meer te achterhalen. De uitkomst van het experiment zouden we nu wiskundig kunnen noteren als een rijtje getallen y1 t/m ym die ons vertellen hoe vaak elke bal is getrokken. Dat geeft de uitkomstenruimte S′ = {(y1 , y2 , . . . , ym ) : y1 , y2 , . . . , ym ∈ {0, 1, . . . }, y1 + y2 + · · · + ym = n}. Vergelijk dit met het trekken zonder terugleggen/zonder volgorde: het verschil is dat elke bal nu meer dan 1 keer getrokken kan worden. Net als bij het trekken zonder terugleggen/zonder volgorde is het weer mogelijk de uitkomsten op een tweede manier te noteren, namelijk door de getrokken nummers in oplopende volgorde te noteren. Deze aanpak geeft de uitkomstenruimte S = {(x1 , x2 , . . . , xn ) : x1 , x2 , . . . , xn ∈ {1, 2, . . . , m}, x1 ≤ x2 ≤ · · · ≤ xn }, waarbij nu opeenvolgende nummers hetzelfde kunnen zijn (kleiner-gelijk-tekens in plaats van kleiner-dan-tekens). Weer is het zo dat er een natuurlijk e´ e´ n-op-´ee´ n verband bestaat tussen S en S′ (opgave 1). Een belangrijk verschil met de hiervoor besproken manieren van trekken is echter dat het bij trekken met terugleggen/zonder volgorde normaal gesproken niet zo is dat de verschillende uitkomsten in S (danwel S′ ) dezelfde kans hebben! De reden daarvoor is dat het aantal mogelijke volgordes waarin de nummers getrokken kunnen worden afhangt van het aantal keer dat hetzelfde nummer getrokken wordt. ⋆
Wij zullen de uitkomstenruimtes voor trekken met terugleggen/zonder volgorde in de praktijk nooit gebruiken, maar het is toch nuttig om deze paragraaf wel te lezen.
2
S
20
Bekijk om dat in te zien maar eens een uitkomst (y1 , . . . , ym ) ∈ S′ . Deze uitkomst komt overeen met het geordende rijtje (x1 , . . . , xn ) ∈ S van n getrokken nummers, waarbij het nummer i precies yi keer voorkomt. Stel nu dat we deze getrokken nummers van plaats gaan verwisselen. Dan zal daarbij het rijtje getrokken nummers hetzelfde blijven als we de yi nummers i onderling van plaats verwisselen. Omdat er yi ! verwisselingen mogelijk zijn van de nummers i onderling en er in totaal n! verwisselingen mogelijk zijn van een rijtje met lengte n, concluderen we dat het aantal verschillende volgordes waarin we de nummers (x1 , . . . , xn ) kunnen noteren gelijk is aan ! n n! . (2.1) =: y1 !y2 ! · · · ym ! y1 , y2 , . . . , ym We noemen dit de multinomiaalco¨effici¨ent met parameters n en y1 , . . . , ym . Merk op dat dit aantal inderdaad afhangt van het aantal keer dat hetzelfde nummer getrokken wordt, d.w.z. van de waarden van de yi , zoals we hierboven beweerden. Als we nu (2.1) sommeren over alle (y1 , . . . , ym ) ∈ S′ , dan moeten we uiteraard het aantal mogelijke uitkomsten voor trekken met terugleggen/met volgorde krijgen. Beknopt genoteerd geldt dus ! X n = mn . (2.2) y1 , y2 , . . . , ym y +y +···+y =n 1
2
m
Bovendien weten we dat elke uitkomst in het kansmodel voor trekken met terugleggen/met volgorde kans m−n heeft. Daaruit volgt dan dat de natuurlijke kansmaat voor trekken met terugleggen/zonder volgorde de kans ! n 1 · n P {(y1 , y2 , . . . , ym )} = y1 , y2 , . . . , ym m toekent aan de uitkomst (y1 , . . . , ym ) ∈ S′ (of, zo je wilt, aan de bijbehorende uitkomst (x1 , . . . , xn ) ∈ S). De verschillende uitkomsten zijn dus niet allemaal even waarschijnlijk als je de uitkomstenruimte S of S′ gebruikt! Om deze reden is het voor ons niet zinvol om #S′ = #S uit te rekenen voor het trekken met terugleggen/zonder volgorde. Om in deze situatie kansen uit te rekenen is het over het algemeen handiger om de uitkomstenruimte voor het trekken met terugleggen/met volgorde te gebruiken, omdat je dan kunt werken met een homogeen kansmodel. Desondanks zullen we hier met een voorbeeld illustreren hoe je in het hier beschreven model kansen op gebeurtenissen kunt uitrekenen. Voorbeeld 15. Neem m = 20, n = 5 en A = {alleen ballen met een nummer kleiner dan 11 worden getrokken}. Werken we met de uitkomstenruimte S′ , dan kunnen we A uitdrukken als A = {(y1 , y2 , . . . , y20 ) ∈ S′ : y1 + y2 + · · · + y10 = 5}. Als je liever werkt met S, dan wordt A uitgedrukt door A = {(x1 , x2 , . . . , x5 ) ∈ S : x1 , x2 , . . . , x5 ∈ {1, 2, . . . , 10}}.
2.5
M /
21
Het is dus niet zo ingewikkeld om A uit te drukken als deelverzameling van de uitkomstenruimte. Het berekenen van P(A) is in het huidige kansmodel echter lastig, omdat de verschillende uitkomsten niet allemaal dezelfde kans hebben. De formulering in termen van de uitkomstenruimte S′ is in dit geval het prettigst om mee te werken. Door te sommeren over alle uitkomsten in A en (2.2) te gebruiken, krijgen we X P(A) = P {(y1 , . . . , y20 )} (y1 ,...,y20 )∈A
! 5 1 105 1 1 5 . = · 5 = 5 = 2 32 y1 , y2 , . . . , y10 20 20
X
=
y1 +···+y10 =5
Vergelijk dit met de overeenkomstige berekening bij het trekken met terugleggen/ met volgorde in voorbeeld 14. ⊳ Hoewel we in deze cursus nooit gebruik zullen maken van het homogene kansmodel met de uitkomstenruimte S of S′ , vermelden we hier toch het aantal elementen van deze uitkomstenruimte: ! n+m−1 ′ #S = #S = . m−1 Je kunt dit zelf bewijzen in de opgaven. Opmerking. Het homogene kansmodel met uitkomstenruimte S of S′ speelt wel een belangrijke rol in de quantummechanica, namelijk in de beschrijving van het gedrag van bosonen. In de quantumwereld zijn bosonen zogenaamde ononderscheidbare deeltjes, dit in tegenstelling tot genummerde ballen in een vaas, die wel onderscheidbaar zijn.
Opgaven 1.
Teken 8 punten op een lijn: •
•
•
•
•
•
•
•
Merk op dat er dan 7 tussenruimtes tussen de punten zijn. We kunnen de punten groeperen in 4 groepen door in 3 van de tussenruimtes een verticale streep te tekenen, bijvoorbeeld: •
•
•
•
•
•
• •
(a) Hoeveel manieren zijn er om de 8 punten te verdelen over 4 groepen? (b) Noem het aantal punten in de i-de groep xi (met 1 ≤ i ≤ 4). Leg nu uit dat het aantal manieren waarop je 4 natuurlijke getallen x1 , x2 , x3 , x4 ∈ N kunt kiezen, zodanig dat hun som gelijk is aan 8, gegeven wordt door 73 . (c) Generaliseer het bovenstaande: neem r ∈ N en toon aan dat het aantal manieren waarop je s ≤ r natuurlijke getallen x1 , . . . , xs ∈ N kunt kiezen, zodanig dat hun som gelijk is aan r, gegeven wordt door r−1 s−1 .
2
S
2.
22
(lastig) Bewijs dat voor trekken met terugleggen/zonder volgorde geldt ! n+m−1 ′ #S = . m−1 Aanwijzing: gebruik de idee¨en uit opgave 1, maar let op dat in de omschrijving van S′ de getallen yi (die optellen tot n) ook de waarde 0 kunnen hebben!
3
Gevorderde verzamelingenleer
3.1 Collecties van verzamelingen Met een beetje wiskundige vaardigheid zijn we nu ook in staat om meer geavanceerde begrippen uit de verzamelingenleer te behandelen. Die begrippen vormen het onderwerp van dit hoofdstuk. Het eerste onderwerp dat we zullen behandelen vertoont analogie met de uit de calculus bekende notaties voor sommen en producten. Gegeven n getallen a1 , a2 , . . . , an kunnen we schrijven n X i=1
ai := a1 + a2 + · · · + an
en
n Y i=1
ai := a1 · a2 · · · · · an .
In de verzamelingenleer kunnen we, gegeven n verzamelingen A1 , A2 , . . . , An , in principe hetzelfde doen met de operaties van het nemen van verenigingen en doorsnedes: n [ i=1
Ai := A1 ∪ A2 ∪ · · · ∪ An
en
n \ i=1
Ai := A1 ∩ A2 ∩ · · · ∩ An .
We kunnen dit idee eenvoudig veralgemeniseren. Neem namelijk I := {1, . . . , n} en definieer [ Ai := {x ∈ S : er is een i ∈ I waarvoor geldt x ∈ Ai }; i∈I
\ i∈I
Ai := {x ∈ S : voor alle i ∈ I geldt x ∈ Ai }.
S Dan bestaat i∈I Ai dus T uit alle elementen die tot tenminste e´ e´ n van de verzamelingen Ai , met i ∈ I, horen. i∈I Ai bestaat uit alle elementen die gemeenschappelijk Sn S zijn aanTalle verzamelingen A , met i ∈ I. Het is meteen duidelijk dat A = i i∈I Ai i=1 i T en ni=1 Ai = i∈I Ai als we I := {1, . . . , n} nemen. Voorbeeld 16. Bekijk S := R, I := {1, 2, . . . , 10} en Ai := [i, i + 1] (het gesloten interval met de eindpunten i en i + 1). Dan is dus A1 = [1, 2], A2 = [2, 3], enzovoort. Het is
3
G
24
S S niet moeilijk in te zien dat i∈I Ai = [1, 11], immers, i∈I Ai is de verzameling die bestaat uit de re¨ele getallen die in tenminste e´ e´ n van de intervallen [i, i + 1] liggen, met i ∈ {1, 2, . . . , 10}. ⊳ Voorbeeld 17. Bekijk S := R, IT := {1, 2, . . . , 5} en Ai := [−i, 5 − i]. Dus A1 = [−1, 4], A2 = [−2, 3], enzovoort. Dan is i∈I Ai = [−1, 0]. ⊳
We noemen de verzameling I de indexverzameling. Het gebruik van zo’n indexverzameling is, in de eerste plaats, gemakkelijk qua S T notatie. Een bijkomend voordeel is dat de voorgaande definities van i∈I Ai en i∈I Ai ook zinvol zijn voor een willekeurige andere (niet-lege) collectie I. Nemen we in het bijzonder I := N, dan geeft dit ∞ [
i=1 ∞ \
Ai :=
[
Ai = {x ∈ S : er is een i ∈ N waarvoor geldt dat x ∈ Ai };
\
Ai = {x ∈ S : voor alle i ∈ N geldt dat x ∈ Ai }.
i∈N
Ai :=
i=1
i∈N
Op deze manier defini¨eren we dus oneindige verenigingen en doorsnedes. Voorbeeld 18. Neem opnieuw S := R S en Ai := [i, i + 1], maar neem deze keer als indexverzameling I := N. Dan geldt ∞ i=1 Ai = [1, ∞). Bewijs: ieder getal x ∈ R met x ≥ 1 is een element van tenminste e´ e´ n van de intervallen [i, i + 1], en omgekeerd, ieder element S van zo’n interval is een re¨ Se∞el getal groter of gelijk aan 1. Er geldt dus inderdaad ∞ A ⊂ [1, ∞) en [1, ∞) ⊂ ⊳ i i=1 i=1 Ai .
We zeggen dat de verzamelingen Ai met indexverzameling I := N een stijgende rij vormen alsSA1 ⊂ A2 ⊂ A3 ⊂ · · · . In dat geval defini¨eren we de limiet van de rij als limi→∞ Ai := ∞ i=1 Ai . Net zo spreken we van een dalende rij als A T1 ⊃ A2 ⊃ A3 ⊃ · · · , en we defini¨eren de limiet van zo’n dalende rij als limi→∞ Ai := ∞ i=1 Ai .
We kunnen nu ook de wetten van De Morgan en de distributieve wetten generaliseren naar verenigingen en doorsnedes over een indexverzameling I. De gegeneraliseerde wetten van De Morgan luiden \
Ai
[
Ai
i∈I
i∈I
c
=
c
=
[
Aci
(niet in allemaal = in tenminste e´ e´ n niet);
\
Aci
(niet in tenminste e´ e´ n = in allemaal niet).
i∈I
i∈I
Bewijs. We bewijzen alleen de eerste wet van De Morgan; het bewijs van de tweede is een opgave. Het bewijs gaat in twee stappen: T 1. Stel dat x < i∈I Ai . Dat betekent dat S er tenminste T e´ e´ n j ∈ ISis, zodanig dat x < A j . Dus x ∈ Acj , waaruit volgt x ∈ i∈I Aci . Dus ( i∈I Ai )c ⊂ i∈I Aci . S 2. Stel dat x ∈ i∈I Aci . Dan is er een j ∈ I waarvoor geldt dat x ∈ Acj , en dus x < A j . T S T Maar dat betekent dat x < i∈I Ai . Daarom geldt i∈I Aci ⊂ ( i∈I Ai )c .
3.1
C
25
De gegeneraliseerde distributieve wetten luiden [ [ \ \ (A ∪ Ai ). Ai = (A ∩ Ai ) en A∪ Ai = A∩ i∈I
i∈Ai
i∈I
i∈Ai
Voorbeeld 19. Zij S := (0, 2) en laat Ai := ( 12 , 1 + 1i ) voor i ∈ N. Merk op dat de Ai een dalende rij verzamelingen vormen: A1 ⊃ A2 ⊃ · · · . De verzameling T limi→∞ Ai = ∞ ele getallen die in al de verzamelingen Ai i=1 Ai bestaat uit de re¨ zitten. Dat betekent dat zo’n getal groter dan 21 moet zijn, en niet groter dan 1 mag T c zijn. Er volgt dat limi→∞ Ai = ( 21 , 1]. Ter bepaling van (bijvoorbeeld) ∞ i=1 Ai kan men T∞ c 1 een wet van De Morgan toepassen met als resultaat i=1 Ai = (0, 2 ]. merk overigens op dat de Aci een stijgende rij verzamelingen vormen: elk van deze verzamelingen omvat zijn voorganger. ⊳ In de voorgaande situaties gebruikten we een indexverzameling I en hadden we voor elke i ∈ I een verzameling Ai tot onze beschikking. Het ligt dan voor de hand om ook eens de verzameling {Ai : i ∈ I} te bekijken. Er bestaat geen beperking voor de objecten die we willen collecteren; waarom dus geen verzamelingen verzamelen? In een dergelijke context spreken we liever van een familie of een collectie, en gebruiken we sier-hoofdletters zoals F en C om deze collecties aan te duiden. Voorbeeld 20. De collectie van a´ lle deelverzamelingen van een verzameling S wordt de machtsverzameling (Engels: power set) van S genoemd, en genoteerd als P(S). Dus: P(S) := {A : A ⊂ S} Nemen we bijvoorbeeld S := {1, 2}, dan kunnen we de machtsverzameling van S expliciet weergeven door opsomming: n o P(S) = ∅, {1}, {2}, {1, 2}
Expliciete opsomming is meestal geen optie: machtsverzamelingen worden al snel gigantisch groot. Ze hebben hun naam dan ook niet gestolen. ⊳ Wanneer S wordt gebruikt als universum is de eerdere collectie C := {Ai : i ∈ I} dus een deelcollectie van P(S): ieder element van C is immers een deelverzameling van S, en dus een element van P(S).
Collecties van verzamelingen treden ook op in andere omstandigheden, namelijk bij zogenaamde partities. Dit zijn opdelingen van S in zogenaamde parten, vergelijkbaar met hoe wij de dagen van een jaar opdelen in verschillende maanden, en de dagen van de week in werkdagen en het weekend. Wiskundig zeggen we dat een collectie P van deelverzamelingen Ai van S een partitie is van S met parten Ai (voor i ∈ I met een zekere indexverzameling I) als aan drie voorwaarden is voldaan: P1 De parten zijn niet leeg: Ai , ∅ voor alle i ∈ I; P2 De parten zijn (paarsgewijs) disjunct: S Ai ∩ A j = ∅ voor alle i, j ∈ I met i , j; P3 De parten bedekken samen geheel S: i∈I Ai = S. Voorbeeld 21. Een eenvoudig ontwerp van een partitie van S is dit: neem een deelverzameling A van S met A , ∅ en A , S. Vorm de collectie P := {A, Ac }. ⊳
3
G
26
Opgaven 1. 2.
3.
4.
5.
6.
7. 8. 9.
S c T Bewijs de tweede wet van De Morgan: = i∈I Aci voor een algemene i∈I Ai indexverzameling I. Weerleg: (a) (A ∩ B) \ (C ∩ D) = (A \ C) ∩ (B \ D). (b) (A ∪ B) \ (C ∪ D) = (A \ C) ∪ (B \ D). Bewijs met een gepaste strategie: (a) Als C ⊂ A dan A ∩ (B ∪ C) = (A ∩ B) ∪ C. (b) Als A ∩ C = ∅ dan A ∪ (B \ C) = (A ∪ B) \ C. Aanwijzing: A ∩ C = ∅ impliceert: als x ∈ A, dan x < C. Laat A, B ⊂ S. Neem aan dat A ∩ B , ∅, A \ B , ∅ en B \ A , ∅. Bewijs: (a) {A ∩ B, A \ B} is een partitie van A. (b) {A ∩ B, A \ B, B \ A} is een partitie van A ∪ B. (c) Als bovendien A ∪ B , S, dan is {A ∩ B, A ∩ Bc , Ac ∩ B, Ac ∩ Bc } een partitie van S. Zij An := [1, n] ⊂ R en Bn := [n, n + 1] ⊂ R, n ∈ Z. T S10 (a) Geef de verzamelingen 10 A expliciet weer. n=1 An en S5 S n=1 n (b) Geef de verzamelingen n=1 Bn en n∈Z Bn expliciet weer. Zij S := {1, 2, 3}. (a) Beschrijf de machtsverzameling van S door opsomming. (b) Geef alle partities die S opdelen in twee parten. Geef een voorbeeld van een strict stijgende rij verzamelingen An in het universum R. S∞ T T∞ 1 1 Bepaal in R: ∞ n=1 [−n, n]. n=1 [n, ∞), n=1 [− n , n ] en Neem het universum S := [0, 2] met daarin de deelverzamelingen A1 , A2 , . . . , waarbij An :=
1 1 , 1 + 2−n = x ∈ S : < x < 1 + 2−n n+1 n+1
(n ∈ N)
(a) Bepaal T A1 ∩ A2 , A A1 ∪ A2 ∪ A3 . S1∞∩ A2 ∩TA∞3 , A1c ∪ A2Sen ∞ c A , A , en A (b) Bepaal ∞ n=1 n n=1 n n=1 n n=1 An . 10. Zij voor n ∈ N de verzameling An ⊂ (0, 1] gegeven door An := (2−n , 21−n ]. Bijvoorbeeld, A1 = ( 12 , 1]. Toon aan dat P := {A1 , A2 , . . . } een partitie is van (0, 1].
3.2 Productverzamelingen Punten in het vlak worden vaak weergegeven met twee re¨ele coordinaten als (x, y). ¨ Dat tweetal is een geordend paar: het is een paar, en de volgorde doet ertoe. De eerste coordinaat is x en de tweede is y. In hoofdstuk twee hebben we gezien dat het idee ¨ van geordende paren en, meer algemeen, geordende rijtjes ook op andere plaatsen in de wiskunde, zoals in de kansrekening, nuttig kan zijn. Bijvoorbeeld, als we twee keer met een munt werpen, dan kunnen we de mogelijke uitkomsten noteren als (0, 0), (0, 1), (1, 0), (1, 1). Hierbij staat (0, 1) voor
3.2
P
27
eerst munt en dan kop, enzovoort. Naar analogie met de notatie R2 voor het platte vlak kunnen we schrijven {0, 1}2 := {(0, 0), (0, 1), (1, 0), (1, 1)}. In deze paragraaf zullen we dit idee nog wat algemener uitwerken. Laat x en y willekeurige elementen zijn. Het geordend paar met eerste co¨ordinaat x en tweede co¨ordinaat y wordt genoteerd als (x, y). We noemen twee geordende paren (x, y) en (u, v) gelijk, notatie (x, y) = (u, v), dan en slechts dan als x = u en y = v. Bijgevolg geldt (x, y) = (y, x) alleen als x = y: de volgorde telt. Het paar (x, y) is dus iets anders dan de verzameling {x, y} (waar de volgorde er niet toe doet). Let op: als a, b ∈ R kan de notatie (a, b) ook het interval {x ∈ R : a < x < b} betekenen. In de praktijk leidt deze tweeduidigheid zelden tot verwarring: uit de context blijkt meestal wat bedoeld wordt. Stel nu dat A een deelverzameling is van een universum V, en B een deelverzameling van een universum W. Dan defini¨eren we het Cartesisch product A × B van A met B als de verzameling van alle paren (a, b) met a ∈ A en b ∈ B: A × B := {(a, b) : a ∈ A, b ∈ B}. Het prototype is hier een paar. Een alternatieve formulering is: A × B := {x : x = (a, b) voor zekere a ∈ A en b ∈ B}. De productverzameling A × B is deel van een nieuw universum, namelijk V × W. De operatie × geeft in zekere zin dus een methode om nieuwe universa te cre¨eren. Denk bijvoorbeeld terug aan de trekkingen uit hoofdstuk 2. Voor het trekken van e´ e´ n bal uit een vaas met m ballen kunnen we als “universum” nemen V := {1, 2, . . . , m}. In de kansrekening noemen we dit dan de uitkomstenruimte (S = V). Trekken we twee ballen uit de vaas, dan zitten alle mogelijke uitkomsten in de verzameling V × V := {(v1 , v2 ) : v1 , v2 ∈ V}. De operatie × cre¨eert op deze wijze dus een universum voor het trekken van twee ballen. Afhankelijk van de soort trekking is de standaard uitkomstenruimte voor de trekking gelijk aan V × V, of een echte deelverzameling van V × V. Dit kun je uitbreiden naar trekkingen van meer dan 2 ballen, zoals we hieronder zullen zien. Aangezien de verzameling A × B deel is van een nieuw universum V × W, is de operatie × van een essentieel ander type dan de operaties ∪ en ∩ uit paragraaf 1.3. Dit blijkt ook uit het feit dat ×, in tegenstelling tot ∪ en ∩, niet commutatief is: in het algemeen is A × B , B × A. Wanneer A = B geldt natuurlijk wel A × B = B × A. In dat geval schrijven we A2 := A × A = {(a, b) : a, b ∈ A} zoals in de notatie R2 voor het twee-dimensionale vlak. De toevoeging “cartesisch” verwijst naar de analogie met de door Descartes (Cartesius) ingevoerde co¨ordinaten in het vlak R2 t.o.v. een x- en een y-as. Ook gebruiken we het gewone vlak om allerlei eigenschappen van cartesische producten
3
G
2
28
C B
1
1
2
111111 000000 000000 111111 000000 111111 000000 111111 A
3
{1, 2, 3} × {1, 2}
A × (B ∩ C) = (A × B) ∩ (A × C)
A × B te illustreren. De factoren A en B worden dan voorgesteld als deelverzamelingen van de x- en y-as, respectievelijk. Daardoor wordt A × B een aanschouwelijk deel van R2 . Zo is het klassieke vlak een belangrijke inspiratiebron voor diverse eigenschappen van algemene producten. Hier zijn enkele te verwachten resultaten: als A ⊂ C en B ⊂ D dan A × B ⊂ C × D A × (B ∩ C) = (A × B) ∩ (A × C) A × (B ∪ C) = (A × B) ∪ (A × C)
(monotonie van ×); (distributiviteit van × over ∩);
(distributiviteit van × over ∪).
Analoge formules gelden voor (A ∩ B) × C en (A ∪ B) × C. We bewijzen slechts de laatste formule hierboven. Bewijs van A × (B ∪ C) = (A × B) ∪ (A × C). 1.
2.
Stel dat x ∈ A × (B ∪ C). Dan is x = (a, b) met a ∈ A en ofwel b ∈ B, of anders b ∈ C. Dus er geldt ofwel a ∈ A en b ∈ B, of anders a ∈ A en b ∈ C. Maar dan zit (a, b) in A × B of anders in A × C. Dus er geldt A × (B ∪ C) ⊂ (A × B) ∪ (A × C). Het bewijs dat (A × B) ∪ (A × C) ⊂ A × (B ∪ C) gaat op een vergelijkbare manier. Probeer dit zelf.
Er is, bij gegeven verzamelingen A, B en C een (subtiel) verschil tussen de producten A × (B × C) en (A × B) × C. De eerste verzameling bestaat uit paren waarvan de tweede coordinaat zelf een paar is, terwijl bij de paren uit de tweede ¨ verzameling de eerste coordinaat een paar is: ¨ n o A × (B × C) = (a, (b, c)) : a ∈ A, b ∈ B, c ∈ C ; n o (A × B) × C = ((a, b), c) : a ∈ A, b ∈ B, c ∈ C . De operatie × is dus behalve niet commutatief, ook niet associatief. Een nauw verwante verzameling is de volgende: A × B × C := {(a, b, c) : a ∈ A, b ∈ B, c ∈ C} met (a, b, c) een geordend drietal of tripel of geordend rijtje van lengte 3. Een belangrijk voorbeeld hiervan is de euclidische ruimte R3 . Andere voorbeelden zijn de verzameling {0, 1}3 van alle mogelijke uitkomsten bij een worp met 3 muntstukken of de uitkomstenruimte {1, 2, . . . , m}3 voor een trekking met terugleggen/met volgorde van 3 ballen uit een verzameling van m ballen.
3.2
P
29
Bij gegeven verzamelingen A1 , . . . , An met zekere n ≥ 2, wordt het n-voudige Cartesisch product gedefinieerd door n i=1
Ai := A1 × · · · × An := {(a1 , . . . , an ) : ai ∈ Ai voor i = 1, 2, . . . , n}.
Hierbij is (a1 , . . . , an ) een geordend n-tal of een geordend rijtje van lengte n. We spreken ook wel van een vector van lengte n. Het element ai wordt de i-de co¨ordinaat (of component) van het n-tal genoemd. Voor n-tallen geldt het voor de hand liggende gelijkheidsvoorschrift (a1 , . . . , an ) = (b1 , . . . , bn ) ⇐⇒ ai = bi voor alle i = 1, 2, . . . , n. In woorden: twee n-tallen zijn gelijk dan en slechts dan als componenten op gelijke posities gelijk zijn. Wanneer Ai dezelfde verzameling A is voor alle i, dan noteren we het product ook als An := A × A × · · · × A . | {z } n factoren
Een belangrijk voorbeeld hiervan is de n-dimensionale euclidische ruimte R3 . Voorbeeld 22. Schets in R2 de verzameling {1, 2} × [ 21 , 32 ]. Oplossing. {1, 2} × [ 12 , 23 ] bestaat uit alle punten (x, y) ∈ R2 waarbij x = 1 of x = 2, en 21 ≤ y ≤ 32 . Zie onderstaande figuur: 2 1
1
2
⊳
Opgaven 1. 2.
3. 4. 5. 6.
Zij A := {1, 2} en B := {2, 3}. Beschrijf de verzameling A × B door opsomming. Doe dit ook voor B × A. Zijn de verzamelingen gelijk? Zij A := {0, 1}. (a) Geef alle elementen van A2 en van A3 . (b) Geef drie verschillende punten in A4 . (c) Wat is het verschil tussen A4 en A2 × A2 ? Is R2 ⊂ R3 ? Ben je zeker van je antwoord? Teken [0, 1] × [1, 2] als deel van R2 . Teken als deel van R2 de verzamelingen: {0, 1} × R, R × {1, 2, 3}, {0, 1} × {1, 2}. Schrijf de volgende deelverzamelingen van R2 als een product van twee deelverzamelingen van R: (a) Het eerste kwadrant in R2 . (b) Het halfvlak {(x, y) ∈ R2 : x ≥ 2}.
3
G
30
(c) De verzameling {(1, 3), (1, 5), (2, 3), (2, 5), (4, 3), (4, 5)}. Schets in R2 de volgende verzamelingen: (a) A := {(x, y) ∈ R2 : x2 + y2 ≤ 1 of x ≥ y}. (b) B := {(x, y) ∈ R+2 : x + y ≤ 4 en x − y ≤ 0}. 8. Laat A, B, C, D willekeurige verzamelingen zijn. (a) Bewijs: (A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D). (b) Waarom geldt nu ook (A ∩ B) × (C ∩ D) = (A × D) ∩ (B × C)? (c) Bewijs: (A ∩ B)2 = A2 ∩ B2 , en ook: (A ∩ B)2 = (A × B) ∩ (B × A). 9. Geldt (A ∪ B) × (C ∪ D) = (A × C) ∪ (B × D) voor alle verzamelingen A, B, C, D? 10. Gegeven dat A, B, C, D niet-lege verzamelingen zijn, toon aan dat
7.
als A × B ⊂ C × D dan A ⊂ C en B ⊂ D. 11. Bewijs of weerleg de volgende uitspraken over verzamelingen A, B, C, D: (a) (A ∪ B) × C = (A × C) ∩ (B × C). (b) (A \ B) × C = (A × C) \ (B × C). (c) (A \ B) × (C ∪ D) = (A × C) \ (B × C) ∪ (A × D) \ (B × D) .
3.3 Functies en grafieken Laat V en W verzamelingen zijn. Onder een functie (of afbeelding) f van V naar W, symbolisch weergegeven door f : V → W, verstaan we een voorschrift waardoor aan elk element x van V precies e´ e´ n element y van W wordt toegevoegd. We geven deze toevoeging weer als y = f (x). Daarbij heet y de waarde van f in x, of ook wel het beeld van x onder f , en wordt x een origineel van y onder f genoemd. In de uitdrukking f (x) heet x het argument van f . Voorbeeld 23 (Kop-functie). We werpen met twee munten. De uitkomstenruimte voor dit experiment wordt gegeven door S := {0, 1}2 . Aan iedere mogelijke uitkomst kennen we nu het aantal malen kop toe. Dat kunnen we opvatten als een afbeelding X van V := S naar W := R. Zo’n afbeelding van S naar R heet in de kansrekening een stochast, en wordt meestal weergegeven met een hoofdletter aan het eind van het alfabet (dus X, Y, . . . i.p.v. f, g, . . . ). Als u := (1, 0) ∈ S dan is X(u) = 1. Voor v := (0, 1) ∈ S vinden we eveneens X(v) = 1. Omdat deze functie eindig is, kunnen we haar helemaal specificeren door bij iedere mogelijke uitkomst de waarde te noteren: X(0, 0) = 0,
X(0, 1) = 1,
X(1, 0) = 1,
X(1, 1) = 2.
⊳
Wanneer we een concrete functie f : V → W expliciet willen weergeven, doen we dit meestal door middel van een formule voor f (x). Daarbij moet duidelijk worden aangegeven in welk domein (of definitieverzameling) V het argument x gekozen wordt en in welk codomein (of bereik) W de waarde f (x) terecht moet komen. Twee functies f en g heten gelijk, notatie f = g, als (i) f en g dezelfde definitieverzameling V hebben, (ii) f en g hetzelfde bereik W hebben en (iii) voor alle x ∈ V geldt f (x) = g(x).
3.3
F
31
2
2
1
1
0
(0, 0) (0, 1) (1, 0) (1, 1) Grafiek van kop-functie
−1
0
1
Grafiek van kwadraat-functie
Voorbeeld 24 (Kwadraat). We defini¨eren de functie f : R → R met f (x) := x2 . Hier is dus V = W := R. ⊳ Iedere functie f wordt vastgelegd door haar grafiek G f . Daarmee wordt bedoeld de verzameling van alle origineel/beeld paren (x, y): G f := {(x, y) ∈ V × W : y = f (x)} = {(x, f (x)) : x ∈ V}. Voorbeeld 25 (Kop-functie, vervolg). De grafiek van de kop-functie X is n o GX = ((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2) .
⊳
Voorbeeld 26 (Kwadraat, vervolg). De grafiek van de kwadraat-functie g is de bekende dalparabool G f = {(x, x2 ) : x ∈ R}.
• • •
⊳
Een functie f : V → W heet
een injectie (injectief ) als voor alle x, y ∈ V uit f (x) = f (y) volgt dat x = y; een surjectie (surjectief ) als er voor alle y ∈ W een x ∈ V is met f (x) = y; een bijectie (bijectief ) als f injectief en surjectief is.
Een injectieve functie wordt ook wel e´e´n-´ee´nduidig of e´e´n-op-´ee´n genoemd. Injectiviteit houdt namelijk in dat twee verschillende originelen ook verschillende beelden moeten hebben. Surjectiviteit houdt in dat elk punt in W het beeld is onder f van tenminste e´ e´ n punt in V. Een surjectieve functie f : V → W wordt daarom ook wel een functie van V op W genoemd. Voorbeeld 27 (Injecties, surjecties en bijecties). • • • • •
De functie De functie De functie De functie De functie
f: f: f: f: f:
R+ → R gegeven door f (x) = x2 is injectief. R+ → R gegeven door f (x) = (x − 1)2 is niet injectief. R → R+ gegeven door f (x) = x2 is surjectief. R → R+ gegeven door f (x) = x2 + 1 is niet surjectief. R+ → R+ gegeven door f (x) = x2 is bijectief.
⊳
Beschouw weer een functie f : V → W. Zij A een deelverzameling van het domein V. Onder het beeld f (A) van A onder f verstaan we de verzameling van beelden van elementen van A: f (A) := { f (x) : x ∈ A}.
3
G
32
Het beeld f (V) van geheel V wordt de waardenverzameling W f van f genoemd: W f := f (V) = { f (x) : x ∈ V}. We kunnen ook de andere kant op. Zij B een deelverzameling van het bereik W. Het volledig origineel van de verzameling B is de verzameling f −1 (B) van alle x ∈ V met f (x) ∈ B: f −1 (B) := {x ∈ V : f (x) ∈ B}. Als B = {y} (een singleton verzameling, d.w.z., een verzameling met e´ e´ n element), dan spreken we ook wel van het volledig origineel van y (i.p.v. het singleton {y}). Voorbeeld 28 (Kop-functie, vervolg). Zij A := {(0, 0), (1, 0)}. Dan bestaat X(A) uit de elementen X(0, 0) en X(1, 0), en bijgevolg is X(A) = {0, 1}. De waardenverzameling van X is WX = X(S) = {0, 1, 2}. De worp (1, 0) is een origineel van 1 onder X. Het volledig origineel van 1 is X−1 ({1}) = {x ∈ S : X(x) = 1} = {(0, 1), (1, 0)}, en bestaat dus uit twee elementen. Anderzijds is X−1 ({3}) = ∅. Voor B := {0, 1} vinden we X−1 (B) = {(0, 0), (0, 1), (1, 0)}.
⊳
Voorbeeld 29 (Kwadraat, vervolg). Als A := (−1, 2], dan is f (A) = [0, 4]. De waardenverzameling is W f = f (V) = [0, ∞). Voor B := [−2, 1] vinden we f −1 (B) = [−1, 1]. √ √ ⊳ Verder is f −1 ({0}) = {0} en f −1 ({5}) = {− 5, 5}. In het algemene geval van een functie f : V → W kan worden vastgesteld dat f −1 (W) = V en f −1 (W f ) = V. Als B ⊂ W disjunct is met W f , dan is f −1 (B) = ∅. Tenslotte vermelden we hieronder een reeks eigenschappen die voor beeld- en origineelconstructies gelden. Daaruit blijkt dat volledig originelen zich net even iets netter gedragen dan beelden: f −1 ( f (A)) ⊃ A
(A ⊂ V);
−1
f ( f (B)) ⊂ B f (A1 ∩ A2 ) ⊂ f (A1 ) ∩ f (A2 )
f (A1 ∪ A2 ) = f (A1 ) ∪ f (A2 )
f
−1
(B1 ∩ B2 ) = f
−1
(B1 ) ∩ f
−1
(B ⊂ W); (A1 , A2 ⊂ V); (B2 )
f −1 (B1 ∪ B2 ) = f −1 (B1 ) ∪ f −1 (B2 ) Bewijs van f −1 (B1 ∪ B2 ) = f −1 (B1 ) ∪ f −1 (B2 ). 1.
2.
(A1 , A2 ⊂ V);
(B1 , B2 ⊂ W);
(B1 , B2 ⊂ W).
Zij x ∈ V willekeurig en neem aan dat x ∈ f −1 (B1 ∪ B2 ). Dan is f (x) ∈ B1 ∪ B2 (definitie origineel), dus f (x) ∈ B1 of f (x) ∈ B2 . De definitie van origineel geeft dan x ∈ f −1 (B1 ) of x ∈ f −1 (B2 ). Dus x ∈ f −1 (B1 ) ∪ f −1 (B2 ). Neem vervolgens aan dat x ∈ f −1 (B1 ) ∪ f −1 (B2 ). De definitie van origineel geeft f (x) ∈ B1 of f (x) ∈ B2 . Met andere woorden: f (x) ∈ B1 ∪ B2 , en dus (weer de definitie van origineel) x ∈ f −1 (B1 ∪ B2 ).
3.3
F
33
Opgaven Zij f : (−1, 3) → R gegeven door f (x) := x2 . (a) Wat is het domein van f en wat is het codomein? (b) Wat is de waardenverzameling W f ? 2. Zij f : (−1, 1) → R gegeven door f (x) := |x|. (a) Teken de grafiek G f van f . (b) Wat is het beeld f ((− 13 , 14 )) van het open interval (− 13 , 41 )? (c) Wat is het volledig origineel f −1 ([0, 12 ]) van het gesloten interval [0, 21 ]? (d) Geef twee verzamelingen A1 , A2 ⊂ (−1, 1) waarvoor f (A1 ∩ A2 ) , f (A1 ) ∩ f (A2 ). (e) Waar of niet waar: f (A ∪ B) = f (A) ∪ f (B) voor iedere A, B ⊂ (−1, 1)? (f) Waar of niet waar: f −1 (A ∪ B) = f −1 (A) ∪ f −1 (B) voor iedere A, B ⊂ R? 3. Ga na of de gegeven verzameling G gezien kan worden als de grafiek G f van een R-waardige functie f op een deel van R. Zo ja, geef domein en bereik van f : (a) G := {(x, y) ∈ R2 : x2 + y2 = 1}. (b) G := {(x, y) ∈ R × R+ : x2 + y2 = 1}. (c) G := {(x, y) ∈ R2 : x · y = 1}. (d) G := {(x, y) ∈ R2 : x · y = 0}. 4. Bepaal het beeld van A onder f : (a) A := [−2, 0) en f : R → R met f (x) := x2 . (b) A := [0, 1]2 en f : R2 → R met f (x, y) := x2 + y2 . (c) A := {1, . . . , 10} en f : N → R met f (n) := 1/n2 . 5. Bepaal het volledig origineel van B onder f : (a) B := {0} en f : R → R met f (x) := sin(x). (b) B := {−1} en f : R → R met f (x) := x2 + x. (c) B := Z en f : R → R met f (x) := x2 . (d) B := {−1, 0, 1, 2, 3} en f : Z → Z met f (n) := 1 − n. (e) B := [1, 2]2 en f : R → R2 met f (x) := (2x + 1, x − 1). 6. Zij f een functie van V naar W. (a) Bewijs: f (Ac ) ⊃ ( f (A))c ∩ W f voor alle A ⊂ V. (b) Bewijs: f −1 (Bc ) = ( f −1 (B))c voor alle B ⊂ W. 7. Ga na of de volgende functies injectief, surjectief of beide (dus bijectief) zijn: (a) f : Z → N met f (n) := |n| + 1. (b) f : R → R met f (x) := x3 . (c) f : R → R met f (x) := x3 − x. (d) f : R+ → [0, 1) met f (x) := x/(1 + x). (e) f : R → R2 met f (x) := (2x + 1, x − 1). 8. Laat zien dat voor een functie f : V → W geldt: (a) f is injectief ⇐⇒ f −1 ( f (A)) = A voor alle A ⊂ V. (b) f is surjectief ⇐⇒ f ( f −1 (B)) = B voor alle B ⊂ W. (c) f is injectief ⇐⇒ f (A1 ∩ A2 ) = f (A1 ) ∩ f (A2 ) voor alle A1 , A2 ⊂ V. 9. Gegeven zijn twee functies f1 : V → W1 en f2 : V → W2 . Vorm nu een nieuwe functie f : V → W1 × W2 , gegeven door f (x) := ( f1 (x), f2 (x)). (a) Toon aan: f is injectief als f1 en f2 injectief zijn. (b) Laat met een voorbeeld zien dat het resultaat in (a) niet waar is als “injectief” wordt vervangen door “surjectief” of “bijectief”. 10. Is de gegeven functie injectief, surjectief of bijectief? (a) f : R → R gedefinieerd door f (x) := ex . 1.
3
G
34
√ (b) g : (0, ∞) → R2 gedefinieerd door g(x) := ( x, ln(x)). (c) h : R2 → R gedefinieerd door h(x, y) = 2y. 11. Gegeven is de functie h : R2 → R2 met h(x, y) := (2xy, x2 + y2 ). Laat zien dat h niet injectief en niet surjectief is. 12. Gegeven is de functie h : R × (0, ∞) → R met h(x, y) := 2x + ln(y). Is h injectief, surjectief of bijectief? 13. Is de gegeven functie injectief, surjectief of bijectief? (a) f : R2 → R2 gedefinieerd door f (x, y) := (x2 , y2 ). (b) f : R+2 → R+2 gedefinieerd door f (x, y) := (x2 , y2 ). (c) g : R → R2 gedefinieerd door g(x) := (sin(x), cos(x)). (d) g : [0, 2π) → R2 gedefinieerd door g(x) := (sin(x), cos(x)). (e) h : R2 → R gedefinieerd door h(x, y) := x + y.
3.4 Grootte van verzamelingen Het deel van de wiskunde dat zich bezig houdt met de bepaling van het aantal elementen van allerlei eindige verzamelingen, wordt de combinatoriek genoemd. In deze paragraaf gaan we op zoek naar een wiskundig precieze definitie van de grootte van een verzameling, waarmee we niet alleen de groottes van eindige, maar ook van oneindige verzamelingen met elkaar kunnen vergelijken. Eerst keren we terug naar de intu¨ıtieve manier waarop we het aantal elementen van de standaard uitkomstenruimtes uit hoofdstuk 2 hebben geteld. Bestudeer daarom voordat je verder leest nogmaals voorbeeld 11. Met de grafische telmethode uit voobeeld 11 is het niet moeilijk om een drietal elementaire telregels te bewijzen, die we nu zullen formuleren. Hierbij veronderstellen we een eindige verzameling V gegeven, en noteren het aantal elementen van V door #V. De eerste telregel is zo elementair, dat we geen bewijs geven. Telregel 1 (De somregel). Als n ∈ N en {Ai : i = 1, . . . , n} is een partitie van V, dan is #V =
n X i=1
#Ai = #A1 + #A2 + · · · + #An .
Deze regel laat toe om een verzameling te tellen door bepaalde delen Ai (i = 1, . . . , n) ervan te tellen. Daarbij moet men vooral op twee dingen letten: S 1. Zijn alle elementen van V wel meegeteld, m.a.w., is ni=1 Ai = V? 2. Zijn er geen elementen dubbel geteld, m.a.w., is Ai ∩ A j = ∅ voor i , j? Aan deze voorwaarden is voldaan als {Ai : i = 1, . . . , n} een partitie vormt van V (met de extra eis dat de parten niet leeg zijn). Bij toepassing van de eerste telregel is het dus zaak een handige partitie van V te vinden. Voorbeeld 30 (Werpen met twee dobbelstenen). Bij een worp met twee dobbelstenen I en II zijn er 6 mogelijke uitkomsten waarbij I een 6 te zien geeft (verzameling A), en ook 6 waarbij II een 6 te zien geeft (verzameling B). Maar het aantal uitkomsten met tenminste e´ e´ n 6 is dan niet #A + #B = 6 + 6 = 12, maar 11: de collectie {A, B}
3.4
G
35
is g´ee´ n partitie van de worpenverzameling. W´el een partitie is de collectie {A, B, C} met A : alle worpen waarbij alleen I een 6 geeft; B : alle worpen waarbij alleen II een 6 geeft; C : alle worpen waarbij zowel I als II een 6 geven. Dat geeft als telresultaat: #A + #B + #C = 5 + 5 + 1 = 11.
⊳
De tweede en derde telregel vertonen grote analogie met de tellingen die we gedaan hebben van het aantal elementen van de uitkomstenruimtes voor trekkingen met terugleggen/met volgorde, en zonder terugleggen/met volgorde. We geven hier alleen het bewijs van de derde telregel (die een generalisatie is van de tweede). Telregel 2 (De productregel). Zij n ≥ 2 en V := ni=1 Ai = A1 × · · · × An . Dan is #V =
n Y i=1
#Ai = #A1 · #A2 · · · #An .
Telregel 3 (Gegeneraliseerde productregel). Zij n ≥ 2 en V een verzameling n-tallen uit ni=1 Ai , met de eigenschap dat de eerste coordinaat m1 verschillende waardes ¨ kan hebben, bij elke waarde van de eerste coordinaat, de tweede coordinaat m2 ¨ ¨ verschillende waardes kan hebben, bij elke waarde van de eerste twee coordinaten, ¨ de derde coordinaat m3 verschillende waardes kan hebben, enzovoort. Dan is ¨ #V =
n Y i=1
mi = m1 · m2 · · · mn .
Bewijs. Gebruik de grafische constructie uit voorbeeld 11. In de eerste stap deel je het interval (0, 1] op in m1 even lange stukken, elk corresponderend met e´ e´ n van de mogelijke waardes voor de eerste coordinaat. In stap 2 deel je elk verkregen ¨ interval weer op in m2 stukken, elk stuk corresponderend met e´ e´ n van de mogelijke waardes voor de eerste twee coordinaten samen. Enzovoort. ¨ Na n stappen heb je m1 · m2 · · · mn intervallen gekregen. Het is duidelijk uit de constructie dat elk interval correspondeert met e´ e´ n van de n-tallen uit de verzameling V. Bovendien corresponderen twee verschillende intervallen met twee verschillende n-tallen uit V: er moet immers een stap m ≤ n geweest zijn waarbij de intervallen voor het eerst van elkaar gescheiden werden, hetgeen betekent dat de bijbehorende n-tallen van elkaar verschillen in de m-de coordinaat. Hieruit volgt ¨ dat het aantal elementen van V gelijk is aan het aantal verkregen intervallen. In het voorgaande bewijs hebben we in feite een bijectie geconstrueerd tussen de collectie sub-intervallen van (0, 1] en de verzameling V, waaruit we concludeerden dat de twee verzamelingen dezelfde grootte hebben. Dit is nu precies hoe we in de wiskunde de grootte van verzamelingen zullen defini¨eren: twee verzamelingen V en W noemen we gelijkmachtig, of van dezelfde grootte, als er een bijectie van V naar W bestaat. Verder defini¨eren we de grootte van de verzameling {1, 2, . . . , m} als m. Daaruit volgt dus: #V = m ⇐⇒ er bestaat een bijectie f : {1, . . . , m} → V.
3
G
36
Dat dit een natuurlijke definitie is blijkt ook uit het volgende voorbeeld: Voorbeeld 31 (Stoelendans). Stel dat je een groep mensen wilt laten plaatsnemen in een zaal met een beperkt aantal stoelen, en je wilt weten of er genoeg stoelen zijn. Dan kun je de mensen e´ e´ n voor e´ e´ n naar binnen laten, en ieder op de eerstvolgende vrije stoel laten plaatsnemen. Zo contrueer je een injectieve afbeelding van de groep mensen naar de stoelen. Als er aan het eind stoelen over zijn (de afbeelding is injectief maar niet surjectief), dan kun je concluderen dat het aantal mensen kleiner was dan het aantal stoelen. Als uiteindelijk alle stoelen bezet raken, terwijl iedereen een plaats heeft gevonden (de afbeelding is zowel injectief als surjectief), dan waren er precies evenveel stoelen als mensen. En als op een zeker moment alle stoelen bezet zijn, terwijl er nog mensen buiten staan, dan kun je de overgebleven mensen alleen nog in de zaal kwijt door ze bij anderen op schoot te laten zitten (de afbeelding is surjectief maar niet injectief). In dat geval waren er meer mensen dan stoelen. ⊳ Als toepassing van de definitie van gelijkmachtigheid bepalen we in het volgende voorbeeld de grootte van de machtsverzameling van een eindige verzameling V. Voorbeeld 32 (Grootte van een machtsverzameling). Het aantal deelverzamelingen van een verzameling V met m elementen is 2m . Bewijs. We construeren een bijectie f : P(V) → {0, 1}m , als volgt. Laat a1 , a2 , . . . , am de elementen van V zijn. Als X ⊂ V dan defini¨eren we f (X) := (b1 , b2 , . . . , bm ) met op positie i het “bit” 1 als ai ∈ X; bi := 0 als ai < X.
Het bit op positie i geeft dus aan of het punt ai al dan niet in de deelverzameling X zit. Bij elk m-tal (b1 , . . . , bm ) is er dus een origineel X ⊂ V dat door f op dit m-tal wordt afgebeeld, bestaande uit precies die ai waarvoor het bijbehorende bit bi 1 is. En dit origineel is uniek, want voor elke Y ⊂ V met Y , X zal f (Y) op tenminste e´ e´ n positie van f (X) verschillen. Daarom is f : P(V) → {0, 1}m een bijectie, en dus geldt #P(V) = #({0, 1}m ) = 2m . ⊳ Het mooie van de definitie van gelijkmachtigheid is dat deze definitie ook prima hanteerbaar is voor verzamelingen die oneindig veel elementen bevatten. De definitie stelt ons in staat de grootte van zulke oneindige verzamelingen met elkaar te vergelijken. In de wiskunde spreekt men overigens vaak liever over de cardinaliteit van een verzameling i.p.v. de grootte. De cardinaliteit van een verzameling A wordt vaak genoteerd als |A| i.p.v. #A. Er geldt dus per definitie • •
|A| ≤ |B| als er een injectie f : A → B bestaat; |A| = |B| als er een bijectie f : A → B bestaat.
Voorbeeld 33. De verzamelingen Q en (−1, 1) ∩ Q zijn gelijkmachtig. Dit volgt uit het feit dat de afbeelding f : Q → (−1, 1) ∩ Q een bijectie is (ga na).
gegeven door
f (x) :=
x 1 + |x| ⊳
3.4
G
37
Voor ieder getal n ∈ N, hoe groot ook, is {1, . . . , n} een eindige verzameling. Daarom lijkt de limiet van deze (stijgende) rij verzamelingen, dit is de verzameling N := {1, 2, 3 . . . }, de “kleinst mogelijke” oneindige verzameling te zijn. Maar deze zienswijze is niet erg adequaat. Voorbeeld 34. De verzameling V van natuurlijke getallen groter dan 100 is een echte deelverzameling van N. Toch is V gelijkmachtig met N, want de funtie f : N → V gegeven door f (n) := n + 100 is een bijectie. ⊳ Voorbeeld 35 (Even getallen). De verzameling W van alle even natuurlijke getallen is een echte deelverzameling van N. Intu¨ıtief gesproken is W maar half zo groot als N, want het complement van W in N is even groot als W (er is een bijectie f : W c → W gegeven door f (n) := n + 1). Toch zijn W en N gelijkmachtig. Om dit in te zien construeren we de bijectie g : N → W gegeven door g(n) := 2n. ⊳ Een verzameling V die gelijkmachtig is met N wordt aftelbaar oneindig genoemd. De elementen van zo’n verzameling kun je door middel van een bijectie f : N → V met de natuurlijke getallen aftellen. Anders uitgedrukt: je kunt ze op een rij zetten in een volledige aftelling (of opsomming) van V, V = {x1 , x2 , x3 , . . . }, waarbij het n-de element is gegeven door xn := f (n). Zo heeft de bijectie g uit voorbeeld 35 de volgende aftelling van de even natuurlijke getallen W tot gevolg: W = {2, 4, 6, . . . }. Voorbeeld 36 (Gehele getallen). De verzameling Z is aftelbaar oneindig. Om dit aan te tonen construeren we de functie h : N → Z gegeven door 1 voor n even; 2n h(n) := − 12 (n − 1) voor n oneven.
We bewijzen dat h een bijectie is: 1. 2.
Zij z ∈ Z willekeurig. Als z > 0, neem dan n = 2z. Als z ≤ 0, neem dan n = −2z + 1. In beide gevallen is n ∈ N en h(n) = z. Dus h is surjectief. Zij n, m ∈ N willekeurig en neem aan dat h(n) = h(m). Als h(n) > 0, dan volgt uit h(n) = h(m) dat 21 n = 21 m en dus n = m. Als daarentegen h(n) ≤ 0, dan volgt uit h(n) = h(m) dat − 21 (n − 1) = − 12 (m − 1), dus wederom n = m. Dus h is injectief.
De bijectie h geeft ons de volgende aftelling van Z: Z = {0, 1, −1, 2, −2, 3, −3, . . . }.
⊳
Een verzameling V wordt aftelbaar genoemd als V eindig of aftelbaar oneindig is. Niet-aftelbare verzamelingen worden overaftelbaar genoemd. Aftelbare verzamelingen zijn in veel opzichten eenvoudiger dan overaftelbare verzamelingen. Dit blijkt al uit het feit dat het niet mogelijk is om de elementen van een overaftelbare verzameling “op een rij te zetten”. De verzameling Q van de rationale getallen lijkt een kandidaat te zijn: Q lijkt immers flink wat groter dan N en Z. Bovendien weten we dat er tussen twee verschillende rationale getallen altijd een derde rationaal getal bestaat. Dat bemoeilijkt het op een rij zetten van deze getallen. Toch kunnen we ook Q aftellen.
3
G
38
Voorbeeld 37 (Rationale getallen). Een aftelling van het rationale interval (0, 1) ∩ Q wordt gegeven door o n1 1 2 1 3 1 2 3 4 (0, 1) ∩ Q = , , , , , , , , , . . . . 2 3 3 4 4 5 5 5 5
Hierbij worden de onherleidbare breuken afgeteld naar stijgende noemers, en, bij gelijke noemers, naar stijgende tellers. Aftelbaarheid van Q kan uit dit resultaat worden afgeleid met een bijectie van Q naar (0, 1) ∩ Q, zie de opgaven. ⊳ Omdat elk positief rationaal getal x te schrijven is als x = m/n voor zekere (m, n) ∈ N2 , vermoeden we dat ook N2 aftelbaar is. Dat vermoeden is juist, zie de opgaven. Meer in het algemeen volgt dat het product van twee aftelbare verzamelingen aftelbaar is. De verzameling R van alle re¨ele getallen is niet aftelbaar. In het volgende voorbeeld laten we zien dat het re¨ele interval (0, 1) niet aftelbaar is, waaruit dit resultaat onmiddellijk volgt. Het is een opgave om zelf een bijectie van (0, 1) naar R te construeren. Voorbeeld 38 (Het interval (0, 1) is niet aftelbaar). Elk punt x ∈ (0, 1) heeft een unieke decimale voorstelling 0,d1 (x) d2 (x) d3 (x) . . . die niet eindigt in alleen maar nullen, dus bijvoorbeeld 1/4 = 0,24999 · · · i.p.v. 0,25000 · · · . Stel nu dat we (0, 1) w´el zouden kunnen aftellen: (0, 1) = {x1 , x2 , . . . } voor zekere x1 , x2 , . . . . Beschouw de decimale voorstellingen van de xi ’s uit deze veronderstelde aftelling: x1 = 0,d1 (x1 ) d2 (x1 ) d3 (x1 ) · · ·
x2 = 0,d1 (x2 ) d2 (x2 ) d3 (x2 ) · · ·
x3 = 0,d1 (x3 ) d2 (x3 ) d3 (x3 ) · · · ...
We zullen nu een nieuw punt x ∈ (0, 1) cre¨eren, dat verschilt van elk van de xi ’s. Dat nieuwe getal x leggen we als volgt vast middels zijn decimale voorstelling x = 0,d1 (x) d2 (x) d3 (x) · · · : als (voor i = 1, 2, 3, . . . ) di (xi ) > 5, dan stellen we di (x) = di (xi ) − 1, en anders stellen we di (x) = di (xi ) + 1. Het is niet moeilijk in te zien dat x in (0, 1) ligt, omdat geen van de decimalen van x 0 of 9 is. Bovendien verschilt x vanwege de constructie van elk getal xi in de i-de decimaal. Dus is x een getal uit het interval (0, 1) dat geen element is van {x1 , x2 , . . . }. Daarom kan {x1 , x2 , . . . } geen aftelling van (0, 1) geweest zijn. ⊳ Het is niet moeilijk te bewijzen dat de machtsverzameling P(V) van een verzameling V niet gelijkmachtig kan zijn met V zelf. Veronderstel namelijk dat f : V → P(V) een bijectie is, en definieer A := {x ∈ V : x < f (x)}. Dan is A een deelverzameling van V, dus als f een bijectie is, dan moet er een x ∈ V bestaan zodanig, dat f (x) = A. Stel nu dat x ∈ A. Op grond van de definitie van A moet dan gelden x < f (x), maar dat is onmogelijk, aangezien f (x) = A. Maar als je veronderstelt dat x < A, dan volgt uit de definitie van A dat moet gelden x ∈ f (x), hetgeen weer onmogelijk is, aangezien f (x) = A. De aanname dat f een bijectie is leidt dus tot een contradictie. Daarom kan er geen bijectie f : V → P(V) bestaan. Hiermee volgt dat ook de verzameling P(N) overaftelbaar is. In de opgaven wordt aannemelijk gemaakt dat P(N) gelijkmachtig is met (0, 1). De verzameling P((0, 1)) heeft dan weer grotere machtigheid. Zo kan men steeds “machtiger” verzamelingen construeren: er is geen “machtigste” verzameling.
3.4
G
39
Opgaven 1.
2.
Laat A en B twee verzamelingen zijn. Leg uit aan de hand van een telregel: (a) #A = #(A \ B) + #(A ∩ B). (b) #(A ∪ B) = #(A \ B) + #(A ∩ B) + #(B \ A). Bewijs dat voor willekeurige eindige verzamelingen A en B geldt #(A ∪ B) = #A + #B − #(A ∩ B).
3.
Aanwijzing: pas de vorige opgave toe. Bewijs dat voor elke drie eindige verzamelingen A, B, C geldt #(A ∪ B ∪ C) = #A + #B + #C − #(A ∩ B) − #(B ∩ C) − #(A ∩ C) + #(A ∩ B ∩ C).
4.
Aanwijzing: pas herhaald de vorige opgave toe. Zij V := {1, 2, . . . , 6}. We construeren hiermee de verzameling W := {(x, y) ∈ V 2 : x < y}.
5. 6. 7.
8.
9.
Laat zien dat de verzamelingen Ai := {(i, y) ∈ V 2 : i < y} voor i = 1, . . . , 5 een partitie vormen van W en bepaal vervolgens met de eerste telregel #W. Hoeveel deelverzamelingen heeft de verzameling {1, 2, . . . , 6}? Hoeveel deelverzamelingen heeft {1, 2}3 ? (a) Als V ⊂ W en V , W, kan V dan gelijkmachtig zijn met W? (b) Als V ⊂ W, W eindig en V , W, kan V dan gelijkmachtig zijn met W? Gegeven zijn telkens twee verzamelingen V en W. Laat met een concrete bijectie f : V → W zien dat de twee verzamelingen gelijkmachtig zijn: (a) V := {3n + 1 : n ∈ N} en W := {2n : n ∈ N}. (b) V := [0, 1] en W := [3, 8]. (c) V := [0, 1) en W := {(x, y) ∈ R2 : x2 + y2 = 1}. (d) V := R en W := (− 21 π, 12 π). (e) V := Q en W := (0, 1) ∩ Q. (f) V := R en W := (0, 1). (lastig) Het doel van deze opgave is om in enkele stappen aan te tonen dat elke oneindige deelverzameling A van N aftelbaar is. Merk eerst op dat voor iedere a ∈ A de verzameling [1, a]∩N eindig is. Dus is ook de deelverzameling [1, a]∩A eindig. Zij nu g : A → N de functie met als voorschrift g(a) := #{x ∈ A : x ≤ a}. (a) Laat zien dat als a1 < a2 , dan g(a1 ) < g(a2 ) voor alle a1 , a2 ∈ A. (b) Toon aan: voor iedere a ∈ A en n ∈ N geldt: als n ≤ g(a), dan is n ∈ g(A). Aanwijzing: er zijn precies g(a) elementen x in A met x ≤ a, en voor iedere dergelijke x is g(x) ≤ g(a)—gebruik nu onderdeel (a). (c) Gebruik de onderdelen (a) en (b) om aan te tonen dat g : A → N een bijectie is. (bewerkelijke opgave) Laat f : N2 → N gedefinieerd zijn door f (m, n) := (2m − 1)2n−1 . (a) Bereken de waarden van f (m, n) voor m, n ≤ 3. (b) Voor welke (m, n) ∈ N2 geldt f (m, n) = 112? (c) Geef achtereenvolgens f −1 ({i}) voor i = 1, 2, . . . , 10.
3
G
40
(d) Laat zien dat f bijectief is. Aanwijzing: toon ineens aan dat elk natuurlijk getal e´ e´ n origineel heeft onder f . (e) Wat betekent dit resultaat voor de “grootte” van N2 ? 10. Beschouw de verzameling P(N) van alle deelverzamelingen van N en de verzameling {0, 1}∞ van alle oneindige rijtjes van nullen en enen. Definieer f : P(N) → {0, 1}∞ door 1 als i ∈ X; f (X) := (a1 , a2 , . . . ) met a + i := 0 als i < X. Laat zien dat f bijectief is, en dus dat P(N) en {0, 1}∞ gelijkmachtig zijn. NB: Omdat een oneindig rijtje nullen en enen gezien kan worden als de binaire voorstelling van een re¨eel getal tussen 0 en 1, volgt hiermee (met wat extra werk) dat ook P(N) en (0, 1) gelijkmachtig zijn.
Antwoorden op opgaven
Hieronder vind je, per paragraaf, de antwoorden op een deel van de opgaven. §1.1 1a: niet waar, 1b: waar, 1c: waar, 1d: niet waar, 1e: niet waar, 1f: waar, 1g: niet waar, 2a: waar, 2b: waar, 2c: niet waar, 2d: niet waar, 2e: niet waar, 2f: waar, 2g: niet waar, 3a: {z ∈ Z : z < 0}, 3b: {x ∈ R : x < Q}, 3c: {z ∈ Z : 7z ∈ Z} of {7z ∈ Z : z ∈ Z}, 3d: {x ∈ R : x > 0 en x < Q}, 3e: {x ∈ R : x3 − 6x2 + 11x − 6 = 0}, 4a: “Ieder getal tussen 0 en 10 is een oplossing van x2 + x + 1 = 0”; niet waar, 4b: “Als x2 + x + 1 = 0 en x re¨eel, dan x3 − 1 = 0”; waar, 4c: “Alle re¨ele oplossingen van x3 − 1 = 0 liggen tussen 0 en 10”; waar, 5a: A = {21z : z ∈ Z} en B = {7z : z ∈ Z}, 5b: A = {x ∈ R : x2 − x + 3 = 0} en B = (0, 10), 5c: A = {x ∈ R : x3 − 6x2 + 11x − 6 = 0} en B = {x ∈ R : x ≤ 0}, 6: van V: ∅ en {1} = V, van W: ∅, {1}, {2} en {1, 2} = W, 7: 16. §1.3 1: A △ B treedt op dan en slechts dan als precies e´ e´ n van beide gebeurtenissen A en B optreedt, 3a: ja, 3b: ja, 3c: hangt af van A en B, 5a: A ∪ B, 5b: A \ B, 5c: A ∪ B, 5d: A ∩ Bc = A \ B, 5e: Ac ∩ Bc , 6a: waar, 6b: niet waar, 6c: waar, 6d: niet waar. §1.4 3a: waar, 3b: waar, 3c: waar, 6a: niet waar, waar, waar, 6b: waar, niet waar, niet waar. §2.1 1: met terugleggen/met volgorde (38 ballen), 2a: met terugleggen/met volgorde (365 ballen), 2b: zonder terugleggen/met volgorde (365 ballen). §2.2 1: A ∩ B = {(x1 , . . . , x5 ) ∈ S : x1 , . . . , x5 ∈ {1, . . . , 10}, x1 < x2 < · · · < x5 }. §2.3 2: A = {(y1 , . . . , y20 ) ∈ S′ : y1 + · · · + y10 = 5}, 3: laat yi het nummer van de trekking zijn waarbij je bal i pakt; S′ = {(y1 , . . . , ym ) : y1 , . . . , ym ∈ {0, 1, . . . , n} en voor elke j ∈ {1, . . . , n} is er precies e´ e´ n i ∈ {1, . . . , m} zodat yi = j}. §2.5 1a: 73 , 2: verdeel n + m punten in m groepen, en noem yi + 1 het aantal punten in groep i. §3.1 2a: neem bv. B = D = A en C = ∅, 2b: neem bv. C = B en D = A, 5a: {1}, [1, 10], 5b: [1, 6], R, 6a: {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}, 6b: {{1}, {2, 3}}, {{2}, {1, 3}}, {{3}, {1, 2}}, 7: bv. An = (0, n], n ∈ N, 8: ∅, {0}, R, 9a: ( 21 , 54 ), ( 21 , 98 ), ( 31 , 32 ), ( 41 , 23 ), 9b: ( 21 , 1], (0, 32 ), (−∞, 0] ∪ [ 23 , ∞), (−∞, 21 ] ∪ (1, ∞).
A
42
§3.2 1: {(1, 2), (1, 3), (2, 2), (2, 3)} en {(2, 1), (2, 2), (3, 1), (3, 2)}; niet gelijk, 2a: (0, 0), (0, 1), (1, 0), (1, 1) en (0, 0, 0), (0, 0, 1) , (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1), 2c: A4 bestaat uit 4-tallen, A2 × A2 uit paren van paren, 3: nee; ja, 6a: R+ × R+ , [2, ∞) × R, {1, 2, 4} × {3, 5}, 9: nee, neem bv. A = C := {0} en B = D := {1}, 11a: niet waar, 11b: waar, 11c: waar. §3.3 1a: (−1, 3) en R, 1b: [0, 9), 2b: [0, 31 ), 2c: [− 12 , 12 ], 2d: bv. A1 := (−1, 0) en A2 := (0, 1), 2e: √ waar, 2f: waar, 3a: nee, 3b: ja, f : [−1, 1] → R met f (x) := 1 − x2 , 3c: ja, f : R \ {0} → 1 1 , . . . , 100 }, 5a: {kπ : k ∈ Z}, R\{0} met f (x) := 1x , 3d: nee, 4a: (0, 4], 4b: [0, 2], 4c: {1, 41 , 19 , 16 √ √ 5b: ∅, 5c: { n : n ∈ N0 } ∪ {− n : n ∈ N}, 5d: {−2, −1, 0, 1, 2}, 5e: ∅, 7a: surjectie, 7b: bijectie, 7c: surjectie, 7d: bijectie, 7e: injectie, 10a: injectie, 10b: injectie, 10c: surjectie, 12: surjectie, 13a: geen van alle, 13b: bijectief, 13c: geen van alle, 13d: injectief, 13e: surjectief. §3.3 4: #W = 15, 5: 26 = 64 en 28 = 256, 7a: f (k) = 32 (k − 1), 7b: f (x) = 5x + 3, 7c: x + 1 , 7f: f (x) = f (x) = (cos(2πx), sin(2πx)), 7d: f (x) = arctan(x), 7e: f (x) = 21 1+|x| 1 1 π arctan(x) + 2 , 9b: (4, 5), 9c: (1, 1), (1, 2), (2, 1), (1, 3), (3, 1), (2, 2), (4, 1), (1, 4), (5, 1), (3, 2).
Index
aantal elementen, 34 afbeelding, 30 e´ e´ n-´ee´ n-duidige —, 31 aftelbaar, 37 aftelbaar oneindig, 37 aftelling, 37 argument, 30 associativiteit, 9 beeld, 30, 31 bereik, 30 bijectie, 31, 35 binomiaalco¨effici¨ent, 16 breuken, 1 cardinaliteit, 36 Cartesisch product, 27, 29 coordinaat, 27, 29 ¨ codomein, 30 collectie, 25 combinaties, 16 combinatoriek, 34 commutativiteit, 9 complement, 7, 9 component, 29 dalende rij, 24 deelverzameling, 2, 4 echte —, 2 definitieverzameling, 30 disjunct, 7 distributiviteit, 9, 25, 28 domein, 30
doorsnede, 6, 23, 24 element, 1, 2, 4 euclidische ruimte, 29 faculteit, 14 familie, 25 formule, 30 functie, 30 e´ e´ n-´ee´ n-duidige —, 31 gebeurtenis, 4 gehele getallen, 1, 37 niet-negatieve —, 1 gelijkheid, 2, 27, 29, 30 gelijkmachtig, 35 geordend n-tal, 29 geordend drietal, 28 geordend paar, 26, 27 geordend rijtje, 5, 26, 28, 29 grafiek, 31 grootte, 35, 36 homogeen kansmodel, 13 idempotentie, 9 indexverzameling, 24 injectie, 31 intervallen, 3 involutie, 9 lege verzameling, 2 limiet, 24
I
machtsverzameling, 25, 36 monotonie, 28 multinomiaalco¨effici¨ent, 20
44
verschil, 6 verzameling, 1 verzamelingenalgebra, 9 volledig origineel, 32
natuurlijke getallen, 1 omschrijving, 2, 4, 5 opsomming, 1 origineel, 30 overaftelbaar, 37 part, 25 partitie, 25 permutaties, 14 power set, 25 productregel, 35 productverzamelingen, 13 prototype, 2, 5 rationale getallen, 1, 38 re¨ele getallen, 1, 38 niet-negatieve —, 3 singleton, 32 somregel, 34 stijgende rij, 24 stochast, 30 surjectie, 31 symmetrisch verschil, 7 telregels, 13, 34, 35 toekenningssymbool, 1 trekkingen, 12–21 m terugleggen/m volgorde, 17 m terugleggen/z volgorde, 19 soorten —, 12 z terugleggen/m volgorde, 13 z terugleggen/z volgorde, 16 tripel, 28 uitkomstenruimte, 4 m terugleggen/m volgorde, 18 m terugleggen/z volgorde, 19 standaard —, 12–21 z terugleggen/m volgorde, 13 z terugleggen/z volgorde, 16, 17 universum, 4 vector, 29 Venn-diagrammen, 6 vereniging, 6, 23, 24
waarde, 30 waardenverzameling, 32 wet van De Morgan, 9, 10, 24
