V-5. Les cardinaux des ensembles infinis - Partie I
FOIRE AUX QUESTIONS DE fr.sci.maths CHAPITRE V: QUESTIONS FONDAMENTALES
V-5. Les cardinaux des ensembles infinis - Partie I
SUJET PRECEDENT - INDEX - SUJET SUIVANTa) Avertissement Le sujet est vaste et peut intéresser des gens de niveaux divers (à partir du lycée et bien au-delà). C'est pourquoi cet article est découpé en 2 parties. La première s'adresse au niveau pré-bac, la seconde est accessible à partir du DEUG, environ. Dans la première partie, l'accent est mis sur la "vulgarisation", parfois au détriment de la rigueur : pour éviter des complications techniques, certaines démonstrations sont "un peu fausses", tout en donnant l'idée principale de la méthode. Chaque fois que c'est le cas, c'est signalé, et on peut se reporter à la seconde partie pour trouver une démonstration (à priori) rigoureuse. La seconde partie complète la première, avec des outils plus abstraits et plus puissants. Elle s'efforce à la rigueur, mais elle peut comporter des erreurs ou imprécisions. Merci enfin à David Madore (David.Madore@ens.fr), spécialiste du sujet, d'avoir corrigé et complété une première mouture de cet article. Merci également à tous les lecteurs de fr.sci.maths qui m'ont indiqué des corrections diverses. Rappel : N : ensemble des entiers naturels = {0,1,2,3,...} Z : ensemble des entiers relatifs (signés) = {...,-1,0,1,...} Q : ensemble des nombres rationnels (fractions) R : ensemble des nombres réels C : ensemble des nombres complexes L'étoile signifie que l'ensemble est privé de 0 (N*={1,2,3,...}). Voici d'abord les résultats essentiels, qui seront suivis par quelques explications : _ N, Z, Q ont autant d'éléments _ R, C ont autant d'éléments _ Les 3 premiers ont moins d'éléments que les 2 derniers. La notion de cardinal étend la notion de nombre aux infinités, de façon à ce que l'on puisse comparer les ensembles infinis. Voici comment. b) Cardinal d'un ensemble fini Pour un ensemble fini, le cardinal est une notion intuitive, c'est simplement le nombre d'éléments de l'ensemble. Il appartient à N. Ex : Card {1,2,3} = 3 = Card {6,15,28} (*) Opérations sur les cardinaux (finis) : -------------------------------------- (1) Si A et B sont deux ensembles finis *disjoints* alors Card (A Û B) = Card A + Card B où Û désigne l'union disjointe. Ex : A = {1,2,3} Card A = 3 B = {8,9} Card B = 2 A Û B = {1,2,3,8,9} Card(A Û B) = 5 = 3+2. (2) Si A et B sont deux ensembles finis, alors Card (A × B) = (Card A) . (Card B) où A × B désigne le produit cartésien des ensembles A et B. Ex : A = {1,2,3} Card A = 3 B = {a,b} Card B = 2 A × B = { (1,a), (1,b), (2,a), (2,b), (3,a), (3,b) } Card (A × B) = 6 = 3x2. (3) Si A est un ensemble fini on note P(A) l'ensemble des parties de A, c'est a dire l'ensemble des sous-ensembles de A. alors Card P(A) = 2^(Card A) En effet : pour constituer une partie B de A, il y a un choix à faire pour chaque élément de A : soit on le met dans B, soit on ne l'y met pas (2 possibilités). S'il y a n éléments dans A, cela donne 2^n possibilités pour B, soit 2^n parties différentes. Ex : A = {1,2,3} Card A = 3 P(A) = { Ø, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3} } Card P(A) = 8 = 2^3 Ce sont ces propriétés (1), (2), (3) qu'on va vouloir généraliser aux ensembles infinis. ----- Pour un ensemble infini, l'intuition ne s'applique plus : il faut recourir à des définitions formelles. C'est Cantor qui, le premier, a fourni un système cohérent permettant de traiter les ensembles infinis. c) Définition rigoureuse d'un ensemble infini : Une bijection f entre 2 ensembles E et F est une application qui fait correspondre à chaque élément de E un unique élément de F et inversement. S'il existe une bijection entre E et F, on dit que E et F sont équipotents et on note : E ~ F. Un ensemble est dit fini s'il est en bijection avec un ensemble A_n = {1, 2, 3, ..., n} avec n un entier naturel (et A_0 = Ø). Alors Card(E) = n, et on retrouve la notion intuitive. Un ensemble E qui ne peut pas être mis en bijection avec un tel ensemble A_n est dit infini. Ex : N est un ensemble infini. d) Cardinal d'un ensemble infini : On étend la notion de cardinal aux ensembles infinis de la façon suivante (schématiquement ; pour plus de rigueur voir partie II) : 1. Si 2 ensembles sont équipotents (en bijection), on dit qu'ils ont le même cardinal. 2. On dit que Card E <= Card F si E a même cardinal qu'une partie de F. En particulier, si un ensemble infini E est inclus dans un ensemble (infini) F alors Card E <= Card F (inégalité large). Ex. (règle 1) : Card Z = Card N car il existe (au moins) une bijection de N dans Z, qu'on peut expliciter : g : n --> n/2 si n est pair n --> -(n+1)/2 si n est impair ce qui donne 0 --> 0 1 --> -1 2 --> 1 3 --> -2 ... Ex. (règle 2) : Card N <= Card Z <= Card Q <= Card R <= Card C. e) Quelques résultats sur les ensembles dénombrables On a vu Card N = Card Z. Établissons quelques autres résultats : (*) Card N = Card (N^2) On peut en effet compter les éléments de N^2 = { (a,b) | a,b dans N }. Une bijection possible de N^2 dans N est le "comptage en diagonale" : (0,0) --> 0 (1,0) --> 1 (0,1) --> 2 (2,0) --> 3 (1,1) --> 4 (0,2) --> 5 ... (on compte les points de N^2 selon les diagonales bas-droite -> haut gauche, en s'éloignant de l'origine). On peut même expliciter la bijection : (p,q) --> (p+q).(p+q+1)/2 + q De même, on a Card (Z^2) = Card Z. (*) Card (Z) = Card Q Essentiellement, une fraction p/q est un couple d'entiers relatifs (p,q). Cette égalité n'est donc pas particulièrement surprenante quand on a admis Card (Z^2) = Card Z. Formellement, la démonstration est un peu technique : elle est donc donnée dans la deuxième partie. On a donc : Card N = Card Z = Card Q. Ce cardinal est noté aleph_0. (aleph est la première lettre de l'alphabet hébreu). Tous les ensembles infinis qui ont le même cardinal que N sont dits dénombrables. Au sens large, "dénombrable" signifie aussi "fini ou dénombrable". Enfin, un ensemble qui n'est ni fini ni dénombrable est dit... indénombrable. f) Quelques résultats sur les ensembles indénombrables Plaçons nous maintenant dans les réels. (*) Card [0,1] = Card [0,2] = Card [a,b] = ... Il est facile de trouver une bijection de [0,1] dans [0,2] : k : x --> 2x par exemple. De même, on peut toujours trouver une bijection entre 2 intervalles de R, ouverts ou fermés. Tous les intervalles de R ont donc le même cardinal. (*) Card (a,b) = Card R (a,b) désigne l'intervalle, sans se préoccuper de l'inclusion ou non des bornes. La fonction tangente, par exemple, fournit une bijection de ]-pi/2,pi/2[ dans R. En appliquant ce qui précède, tout intervalle de R a le même cardinal que R. (*) Card ([0,1[^2) = Card [0,1[ En effet on peut expliciter une bijection de [0,1[^2 dans [0,1[ : Soit (a,b) dans [0,1[^2. Écrivons leur développement décimal : a = 0, a1 a2 a3 a4 ... b = 0, b1 b2 b3 b4 ... formons alors c = 0, a1 b1 a2 b2 a3 b3 a4 b4 ... N'est-il pas alors clair que la fonction l : (a,b) --> c est une bijection de [0,1[^2 dans [0,1[ ? [en fait, pas tout a fait : il y a une lacune, expliquée dans la seconde partie, mais ça ne change pas le résultat] Grâce à ce qui précède on déduit que : Card R = Card [0,1[ = Card ([0,1]^2) = Card R^2. On peut démontrer la même chose avec n'importe quel exposant à la place de 2. (*) Card C = Card R En effet, les fonctions partie réelle et partie imaginaire d'un complexe fournissent une bijection évidente de C dans R^2. Avec ce qui précède on a donc Card C = Card R^2 = Card R. g) Rapport dénombrable/indénombrable On va maintenant voir que R n'est pas dénombrable. Pour simplifier, on va montrer que [0,1[ n'est pas dénombrable ; ce qui implique, bien sûr, que R ne l'est pas. Supposons le contraire : on peut alors énumérer [0,1[, c'est-à-dire qu'il existe une suite (u_n), n dans N, qui contient tous les réels de [0,1[. Écrivons le développement décimal (par exemple) des premiers termes de (u_n) en notant u_n,i le i-ème chiffre après la virgule de u_n : u_1 = 0, u_1,1 u_1,2 u_1,3 u_1,4 ... u_2 = 0, u_2,1 u_2,2 u_2,3 u_2,4 ... ... u_n = 0, u_n,1 u_n,2 u_n,3 u_n,4 ... ... On forme maintenant le nombre v s'écrivant : v = 0, u_1,1 u_2,2 u_3,3 u_4,4 ... u_i,i ... (on prend les chiffres de la diagonale principale ci-dessus) On forme enfin le nombre w en remplaçant chaque chiffre de v par son prédécesseur (et 0 par 8) : w = 0, w_1 w_2 w_3 w_4 ... avec : w_i = 8 si u_i,i = 0 w_i = u_i,i - 1 sinon Alors le nombre w, qui est bien défini, n'est pas dans la liste des valeurs parcourues par (u_n). En effet : w_1 (le premier chiffre de w après la virgule) est différent de u_1,1 (le premier chiffre de u_1 après la virgule) donc w <> u_1. w_2 <> u_2,2 donc w <> u_2 ... w_n <> u_n,n donc w <> u_n pour tout n. On a donc construit un réel de [0,1[ qui n'est pas dans (u_n) : contradiction avec l'hypothèse. Une telle suite u_n parcourant tous les réels de [0,1[ n'existe donc pas, donc [0,1[ est indénombrable. La technique qui nous a permis de le montrer est classique, et connue sous le nom de "Procédé diagonal de Cantor". h) Conclusion : Tout ceci nous permet d'écrire : Card N = Card Z = Card Q < Card R = Card C. Pour d'autres développements, et des justifications plus rigoureuses, voir la partie II.