L’Infini Mathématique [C1.II.4]

1. Le premier ensemble infini

Rappelons que nous avons défini dans [C1.II.3, définition 1.1] la notion d’ensemble infini comme un ensemble qui n’est pas fini. Notre étude de l’infini mathématique commence donc avec cette définition simple, et la place de l’ensemble $\mathbb N$, le plus « simple » des ensembles infinis, dans la théorie des ensembles finis et infinis. Il nous sera utile d’identifier les sous-ensembles finis de $\mathbb N$, pour démontrer que l’ensemble $\mathbb N$ est infini.

Proposition 1.1
Si $X\subseteq\mathbb N$, alors $X$ est fini si et seulement si il existe un entier $n\in\mathbb N$ tel que $X\subseteq [[0,n]]=\{i\in\mathbb N : i\leq n\}$.

Démonstration
Supposons que $X$ est fini, de cardinal $m$, et démontrons la propriété par récurrence sur $m$. Si $m=0$, alors $X$ est vide, et alors $X\subseteq [[0,0]]$, donc la propriété est vérifiée au rang $m=0$ avec $n=0$. Supposons que $X$ est de cardinal $m+1$ et que la propriété est vérifiée au rang $m$, et soit $x$ un élément de $X$ (qui est non vide par hypothèse) : le cardinal de l’ensemble $Y=X-\{x\}$ est $m$ par [C1.II.3, proposition 1.7], donc par hypothèse de récurrence il existe un entier $n\in\mathbb N$ tel que $Y\subseteq [[0,n]]$. Par suite, si $n’$ désigne le plus grand des entiers $n$ et $x$, on a $X\subseteq [[0,n’]]$, et la propriété est vérifiée au rang $m+1$. Par le principe de récurrence, elle est valide pour tout $m\in\mathbb N$, donc tout sous-ensemble fini de $\mathbb N$ est inclus dans un ensemble de la forme $[[0,n]]$ (appelé un segment initial).
Réciproquement, supposons qu’il existe $n\in\mathbb N$ tel que $X\subseteq [[0,n]]$. L’ensemble $[[0,n]]$ est fini, puisque l’application $[[0,n]]\to [[1,n+1]]$, $i\mapsto i+1$ est une bijection, et $X$ est alors un sous-ensemble d’un ensemble fini : il est donc fini par [C1.II.3, corollaire 2.1]. $\square$

La première caractérisation de l’infini que nous donnerons s’appuie sur l’exemple fondamental d’ensemble infini, l’ensemble $\mathbb N$ des nombres entiers naturels. Toutefois, il nous faut déjà démontrer que cet ensemble est infini ! Nous aurons besoin du lemme suivant.

Lemme 1.2
Si $f:E\to F$ est une application et si $E$ est fini, alors $f(E)$ est fini (l’image d’un ensemble fini est un ensemble fini).

Démonstration
Supposons que $y\in f(E)$ : il existe $x\in E$ tel que $f(x)=y$; pour tout $y\in f(E)$ choisissons donc un élément $x_y$ de $E$, que nous notons $g(y)$, et tel que $f(x_y)=y$ (c’est-à-dire un antécédent de $y$ par $f$). Nous définissons ainsi une application $g:f(E)\to E$, $y\mapsto g(y)=x_y$. Supposons que $y,y’\in f(E)$ et que $g(y)=g(y’)$ : par définition de $g$, on a $y=f(g(y))=f(g(y’))=y’$, ce qui montre que $g$ est injective. L’application $g$ est donc une bijection de $f(E)$ sur un sous-ensemble $g(f(E))$ de $E$. Par le corollaire 2 de [Dénombrement des ensembles finis] (ibid.), l’ensemble $g(f(E))$ est fini, et on en conclut que $f(E)$ est fini. $\square$

La figure suivante illustre dans l’ensemble $\mathbb N$ le principe que l’image d’un ensemble fini est finie.

Théorème 1.3
L’ensemble $\mathbb N$ des nombres entiers naturels est infini.

Démonstration
Par définition, nous devons démontrer qu’il n’existe aucune bijection entre $\mathbb N$ et un ensemble de la forme $[[1,n]]$. Il suffit de montrer que pour tout entier naturel $n$, une application $f:[[1,n]]\to \mathbb N$ ne peut pas être surjective (il ne peut donc \textit{a fortiori} pas exister de bijection de $[[1,n]]$ sur $\mathbb N$), ce qui vient directement du lemme 1.2. En effet, si $f:[[1,n]]\to \mathbb N$ est une telle application, par ce lemme le sous-ensemble $Im(f)$ de $\mathbb N$ est fini, et par la proposition 1.1 il existe un entier naturel $k$ tel que $Im(f)\subseteq [[0,k]]$. Il s’ensuit que $k+1$, par exemple, n’a pas d’antécédent par $f$, si bien que $f$ ne peut pas être surjective. $\square$

