MPSI · Dénombrement

Propriétés des applications entre ensembles finis

Palier 0Palier 1Palier 1+Palier 2

Injections, surjections et cardinaux

Question

Une application de EE dans FF met les deux ensembles en relation. Si cette relation est contrainte — injective, surjective, bijective — impose-t-elle quelque chose aux tailles de EE et FF ? Autrement dit : la seule existence d'une application d'un certain type est-elle déjà une information de comptage, avant même qu'on ait compté quoi que ce soit ?

Proposition 1

Soient EE et FF deux ensembles finis et f:E→Ff:E\to F.

  1. Si ff est injective, alors Card⁡E⩽Card⁡F\operatorname{Card} E\leqslant\operatorname{Card} F.
  2. Si ff est surjective, alors Card⁡E⩾Card⁡F\operatorname{Card} E\geqslant\operatorname{Card} F.
  3. Si ff est bijective, alors Card⁡E=Card⁡F\operatorname{Card} E=\operatorname{Card} F.

Remarque :

Ce résultat est très intuitif.

  1. Pour injecter EE dans FF, il faut qu'il y ait assez de place dans FF pour contenir EE tout entier : FF a donc plus d'éléments que EE.
  2. Pour construire une surjection de EE sur FF, il faut recouvrir entièrement FF par EE : EE a donc plus d'éléments que FF.
  3. C'est ainsi que nous avons débuté le chapitre : on apparie les éléments deux à deux.

