Hoofdstuk 2

Question 1

Wat zijn de 7 axioma’s bij optelling en vermenigvuldiging?

Answer 1

1. Voor elke a,b ∈ ℤ geldt a+b ∈ ℤ. De verzameling ℤ is gesloten voor de bewerkingen optelling en vermenigvuldiging of vermenigvuldiging en optelling zijn inwendige bewerkingen.
2. Voor alle a,b ∈ ℤ geldt a+b = b+a en ab = ba. De bewerkingen optelling en vermenigvuldiging zijn commutatieve of abelse bewerkingen.
3. Voor alle a,b,c ∈ ℤ geldt (a+b)+c = a+(b+c) en (ab)c = a(bc). De bewerkingen optelling en vermenigvuldiging zijn associatieve bewerkingen.
4. Voor alle a ∈ ℤ geldt a+0 = a en a*1 = a. Het getal 0 is het neutraal element van de optelling en het getal 1 is het neutraal element van de vermenigvuldiging.
5. Voor alle a,b,c ∈ ℤ geldt a(b+c) = ab + ac. De (linkse) distributiviteitsregel (wegens 2. ook rechtse) van de vermenigvuldiging t.o.v. de optelling geldt.
6. Voor alle a ∈ ℤ bestaat er een element -a zodat a+(-a)=0. Elk geheel getal bezit een tegengesteld geheel getal
7. Als ab = ac en a≠0, dan is b = c. De linkse schrappingswet (wegens 2. ook de rechtse) geldt voor de vermenigvuldiging.

Question 2

Wanneer is een relatie een partiële orderelatie/ordening? (Bij ≤)

Answer 2

1. Reflexief : voor alle a ∈ ℤ geldt a≤a
2. Anti-symmetrisch: voor alle a,b ∈ ℤ geldt: als a≤b en b≤a, dan is a=b
3. Transitief: voor alle a,b,c ∈ ℤ geldt: als a≤b en b≤c dan is a≤c

Question 3

Wanneer is een relatie een totale orderelatie/ordening? (Bij ≤)

Answer 3

Indien elke a,b uit ℤ vergeleken kunnen worden, noemt men de ordening een totale ordening of totale orderelatie.

≤ is totaal: Voor alle a,b ∈ ℤ geldt: a≤b of b≤a

Question 4

Geef een voorbeeld van een pärtiele orderelatie die niet totaal is.

Answer 4

Een voorbeeld van een partiële orderelatie die niet totaal is is de relatie ‘deelt’ (a|b) op de verzameling van de positieve getallen, want niet elke 2 elementen kunnen met elkaar vergeleken worden (2∤3 en 3∤2).

Question 5

Wat zijn 2 eigenschappen van strikt-orderelaties?

Answer 5

Transitief en anti-reflexief.

Question 6

Om de relatie ≤ in verband te brengen met de bewerkingen op de gehele getallen hebben we 2 axioma’s nodig, welke?

Answer 6

1. Voor alle a,b,c ∈ ℤ geldt: als a≤b, dan ook a+c≤b+c

2. Voor alle a,b,c ∈ ℤ geldt: als a≤b en c≥0 dan bc ≤ ac

Question 7

Wanneer is een getal een benedengrens? En wanneer is het een kleinste element?

Answer 7

Noem X een willekeurige deelverzameling van ℤ, dan is het getal b een benedengrens van X als voor alle elementen x van X geldt: b≤x.

Als een benedengrens van X tot de verzameling X behoort, is deze het kleinste element van X.

Question 8

Wat is het axioma van de goede ordening?

Answer 8

Als X een deelverzameling is van ℤ, verschillend van de lege verzameling, die een benedengrens heeft, bezit zij een kleinste element

Question 9

Geldt het axioma van de goede ordening ook voor ℚ?

Answer 9

Dit axioma geldt voor ℤ, maar niet voor ℚ (neem X = {1/n | n ∈ ℤ, n ≥ 1} heeft minstens een benedengrens (namelijk 0) maar geen kleinste element)

