MPSI · Dénombrement

Cardinal d'un ensemble fini

Palier 0Palier 1Palier 1+Palier 2

Le dénombrement est une partie délicate des mathématiques. Notre objectif ne sera pas d'étudier la théorie du dénombrement pour elle-même, mais simplement d'en utiliser quelques outils en probabilités.

Ensembles finis

Intuitivement un ensemble est fini s'il possède un nombre fini d'éléments, mais cette définition manque de précision.

Question

Comment définir « avoir un nombre fini d'éléments » sans employer le mot fini dans la définition même ? Reprenons le geste élémentaire : lorsqu'on compte un tas d'objets, on les désigne un par un — le premier, le deuxième, le troisième… — c'est-à-dire qu'on les met en correspondance, sans oubli ni doublon, avec un segment initial des entiers. C'est cette correspondance, et non le mot « nombre », qui va servir de définition.

Définition 1 : Ensemble fini

Un ensemble EE est dit fini s'il existe n∈Nn\in\mathbb{N} tel que EE soit en bijection avec ⟦1,n⟧\llbracket 1,n\rrbracket.

Un ensemble est dit infini s'il n'est pas fini.

Remarque :

Établir une bijection entre EE et ⟦1,n⟧\llbracket 1,n\rrbracket, c'est attribuer un numéro distinct à chaque élément de EE : c'est donc compter les éléments de EE.

Question

La définition affirme l'existence d'un entier nn, mais elle ne dit rien de son unicité. Un même ensemble pourrait-il être en bijection à la fois avec ⟦1,4⟧\llbracket 1,4\rrbracket et avec ⟦1,7⟧\llbracket 1,7\rrbracket ? Si c'était le cas, l'acte de compter perdrait tout son sens : deux personnes comptant le même tas pourraient trouver des résultats différents sans qu'aucune ne se trompe. La réponse est non, et c'est l'objet du lemme suivant.

Lemme 1

Soient n,pn,p deux entiers naturels non nuls.

  1. S'il existe une injection de ⟦1,n⟧\llbracket 1,n\rrbracket dans ⟦1,p⟧\llbracket 1,p\rrbracket, alors n⩽pn\leqslant p.
  2. S'il existe une bijection de ⟦1,n⟧\llbracket 1,n\rrbracket sur ⟦1,p⟧\llbracket 1,p\rrbracket, alors n=pn=p.

Démonstration :

Montrons d'abord que l'existence d'une injection de ⟦1,n⟧\llbracket 1,n\rrbracket dans ⟦1,p⟧\llbracket 1,p\rrbracket entraîne n⩽pn\leqslant p, par récurrence sur p∈N∗p\in\mathbb{N}^*.

  • Si p=1p=1, alors nécessairement n⩽1=pn\leqslant 1=p. En effet, si n⩾2n\geqslant 2 et f:⟦1,n⟧→⟦1,p⟧f:\llbracket 1,n\rrbracket\to\llbracket 1,p\rrbracket, alors f(1)=1=f(2)f(1)=1=f(2), donc ff n'est pas injective.
  • Soit p∈N∗p\in\mathbb{N}^* fixé ; on suppose le résultat vrai à ce rang. Soit n∈N∗n\in\mathbb{N}^* tel qu'il existe une injection ff de ⟦1,n⟧\llbracket 1,n\rrbracket dans ⟦1,p+1⟧\llbracket 1,p+1\rrbracket. Si n=1n=1, alors n⩽pn\leqslant p et le résultat est vérifié. On suppose donc n⩾2n\geqslant 2.
    • Si f(⟦1,n⟧)⊂⟦1,p⟧f(\llbracket 1,n\rrbracket)\subset\llbracket 1,p\rrbracket, on applique l'hypothèse de récurrence et n⩽p⩽p+1n\leqslant p\leqslant p+1.
    • Sinon, il existe k∈⟦1,n⟧k\in\llbracket 1,n\rrbracket tel que f(k)=p+1f(k)=p+1. On définit alors une nouvelle application
