§ 6. Ensembles infinis

1. L’ensemble des entiers naturels

En particulier, un cardinal est infini s’il n’est pas un entier.

Remarquons que la relation « il existe un ensemble infini » entraîne que la relation « x est un entier » est collectivisante (II, p. 3); en effet, si α est un cardinal infini, et n un entier quelconque, on ne peut avoir α ≤ n (III, p. 31, prop. 2); on a donc n < α pour tout entier n, ce qui prouve que l’ensemble des entiers < α (III, p. 25, Remarque) contient tous les entiers. Inversement, si la relation « x est un entier » est collectivisante, l’ensemble des entiers E est un ensemble infini: en effet, pour tout entier n, l’intervalle {0, n} est une partie à n + 1 éléments de E (III, p. 38, prop. 5), donc Card (E) ≥ n + 1 > n; mais dire que Card (E) ≠ n pour tout entier n signifie que E est infini.

Introduisons l’axiome suivant:

A4 (« axiome de l’infini »). Il existe un ensemble infini.

On ne sait pas déduire cet axiome des axiomes et schémas d’axiomes introduits jusqu’ici, et, bien que la question ne soit pas définitivement tranchée, il est à présumer qu’il en est indépendant.

Les remarques qui précèdent prouvent alors le théorème suivant:

Soit P\{n\} une relation; notons I l’ensemble des entiers n tels que P\{n\} soit vraie, qui est donc une partie de N; une suite $(x_n)_{n \in I}$ se note souvent $(x_n)_{P\{n\}}$; on dit que $x_n$ est le terme d’indice n de la suite. Une suite dont l’ensemble d’indices est l’ensemble des entiers $n \geq k$ se note souvent $(x_n)_{k \leq n}$ ou $(x_n)_{n \geq k}$, ou même $(x_n)$ lorsque $k = 0$ ou $k = 1$. Dans les mêmes conditions, pour désigner, par exemple, le produit de la suite d’ensembles $(X_n)_{n \in I}$, on utilise les notations $\prod_{P\{n\}} X_n$ et $\prod_{n = k}^\infty X_n$; notations analogues pour la réunion, l’intersection, la somme cardinale et le produit cardinal.

Toute sous-famille d’une suite est une suite, qu’on dit extraite de la suite considérée.

On dit que deux suites $(x_n)_{n \in I}, (y_n)_{n \in I}$ ayant même ensemble d’indices ne diffèrent que par l’ordre des termes s’il existe une permutation $f$ de l’ensemble d’indices $I$ telle que l’on ait $x_{f(n)} = y_n$ pour tout $n \in I$.

On appelle suite multiple une famille dont l’ensemble d’indices est une partie d’un produit $\mathbf{N}^p$ ($p$ entier) (on dit encore « suite $p$-uple », « suite double » pour $p = 2$, « suite triple » pour $p = 3$, etc.).

Soient $I$ un ensemble équipotent à $\mathbf{N}$, $f$ une bijection de $\mathbf{N}$ sur $I$. Pour toute famille $(x_i)_{i \in I}$ ayant $I$ pour ensemble d’indices, la suite $n \mapsto x_{f(n)}$ est dite obtenue en rangeant dans l’ordre défini par $f$ la famille $(x_i)_{i \in I}$. Les suites correspondant ainsi à deux bijections distinctes de $\mathbf{N}$ sur $I$ ne diffèrent que par l’ordre des termes. Pour une famille finie ayant un ensemble d’indices $I$ à $n$ éléments, on définit de même une suite finie ayant pour ensemble d’indices $[1, n]$ ou $[0, n - 1]$ en rangeant la famille dans l’ordre défini par une bijection de $I$ sur l’un des intervalles précédents.

2. Définition d’applications par récurrence

L’ensemble $\mathbf{N}$ étant bien ordonné, on peut lui appliquer le critère C60 (III, p. 18), qui s’écrit ici (avec les mêmes notations):

