Hoofdstuk 2 Flashcards
Wat zijn de 7 axioma’s bij optelling en vermenigvuldiging?
- Voor elke a,b ∈ ℤ geldt a+b ∈ ℤ. De verzameling ℤ is gesloten voor de bewerkingen optelling en vermenigvuldiging of vermenigvuldiging en optelling zijn inwendige bewerkingen.
- Voor alle a,b ∈ ℤ geldt a+b = b+a en ab = ba. De bewerkingen optelling en vermenigvuldiging zijn commutatieve of abelse bewerkingen.
- 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.
- 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.
- 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.
- Voor alle a ∈ ℤ bestaat er een element -a zodat a+(-a)=0. Elk geheel getal bezit een tegengesteld geheel getal
- Als ab = ac en a≠0, dan is b = c. De linkse schrappingswet (wegens 2. ook de rechtse) geldt voor de vermenigvuldiging.
Wanneer is een relatie een partiële orderelatie/ordening? (Bij ≤)
- Reflexief : voor alle a ∈ ℤ geldt a≤a
- Anti-symmetrisch: voor alle a,b ∈ ℤ geldt: als a≤b en b≤a, dan is a=b
- Transitief: voor alle a,b,c ∈ ℤ geldt: als a≤b en b≤c dan is a≤c
Wanneer is een relatie een totale orderelatie/ordening? (Bij ≤)
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
Geef een voorbeeld van een pärtiele orderelatie die niet totaal is.
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).
Wat zijn 2 eigenschappen van strikt-orderelaties?
Transitief en anti-reflexief.
Om de relatie ≤ in verband te brengen met de bewerkingen op de gehele getallen hebben we 2 axioma’s nodig, welke?
- 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
Wanneer is een getal een benedengrens? En wanneer is het een kleinste element?
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.
Wat is het axioma van de goede ordening?
Als X een deelverzameling is van ℤ, verschillend van de lege verzameling, die een benedengrens heeft, bezit zij een kleinste element
Geldt het axioma van de goede ordening ook voor ℚ?
Dit axioma geldt voor ℤ, maar niet voor ℚ (neem X = {1/n | n ∈ ℤ, n ≥ 1} heeft minstens een benedengrens (namelijk 0) maar geen kleinste element)
Wat is het principe van het kleinste tegenvoorbeeld?
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 = ℕ*
Wat is de inductiebasis?
Het feit dat het resultaat waar is voor n = 1 noemt men de inductiebasis.
Wat is de inductiehypothese? (IH)
De veronderstelling dat de uitdrukking waar is voor n = k noemt men de inductiehypothese.
Kan je het principe van het kleinste tegenvoorbeeld ook toepassen op ℤ?
Het inductieprincipe kan op deze manier niet toegepast worden op ℤ want ℤ heeft geen kleinste element.
Wat is het ladenprincipe van Dirichlet?
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.
Wat is een eindige verzameling?
Een verzameling X waarvoor er een n bestaat waarbij men een bijectie kan opstellen tussen X en ℕ[1,n] is een eindige verzameling.
Wanneer is een oneindige verzameling aftelbaar?
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.
Zijn eindige verzamelingen altijd aftelbaar?
Ja.
Is ℤ aftelbaar?
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, …).
Is ℚ aftelbaar?
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.
Is ℝ aftelbaar?
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.
Wanneer zijn 2 verzamelingen disjunct?
Wanneer zij geen element met elkaar gemeen hebben.
Wat is het vereenvoudigd somprincipe?
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.
Wat is het eenvoudig inclusie-exclusie principe?
Als A en B twee eindige verzamelingen zijn, dan gedlt: |A ∪ B| = |A| + |B| - |A ∩ B|
Hoeveel is Vn^0? (Variaties)
Vn^0 = 1 (er is maar 1 manier om 0 elementen te nemen)
Wat is een permutatie?
Een permutatie is een bijectie van een verzameling met n elementen op zichzelf.
Wat is een variatie?
Een variatie van k elementen uit n elementen is een geordend k-tal van k verschillende elementen gekozen uit een verzameling van n elementen.
Wat is een combinatie?
Een combinatie van k elementen uit n elementen is een deelverzameling met k elementen uit de verzameling van n elementen.
Bewijs dat P(n, k) = C(n,k)*k!
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!)
Geef me de 3 eigenschappen van combinaties.
- Voor alle n, k ∈ ℕ met k ≤ n geldt: C(n, k) = C(n, n-k)
- 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) - 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.
Wat is de driehoek van Pascal?
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.
Wat is een herhalingsvariatie?
Een herhalingsvariatie van k elementen uit n elementen is een geordend k-tal uit een verzameling van n elementen.
Wat is een herhalingscombinatie?
Een herhalingscombinatie van k elementen uit n elementen is een niet-geordend k-tal, gekozen uit n elementen.
Hoeveel keer kunnen elementen voorkomen in combinaties, variaties, herhalingscombinaties en herhalingsvariaties en in welke maakt volgorde niet uit en in welke wel?
Elk element mag 1x voorkomen Elk element mag meer voorkomen
Volgorde maakt niet uit Combinatie Herhalingscombinatie
Volgorde maakt uit Variatie Herhalingsvariatie
Hoeveel keer kunnen elementen voorkomen in combinaties, variaties, herhalingscombinaties en herhalingsvariaties en in welke maakt volgorde niet uit en in welke wel?
………………………………………Elk element mag 1x voorkomen Elk element mag meer voorkomen
Volgorde maakt niet uit Combinatie Herhalingscombinatie
Volgorde maakt uit Variatie Herhalingsvariatie
Hoe kan je berekenen hoeveel deelverzamelingen een verzameling heeft?
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
Hoe kan je het binomium van Newton berekenen?
(a+b)ⁿ = Σ voor k=0 tot n van (ⁿₖ)aᵏbⁿ⁻ᵏ
Hoe kan je het veralgemeend inclusie-exclusie principe berekenen?
Als A1, A2, … An eindige verzamelingen zijn, dan is |A1 ∪ A2 ∪ … ∪ An| = α1 - α2 + α3 - … + (-1)^n-1 αn.
Wat is een wanorde?
Een permutatie zonder fixelementen of wanorde is een permutatie die geen elementen bevat die “juist” staan.
Wat zijn de Stirling getallen?
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.
Hoe wordt het Stirling getal S(n, k) met 1 ≤ k ≤ n recursief gedefinieerd?
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
Wat zijn multinomiaalgetallen?
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.
