La finitude, et elle seule

Ce qu'on a le droit d'utiliser. Une seule proposition du cours : si $A\subset E$ avec $E$ fini, alors $|A|\le |E|$, avec égalité si et seulement si $A=E$. Et la propriété intuitive, admise par le programme, que l'image d'un ensemble fini $A$ par une application a au plus $|A|$ éléments — en choisissant un antécédent par élément de l'image, on injecte $f(A)$ dans $A$. Posons $n=|E|$.

a) Les trois équivalences.

Injective implique surjective. Si $f$ est injective, elle induit une bijection de $E$ sur $f(E)$, donc $|f(E)|=n$. Comme $f(E)\subset E$ et $|f(E)|=|E|$, le cas d'égalité donne $f(E)=E$ : $f$ est surjective.

Surjective implique injective. Supposons $f$ surjective et, par l'absurde, non injective : il existe $x\ne x^{\prime }$ dans $E$ avec $f(x)=f(x^{\prime })$. Alors tout élément de $f(E)$ est atteint sur $E\setminus \{x^{\prime }\}$ — l'image $f(x^{\prime })$ l'est par $x$ —, donc $f(E)=f(E\setminus \{x^{\prime }\})$, et $|f(E)|\le |E\setminus \{x^{\prime }\}|=n-1$. Or $f(E)=E$ a $n$ éléments. Contradiction.

Les deux implications donnent l'équivalence entre injectivité et surjectivité, et chacune équivaut alors à la bijectivité, qui est leur conjonction.

Le point délicat : où sert la finitude ? Uniquement dans le cas d'égalité $|A|=|E|\Rightarrow A=E$. Une partie stricte d'un ensemble infini peut être en bijection avec lui — c'est exactement ce que le b) va montrer sur $\mathbb{N}$. On notera l'analogie exacte avec la dimension finie du chapitre 12 : pour un endomorphisme d'un espace de dimension finie, injectif, surjectif et bijectif sont équivalents, par la même démonstration, les dimensions remplaçant les cardinaux.

b) Les deux contre-exemples sur $\mathbb{N}$. L'application $s:n\mapsto n+1$ est injective ($n+1=m+1$ donne $n=m$) mais non surjective : $0$ n'a pas d'antécédent, puisque $n+1\ge 1$ pour tout $n$. L'application $p:n\mapsto \max (n-1,0)$, c'est-à-dire $p(0)=0$ et $p(n)=n-1$ pour $n\ge 1$, est surjective (tout $m$ s'écrit $m=p(m+1)$) mais non injective : $p(0)=p(1)=0$. On remarquera que $p\circ s={\mathrm{Id}}_{\mathbb{N}}$ alors que $s\circ p\ne {\mathrm{Id}}_{\mathbb{N}}$ : en infini, un inverse à gauche n'est pas un inverse.

c) Une puissance de $f$ est l'identité. Considérons les itérées $f^0={\mathrm{Id}}_E,f^1=f,f^2=f\circ f,\dots$ Ce sont des éléments de $E^E$, l'ensemble des applications de $E$ dans $E$, qui est fini de cardinal $n^n$. Les $n^n+1$ applications $f^0,f^1,\dots ,f^{n^n}$ ne peuvent pas être deux à deux distinctes — c'est le principe des tiroirs : il existe $0\le i<j\le n^n$ tels que $f^i=f^j$.

Simplifier. Par a), $f$ est bijective, donc $f^i$ aussi, comme composée de bijections. Écrivons $f^j=f^{j-i}\circ f^i$ et composons à droite par $(f^i{)}^{-1}$ : $$f^{j-i}=f^j\circ (f^i{)}^{-1}=f^i\circ (f^i{)}^{-1}={\mathrm{Id}}_E.$$ L'entier $k=j-i\ge 1$ convient : $f^k={\mathrm{Id}}_E$.

Sur $\mathbb{N}$. Pour $s:n\mapsto n+1$, on a $s^k(n)=n+k\ne n$ pour tout $k\ge 1$ : aucune puissance n'est l'identité. L'argument s'effondre dès la première ligne, l'ensemble ${\mathbb{N}}^{\mathbb{N}}$ n'étant pas fini : les itérées $s^j$ sont toutes distinctes.

L'inverse. De $f^k={\mathrm{Id}}_E$ avec $k\ge 1$ : $f\circ f^{k-1}=f^{k-1}\circ f={\mathrm{Id}}_E$, donc $f^{-1}=f^{k-1}$ — l'identité si $k=1$, auquel cas $f={\mathrm{Id}}_E$. Une injection d'un ensemble fini dans lui-même est une permutation, et son inverse s'obtient en itérant.

Ce que l'exercice installe. Le réflexe « en cardinal fini, une seule des deux propriétés suffit » : pour prouver qu'une application entre ensembles de même cardinal est bijective, un comptage et l'injectivité suffisent. Et la finitude force une période : deux itérées coïncident, donc une puissance est l'identité — c'est le germe de la notion d'ordre d'un élément, qu'on retrouvera en seconde année, et de l'ordre d'une permutation.