C62. Soient $u$ une lettre, $T\{u\}$ un terme. Il existe un ensemble $U$ et une application $f$ de $\mathbf{N}$ sur $U$ tels que, pour tout entier $n$, on ait $f(n) = T\{f^{(n)}\}$, en désignant par $f^{(n)}$ l’application de $[0, n[$ sur $f([0, n[)$ qui coïncide avec $f$ dans $[0, n[$. L’ensemble $U$ et l’application $f$ sont alors déterminés de façon unique par cette condition.

Nous allons en déduire le critère suivant:

C63. Soient $S\{v\}$ et $a$ deux termes. Il existe un ensemble $V$ et une application $f$ de $\mathbf{N}$ sur $V$ tels que l’on ait $f(0) = a$ et, pour tout entier $n \geqslant 1$, $f(n) = S\{f(n - 1)\}$. En outre, l’ensemble $V$ et l’application $f$ sont déterminés de façon unique par ces conditions.

Pour déduire C63 de C62,$^1$ convenons, pour toute lettre $u$, de poser

Lorsque $u$ est une application d’une partie de $\mathbf{N}$ dans un ensemble, $D(u)$ n’est donc pas autre chose que l’ensemble de définition de $u$ (II, p. 10). Soit $M(u)$ la borne supérieure de $D(u)$ dans $\mathbf{N}.$^2 Soit $\varphi$ l’application vide (ayant $\varnothing$ comme ensemble de départ et ensemble d’arrivée, autrement dit (II, p. 14) le triplet $(\varnothing, \varnothing, \varnothing)$); considérons la relation

que nous désignerons par $R\{y, u\}$; enfin, soit $T\{u\}$ le terme $\tau_y(R\{y, u\})$. Appliquons

$1$ On pourrait aussi démontrer C63 directement, par un raisonnement analogue à la démonstration de C60 (III, p. 18). $2$ La définition de la borne supérieure (III, p. 10) peut être formulée de telle sorte qu’elle garde un sens même pour un ensemble non majoré (elle désigne un terme du langage formalisé de la forme $\tau_x(R\{x\}),$ que le lecteur explicitera sans peine).

le critère C62 au terme T

Exemples

1) Supposons que $a$ soit un élément d'un ensemble $E$ et $S[u]$ le terme $g(u)$, où $g$ est une application de $E$ dans lui-même.$^1$ Alors, on voit aussitôt par récurrence sur $n$ que, pour tout $n \in \mathbf{N}$, on a $f(n) \in E$; $f$ est par suite une application de $\mathbf{N}$ dans $E$ telle que $f(0) = a$ et $f(n + 1) = g(f(n))$ pour tout entier $n$.

De même, soit $h$ une application de $\mathbf{N} \times E$ dans $E$, et soit $\psi$ l'application de $\mathbf{N} \times E$ dans lui-même définie par $\psi(n, x) = (n + 1, h(n, x))$. D'après ce qui précède, il existe une application $g = (\theta, f)$ de $\mathbf{N}$ dans $\mathbf{N} \times E$ et une seule telle que $g(0) = (0, a)$ et $g(n + 1) = \psi(g(n))$ pour tout $n$; on en conclut l'existence et l'unicité d'une application $f$ de $\mathbf{N}$ dans $E$ telle que $f(0) = a$ et $f(n + 1) = h(n, f(n))$ pour tout entier $n$.

2) Soient $X$ un ensemble, $E$ l'ensemble des applications de $X$ dans lui-même; soient $e$ l'application identique de $X$ dans lui-même, et $f$ un élément quelconque de $E$. Prenons pour $S[u]$ le terme $f \circ u$.$^2$ On voit, par application de C63, qu'il existe une application de $\mathbf{N}$ dans $E$ et une seule, notée $n \mapsto f^n$, telle que $f^0 = e$ et $f^{n+1} = f \circ f^n$. On dit que $f^n$ est la n-ème itérée de l'application $f$.

3) Si on prend pour $S[u]$ le terme $\mathfrak{P}(u)$, et pour $a$ un ensemble $E$, on voit de même qu'il existe une application, notée $n \mapsto \mathfrak{P}^n(E)$ de $\mathbf{N}$ dans un ensemble $V(E)$, telle que $\mathfrak{P}^0(E) = E$, $\mathfrak{P}^1(E) = \mathfrak{P}(E)$ et $\mathfrak{P}^{n+1}(E) = \mathfrak{P}(\mathfrak{P}^n(E))$ pour tout entier $n$.

3. Calcul sur les cardinaux infinis

4. Ensembles dénombrables

Un ensemble qui a la puissance du continu n'est pas dénombrable (III, p. 30, th. 2).

\* Le nom de « puissance du continu » provient de ce que l'ensemble des nombres réels est équipotent à $\mathfrak{P}(\mathbf{N})$ (TG, IV, § 8).* L'hypothèse du continu est l'assertion que tout ensemble non dénombrable contient une partie ayant la puissance du continu; l'hypothèse du continuum généralisée est l'assertion que, pour tout cardinal infini $\alpha$, tout cardinal $> \alpha$ est $\geq 2^\alpha$. Un théorème de métamathématique (Gödel–P.Cohen) affirme que ni ces assertions, ni leurs négations, ne peuvent être démontrées dans la théorie des ensembles telle qu'elle a été définie dans cet ouvrage (II, p. 1).

5. Suites stationnaires

Exercices

See the exercises for § 6.