Introduction

Parmi les innombrables curiosités mathématiques, je souhaite parler ici de la notion d’ infini. Sans-doute avez vous déjà entendu parler d’ ensembles infinis, et peut-être même avez-vous déjà entendu l’ expression « rien n’ est plus grand que l’ infini ». Et bien c’ est faux: il existe des infinis plus grands que d’ autres! Il existe même une infinité d’ infinis de tailles différentes! C’ est ce que je voudrais tenter de présenter ici, ainsi qu’ une conséquence dans le domaine de l’ informatique, et ce, de manière accessible. Mais rappelons d’ abord quelques notions et un minimum de formalisme après avoir vu quelques paradoxes sur les ensembles et l’ infini.

Quelques paradoxes sur les ensembles

1. L’antinomie de B. Russell

B. Russell classe les ensembles en deux sortes: ceux qui ne se contiennent pas eux-même comme élément et ceux qui se contiennent eux-mêmes. On dit qu’un ensemble est « normal » si, et seulement si, il ne se contient pas lui-même comme élément. Il est dit « non normal » dans le cas contraire.

Exemple d’ensemble normal: l’ensemble des mathématiciens, car cet ensemble n’est évidemment pas lui-même un mathématicien.
Exemple d’ensemble non normal: l’ensemble de toutes les choses pensables. Cet ensemble est lui-même une chose pensable, donc un élément de lui-même.

Appelons N l’ensemble de tous les ensembles normaux. La question est de savoir si N lui-même est un ensemble normal. Si N est normal, c’est un élément de lui-même (puisque, par définition, N contient tous les ensembles normaux); mais, dans ce cas, N est non normal, puisque, par définition, un ensemble qui se contient lui-même comme élément est non normal. D’un autre coté, si N est non normal, c’est un élément de lui-même (par définition du non normal), mais, dans ce cas, N est normal, puisque par définition, les éléments de N sont les ensembles normaux. Cela conduit donc à la contradiction que « N est normal » est à la fois vrai et faux.

2. L’ urne aux boules

On a d’ un coté, une urne infiniment grande et d’ un autre, un nombre infini de boules numérotées de 1 en 1 à partir de 1. A chaque étape numéro n, on effectue les 2 opérations suivantes consécutivement: on prend les boules de n à n+9 qu’ on place dans l’ urne, puis on enlève de l’ urne la boule numéro n. A la première étape, il y a donc dans l’ urne les boules de 2 à 10. A la seconde étape, il y a les boules 3 à 20, etc. La question est de savoir combien de boules contient l’ urne après un nombre infini d’ étapes. La démonstration formelle conduit à la conclusion que l’ urne est vide, ce qui est paradoxal, puisqu’ à chaque étape on met 10 boules et on en enlève une, ce qui revient à mettre 9 boules…

3. L’ hôtel de Hilbert

C’ est sans doute l’ un des paradoxes les plus connus sur les ensembles. Je me contente donc de le citer, mais voici un lien qui en parle très bien: https://fr.wikipedia.org/wiki/H%C3%B4tel_de_Hilbert.

Ensembles

Nombre de paradoxes proviennent de définitions imprécises ou pas assez rigoureuses. Ces paradoxes et les questions qui en découlent, ont historiquement une part de responsabilité de la nécessité de mettre au point une véritable théorie axiomatique des ensembles, vraiment rigoureuse. Ce n’est pas l’objectif de cet article, néanmoins, nous aurons besoin de quelques définitions.

De manière simple, un ensemble est un tas de trucs. Par exemple, l’ ensemble des lettres de l’ alphabet, l’ ensemble des mots du dictionnaire, l’ ensemble des brins d’ herbe de votre jardin, l’ ensemble des parties d’ échec possibles, etc. Les trucs contenus dans un ensemble portent le nom d’ éléments. Pour indiquer qu’ un élément $e$ appartient à un ensemble $E$ , on écrit $e \in E$ , inversement, lorsqu’ un élément $e$ n’ appartient pas à un ensemble $E$ , on l’ écrit $e \notin E$ . Le nombre d’ éléments contenu dans un ensemble $E$ s’ appelle le cardinal de l’ ensemble et se note $|E|$ . Ce nombre peut être un entier positif dans le cas d’ un ensemble contenant un nombre fini d’ éléments (ensemble fini), ou infini dans le cas d’ un ensemble contenant un nombre infini d’ éléments (ensemble infini). Un sous-ensemble $s$ d’ un ensemble $E$ désigne simplement une partie de $E$ , on note $s \subset E$ , qui se lit: « $s$ est inclus dans $E$ « .

