Hoofdstuk 3
Een eindige verzameling is een verzameling die de eigenschap heeft dat we de elementen van
die verzameling kunnen tellen, en wel zo dat dat telproces op een gegeven ogenblik is afgerond.
Deze verzameling kan wel onvoorstelbaar groot zijn.
Eindigheid en oneindigheid maken gebruik van bijectie. Bijectief: Een functie f heet bijectief
wanneer f zowel injectief als surjectief is.
Injectief: Een functie f heet injectief als f aan verschillende elementen uit zijn domein
verschillende waarden toekent.
Surjectief: Een functie f heet surjectief wanneer elk element uit het codomein van f optreedt als
functie-waarde.
Verzameling A heet eindig wanneer er een n ∈ N te vinden is zo dat er een bijectie bestaat
tussen {x ∈ N | x < n} en A. ∅ is eindig. Waarom? Omdat er een bijectie bestaat tussen de
verzameling {x ∈ N | x < 0} en de lege verzameling.
De verzameling {a, b, c} is eindig. De volgende functie is immers een bijectie tussen {x ∈ N | x < 3}
en {a, b, c}:
De verzameling {1, 3, 5, 7, 9} is eindig. De volgende functie is een bijectie tussen de verzameling
{x ∈ N | x < 5} en deze verzameling:
Verzameling A heet oneindig wanneer A niet eindig is. De verzameling van natuurlijke getallen
N is oneindig volgens deze definitie.
Twee eindige verzamelingen A en B zijn even groot wanneer er een getal n is zo dat er een
bijectie is van {x ∈ N | x < n} naar A en een bijectie van {x ∈ N | x < n} naar B. Maar dan is er ook
een directe bijectie van A naar B.
, In plaats van over even groot als zullen we het nu hebben over gelijkmachtig met.
Gelijkmachtigheid is een begrip dat zowel op eindige als op oneindige verzamelingen van
toepassing is. Hier is de definitie van gelijkmachtigheid: Verzameling A heet gelijkmachtig met
verzameling B (notatie: A =1 B) wanneer er een bijectie van A naar B bestaat.
De definitie van ‘gelijkmachtigheid’ heeft als merkwaardig gevolg dat bijvoorbeeld de
verzameling N en de verzameling N − {0} gelijkmachtig (‘even groot’) zijn. Immers, de functie f :
N → N − {0} gedefinieerd door f(n) = n + 1 is een bijectie:
We zien aan dit voorbeeld dat de oneindige verzameling N een echte deelverzameling heeft van
dezelfde machtigheid. Als A een eindige verzameling is, dan is er geen echte deelverzameling van
A waarmee A gelijkmachtig is.
We kunnen een oneindige verzameling definiëren als: verzameling die gelijkmachtig is met een
van zijn echte deelverzamelingen.
De verzameling van alle natuurlijke getallen N is ‘even groot’ als de verzameling O van de oneven
natuurlijke getallen. Immers, f : N → O, gedefinieerd door f(n) = 2n + 1, is een bijectie:
Een verzameling die gelijkmachtig is met N heet aftelbaar. Wanneer A aftelbaar is en f is een
bijectie tussen A en N, dan noemen we f een aftelling van A.
De verzameling Z van de gehele getallen is gelijkmachtig met N:
De verzameling van alle velden van een oneindig schaakbord is aftelbaar:
Een eindige verzameling is een verzameling die de eigenschap heeft dat we de elementen van
die verzameling kunnen tellen, en wel zo dat dat telproces op een gegeven ogenblik is afgerond.
Deze verzameling kan wel onvoorstelbaar groot zijn.
Eindigheid en oneindigheid maken gebruik van bijectie. Bijectief: Een functie f heet bijectief
wanneer f zowel injectief als surjectief is.
Injectief: Een functie f heet injectief als f aan verschillende elementen uit zijn domein
verschillende waarden toekent.
Surjectief: Een functie f heet surjectief wanneer elk element uit het codomein van f optreedt als
functie-waarde.
Verzameling A heet eindig wanneer er een n ∈ N te vinden is zo dat er een bijectie bestaat
tussen {x ∈ N | x < n} en A. ∅ is eindig. Waarom? Omdat er een bijectie bestaat tussen de
verzameling {x ∈ N | x < 0} en de lege verzameling.
De verzameling {a, b, c} is eindig. De volgende functie is immers een bijectie tussen {x ∈ N | x < 3}
en {a, b, c}:
De verzameling {1, 3, 5, 7, 9} is eindig. De volgende functie is een bijectie tussen de verzameling
{x ∈ N | x < 5} en deze verzameling:
Verzameling A heet oneindig wanneer A niet eindig is. De verzameling van natuurlijke getallen
N is oneindig volgens deze definitie.
Twee eindige verzamelingen A en B zijn even groot wanneer er een getal n is zo dat er een
bijectie is van {x ∈ N | x < n} naar A en een bijectie van {x ∈ N | x < n} naar B. Maar dan is er ook
een directe bijectie van A naar B.
, In plaats van over even groot als zullen we het nu hebben over gelijkmachtig met.
Gelijkmachtigheid is een begrip dat zowel op eindige als op oneindige verzamelingen van
toepassing is. Hier is de definitie van gelijkmachtigheid: Verzameling A heet gelijkmachtig met
verzameling B (notatie: A =1 B) wanneer er een bijectie van A naar B bestaat.
De definitie van ‘gelijkmachtigheid’ heeft als merkwaardig gevolg dat bijvoorbeeld de
verzameling N en de verzameling N − {0} gelijkmachtig (‘even groot’) zijn. Immers, de functie f :
N → N − {0} gedefinieerd door f(n) = n + 1 is een bijectie:
We zien aan dit voorbeeld dat de oneindige verzameling N een echte deelverzameling heeft van
dezelfde machtigheid. Als A een eindige verzameling is, dan is er geen echte deelverzameling van
A waarmee A gelijkmachtig is.
We kunnen een oneindige verzameling definiëren als: verzameling die gelijkmachtig is met een
van zijn echte deelverzamelingen.
De verzameling van alle natuurlijke getallen N is ‘even groot’ als de verzameling O van de oneven
natuurlijke getallen. Immers, f : N → O, gedefinieerd door f(n) = 2n + 1, is een bijectie:
Een verzameling die gelijkmachtig is met N heet aftelbaar. Wanneer A aftelbaar is en f is een
bijectie tussen A en N, dan noemen we f een aftelling van A.
De verzameling Z van de gehele getallen is gelijkmachtig met N:
De verzameling van alle velden van een oneindig schaakbord is aftelbaar:
