mardi 23 décembre 2008

A l'infini et au-delà!

C'est assez facile de comparer les grandeurs des objets physiques autour de nous: un bâton est plus grand qu'un autre, si la longueur du plus petit tient dans la longueur du plus grand. Le tout est plus grand que ses parties, nous a appris Euclide, et on le vérifie avec un sac de billes rouges et bleues: il contient plus de billes que lorsqu'on lui retire toutes ses billes rouges. Evident non?




Pour les ensembles infinis, le tout est aussi grand qu'une de ses parties

Ce qui est vrai pour les sac de billes ne l'est pas pour les collections infinies d'objets. Comparons le sac des nombres entiers (0,1,2,3 etc) avec celui de tous les nombres entiers pairs (0,2,4,6 etc). Si l'on applique le raisonnement ci-dessus, l'ensemble des nombres entiers contient les nombres pairs, ergo il est plus grand... En fait les choses ne sont pas aussi simples quand on traite des ensembles infinis: pour savoir si deux ensembles infinis ont la même "taille", on regarde si on peut faire correspondre chaque élément de l'un avec un et un seul élément de l'autre (ce type de correspondance terme à terme s'appelle une bijection). Or on peut parfaitement faire correspondre chaque nombre entier avec un nombre pair et vice versa: il suffit d'associer chaque nombre entier n avec son double 2n (qui est pair). Donc il y a autant de nombres pairs que de nombres entiers! Bienvenue dans les mystères de l'infini où le tout peut être exactement aussi grand qu'une de ses parties. Cette drôle de propriété signe d'ailleurs l'infinitude de l'ensemble (enfin, là je spécule...).

En raisonnant de la sorte on montre que l'ensemble des entiers (N de son petit nom: 0,1,2,3...) est de la même "taille" que tous ses sous-ensembles infinis: il y autant d'entiers que de nombres pairs (on l'a vu), de nombres premiers (divisibles seulement par 1 et par eux-mêmes comme 1,3,5,7,11,13,17,19...), de carrés parfaits (1, 4, 9, 16...). L'hôtel de Hilbert qui possèderait une infinité de chambres toutes occupées, pourrait toujours accueillir des hordes de bus contenant chacun une infinité dénombrable de clients. Il suffirait de transférer chaque occupant d'une chambre n vers une autre chambre (de numéro 2n par exemple si l'on veut doubler la capacité de l'hôtel) et de loger les nouveaux arrivants dans l'infinité de chambres ainsi libérées.

Et de la même manière, N a la même taille que des ensembles plus grands, par exemple l'ensemble Z des "entiers relatifs" (les nombres entiers positifs et négatifs:-5,-4,-3,-2,-1,0,1,2,3 etc.) [Lecteurs non matheux: sautez les paragraphes en italiques comme ci-dessous, pour vous éviter les maux de tête...]
Pour le montrer il suffit d'attribuer à chaque entier relatif n l'entier 2n si n est positif et -(2n+1) si n est négatif: on a ainsi une correspondance terme à terme entre N et Z: à 0,1,2,3 correspondent 0,2,4,6 et à -1,-2,-3 correspondent 1,3,5...

Rationnels et irrationnels: si proches et pourtant si différents...
Plus étonnant encore, il y a autant de fractions rationnelles (rapport entre deux nombres entiers relatifs) que d'entiers naturels!
Pour trouver la correspondance entre entiers et fractions, prenez n'importe quel entier n et divisez le par 2 autant de fois que vous pouvez. Quand finalement (au bout de p divisions), vous obtenez un reste impair (noté 2q+1), vous pouvez écrire n=2p x (2q+1). Et voilà, vous venez de trouver comment associer à tout entier n deux entiers p et q de manière unique. On étend facilement cette méthode aux fractions relatives (positives et négatives) pour montrer qu'il y a autant d'entiers que de fractions.

Ces ensembles qui ont la même taille que N sont dits "dénombrables". Le terme est un peu trompeur car il laisse imaginer qu'on peut toujours les compter sur un intervalle donné. Or quelque soit l'intervalle que vous choisissez (s'il ne se réduit pas à un point) vous y trouvez une infinité de fractions: on dit que l'ensemble des fractions noté \mathbb{Q}, est "dense" dans l'ensemble des nombres réels R.
Prenez un intervalle [a,b], de dimension b-a=ε très petit. Vous pouvez trouver un entier n tel que n>1/ε, puis le plus grand entier p tel que p/n≤a On peut écrire a < (p+1)/n <>

Alors tous les ensembles sont-ils dénombrables? Eh non, ce serait trop simple! L'ensemble des nombres réels R (tous les nombres, y compris les irrationnels qui comme √2 ne peuvent pas s'écrire comme des fractions). Bien qu'étant de la même taille que l'intervalle ]0,1[, R n'est pas dénombrable, ainsi que l'a découvert Cantor, l'inventeur de la théorie des ensembles.
Pour prouver que R est de même taille que ]0,1[, il suffit de considérer la fonction qui associe à tout réel x, f(x)=1/2 [1+x/(1+|x|)]
Cette fonction "projette" tous les nombres réels entre O et 1...


On prouve ensuite que ]0,1[ n'est pas dénombrable grâce à la célèbre diagonale de Cantor, en raisonnant par l'absurde.
Supposons que ]0,1[ soit dénombrable: cela signifie qu'à tout réel x on peut associer un unique nombre décimal un.
Ecrivons les un les uns en dessous des autres en écriture décimale:

uij est la jième décimale du nombre rationnel ui.

Considérons la diagonale des décimales uii (la fameuse diagonale qui a donné le nom à ce théorème) et imaginons le nombre x=0,x1x2x3.... dont chaque décimale vaut xi = 1 si uii≠1 et xi = 2 si uii=1.
x diffère de u1 au niveau de la première décimale (x1≠ u11), x diffère de u2 au niveau de la seconde (x2≠u22) et de manière générale x diffère de un au niveau de la nième décimale (car xn≠unn) .
x est bien un nombre décimal compris entre 0 et 1 et pourtant on ne peut le faire correspondre avec aucun des nombres de la collection des (un), ce qui est contradictoire avec l'hypothèse que ]0,1[ est dénombrable...
La taille des infinis
Récapitulons: \mathbb{Q} est à la fois dense dans R ( les deux ensembles sont inextricables en quelque sorte l'un de l'autre) et pourtant l'un est dénombrable et l'autre pas. La taille de R est appelée 1 (c'est la lettre hébraïque Alef, les mathématiciens adorent les écritures anciennes), celle de \mathbb{Q} et de tous les ensembles dénombrables est appelée 0.
Pour comparer la taille de \mathbb{Q} et celle de R, on peut comparer leur correspondance respective sur ]0,1[.
R correspond exactement à ]0,1[, sa mesure vaut 1.
Pour mesurer \mathbb{Q}, on représente chaque fraction par un point un dans l'intervalle ]0,1[. Définissons autour de ce point un petit intervalle, de longueur décroissante:
Pour u1, on choisit un intervalle de taille 0,1
pour u2, l'intervalle 0,01
pour u3, l'intervalle 0,001
etc.
La taille de \mathbb{Q} sera au plus égale à la somme des intervalles de tous les un, donc vaut au plus 0,111111 etc. On aurait pu commencer par un intervalle de 0,001 pour u1 et la taille de \mathbb{Q} aurait été majorée par 0,001111: la mesure de \mathbb{Q} peut donc être rendue aussi petite que l'on veut et vaut donc 0!


L'une des grandes questions encore mal résolue est de savoir si R est le plus petit ensemble non dénombrable ou s'il existe d'autres ensembles de taille intermédiaire entre R et N. Autrement dit existe-t-il des infinis de taille 0,5? Cantor émit l'hypothèse que non mais l'on a démontré en 1963 que cette question était en fait indécidable, à moins d'admettre même en admettant un axiome supplémentaire (l'axiome du choix) pour que ce type d'infini existe. Indécidable, c'est à dire qu'on ne pourra démontrer ni que c'est vrai ni que c'est faux: c'est bizarre mais c'est comme ça!
D'un autre côté existe-t-il des infinis plus grands que R? Oui bien sûr, plein!!! L'ensemble des parties de R, ou plus simplement l'ensemble des fonctions de R dans R.
Considérons l'ensemble F des fonctions f : [0,1] {0,1} qui ne prennent comme valeurs que 0 et 1. Supposons qu'il y ait autant de telles fonctions f que de réels dans ]0,1[. A chaque réel x de ]0,1[, on peut faire correspondre une unique fonction fx de F et vice versa. On procède comme pour la diagonale de Cantor: construisons la fonction g telle que : g(x) = 1 si fx(x) = 0 et g(x) = 0 si fx(x) = 1. g est bien une fonction de F prenant comme valeurs 0 et 1 et pourtant g ne coincide avec aucune des fonctions fx puisque pour chaque valeur x, fx(x)≠g(x) ce qui est contradictoire avec l'hypothèse d'une bijection entre F et ]0,1[... Le nombre de fonctions de F est donc supérieur au nombre de réels contenus dans ]0,1[, donc au nombre de réels de R.


Par contre, n'allez pas croire que, R étant semblable à une droite, une surface infinie (RxR) ou même l'espace infini (R3) soient de tailles différentes de R, pas du tout! De la même manière que l'on a montré ci-dessus l'équivalence entre N et \mathbb{Q} (qui s'écrit ZxN), on peut construire des courbes infiniment tarabiscotées (qui ressemblent d'ailleurs furieusement à des fractales) correpondant à une surface ou à un volume. Je vous laisse découvrir ça par exemple...


De manière générale on peut prouver qu'il n'existe pas de taille limite des infinis, car un ensemble est toujours plus "petit" que l'ensemble de ses parties: c'est LE théorème de Cantor, qui a d'ailleurs démontré que l'ensemble des parties de N est en bijection avec R.
Prenons un ensemble E d'objets x et appelons (E) l'ensemble des parties de E. Supposons qu'il existe une bijection entre E et (E): à chaque élément x de E, on peut faire correspondre un sous-ensemble de E qu'on appellera Px. Vous êtes habitués maintenant aux constructions bizarroïdes: ici on va définir le sous-ensemble P de E constitué des éléments x qui n'appartiennent pas à leur correspondant Px. Comme il existe une bijection entre E et (E) il existe un élément y correspondant à P et P=Py. y appartient-il à P? Non car dans ce cas y appartiendrait à son correspondant Pyy, y appartient à P par construction même de P. Si vous avez perdu le fil, relisez ces deux phrases et laissez mariner un petit moment. On aboutit à une contradiction qui prouve qu'il n'existe pas de bijection entre un ensemble et ses parties.

Au fait, d'où vient ce drôle de symbole, désignant l'infini par un 8 couché? Même sur ce point, la réponse n'est pas tranchée: est-ce le descendant du CIƆ romain, désignant le nombre "mille" avant que l'on n'utilise la lettre M? Est-ce l'hériter de l'oméga minuscule ω, dernière lettre de l'alphabet grec? Ou s'agit-il de la représentation graphique du "serpent-infini" du dieu Vishnu, enroulé sur lui-même comme un huit renversé?

Sources:
Le site chronomath, très complet de Serge Mehl