Démonstration :

  1. C'est le premier résultat démontré dans ce cours, pour établir l'unicité du cardinal. À défaut, pour toute injection f:E→Ff:E\to F, on considère la bijection f~:E→f(E)\widetilde{f}:E\to f(E) : alors Card⁡(E)=Card⁡(f(E))\operatorname{Card}(E)=\operatorname{Card}(f(E)), et Card⁡(f(E))⩽Card⁡F\operatorname{Card}(f(E))\leqslant\operatorname{Card} F car f(E)⊂Ff(E)\subset F.
  2. Pour chaque y∈Fy\in F, on choisit un antécédent xyx_y de yy par ff (n'importe lequel) et on pose φ(y)=xy\varphi(y)=x_y. Alors φ\varphi est une injection de FF dans EE : en effet, si φ(y)=φ(y′)\varphi(y)=\varphi(y'), alors en appliquant ff on obtient y=f(xy)=f(xy′)=y′y=f(x_y)=f(x_{y'})=y'. Le point 1, appliqué à φ\varphi, donne Card⁡F⩽Card⁡E\operatorname{Card} F\leqslant\operatorname{Card} E.
  3. Si ff est bijective, elle est à la fois injective et surjective : les points 1 et 2 donnent Card⁡E⩽Card⁡F\operatorname{Card} E\leqslant\operatorname{Card} F et Card⁡E⩾Card⁡F\operatorname{Card} E\geqslant\operatorname{Card} F, d'où l'égalité.

Test 1 : Une injection contraint les tailles

S'il existe une injection d'un ensemble fini EE dans un ensemble fini FF, alors Card⁡E⩽Card⁡F\operatorname{Card} E\leqslant\operatorname{Card} F.

Test 2 : Une injection dans soi-même

Toute application injective d'un ensemble dans lui-même est surjective.

Le principe des tiroirs

Question

Lisons le point 1 à l'envers. Il affirme : injective ⇒\Rightarrow Card⁡E⩽Card⁡F\operatorname{Card} E\leqslant\operatorname{Card} F. Sa contraposée dit donc que si EE est strictement plus gros que FF, aucune application de EE vers FF ne peut être injective — deux éléments au moins doivent se télescoper. Cet énoncé, d'apparence anodine, est l'un des outils de démonstration les plus puissants des mathématiques discrètes. Comment l'énoncer sous la forme la plus utilisable ?

Corollaire 1 : Le principe des tiroirs (Dirichlet)

Soient EE et FF deux ensembles finis et f:E→Ff:E\to F.

Si Card⁡E>Card⁡F\operatorname{Card} E>\operatorname{Card} F, alors ff n'est pas injective, c'est-à-dire : il existe deux éléments distincts de EE ayant la même image dans FF.

Démonstration :

Raisonnons par contraposition. Si ff était injective, le point 1 de la proposition précédente donnerait Card⁡E⩽Card⁡F\operatorname{Card} E\leqslant\operatorname{Card} F, ce qui contredit l'hypothèse Card⁡E>Card⁡F\operatorname{Card} E>\operatorname{Card} F.

Donc ff n'est pas injective : il existe x,x′∈Ex,x'\in E tels que x≠x′x\neq x' et f(x)=f(x′)f(x)=f(x').

Remarque :

Si l'on répartit nn objets dans pp tiroirs avec n>pn>p, alors au moins un tiroir contient au moins deux objets.

Exemple :

Dans un groupe de 1313 personnes, deux au moins sont nées le même mois : l'application « personne ↦\mapsto mois de naissance » va d'un ensemble à 1313 éléments vers un ensemble à 1212 éléments. Toute la difficulté, dans les usages sérieux du principe, est de deviner quels sont les tiroirs. Comment les fabriquer quand ils ne sont pas donnés par l'énoncé ?

Test 3 : Ce que le principe ne dit pas

Soient EE et FF finis et f:E→Ff:E\to F. Si Card⁡E>Card⁡F\operatorname{Card} E>\operatorname{Card} F, alors ff n'est pas surjective.

Exercice 1 : Approximation rationnelle — Théorème de Dirichlet

Soient x∈Rx\in\mathbb{R} et N∈N∗N\in\mathbb{N}^*. Montrer qu'il existe p∈Zp\in\mathbb{Z} et q∈N∗q\in\mathbb{N}^* avec q⩽Nq\leqslant N tels que

∣x−pq∣⩽1qN.\left|x-\frac{p}{q}\right|\leqslant\frac{1}{qN}.
Solution :(cliquer pour afficher)

Pour k∈⟦0,N⟧k\in\llbracket 0,N\rrbracket, posons xk=kx−⌊kx⌋∈[0,1[x_k=kx-\lfloor kx\rfloor\in[0,1[. On obtient ainsi N+1N+1 réels dans [0,1[[0,1[.

Découpons cet intervalle en NN tiroirs :

Ir=[rN, r+1N[,r∈⟦0,N−1⟧.I_r=\left[\frac{r}{N},\ \frac{r+1}{N}\right[,\qquad r\in\llbracket 0,N-1\rrbracket .

Ces intervalles sont deux à deux disjoints et de réunion [0,1[[0,1[ : chaque xkx_k appartient donc à exactement un IrI_r. Notons g:⟦0,N⟧→⟦0,N−1⟧g:\llbracket 0,N\rrbracket\to\llbracket 0,N-1\rrbracket l'application associant à kk l'indice rr de ce tiroir.

Comme Card⁡⟦0,N⟧=N+1>N=Card⁡⟦0,N−1⟧\operatorname{Card}\llbracket 0,N\rrbracket=N+1>N=\operatorname{Card}\llbracket 0,N-1\rrbracket, le principe des tiroirs affirme que gg n'est pas injective : au moins deux des nombres xkx_k appartiennent au même intervalle IrI_r.

Il existe donc k<ℓk<\ell dans ⟦0,N⟧\llbracket 0,N\rrbracket tels que xkx_k et xℓx_\ell soient dans un même IrI_r, lequel est de longueur 1N\frac1N :

∣xℓ−xk∣<1N.|x_\ell-x_k|<\frac{1}{N}.

Posons q=ℓ−kq=\ell-k et p=⌊ℓx⌋−⌊kx⌋p=\lfloor\ell x\rfloor-\lfloor kx\rfloor. Comme 0⩽k<ℓ⩽N0\leqslant k<\ell\leqslant N, on a 1⩽q⩽N1\leqslant q\leqslant N. Par ailleurs

xℓ−xk=(ℓx−⌊ℓx⌋)−(kx−⌊kx⌋)=(ℓ−k)x−(⌊ℓx⌋−⌊kx⌋)=qx−p,x_\ell-x_k=\bigl(\ell x-\lfloor\ell x\rfloor\bigr)-\bigl(kx-\lfloor kx\rfloor\bigr)=(\ell-k)x-\bigl(\lfloor\ell x\rfloor-\lfloor kx\rfloor\bigr)=qx-p,

de sorte que l'inégalité précédente se réécrit ∣qx−p∣<1N|qx-p|<\dfrac{1}{N}.

En divisant par q>0q>0 :

∣x−pq∣<1qN,\left|x-\frac{p}{q}\right|<\frac{1}{qN},

ce qui entraîne en particulier l'inégalité large demandée.

Exercice 2 : Entiers et divisibilité

Soit n⩾1n\geqslant 1 un entier. Montrer que parmi tout ensemble de n+1n+1 entiers distincts choisis dans {1,2,…,2n}\{1,2,\dots,2n\}, il en existe toujours deux dont l'un divise l'autre.

Solution :(cliquer pour afficher)

Soit {a1,…,an+1}\{a_1,\dots,a_{n+1}\} une partie de {1,2,…,2n}\{1,2,\dots,2n\} à n+1n+1 éléments distincts.

Tout entier m⩾1m\geqslant 1 s'écrit de manière unique sous la forme m=2s⋅tm=2^s\cdot t où s∈Ns\in\mathbb{N} et tt est impair.

Notons II l'ensemble des entiers impairs de {1,…,2n}\{1,\dots,2n\}, c'est-à-dire I={1,3,5,…,2n−1}I=\{1,3,5,\dots,2n-1\} : il en compte exactement nn.

On considère f:{a1,…,an+1}→If:\{a_1,\dots,a_{n+1}\}\to I où f(ai)f(a_i) est l'unique entier impair tel que ai=2sif(ai)a_i=2^{s_i}f(a_i).

Comme n+1>nn+1>n, le principe des tiroirs garantit qu'il existe i≠ji\neq j tels que f(ai)=f(aj)=tf(a_i)=f(a_j)=t, c'est-à-dire ai=2sita_i=2^{s_i}t et aj=2sjta_j=2^{s_j}t avec si≠sjs_i\neq s_j (sinon ai=aja_i=a_j).

Si si<sjs_i<s_j, alors aj=2 sj−siaia_j=2^{\,s_j-s_i}a_i, donc ai∣aja_i\mid a_j ; sinon aj∣aia_j\mid a_i. Dans les deux cas, l'un des deux entiers divise l'autre.

Applications entre ensembles de même cardinal

Question

En général, injectivité et surjectivité sont deux propriétés indépendantes : ni l'une n'entraîne l'autre. Mais dans le cas particulier où EE et FF ont exactement le même nombre d'éléments, le point 1 de la proposition disait déjà qu'une injection « remplit tout juste » FF. Cette contrainte de place suffit-elle à forcer la surjectivité — et donc à ramener les trois notions à une seule ?

Théorème 1

Soient EE et FF deux ensembles finis de même cardinal et f:E→Ff:E\to F. Alors

f injective  ⟺  f surjective  ⟺  f bijective.f\text{ injective}\iff f\text{ surjective}\iff f\text{ bijective}.

Démonstration :

Notons (1)(1), (2)(2), (3)(3) les propriétés « ff injective », « ff surjective », « ff bijective ». L'implication (3)⇒(1)(3)\Rightarrow(1) et (3)⇒(2)(3)\Rightarrow(2) étant immédiates, il suffit d'établir (1)⇒(3)(1)\Rightarrow(3) et (2)⇒(3)(2)\Rightarrow(3).

(1)⇒(3)(1)\Rightarrow(3). Si ff est injective, elle est bijective sur f(E)⊂Ff(E)\subset F, donc Card⁡E=Card⁡f(E)⩽Card⁡F\operatorname{Card} E=\operatorname{Card} f(E)\leqslant\operatorname{Card} F. Comme f(E)=Ff(E)=F si et seulement si les cardinaux sont égaux, ce qui est le cas ici, ff est bijective.

(2)⇒(3)(2)\Rightarrow(3). Si ff est surjective, on construit une injection de FF dans EE comme dans la preuve précédente : ff est donc bijective, d'application réciproque cette injection.

Test 4 : Injective suffit

Si EE et FF sont finis de même cardinal, toute application injective de EE dans FF est bijective.

Exercice 3 : Un inverse à gauche suffit

Soient EE un ensemble fini et f,g:E→Ef,g:E\to E deux applications telles que g∘f=IdEg\circ f=\mathrm{Id}_E. Montrer que ff et gg sont bijectives et que g=f−1g=f^{-1}.

Ce résultat subsiste-t-il si l'on supprime l'hypothèse « EE fini » ?

Solution :(cliquer pour afficher)

Bijectivité de ff. Soient x,x′∈Ex,x'\in E tels que f(x)=f(x′)f(x)=f(x'). En appliquant gg, on obtient g(f(x))=g(f(x′))g(f(x))=g(f(x')), c'est-à-dire x=x′x=x' : ff est injective. Comme EE est fini et que ff va de EE dans EE (deux ensembles de même cardinal, à savoir EE lui-même), le théorème donne la bijectivité de ff.

Identification de gg. De g∘f=IdEg\circ f=\mathrm{Id}_E on tire, en composant à droite par f−1f^{-1} :

g=g∘f∘f−1=IdE∘f−1=f−1.g=g\circ f\circ f^{-1}=\mathrm{Id}_E\circ f^{-1}=f^{-1}.

En particulier gg est bijective, comme réciproque d'une bijection.

Sans l'hypothèse de finitude. Le résultat tombe. Prenons E=NE=\mathbb{N}, f(k)=k+1f(k)=k+1 et

g(k)={k−1si k⩾1,0si k=0.g(k)=\begin{cases}k-1 & \text{si } k\geqslant 1,\\ 0 & \text{si } k=0.\end{cases}

On vérifie que g(f(k))=g(k+1)=kg(f(k))=g(k+1)=k pour tout kk, donc g∘f=IdNg\circ f=\mathrm{Id}_{\mathbb{N}}. Pourtant ff n'est pas surjective (00 n'a pas d'antécédent) et gg n'est pas injective (g(0)=g(1)=0g(0)=g(1)=0) : aucune des deux n'est bijective.