g:{⟦1,n−1⟧→⟦1,p⟧i↦{f(i)si i≠k,f(n)si i=k.g:\left\{ \begin{aligned} &\llbracket 1,n-1\rrbracket \to \llbracket 1,p\rrbracket\\ &i\mapsto \begin{cases} f(i) & \text{si } i\neq k,\\ f(n) & \text{si } i=k. \end{cases} \end{aligned}\right.

Par construction, gg est à valeurs dans ⟦1,p⟧\llbracket 1,p\rrbracket et reste clairement injective. C'est donc une injection de ⟦1,n−1⟧\llbracket 1,n-1\rrbracket dans ⟦1,p⟧\llbracket 1,p\rrbracket, d'où, par hypothèse de récurrence, n−1⩽pn-1\leqslant p, c'est-à-dire n⩽p+1n\leqslant p+1.

L'hérédité est vérifiée, donc pour tout (n,p)∈(N∗)2(n,p)\in(\mathbb{N}^*)^2, l'existence d'une injection de ⟦1,n⟧\llbracket 1,n\rrbracket dans ⟦1,p⟧\llbracket 1,p\rrbracket entraîne n⩽pn\leqslant p.

Cas de la bijection. Si ⟦1,n⟧\llbracket 1,n\rrbracket et ⟦1,p⟧\llbracket 1,p\rrbracket sont en bijection, soit ff une telle bijection : d'après ce qui précède, n⩽pn\leqslant p. Comme f−1f^{-1} est une bijection de ⟦1,p⟧\llbracket 1,p\rrbracket sur ⟦1,n⟧\llbracket 1,n\rrbracket, on a aussi p⩽np\leqslant n, d'où p=np=n. Le sens réciproque est trivial.

Test 1 : Sens de l'inégalité

S'il existe une injection de ⟦1,7⟧\llbracket 1,7\rrbracket dans ⟦1,p⟧\llbracket 1,p\rrbracket, alors p⩽7p\leqslant 7.

Exercice 1 : ℕ est infini

Montrer que N\mathbb{N} est un ensemble infini.

Solution :(cliquer pour afficher)

Raisonnons par l'absurde et supposons N\mathbb{N} fini : il existe n∈Nn\in\mathbb{N} et une bijection φ:N→⟦1,n⟧\varphi:\mathbb{N}\to\llbracket 1,n\rrbracket. Comme N≠∅\mathbb{N}\neq\varnothing, on a n⩾1n\geqslant 1.

L'application réciproque φ−1\varphi^{-1} est une bijection de ⟦1,n⟧\llbracket 1,n\rrbracket sur N\mathbb{N}. Posons

M=max⁡{φ−1(1),φ−1(2),…,φ−1(n)},M=\max\bigl\{\varphi^{-1}(1),\varphi^{-1}(2),\dots,\varphi^{-1}(n)\bigr\},

ce maximum existant car il s'agit d'une partie non vide et finie de N\mathbb{N} (au plus nn éléments, explicitement énumérés).

L'entier M+1M+1 appartient à N\mathbb{N}, mais il n'est l'image d'aucun élément de ⟦1,n⟧\llbracket 1,n\rrbracket par φ−1\varphi^{-1}, puisque toutes ces images sont majorées par MM. Cela contredit la surjectivité de φ−1\varphi^{-1}.

Donc N\mathbb{N} n'est en bijection avec aucun ⟦1,n⟧\llbracket 1,n\rrbracket : il est infini.

Le cardinal

Question

Le lemme vient de fermer la porte à toute ambiguïté : un ensemble fini ne peut être en bijection qu'avec un seul ⟦1,n⟧\llbracket 1,n\rrbracket. Cet entier nn ne dépend donc ni de la manière de numéroter les éléments, ni de l'ordre choisi pour le faire : il ne dépend que de EE. Un entier attaché à un ensemble et insensible à toute renumérotation — c'est exactement ce que l'on cherchait à capturer. Comment le nommer et le noter ?

Définition 2 : Cardinal

Soit EE un ensemble fini. L'unique entier nn tel que EE soit en bijection avec ⟦1,n⟧\llbracket 1,n\rrbracket est appelé cardinal de EE et se note Card⁡(E)\operatorname{Card}(E), ∣E∣|E| ou #E\#E.

Remarque :

Si EE est vide, alors Card⁡(∅)=0\operatorname{Card}(\varnothing)=0 car ⟦1,0⟧=∅\llbracket 1,0\rrbracket=\varnothing.

Exemple :

Soit (m,n)∈Z2(m,n)\in\mathbb{Z}^2 tel que m⩽nm\leqslant n. Le cardinal de ⟦m,n⟧\llbracket m,n\rrbracket est n−m+1n-m+1, car l'application k↦k+m−1k\mapsto k+m-1 réalise une bijection de ⟦1,n−m+1⟧\llbracket 1,n-m+1\rrbracket sur ⟦m,n⟧\llbracket m,n\rrbracket. Encore faut-il s'en assurer : comment vérifie-t-on qu'une telle application est bien une bijection ?

Exercice 2 : Les entiers pairs d'un segment

Soit n∈N∗n\in\mathbb{N}^*. Montrer que l'ensemble

Pn={k∈⟦1,2n⟧ : k est pair}P_n=\bigl\{k\in\llbracket 1,2n\rrbracket \ :\ k \text{ est pair}\bigr\}

est fini et déterminer son cardinal.

Solution :(cliquer pour afficher)

Considérons l'application φ:⟦1,n⟧→Pn\varphi : \llbracket 1,n\rrbracket \to P_n définie par φ(j)=2j\varphi(j)=2j.

Elle est bien définie. Si 1⩽j⩽n1\leqslant j\leqslant n, alors 2⩽2j⩽2n2\leqslant 2j\leqslant 2n, donc 2j∈⟦1,2n⟧2j\in\llbracket 1,2n\rrbracket, et 2j2j est pair : ainsi φ(j)∈Pn\varphi(j)\in P_n.

Elle est injective. Si φ(j)=φ(j′)\varphi(j)=\varphi(j'), alors 2j=2j′2j=2j', d'où j=j′j=j'.

Elle est surjective. Soit k∈Pnk\in P_n. Comme kk est pair, il s'écrit k=2jk=2j avec j∈Zj\in\mathbb{Z}. De 1⩽2j⩽2n1\leqslant 2j\leqslant 2n on tire 12⩽j⩽n\tfrac12\leqslant j\leqslant n, donc j∈⟦1,n⟧j\in\llbracket 1,n\rrbracket et k=φ(j)k=\varphi(j).

Ainsi φ\varphi est une bijection de ⟦1,n⟧\llbracket 1,n\rrbracket sur PnP_n ; sa réciproque φ−1\varphi^{-1} est une bijection de PnP_n sur ⟦1,n⟧\llbracket 1,n\rrbracket. Donc PnP_n est fini et Card⁡(Pn)=n\operatorname{Card}(P_n)=n.

Ensembles en bijection

Question

Pour établir que deux ensembles finis ont autant d'éléments l'un que l'autre, faut-il nécessairement les compter tous les deux ? Un berger illettré sait déjà que son troupeau est complet sans savoir compter : il apparie chaque bête à un caillou de sa besace. Cet appariement — une bijection — suffit-il à garantir l'égalité des cardinaux, et réciproquement ?

Théorème 1

Deux ensembles finis non vides EE et FF sont en bijection si et seulement s'ils ont le même cardinal.

Démonstration :

L'idée est d'établir des bijections entre EE et ⟦1,n⟧\llbracket 1,n\rrbracket, puis entre FF et ⟦1,p⟧\llbracket 1,p\rrbracket, et d'utiliser le fait que la composée de deux bijections est une bijection. On note φ1:E→⟦1,n⟧\varphi_1:E\to\llbracket 1,n\rrbracket et φ2:F→⟦1,p⟧\varphi_2:F\to\llbracket 1,p\rrbracket ces deux bijections, de sorte que Card⁡(E)=n\operatorname{Card}(E)=n et Card⁡(F)=p\operatorname{Card}(F)=p.

Sens direct. Si EE et FF sont en bijection, soit ψ:E→F\psi:E\to F une bijection. En posant f=φ2∘ψ∘φ1−1f=\varphi_2\circ\psi\circ\varphi_1^{-1}, on obtient une bijection de ⟦1,n⟧\llbracket 1,n\rrbracket sur ⟦1,p⟧\llbracket 1,p\rrbracket. Donc n=pn=p et Card⁡(E)=Card⁡(F)\operatorname{Card}(E)=\operatorname{Card}(F).

Sens réciproque. Si n=pn=p, on peut choisir f=Idf=\mathrm{Id} dans le schéma précédent. En posant ψ=φ2−1∘Id∘φ1\psi=\varphi_2^{-1}\circ\mathrm{Id}\circ\varphi_1, on obtient une bijection entre EE et FF.

Test 2 : Compter sans compter

Pour prouver que deux ensembles finis ont le même cardinal, il suffit d'exhiber une bijection de l'un sur l'autre, sans calculer aucun des deux cardinaux.

Test 3 : Même cardinal, même ensemble ?

Si EE et FF sont deux ensembles finis tels que Card⁡(E)=Card⁡(F)\operatorname{Card}(E)=\operatorname{Card}(F), alors E=FE=F.

Exercice 3 : Retirer un élément

Soient EE un ensemble fini de cardinal n⩾1n\geqslant 1 et a∈Ea\in E. Montrer que E∖{a}E\setminus\{a\} est fini et que Card⁡(E∖{a})=n−1\operatorname{Card}\bigl(E\setminus\{a\}\bigr)=n-1.

Solution :(cliquer pour afficher)

Soit φ:E→⟦1,n⟧\varphi:E\to\llbracket 1,n\rrbracket une bijection et posons k=φ(a)k=\varphi(a).

Notons τ:⟦1,n⟧→⟦1,n⟧\tau:\llbracket 1,n\rrbracket\to\llbracket 1,n\rrbracket l'application qui échange kk et nn et fixe tous les autres entiers :

τ(i)={nsi i=k,ksi i=n,isinon.\tau(i)= \begin{cases} n & \text{si } i=k,\\ k & \text{si } i=n,\\ i & \text{sinon.} \end{cases}

Elle vérifie τ∘τ=Id\tau\circ\tau=\mathrm{Id}, donc τ\tau est bijective.

Posons ψ=τ∘φ\psi=\tau\circ\varphi : composée de deux bijections, ψ\psi est une bijection de EE sur ⟦1,n⟧\llbracket 1,n\rrbracket, et ψ(a)=τ(k)=n\psi(a)=\tau(k)=n.

Comme ψ\psi est injective, aa est le seul élément de EE dont l'image vaut nn : la restriction de ψ\psi à E∖{a}E\setminus\{a\} est donc à valeurs dans ⟦1,n−1⟧\llbracket 1,n-1\rrbracket. Elle reste injective (restriction d'une injection) et elle est surjective : tout j∈⟦1,n−1⟧j\in\llbracket 1,n-1\rrbracket admet un antécédent x=ψ−1(j)x=\psi^{-1}(j) dans EE, et x≠ax\neq a puisque ψ(a)=n≠j\psi(a)=n\neq j.

C'est donc une bijection de E∖{a}E\setminus\{a\} sur ⟦1,n−1⟧\llbracket 1,n-1\rrbracket, d'où le résultat.