Question 10

Wat is het principe van het kleinste tegenvoorbeeld?

Answer 10

Stel S⊆ℕ* waarvoor we willen bewijzen dat S = ℕ. We gaan dit doen uit het ongerijmde, als S ≠ ℕ dan bestaat er volgens het axioma van de goede ordening een kleinste element in ℕ* \ S, dit element noemen we het kleinste tegenvoorbeeld. Als we uit het bestaan van dit element een tegenstrijdigheid tegenkomen, volgt daaruit dat S = ℕ*

Question 11

Wat is de inductiebasis?

Answer 11

Het feit dat het resultaat waar is voor n = 1 noemt men de inductiebasis.

Question 12

Wat is de inductiehypothese? (IH)

Answer 12

De veronderstelling dat de uitdrukking waar is voor n = k noemt men de inductiehypothese.

Question 13

Kan je het principe van het kleinste tegenvoorbeeld ook toepassen op ℤ?

Answer 13

Het inductieprincipe kan op deze manier niet toegepast worden op ℤ want ℤ heeft geen kleinste element.

Question 14

Wat is het ladenprincipe van Dirichlet?

Answer 14

Veronderstel dat we m objecten willen verdelen in n ≥ 1 laden, dan is het onmiddelijk duidelijk dat indien er meer objecten zijn dan laden, er ten minste 1 lade is die meer dan 1 object bevat. Dit wordt het ladenprincipe of duivenhokprincipe genoemd.

Question 15

Wat is een eindige verzameling?

Answer 15

Een verzameling X waarvoor er een n bestaat waarbij men een bijectie kan opstellen tussen X en ℕ[1,n] is een eindige verzameling.

Question 16

Wanneer is een oneindige verzameling aftelbaar?

Answer 16

We noemen een oneindige verzameling X aftelbaar als er een bijectie bestaat van ℕ naar X, indien er geen zo’n bijectie bestaat, noemt men de verzameling niet-aftelbaar of overaftelbaar.

Question 17

Zijn eindige verzamelingen altijd aftelbaar?

Answer 17

Ja.

Question 18

Is ℤ aftelbaar?

Answer 18

Ja.
Beschouw de afbeelding van ℕ naar ℤ: f(n) = { n/2 als n even is | -(n+1)/2 als n oneven is }

Deze f is een bijectie en de rij of geordende waardenverzameling van f is (0, -1, 1, -2, 2, …).

Question 19

Is ℚ aftelbaar?

Answer 19

Er bestaat een bijectie f van ℕ naar ℚ waarvan de rij er als volgt uitziet:(0,-1,1,-2,-1/2,1/2 ,2,-3,-3/2,-2/3,-1/3,…)

Om de plaats van a/b te bepalen in deze rij, gebruiken we niveaus. Op niveau 0 komt enkel het getal 0. Voor de volgende niveaus nemen we aan dat de breuk niet vereenvoudigbaar is en a≠0 en b>0. We nemen nu n = max(|a|, b) het niveau van de breuk. Per niveau worden de getallen gerangschikt volgens de orderelatie < van ℚ. Dan krijgen we een lijst van volgende gedaante:

n |
0 | 0
1 | -1, 1
2 | -2, -1/2, 1/2, 2
3 | -3, -3/2, -2/3, -1/3, 1/3, 2/3, 3/2, 3
...

Elk rationaal getal komt juist een keer voor in deze lijst en aangezien elk niveau een eindig aantal getallen bevat, is ℚ aftelbaar.

Question 20

Is ℝ aftelbaar?

Answer 20

Deze verzameling is niet-aftelbaar. Bewijs: we gaan dit bewijzen door aan te tonen dat het interval [0,1] niet aftelbaar is d.m.v. Cantor’s diagonaalmethode.