Exemple: considérons l’ ensemble de toutes les données que l’ on peut stocker sur un CD Audio. Les données stockées sur un CD ne sont qu’ une suite de bits (chiffres binaires valant 0 ou 1), c’ est-à-dire un nombre binaire. Si on considère un CD de 700 Mo, celui-ci permet de stocker un total de 700 * 1024 * 1024 * 8 bits (soit 5 872 025 600 bits). Chaque bit ne pouvant avoir que 2 valeurs possibles, le cardinal de l’ ensemble de tous les CD différents possibles vaut donc $2^{5 872 025 600}$ , ce qui est un nombre entier certes grand, mais fini. Même raisonnement pour un DVD, Blu-ray, ou tout autre support de stockage binaire et fini, seules les quantités changent.

Certains ensembles étant très utilisés, il portent un nom qui permet de les identifier sans ambiguïté. Voici les noms des principaux ensembles infinis rencontrés jusqu’ au lycée:

$\mathbb{N}$ : l’ ensemble des nombres naturels (ce sont les entiers positifs) regroupe les nombres entiers à partir de 0: 0, 1, 2, 3, …, jusqu’ à l’ infini $+\infty$ .
$\mathbb{Z}$ : l’ ensemble des entiers relatifs regroupe les nombres de $-\infty$ à 0 et de 0 à $+\infty$ : il est constitué, en quelque sorte, de 2 ensembles $\mathbb{N}$ dont l’ un contient un moins devant tous ses éléments, « soudés ensembles » sur l’ élément 0.
$\mathbb{Q}$ : l’ ensemble des nombres rationnels regroupe les nombres que l’ on peut écrire sous la forme d’ un quotient entre 2 nombres relatifs: $a/b$ avec $a$ et $b$ éléments de $\mathbb{Z}$ .
$\mathbb{R}$ : l’ ensemble des nombres réels qui regroupe les nombres décimaux (nombres comme ceux de $\mathbb{Z}$ mais avec en plus une partie après la virgule).
$\mathbb{C}$ : l’ ensemble des nombres complexes regroupe l’ infinité des nombres qui s’ écrivent sous la forme de la somme de deux nombres réels, dont l’ un se nomme partie réelle, et l’ autre, partie imaginaire, elle-même précédée de la lettre i: $a+ib$ avec $a$ et $b$ éléments de $\mathbb{R}$ .

Un fait important est que tous ces ensembles forment une hiérarchie dans le sens où les plus hauts dans la liste constituent une partie des suivants, c’ est-à-dire que l’ on a $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$ . Autrement dit, tous les éléments de $\mathbb{N}$ sont aussi dans $\mathbb{Z}$ , dont tous les éléments sont aussi dans $\mathbb{Q}$ , etc. Comme ce sont tous des ensembles infinis on voit que se profile la notion de taille: comment par exemple $\mathbb{Z}$ pourrait contenir $\mathbb{N}$ de chaque coté de zéro sans être deux fois plus grand que lui?

Bijections

Exemple de bijection entre 2 ensembles finis E et F.

De manière informelle, une bijection entre 2 ensembles est une relation particulière entre les éléments de ces deux ensembles: tous les éléments de l’ un sont en correspondance avec tous les éléments de l’ autre, de sorte qu’ aucun élément ne se trouve sans correspondant et qu’ aucun élément n’ aie plus d’ un correspondant. On voit bien que si une bijection existe entre deux ensembles, c’ est que ceux-ci doivent avoir le même nombre d’ éléments.

Une bijection peut porter un nom et s’ exprimer simplement par une phrase ou par une expression mathématique qu’ on appelle une fonction. Par exemple une bijection $f$ entre deux ensembles $E$ et $F$ fait correspondre à tout élément $x$ de l’ ensemble $E$ , son image $y$ dans $F$ , que l’on appelle alors $y=f(x)$ et qui se calcule. La bijection inverse existe forcément et se note $f^{-1}$ : à partir de $y$ un élément de $F$ on obtient $x$ , son correspondant dans $E$ : $x=f^{-1}(y)$ .

Exemple: considérons la bijection $f$ , qui à chaque élément $x$ de $E$ lui ajoute 1 pour obtenir son correspondant dans $F$ : on aura $f(x)=x+1$ (pour tout $x \in E$ ). Réciproquement, à partir de tout élément $y$ de $F$ , pour obtenir son correspondant dans $E$ , il faut lui ôter 1: $f^{-1}(y)=y-1$ (pour tout $y \in F$ ).

Exemple de bijection entre deux ensembles infinis.

Qu’ est-ce-qu’ un ensemble dénombrable?

Les infinis ont longtemps posé problème en mathématiques avant que G. Cantor ne s’ y intéresse. En 1874, il pose les premières briques de la théorie des ensembles. Cette théorie définit notamment, de manière rigoureuse, les notions d’ ensembles et d’ infinis. Elle permet, entre autre, de résoudre de nombreux paradoxes dont ces notions étaient à l’ origine, en partie à cause de leur imprécision. Elle introduit notamment la définition suivante afin de pouvoir comparer le nombre d’ éléments entre deux ensembles.

Un ensemble est dénombrable s’ il peut être mis en bijection avec $\mathbb{N}$ . Une façon simple de le dire est qu’ un ensemble est dénombrable si on peut numéroter ses éléments, ou encore, si on peut coder avec un nombre entier unique chacun de ses éléments.

On note $\aleph_0$ le cardinal de l’ ensemble $\mathbb{N}$ , il correspond au premier niveau d’ infini, l’ infini dénombrable (G. Cantor était de culture juive, ce qui explique ce choix de la première lettre de l’ alphabet hébraïque $\aleph$ « aleph »).

Une conséquence de tout ce que nous avons vu jusqu’ ici est que deux ensembles $E$ et $F$ dénombrables vérifient $|E|=|F|=|\mathbb{N}|=\aleph_0$ , ils ont donc le même nombre infini d’éléments.

Exemples d’ ensembles dénombrables

1. L’ ensemble des nombres pairs

L’ ensemble $2\mathbb{N}$ des nombres pairs est dénombrable. On pourrait penser à tort que $|2\mathbb{N}|$ est deux fois plus petit que $|\mathbb{N}|$ , et bien il n’ en est rien! En effet, il suffit de considérer la bijection $f$ qui consiste à multiplier par 2 chaque élément de $\mathbb{N}$ pour tomber sur son correspondant pair dans $2\mathbb{N}$ : $y=f(x)=2x$ . Réciproquement, il suffit de diviser par 2 n’importe quel élément de $2\mathbb{N}$ pour tomber sur son correspondant dans $\mathbb{N}$ : $x=f^{-1}(y)=y/2$ . On a bien le même nombre infini d’éléments entre les ensembles $\mathbb{N}$ et $2\mathbb{N}$ , qui ont donc la même taille: $|\mathbb{N}|=|2\mathbb{N}|=\aleph_0$ .

Exemple de bijection entre N et 2N.

2. L’ ensemble des nombres entiers relatifs

L’ ensemble $\mathbb{Z}$ des entiers relatifs est dénombrable. Là aussi, on pourrait se fier aux apparences et donc croire qu’ il est deux fois plus grand que $\mathbb{N}$ , mais c’ est faux! Pour s’ en convaincre, il suffit de considérer la bijection qui associe les nombres de $\mathbb{N}$ à ceux de $\mathbb{Z}$ ainsi: $0: 0, 1: 1, 2: -1, 3: 2, 4: -2, 5: 3, 6: -3, \cdots$ . Pour caractériser cette bijection, en notant $x$ élement de $\mathbb{N}$ et $y$ élément de $\mathbb{Z}$ , on distingue 2 cas:

si $x$ est pair, on obtient $y$ par $y=-x/2$
si $x$ est impair, on obtient $y$ par $y=(x+1)/2$ .

Pour la réciproque:

si $y$ est positif, on obtient $x$ par $x = 2y-1$
si $y$ est négatif ou nul, on obtient $x$ par $x = -2y$ .

Ici encore les ensembles ont donc le même cardinal: $|\mathbb{N}|=|\mathbb{Z}|=\aleph_0$ .

Exemple de bijection entre N et Z.

3. Langage engendré par un alphabet

Soit $A=\{a, b, c\}$ un alphabet fini (un ensemble fini d’ éléments qu’ on nomme des lettres). L’ ensemble de tous les mots (un mot est une suite finie de lettres) formables avec cet alphabet (que l’ on note $A^*$ et que l’ on appelle langage engendré par $A$ , ou encore $\mathcal{L}(A)$ ) est dénombrable. Il suffit de numéroter les mots, par exemple, ainsi: $0: \epsilon, 1: a, 2: b, 3: c, 4: aa, 5: ab, 6: ac, 7: ba, 8: bb, 9: bc, \cdots$ . Avec $\epsilon$ représentant le mot vide. Comme notre méthode de numérotation n’ oublie aucun mot possible, il s’ agit bien d’ une bijection. Donc l’ ensemble de tous les mots formables avec l’ alphabet $A$ est dénombrable. Grâce à un théorème, ce résultat se généralise à tout alphabet fini. Donc, tout langage $\mathcal{L}(A)$ engendré par un alphabet fini $A$ est dénombrable, il s’ agit d’ un résultat fondamental en théorie des langages (présenté ici sans démonstration).

4. L’ ensemble des programmes informatiques

L’ ensemble $\mathcal{P}$ des programmes exécutable par une machine binaire, comme un ordinateur, est dénombrable. C’ est exactement le même cas que ci-dessus avec $A=\{0, 1\}$ , et le fait que $\mathcal{P}\subset \mathcal{L}(A)$ (l’ ensemble de tous les programmes binaires n’ est qu’ un sous-ensemble de tous les mots possiblement formables avec $\mathcal{L}(A)$ ). En effet, tous les mots engendrés par $\mathcal{L}(A)$ ne sont pas des programmes valides. Ce résultat (présenté sans démonstration ici) se généralise à tout langage de programmation et à tout système de calcul formel, mais cela dépasse largement le cadre fixé ici (cf. l’ isomorphisme de Curry Howard ainsi que la Thèse de Church).

Qu’ est-ce-qu’ un ensemble non-dénombrable?

Un ensemble $E$ est non dénombrable (ou indénombrable) s’ il n’ existe aucune bijection entre $E$ et $\mathbb{N}$ . Pour montrer qu’ un ensemble est non dénombrable, G. Cantor a introduit l’ argument de la diagonalisation permettant d’ élaborer une preuve, souvent par l’ absurde (on l’ appelle souvent la diagonale de Cantor). C’ est ainsi qu’ il démontra que l’ ensemble $\mathbb{R}$ des nombres réels est non-dénombrable (cf. la démonstration sur wikipedia que je reprend ci-dessous de manière informelle).

