1. De natuurlijke getallen
2. De geordende verzameling van de natuurlijke getallen
Als f:AB, a⟼f(a) een afbeelding is, dan noemen we
1. f een injectie ⟺ ∀𝑎, 𝑎′ ∈ 𝐴: f(a) = f(a’) a = a’
Er kan maar 1 pijl toekomen in elk beeld
2. f is een surjectie ⟺ ∀𝑏 ∈ 𝐵; ∃𝑎 ∈ 𝐴: 𝑓(𝑎) = 𝑏
Er moeten overal pijlen toekomen in het beeld
3. f is een bijectie ⟺ f is een injectie en een surjectie ⟺ ∀𝑏 ∈ 𝐵; ∃! 𝑎 ∈ 𝐴: 𝑓 (𝑎) = 𝑏
In het beeld komen er overal maar 1 pijl toe/ elk elementje uit de vertrekverzameling heeft
precies één beeld in het doel.
Definitie 2.1
Als A en B verzamelingen zijn dan noemen we A gelijkmachtig met B of we zeggen dat A dezelfde
kardinaliteit heeft als B (notatie A#B) ⟺ er bestaat een bijectie f: A B
bij.
In symbolen: A#B ⟺ ∃f: AB (er bestaat een bijectie tussen A en B)
Informeel: twee verzamelingen zijn gelijkmachtig met elkaar/ hebben dezelfde kardinaliteit als en
slechts als er een bijectie bestaat tussen die twee verzamelingen.
Formeel: verzameling A en verzameling B zijn gelijkmachtig met elkaar/ hebben dezelfde
kardinaliteit als en slechts als er een bijectie bestaat tussen A en B
‘Gelijkmachtig zijn’ is een relatie tussen verzamelingen.
Het geheel van alle verzamelingen is geen verzameling maar een klasse. We werken daarom hier in
een voldoende grote verzameling V van verzamelingen. (een verzameling die alle verzamelingen
bevat die we nodig hebben)
Er bestaat een bijectie tussen C en D waardoor C gelijkmachtig is
met D.
C#D
Eigenschap 2.2
De relatie #: V V met (A,B) ∈ # ⟺ A#B is een equivalentierelatie in V .
Informeel: de relatie is gelijkmachtig met gaat van voldoende grote verzameling naar voldoende grote
verzameling waarbij het koppel gevormd door twee verzamelingen behoort tot de relatie als en slechts
als die verzamelingen met dezelfde kardinaliteit in equivalentierelatie staan met elkaar.
Formeel: de relatie is gelijkmachtig met gaat van V naar V waarbij het koppel A B behoort tot de relatie
als en slechts als de verzamelingen A en B met dezelfde kardinaliteit in equivalentierelatie staan met
1
elkaar.
,Bewijs # is reflexief
Structuur: gegeven: A, B, C ∈ V T.B.: A#B is een equivalentierelatie in V In woorden: de relatie is
gelijkmachtig met is reflexief
(A,B) ∈ # 1) # is reflexief (A#A)
#: V V 2) # is symmetrisch (A#BB#A)
3) # is transitief (A#B en B#C A#C)
Bewijs:
1) 1A: A A is een bijectie Elke relatie staat in een bijectief verband met zichzelf
door de identieke.
⇕ definitie 2.1: relatie is gelijkmachtig met
A#A
2) A#B
⇕ definitie 2.1: relatie is gelijkmachtig met
Er bestaat een bijectie f: A B
⇕ het omgekeerde van een bijectie is opnieuw een bijectie
Er bestaat een bijectie f-1: B A
⇕ definitie 2.1: relatie is gelijkmachtig met
B#A
3) A#B en B#C
⇕ definitie 2.1: relatie is gelijkmachtig met
Er bestaan bijecties f: A B en g: B C
⇕ samengestelde van twee bijecties is opnieuw een bijectie
Er bestaat een bijectie g o f: A C
⇕ definitie 2.1: relatie is gelijkmachtig met
A#C
Opmerkingen
1. Als A ∈ V dan noteren we #{𝐴} (equivalentieklasse van A) door #A en we noemen #A het
kardinaalgetal van A (of equivalentieklas voortgebracht door A).
2. W = V |# = {#𝐴|𝐴 ∈ 𝑉}
Bij vorige relatie A|R (op A door R)
W ronde W
Informeel: voldoende grote verzameling waarop is gelijkmachtig met werkt is gelijk aan de
verzameling van alle mogelijke kardinaalgetallen/ equivalentieklassen waarvoor geldt dat die
verzameling tot voldoende grote verzameling behoort.
Formeel: ronde W is gelijk aan verzameling V waarop is gelijkmachtig met werkt is gelijk aan de
verzameling van alle mogelijke kardinaalgetallen/equivalentieklassen waarvoor geldt dat A een 2
verzameling is die tot V behoort.
,3. #A = #B ⟺ A ∈ #B ⟺ A#B ⟺ B#A ⟺ B ∈ #A (R{𝑎} = R{𝑏} ⟺ b ∈ R{𝑎} ⟺ aRb)
Het kardinaalgetal van A is gelijk aan het kardinaalgetal van B (#A = #B) ⟺ A en B gelijkmachtig zijn
(A#B) ⟺ er bestaat een bijectie van A naar B ( )
Definitie 2.3: natuurlijke getallen definiëren
#∅ = 0
#{0} = 1
#{0,1} = 2
#{0,1,2} = 3
….
#{0,1,2, … ,356762} = 356763
…
ℕ = {0,1,2, … ,7685493215, … } noemen we de verzameling van de natuurlijke getallen.
Verzameling zonder elementen
#∅ = 0
Zijn er andere verzamelingen die
gelijkmachtig zijn met de lege/ zijn er
andere verzamelingen die je bijectief
kan verbinden met de lege? Neen.
#∅
In woorden: klasse voortgebracht door de lege/
kardinaalgetal van de lege
0 naam equivalentieklas met daarin de lege
verzameling
Verzameling met 1 element
#{0} = 1
Verzameling met 2 elementen
#{0,1} = 2
Opmerkingen …
1. ℕ ⊂ W (verzameling van de natuurlijke getallen behoort tot de verzameling van alle
kardinaalgetallen)
(0,1,2,3,… zijn equivalentieklassen. Die klassen zijn allemaal deelverzamelingen van W. Daardoor is ℕ
dus een deelverzameling van W ).
2. #{0,1,2, … , 𝑛} noemen we de opvolger van n, notatie n+.
Dus 0+ = 1, 1+ = 2,…
3. Men kan aantonen dat alle natuurlijke getallen verschillend zijn (anders is de definitie fout).
Wij bewijzen als voorbeeld alleen dat 0 ≠ 1. Analoog voor de rest.
Stel dat 0 = 1 ⇒ #∅ = #{0} d.w.z. dat er een bijectie bestaat tussen ∅ en {0}. Dat kan niet
want verschillende equivalentieklassen!! 3
, Definitie 2.4
Als A ∈ V , dan noemen we
1. A een eindige verzameling ⟺ #A is een natuurlijk getal.
2. A een oneindige verzameling ⟺ A is geen eindige verzameling. (A is niet eindig dus het
kardinaalgetal van A is geen natuurlijk getal: #A ∉ ℕ)
1. Informeel: verzameling die behoort tot een voldoende grote verzameling is een eindige verzameling
als en slechts als het kardinaal getal van die verzameling een natuurlijk getal is.
Formeel: Als A behoort tot V dan noemen we A een eindige verzameling als en slechts als het
kardinaalgetal van A een natuurlijk getal is.
2. Informeel: verzameling die behoort tot een voldoende grote verzameling is een oneindige
verzameling als en slechts als die verzameling geen eindige verzameling is.
Formeel: Als A behoort tot V dan noemen we A een oneindige verzameling als en slechts als A geen
eindige verzameling is.
Opmerkingen
1. J.W.R. Dedekind bewees de volgende belangrijke stelling:
Een verzameling A is oneindig ⟺ er bestaat een echte deelverzameling B van A zodat #A = #B.
2. Als A een eindige verzameling is, dan noemen we #A het aantal elementen van A.
Voorbeelden
1. (kardinaliteit = 4) is een eindige verzameling waarvan het aantal elementen gelijk is
aan 4. Want #A = #{0,1,2,3} omdat is een bijectie (zijn gelijkmachtig want hebben dezelfde
kardinaliteit)
Dus #A = 4.
2. ℕ is een oneindige verzameling want 2ℕ ⊊ ℕ en f: ℕ 2ℕ; x ↦ f(x) = 2x is een bijectie.
Dus #ℕ = #2ℕ.
2ℕ: alle natuurlijke even getallen 2ℕ = {0,2,4,6,8,10, … }
bij.
f: ℕ 2ℕ In alle elementen van de vertrekverzameling vertrekt er precies
0↦0 één pijl (elk natuurlijk getal heeft maar één dubbel) en in alle
elementen van het doel komt er precies één pijl toe.
1↦2
Daardoor is f dus een bijectie. Daardoor hebben ℕ en 2ℕ
2↦4 dezelfde kardinaliteit. Daardoor is ℕ een oneindige verzameling.
….
4