Veronderstel het tegendeel, dat er een bijectie f van ℕ naar [0,1] met volgende waarden:

f(0) = 0.a0b0c0…
f(1) = 0.a1b1c1…
f(2) = 0.a2b2c2…
…

Hierbij zijn ai,bi,ci,… een cijfer van 0 tot 9. Merk op dat sommige getallen meerdere notaties kunnen hebben in deze rij als ze een oneindig aantal nullen of negens bevatten (0.8000… = 0.7999…).

We gaan nu een getal x dat niet in deze lijst zit produceren op volgende manier:

x = 0.x0x1x2… waarbij xi = { ai+1 als ai≤7 / 1 als ai ∈ {8,9} }

Het getal x zit niet in de lijst, aangezien het voor elke n verschilt van het getal op plaats n op de n-de plaats en niet anders schrijfbaar want het zal nooit een 0 of een 9 bevatten, dus zeker geen oneindig aantal. Dit getal x is strijdig met de definitie van f, dus kan er geen bijectie opgesteld worden van ℕ naar ℝ en dus moet ℝ niet-aftelbaar zijn.

Question 21

Wanneer zijn 2 verzamelingen disjunct?

Answer 21

Wanneer zij geen element met elkaar gemeen hebben.

Question 22

Wat is het vereenvoudigd somprincipe?

Answer 22

Als Ai k disjuncte, eindige verzamelingen zijn, dan is de de kardinaliteit van de unie van deze Ai’s gelijk aan de som van de kardinaliteiten van de individuele Ai’s.

Question 23

Wat is het eenvoudig inclusie-exclusie principe?

Answer 23

Als A en B twee eindige verzamelingen zijn, dan gedlt: |A ∪ B| = |A| + |B| - |A ∩ B|

Question 24

Hoeveel is Vn^0? (Variaties)

Answer 24

Vn^0 = 1 (er is maar 1 manier om 0 elementen te nemen)

Question 25

Wat is een permutatie?

Answer 25

Een permutatie is een bijectie van een verzameling met n elementen op zichzelf.

Question 26

Wat is een variatie?

Answer 26

Een variatie van k elementen uit n elementen is een geordend k-tal van k verschillende elementen gekozen uit een verzameling van n elementen.

Question 27

Wat is een combinatie?

Answer 27

Een combinatie van k elementen uit n elementen is een deelverzameling met k elementen uit de verzameling van n elementen.

Question 28

Bewijs dat P(n, k) = C(n,k)*k!

Answer 28

Een variatie van k elementen uit n elementen ontstaat door eerst een deelverzameling van k elementen te nemen uit n elementen en daarna de volgorde vast te leggen. Dit eerste kan per definitie op Cnk manieren, dit tweede op k! manieren. In totaal kan men dus Cnk*k! variaties van k elementen nemen uit n elementen.

Gevolg: Voor alle n, k ∈ ℕ met k ≤ n geldt: C(n, k) = P(n, k)/k! = n!/((n-k)!*k!)

Question 29

Geef me de 3 eigenschappen van combinaties.

Answer 29

1. Voor alle n, k ∈ ℕ met k ≤ n geldt: C(n, k) = C(n, n-k)
2. Voor alle n, k ∈ ℕ met k + 1 ≤ n geldt: C(n, k+1) = C(n, k)(n-k / k+1)
   Bewijs: C(n, k+1) = n!/ (k+1)!(n-(k1))! = (n! / k!(n-k)!)*(n-k / k+1) = C(n, k) *(n-k / k+1)
3. Voor alle n, k ∈ ℕ met k ≤ n geldt de formule van Stifel-Pascal: C(n,k) = C(n-1, k) + C(n-1, k-1)
   Bewijs: We kunnen deze eerste verzameling opsplitsen in twee deelverzamelingen, namelijk degenen die a bevatten en degenen die a niet bevatten. Deze eerste zal C(n-1, k) elementen bevatten, deze tweede C(n-1, k-1). Hieruit volgt de formule.