Il est important de comprendre que même si la (première) définition d’un ensemble infini adoptée ici n’est que la négation de celle d’un ensemble fini, cette définition est parfaitement valide, et que l’infinité de $\mathbb N$ est une « évidence » qu’il faut cependant démontrer.

Pour terminer cette section, nous rassemblons ici les postulats que nous avons adoptés jusqu’ici concernant la fonction successeur. Ils sont notre version de ce qu’on appelle les axiomes de Peano, qui déterminent de manière univoque les propriétés de cette fonction, et permettent de reconstituer toute la structure opératoire et relationnelle de l’ensemble $\mathbb N$. Nous aborderons en effet l’arithmétique naturelle de manière rigoureuse à partir de ces axiomes dans le cours suivant.

Axiome 1
$0$ n’est le successeur d’aucun entier naturel. En d’autres termes, il n’existe pas d’entier naturel $n$ tel que $s(n)=0$.

En particulier, l’application successeur n’est pas surjective, puisque $0$ ne possède pas d’antécédent.

Axiome 2
Si deux entiers naturels $m$ et $n$ ont le même successeur, alors ils sont égaux. En d’autres termes, pour tous entiers naturels $m,n$, si $s(m)=s(n)$ alors $m=n$.

On peut reformuler cet axiome en disant que l’application successeur est injective.

Axiome 3 [Principe de récurrence (ou d’induction)]
Si $S$ est un sous-ensemble de $\mathbb N$ tel que :
i) $0\in S$
ii) pour tout $n\in S$, $s(n)\in S$ (« étape de récurrence »),
alors on a $S=\mathbb N$.

Ce principe signifie intuitivement que l’ensemble $\mathbb N$ est entièrement « parcouru » si nous l’énumérons à partir de $0$ et ajoutons chaque entier naturel successif, de manière indéfinie. Il fonde la pratique des démonstrations et définitions par récurrence.

Concernant les démonstrations par récurrence, celles-ci portent sur une propriété $P(n)$ portant sur l’entier naturel $n$. En principe pour démontrer que la propriété $P(n)$ est vraie pour tout $n$, il suffit donc de démontrer que l’ensemble des entiers naturels pour lesquels $P(n)$ est vraie, symboliquement $S=\{n\in\mathbb N : P(n)\}$, est l’ensemble $\mathbb N$ tout entier.

Pour cela, on applique le principe de récurrence : on doit montrer que $0\in S$ (autrement dit que la propriété $P(0)$ est vraie, étape initiale), puis que $n+1\in S$ dès que $n\in S$ (autrement dit, que $P(n+1)$ est vraie dès que $P(n)$ est vraie, étape de récurrence). On retrouve exactement le principe de la démonstration par récurrence.

Nous avons dans ce cours rappelé certaines définitions par récurrence, évoquées dans le chapitre [C1.I.5 : Raisonnement mathématique]. Une telle définition consiste essentiellement à décrire une suite d’éléments d’un ensemble $E$, c’est-à-dire une application $f:\mathbb N\to E$, en définissant d’abord $f(0)$ (étape initiale) et en utilisant une propriété ou une fonction auxiliaire pour définir la valeur $f(n+1)$ à partir de la valeur $f(n)$ (étape de récurrence).

La justification d’une telle définition sera faite au Livre 3 (Arithmétique élémentaire), à partir du théorème de récurrence.

1.1. Exercices

Exercice 1.4
i) Trouver un sous-ensemble infini de $\mathbb N$ différent de $\mathbb N$. Démontrer qu’il est infini.
ii) Démontrer par récurrence que tout sous-ensemble fini non vide $X$ de $\mathbb N$ possède un plus grand élément, c’est-à-dire qu’il existe $k\in X$ tel que pour tout $i\in X$, on ait $i\leq k$.
iii) Soit $X\subseteq \mathbb N$ un sous-ensemble non vide. Si $0\notin X$, soient $Y=\{i\in\mathbb N : \forall x\in X,\ i<x\}$, et $k$ le plus grand élément de $Y$ par (ii). Démontrer que $k+1$ est le plus petit élément de $X$, c’est-à-dire que $k+1\in X$, et que pour tout $x\in X$, on a $k+1\leq x$. En déduire que toute partie non vide de $\mathbb N$ possède un plus petit élément.

2. Caractérisation extrinsèque de l’infinité mathématique

Rappelons qu’une caractérisation d’une notion est une condition équivalente à cette notion, qui peut donc être choisie comme définition alternative. Il est possible de donner ici une première caractérisation des ensembles infinis, plus intéressante ou au moins plus suggestive, que la définition initiale, en utilisant l’ensemble $\mathbb N$. Nous parlons ici de caractérisation « extrinsèque », car nous la rapportons à un ensemble particulier « extérieur » à l’ensemble dont nous voulons caractériser l’infinité.