Qu'est-ce que « Ensemble fini, cardinal » ?

Exemple 2.6 (La finitude est essentielle)

Sur un ensemble fini, la Proposition 2.5 est un raccourci puissant : toute application injective de $E$ dans lui-même est automatiquement une permutation de $E$ — la moitié de la bijectivité est offerte. Les deux implications s’effondrent sur les ensembles infinis : $n \mapsto n + 1$ est injective de $\N$ dans $\N$ mais rate $0$, et l’application $\N \to \N$ qui envoie $0 \mapsto 0$ et $n \mapsto n - 1$ pour $n \geq 1$ est surjective sans être injective. Chaque fois que cette proposition est invoquée, l’hypothèse de finitude travaille réellement — un thème que le devoir maison du Chapitre 1 explore par l’autre bout, là où les ensembles infinis sont précisément ceux qui admettent de telles applications d’eux-mêmes dans eux-mêmes.

Exemple 2.7 (La moitié du travail, gratuitement)

Considérons l’application $f$ sur $\{0, 1, \dots, 6\}$ qui envoie $k$ sur le reste de $3k$ dans la division par $7$ ; sa table de valeurs est

$f$ est-elle bijective ? L’injectivité suffit à elle seule (Proposition 2.5) : si $3k$ et $3k'$ ont le même reste, $7$ divise $3(k - k')$, et comme $7$ est premier et ne divise pas $3$, il divise $k - k'$ (lemme d’Euclide, utilisé ici au niveau du secondaire et démontré au Chapitre 6) ; avec $\abs{k - k'} \leq 6$ cela force $k = k'$. La surjectivité vient gratuitement — inutile de résoudre $3k \equiv c$ pour chaque $c$, même si la table confirme que chaque valeur apparaît exactement une fois. Le raccourci est une bête de somme : il donne l’inversibilité de la multiplication modulaire (Chapitre 6), il fait fonctionner l’appariement du théorème de Wilson, et il revient en algèbre linéaire sous la forme « un endomorphisme d’un espace de dimension finie est injectif si et seulement s’il est surjectif » (Chapitre 19).

Exemple 2.17

Deux spécialisations classiques : $a = b = 1$ redonne $\sum_k \binom nk = 2^n$ ; $a = -1$, $b = 1$ donne $\sum_{k} (-1)^k \binom nk = 0$ pour $n \geq 1$ : parmi les parties d’un ensemble non vide, exactement la moitié sont de cardinal pair.