Exercice 46

Sens direct. Supposons $X$ infini, et soit $f : X \to X$. On fixe $x \in X$ et l'on considère $$S = \{f^{n}(x) \mid n \in \mathbb{N}\} \qquad\text{et}\qquad S' = \{f^{n}(x) \mid n \geqslant 1\}.$$ Ces deux parties sont non vides et stables, puisque $f$ envoie $f^{n}(x)$ sur $f^{n+1}(x)$. Si l'une d'elles diffère de $X$, on a trouvé la partie voulue. Sinon $S' = X$ contient $x$, qui s'écrit $x = f^{m}(x)$ avec $m \geqslant 1$. Les itérés de $x$ se répètent alors de $m$ en $m$, et $S = \{x, f(x), \dots, f^{m-1}(x)\}$. Associer à chaque élément de $S$ le plus petit $k \in [\![0\,;m-1]\!]$ tel qu'il s'écrive $f^{k}(x)$ définit une injection de $S$ dans $[\![0\,;m-1]\!]$ : $S$ est en bijection avec une partie d'un ensemble fini, donc finie d'après les lemmes 2 et 3 du cours, alors que $S = X$ est infini. C'est absurde.

Réciproque. Montrons la contraposée : si $X$ est fini, il existe une application sans partie stable autre que $\varnothing$ et $X$. Si $X$ est vide, c'est évident, car $\varnothing = X$. Sinon, écrivons $X = \{x_{1}, \dots, x_{n}\}$, et posons $f(x_{i}) = x_{i+1}$ pour $i < n$ et $f(x_{n}) = x_{1}$. Une partie stable non vide contient un $x_{i}$, donc $x_{i+1}$, et de proche en proche tous les éléments : c'est $X$. $$\boxed{X \text{ est infini} \iff \text{toute application } X \to X \text{ a une partie stable différente de } \varnothing \text{ et de } X.}$$ On obtient ainsi une caractérisation de l'infini qui ne fait intervenir aucun nombre, dans l'esprit de la définition de Dedekind : un ensemble est infini s'il est en bijection avec une partie stricte de lui-même.