Question 30

Wat is de driehoek van Pascal?

Answer 30

Uit de formule van Stifel-Pascal C(n,k) = C(n-1, k) + C(n-1, k-1) volgt een recursieve methode om binomiaalgetallen te berekenen. Deze getallen kan men in een driehoek plaatsen, die men de driehoek van Pascal noemt.

Question 31

Wat is een herhalingsvariatie?

Answer 31

Een herhalingsvariatie van k elementen uit n elementen is een geordend k-tal uit een verzameling van n elementen.

Question 32

Wat is een herhalingscombinatie?

Answer 32

Een herhalingscombinatie van k elementen uit n elementen is een niet-geordend k-tal, gekozen uit n elementen.

Question 33

Hoeveel keer kunnen elementen voorkomen in combinaties, variaties, herhalingscombinaties en herhalingsvariaties en in welke maakt volgorde niet uit en in welke wel?

Answer 33

Elk element mag 1x voorkomen Elk element mag meer voorkomen
Volgorde maakt niet uit Combinatie Herhalingscombinatie
Volgorde maakt uit Variatie Herhalingsvariatie

Question 33

Hoeveel keer kunnen elementen voorkomen in combinaties, variaties, herhalingscombinaties en herhalingsvariaties en in welke maakt volgorde niet uit en in welke wel?

Answer 33

………………………………………Elk element mag 1x voorkomen Elk element mag meer voorkomen
Volgorde maakt niet uit Combinatie Herhalingscombinatie
Volgorde maakt uit Variatie Herhalingsvariatie

Question 34

Hoe kan je berekenen hoeveel deelverzamelingen een verzameling heeft?

Answer 34

Een verzameling X van n elementen bezit 2n deelverzamelingen.

Bewijs: Noem X = {x1, x2, …, xn} en Y = {0,1}. Voor elke deelverzameling van X, namelijk S kunnen we een functie fS van X naar Y opstellen. Deze functie is als volgt gedefinieerd: fS(xi) = { 0 als xi ∉ S | 1 als xi ∈ S }. Het aantal deelverzamelingen is dus gelijk aan het aantal zulke functies men kan opstellen. Dit aantal is gelijk aan het aantal herhalingsvariaties van n elementen uit 2 elementen, namelijk 2n

Question 35

Hoe kan je het binomium van Newton berekenen?

Answer 35

(a+b)ⁿ = Σ voor k=0 tot n van (ⁿₖ)aᵏbⁿ⁻ᵏ

Question 36

Hoe kan je het veralgemeend inclusie-exclusie principe berekenen?

Answer 36

Als A1, A2, … An eindige verzamelingen zijn, dan is |A1 ∪ A2 ∪ … ∪ An| = α1 - α2 + α3 - … + (-1)^n-1 αn.

Question 37

Wat is een wanorde?

Answer 37

Een permutatie zonder fixelementen of wanorde is een permutatie die geen elementen bevat die “juist” staan.

Question 38

Wat zijn de Stirling getallen?

Answer 38

Een Stirling getal S(n,k) is het aantal mogelijkheden waarom een verzameling X van n elementen kan schrijven als een disjuncte unie van k niet-ledige deelverzamelingen.

Question 39

Hoe wordt het Stirling getal S(n, k) met 1 ≤ k ≤ n recursief gedefinieerd?

Answer 39

Het Stirling getal S(n, k) met 1 ≤ k ≤ n wordt recursief gedefinieerd door:

S(n, 1) = 1
S(n, k) = S(n-1,k-1) + kS(n-1,k) als 2 ≤ k ≤ n-1
S(n, n) = 1

Question 40

Wat zijn multinomiaalgetallen?

Answer 40

Het aantal verdelingen van k verschillende elementen over n elementen, waarbij we elk element i net ni keer willen gebruiken (met n1 + n2 + … + nk = n) noemen we een multinomiaalgetal.