TU/e
Mike Boldy en Hans Cuypers

Cardinaliteit

De cardinaliteit van een verzameling is een maat voor het aantal elementen van die verzameling. De cardinaliteit van een verzameling bepaal je door de elementen van die verzameling te nummeren: voorzie ieder element van een uniek natuurlijk getal, te beginnen bij~1, en oplopend in stapjes van 1. Als het procedé eindigt, is het getal waarmee je eindigt het aantal elementen van de verzameling. Als het procedé niet eindigt is de verzameling oneindig.

Definitie

Het aantal elementen van een eindige verzameling A noteren we als |A|.

Er gelden de volgende rekenregels:

1 |A|=0 dan en slechts dan als A=\emptyset
2 Als A\subset B dan |A|\leq|B|
3 |A\cup B|+|A\cap B|=|A|+|B| \\
4 Als A en B disjunct zijn dan |A\cup B|=|A|+|B|
5 |A|+|\overline{A}|=|U|
6 |A\setminus B|+|A\cap B|=|A|
7 |A\div B|+|A\cap B|=|A\cup B|
8 |A\times B|=|A|\cdot|B|
9 |P(A)|=2^{|A|}

Vaak zie je dat het aantal elementen van een oneindige verzameling wordt gedefinieerd als \infty. De rekenregels zijn ook geldig voor oneindige verzamelingen, als je tenminste bereid bent enkele voor de hand liggende rekenregels voor \infty te accepteren. Bijvoorbeeld: \infty+n=\infty voor alle n\in\mathbb N en voor n=\infty.

Voorbeeld

Stel A={a,b,c}. Een nummering van de elementen van A geven we aan met behulp van indices. Een voorbeeld van een nummering is b_1,a_2,c_3. Maar er zijn nog meer nummeringen mogelijk (bijvoorbeeld c_1,b_2,a_3). Allemaal hebben ze dezelfde eigenschap: ze eindigen met het getal 3. Dus |A|=3.

Eigenlijk stuiten we hier op een probleem: waarom eindigen alle nummeringen van een eindige verzameling bij hetzelfde getal? Strikt genomen zou je dit moeten bewijzen. Met een meer precieze definitie van de natuurlijke getallen, en van het begrip ``nummeren'' is dit inderdaad mogelijk.

Voorbeeld

In een groep van 20 studenten zijn 8 studenten geslaagd voor het tentamen Calculus I, en 11 stdenten voor het tentamen Lineaire Algebra. Er zijn 3 studenten die voor beide vakken geslaagd zijn. Hoeveel studenten hebben geen van beide vakken gehaald?

Noem de verzameling studenten die voor Calculus I geslaagd zijn C, en de verzameling studenten die voor Lineaie Algebra geslaagd zijn L. Als universum U kiezen we de totale groep studenten. Gevraagd wordt naar |\overline{C\cup L}|. Dan geldt

|U|=20,
|C|=8,
|L|=11,
en
|C\cap L|=3,
Volgens regel 3 geldt |C\cup L|=|C|+|L|-|C\cap L|=8+11-3=16. En volgens regel 6 geldt |\overline{C\cup L}|=|U|-|C\cup L|=20-16=4. Er zijn dus 4 atudenten geslaagd voor zowel Calculus I als Lineaire Algebra.

Voorbeeld

Rekenregel 3 schrijft men vaak in de volgende vorm:

|A\cup B|=|A|+|B|-|A\cap B|.
Deze regel is eenvoudig uit te breiden tot drie verzamelingen:
|A\cup B\cup C|=|A|+|B|+|C|-|B\cap C|-|A\cap C|-|A\cap B|+|A\cap B\cap C|.

In een groep van 20 studenten zijn 8 studenten geslaagd voor het tentamen Calculus I, 11 zijn geslaagd voor Lineaire Algebra, en 8 voor Kansrekening. Er zijn 3 studenten geslaagd voor Calculus I en Lineaire Algebra. Ook zijn er 3 studenten geslaagd voor Calculus I en Kansrekening. Er zijn 4 studenten geslaagd voor Kansrekening en Lineaire Algebra. Tenslotte is er 1 student die alle drie de vakken heeft gehaald. Hoeveel studenten zijn er die voor geen enkel vak zijn geslaagd?

Noem de verzameling studenten die voor Calculus I geslaagd zijn C, de verzameling studenten die voor Lineaie Algebra geslaagd zijn L, en de studenten die voor Kansrekening zijn geslaagd K. Als universum U kiezen we de totale groep studenten. Gevraagd wordt naar |\overline{C\cup L\cup K}|. Gegeven is |C|=8, |L|=11, |K|=8, |C\cap L|=3, |C\cap K|=3, |L\cap K|=4, en |C\cap L\cap K|=1. Volgens de nieuwe rekenregel geldt

|C\cup L\cup K|=8+11+8-3-3-4+1=18.
Dus |\overline{C\cup L\cup K}|=|U|-|C\cup L\cup K|=20-18=2.

Stelling

Stel A en B zijn eindige verzamelingen waarvoor geldt B\subset A. Dan geldt

|A|=|B|\Leftrightarrow A=B.

Eén kant op is eenvoudig: als A=B dan ook |A|=|B|. Voor het bewijs in de andere richting ga je als volgt te werk. Stel |A|=|B|. Definieer V=A\setminus B. Pas regel 6 toe: |V|+|A\cap B|=|A|. Uit de inclusie B\subset A volgt dan A\cap B=B, dus |V|+|B|=|A|. We namen aan dat |A|=|B|, dus |V|=0. Uit regel 1 volgt dan A\cap\overline{B}=A\setminus B=V=\emptyset. Dan

A\cap B=(A\cap B)\cup\emptyset=(A\cap B)\cup(A\cap\overline{B})= A\cap(B\cup\overline{B})=A\cap U=A
Uit regel 14 voor verzamelingen volgt dan dat A\subset B. Maar gegeven is dat B\subset A, dus A=B.