On considère le sous-ensemble $D=[0,1[$ de $\mathbb{R}$ (les nombres compris entre 0 et 1 exclus) à partir duquel on va construire un nombre qui n’ appartient pas à $D$ . Les éléments de $D$ sont donc des nombres décimaux dont la partie entière vaut 0 et la partie décimale peut contenir un nombre infini de chiffres. On construit un tableau T contenant en ligne chaque partie décimale des éléments de $D$ et en colonne les chiffres de cette partie décimale. Ainsi, T(n, m) désigne la m-ième décimale du nombre se trouvant en ligne n. Chaque élément de $D$ , par exemple 0, 4895397 se trouve quelque part dans le tableau T, disons en ligne k, ainsi T(k, 1) vaut 4, T(k, 2) vaut 8, T(k, 3) vaut 9, etc.:

T	1	2	3	4	5	…	m	…
1
2
…
k	4	8	9	5	3	9	7	…
…
n
…

Maintenant, on va considérer le nombre x=0,… construit en respectant la règle suivante: si T(n, n) vaut 0, alors la n-ième décimale de x vaut 1, si T(n, n) est différent de 0, alors la n-ième décimale de x vaut 2.

Notre nombre x appartient bien à $D$ , puisqu’ il est compris entre 0 et 1. Mais il n’ est dans aucune ligne du tableau, car sa partie décimale n’ est présente sur aucune ligne: il ne peut être en ligne 1 puisque la première décimale de T(1,1) est différente de la première décimale de x, même chose pour la ligne 2, T(2,2) est différente de la seconde décimale de x, etc. Donc x n’ est pas dans le tableau, donc le tableau ne contient pas tous les éléments de $D$ , donc $D$ est suffisamment grand pour n’ être pas dénombrable, ce qui implique que $\mathbb{R}$ non plus, puisqu’ il contient $D$ .

Conclusion: le cardinal de $\mathbb{R}$ est très supérieur à celui de $\mathbb{N}$ . Ce nouvel infini, de second niveau est donc plus grand que $\aleph_0$ , on le nomme l’ infini indénombrable (ou infini continu) et on note son cardinal $\aleph_1$ . On dit que le cardinal de l’ ensemble $\mathbb{R}$ a la puissance du continu, et un résultat étonnant est que $\aleph_1=2^{\aleph_0}$ (cf. ci-dessous pour l’ explication).

Exemples d’ ensembles non-dénombrables

1. L’ ensemble de toutes les fonctions entières à un seul argument entier

Une fonction entière est une fonction qui donne un nombre entier à partir de ses arguments. Par exemple la fonction addition qui prend 2 arguments entiers x et y et qui donne leur somme, elle aussi, un nombre entier: addition(x, y) = x+y. La fonction addition possède deux arguments: les deux nombres entiers x et y, mais ici, on ne parle que des fonctions à un unique argument entier et qui retournent un nombre entier.

L’ ensemble $\mathcal{F}_1$ de toutes les fonctions à un seul argument entier est non dénombrable et l’ argument de la diagonalisation nous permet de voir pourquoi. Pour cela, imaginons la construction du tableau T d’ un nombre infini de lignes et de colonnes, avec en colonne les arguments entiers de 0 à $+\infty$ et en lignes les éléments de l’ ensemble $\mathcal{F}_1$ qui sont donc des fonctions à un seul argument entier que l’ on numérote en séquence:

$F_1$	0	1	2	…	$m$	…
$f_1$	$f_1(0)$	$f_1(1)$	$f_1(2)$	…	$f_1(m)$	…
$f_2$	$f_2(0)$	$f_2(1)$	$f_2(2)$	…	$f_2(m)$	…
…	…	…	…	…	…	…
$f_n$	$f_n(0)$	$f_n(1)$	$f_n(2)$	…	$f_n(m)$	…
…	…	…	…	…	…	…

Toutes les fonctions à un seul entier sont donc par construction dans ce tableau T. Par exemple, la case T(n, m) du tableau représente la fonction $f_n$ appliquée à l’ entier $m$ . Cette case possède une valeur entière qui ne nous intéresse pas, et qu’ on ne peut de toute façon pas déterminer. Maintenant, on va considérer une nouvelle fonction, toujours à un seul argument entier, que l’ on va appeler G et que l’ on va définir ainsi: G(x) = T(x, x)+1. La question est: où se trouve G dans notre tableau? La réponse est: nulle part… Cette fonction n’ appartenant pas au tableau sensé contenir toutes les fonctions à un seul argument entier, on en déduit que le tableau ne les contient pas toutes, donc l’ ensemble $\mathcal{F}_1$ est non dénombrable et a donc la taille de l’ infini continu.

2. L’ ensemble des fonctions entières à plus d’ un argument entier

Le résultat précédent se généralise à l’ ensemble des fonctions entières à 2 arguments entiers, à 3 arguments entiers, et même à une infinité dénombrable d’ arguments entiers. La démonstration, hors propos ici, tient au fait que l’ on peut ‘coder’ par un unique entier la liste des arguments entiers (un peu comme pour un alphabet comme vu ci-dessus). Donc l’ ensemble de toutes les fonctions entières est non-dénombrable et a la taille de l’ infini continu.

3. L’ ensemble des parties d’ un ensemble

Derrière ce nom barbare se cache l’ ensemble de toutes les combinaisons de sous-ensembles que l’ on peut former à partir d’ un ensemble $E$ , on le note généralement $\mathcal{P}(E)$ .

Si $E$ est fini, alors $\mathcal{P}(E)$ est fini et contient $2^{|E|}$ éléments (issu d’ un théorème dont la démonstration est hors de propos ici).

Par exemple, avec l’ ensemble $A=\{a, b, c\}$ , on peut former $2^{|A|}=8$ parties:

l’ ensemble vide: {} (que l’ on note aussi $\emptyset$ ).
l’ ensemble ne contenant que a: {a}
l’ ensemble ne contenant que b: {b}
l’ ensemble ne contenant que c: {c}
l’ ensemble contenant a et b: {a, b}
l’ ensemble contenant b et c: {b, c}
l’ ensemble contenant a et c: {a, c}
l’ ensemble contenant a, b et c: {a, b, c}

Si $E$ est infini dénombrable, alors le nombre de ses parties est égal à $2^{\aleph_0}$ , mais en revanche, $\mathcal{P}(E)$ n’ est pas dénombrable. Ce résultat fondamental en théorie de ensembles est issu du théorème de Cantor, qui utilise là-encore l’ argument de la diagonalisation. On retrouve le résultat présenté ci-dessus, mais cette fois-ci, on comprend bien d’ où sort l’ égalité $\aleph_1=2^{\aleph_0}$ .

4. L’ ensemble des fonctions réelles à un seul argument réél

On a déjà vu ci-dessus que $|\mathbb{N}| = \aleph_0$ et que $|\mathbb{R}|=2^{\aleph_0}=\aleph_1$ . Du coup, en voulant appliquer la même méthode qu’ au point 1 plus haut, on se heurterait au fait que le tableau T ne peut être construit puisque le nombre de colonnes est infini continu…

Et au-delà, la diagonale du fou?

Nous n’ irons guère plus loin ici, mais G. Cantor a démontré qu’ il existe des infinis encore plus grand que les deux que nous avons présenté ici. Il a même découvert qu’ il existe une infinité d’ infinis de cardinalités différentes. Ce résultat fondamental en théorie des ensembles est connu sous le nom de théorème de Cantor.

Il se serait également interrogé sur l’ existence ou non d’ infinis de tailles intermédiaire. Par exemple:

existe-t’ il un infini de cardinalité située entre $\aleph_0$ et $\aleph_1$ ?
est-ce-que le passage de $\aleph_x$ à $\aleph_y$ est continu ou bien se fait-il de manière discrète, c’est-à-dire par saut?
dans le dernier cas, de quelles valeurs sont les sauts?

Sa quête de réponses à ces questions l’ aurait, parait-il, sérieusement perturbé, voire rendu fou…

Une conséquence concrète

Quelque soit le langage de programmation choisi, basé sur un alphabet fini de symboles, l’ ensemble de tous les programmes que l’ on peut écrire avec ce langage est dénombrable. Donc l’ ensemble de tous les programmes informatiques pouvant être écrit avec n’ importe quel langage élaboré avec un alphabet fini est dénombrable.

De manière très simpliste, un programme informatique ne fait qu’ exécuter une ou un très grand nombre de fonctions mathématiques. Or, on a vu plus haut que l’ ensemble des fonctions n’ est pas dénombrable: il est de taille incommensurablement plus grande que celui des programmes.

Conclusion: il existe des fonctions qui ne peuvent être calculées par aucun programme informatique. Il existe donc des problèmes, qui une fois mis sous forme de fonctions mathématiques, ne pourront jamais être solubles par aucun programme informatique. Ce résultat est fondamental, et n’ a rien à voir avec une puissance de machine et/ou de langage de programmation: il pose les limites de l’ informatique et plus généralement de tout système de calcul formel, il est à la base de la théorie de la calculabilité (hors sujet ici).

Pour en savoir plus

Quelques liens sur wikipedia:

Vers l’ infini et au-delà!