Eindige verzameling, kardinaliteit কী?

Voorbeeld 2.6 (Eindigheid is essentieel)

Op een eindige verzameling is Propositie 2.5 een krachtige kortere weg: elke injectieve afbeelding van $E$ naar zichzelf is automatisch een permutatie van $E$ — de helft van de bijectiviteit krijg je gratis. Beide implicaties bezwijken op oneindige verzamelingen: $n \mapsto n + 1$ is injectief van $\N$ naar $\N$ maar mist $0$, en de afbeelding $\N \to \N$ die $0 \mapsto 0$ en $n \mapsto n - 1$ voor $n \geq 1$ stuurt, is surjectief maar niet injectief. Telkens als deze propositie wordt ingeroepen, doet de eindigheidshypothese echt werk — een thema dat de weekendopgave van Hoofdstuk 1 van de andere kant bekijkt, waar oneindige verzamelingen juist die verzamelingen zijn die zulke afbeeldingen op zichzelf toelaten.

Voorbeeld 2.7 (De helft van het werk, gratis)

Beschouw de afbeelding $f$ op $\{0, 1, \dots, 6\}$ die $k$ naar de rest van $3k$ bij deling door $7$ stuurt; haar waardentabel luidt

Is $f$ een bijectie? Alleen de injectiviteit volstaat (Propositie 2.5): hebben $3k$ en $3k'$ dezelfde rest, dan deelt $7$ het getal $3(k - k')$, en omdat $7$ priem is en $3$ niet deelt, deelt het $k - k'$ (lemma van Euclides, hier gebruikt zoals bekend uit het bovenbouwvolume en bewezen in Hoofdstuk 6); met $\abs{k - k'} \leq 6$ dwingt dat $k = k'$ af. De surjectiviteit komt er gratis bij — je hoeft $3k \equiv c$ niet voor elke $c$ op te lossen, al bevestigt de tabel dat elke waarde precies één keer voorkomt. Deze kortere weg is een werkpaard: ze bewijst de inverteerbaarheid van de vermenigvuldiging modulo $n$ (Hoofdstuk 6), drijft het koppelen in de stelling van Wilson aan, en keert in de lineaire algebra terug als “een endomorfisme van een eindigdimensionale ruimte is injectief precies wanneer het surjectief is” (Hoofdstuk 19).

Voorbeeld 2.17

Twee klassieke bijzondere gevallen: $a = b = 1$ geeft $\sum_k \binom nk = 2^n$ terug; $a = -1$, $b = 1$ geeft $\sum_{k} (-1)^k \binom nk = 0$ voor $n \geq 1$: van de deelverzamelingen van een niet-lege verzameling heeft precies de helft een even kardinaliteit.