V-6. Les cardinaux des ensembles infinis - Partie II
FOIRE AUX QUESTIONS DE fr.sci.maths CHAPITRE V: QUESTIONS FONDAMENTALES
V-6. Les cardinaux des ensembles infinis - Partie II
SUJET PRECEDENT - INDEX - SUJET SUIVANTa) Autre définition rigoureuse d'un ensemble infini : Une définition équivalente (moyennant l'axiome du choix) à celle de la première partie est : Un ensemble E est dit infini si on peut trouver une bijection entre lui-même et une de ses parties (strictes) F, ie : F inclus dans E, F <> E, F ~ E. Ex : N est en bijection avec N*, par la fonction f : n --> n+1 ainsi, N est infini b) Cardinal d'un ensemble infini : La façon parfaitement rigoureuse de définir le cardinal pour un ensemble infini s'appuie sur le théorème de Cantor-Bernstein : Thm : Soient A et B deux ensembles (finis ou infinis). Si A s'injecte dans B et B s'injecte dans A, alors A et B sont équipotents. (la démonstration est facile dans le cas fini, un peu moins dans le cas général). Ce théorème justifie les écritures : Card(A) = Card(B) si A et B sont équipotents Card(A) <= Card(B) si A s'injecte dans B En effet, on peut alors appliquer la règle d'antisymétrie : si n <= m et m <= n alors n = m. Écrire cette règle avec les cardinaux infinis est une simple ré-écriture du théorème de Cantor-Bernstein. D'autre part, on a l'équivalence (moyennant l'axiome du choix) : - A s'injecte dans B - B se surjecte sur A et en notant Card(B) >= Card(A) si B se surjecte sur A, on reste cohérent en manipulant les cardinaux. Pour la culture (merci à David Madore) : Si A et B sont deux ensembles quelconques, alors soit A s'injecte dans B (ie Card(A) <= Card(B)), soit B s'injecte dans A (ie Card(B) <= Card(A)). En d'autres termes : les cardinaux forment une classe "totalement ordonnée". c) Quelques précisions sur les ensembles dénombrables (*) Card (Z^2) = Card Q On a une injection évidente f : Q --> Z^2 : f(p/q) = (p,q) avec p,q premiers entre eux et q>0 [on peut rajouter f(0)=(0,1) pour être parfaitement rigoureux] Évidemment, ce n'est pas une bijection : (4,6) par exemple n'a pas d'antécédent, puisque f(4/6) = (2,3). On a donc Card Q <= Card(Z^2). D'autre part, on a vu dans la première partie : Card (Z^2) = Card Z. Or Z s'injecte trivialement dans Q : Card Z <= Card Q. De ces deux inégalités on déduit Card (Z^2) = Card Q, alors qu'il serait fastidieux d'exhiber une bijection explicite entre Q et Z^2. d) Quelques précisions sur les ensembles indénombrables (*) Card ([0,1[^2) = Card [0,1[ En fait, l'application l donnée dans la partie I n'est pas vraiment une bijection, mais seulement une injection. Cela est dû à l'existence de deux écritures décimales distinctes pour les décimaux : l'une avec un nombre fini de chiffre (ex : 1,23), l'autre avec un nombre infini de chiffres (ex : 1,2299999...) [Voir la FAQ 0,999...=1]. En conséquence, le nombre 0,50595959... par exemple n'a pas d'antécédent puisque: l(0,555... , 0,099...) = l(0,555.. , 0,1) = 0,51505050... Cependant, ça suffit : l nous fournit une injection de [0,1[^2 dans [0,1[, et l'injection réciproque est triviale. En appliquant le théorème de Cantor-Bernstein on peut donc conclure en toute rigueur que Card([0,1[) = Card([0,1[^2). La généralisation à Card R = Card (R^2), se fait toujours comme indiqué dans la première partie. e) Rapport dénombrable/indénombrable Voici une démonstration plus indirecte du fait que R est indénombrable, mais qui a l'avantage de préciser le rapport entre les 2, à savoir R ~ P(N), l'ensemble des parties de N. (*) Soit E un ensemble. P(E) n'est jamais équipotent à E. En voici une (jolie) démonstration par l'absurde. Supposons qu'il existe une bijection h : E --> P(E) Pour tout x dans E, h(x) est un sous-ensemble de E. Notons F = { x dans E | x n'est pas dans h(x) }. Par construction, F est une partie de E, donc F est dans P(E). Comme h est une bijection, F a un antécédent dans E, ie : il existe y dans E tel que h(y) = F = {x dans E | x n'est pas dans h(x)} Alors : - si y est dans F, par définition de F, y n'est pas dans h(y)=F. Absurde. - si y n'est pas dans F, par définition de F, y est dans h(y)=F. Absurde aussi. C'est donc l'hypothèse d'existence de la bijection h qui est fausse. Cqfd. (*) Card P(N) = Card R On constitue donc l'application p : P(N) --> R de la façon suivante. Soit E dans P(N). E est donc un sous-ensemble (fini ou infini) de N. On forme un nombre d écrit en base 2 de la façon suivante : d = 0, d0 d1 d2 d3 d4 d5... où dn = 1 si n est dans E, 0 sinon On a alors d dans [0,1], de façon claire (d=0 si E=@, d=1 si E=N). [On peut définir p de façon plus concise : p(E) = \somme_{n dans E} 2^-(n+1)] La fonction p : E --> p(E)=d est alors une surjection de P(N) dans R. [Tout réel r de [0,1] est atteint, et pour connaître son antécédent, il suffit d'écrire le développement binaire de r. En revanche, p n'est pas une bijection, en raison de l'existence de 2 développements binaires, comme pour les développements décimaux.] D'autre part, si on fabrique l'application q comme p, mais en considérant que cette fois d est écrit en base 3 (ou 10, ou n>2), alors l'application q est une injection de P(N) dans R. [Tous les réels ne sont pas atteints, mais chaque réel atteint a un antécédent unique.] P(N) se surjecte et s'injecte à la fois dans R, donc P(N) ~ R : Card P(N) = Card R Par généralisation du cas fini, on écrit : Card R = Card P(N) = 2^(Card N) = 2^(aleph_0) (*) Card N < Card R En effet, puisque N est inclus (donc s'injecte) dans R,Card N <= Card R. De plus, on vient de montrer que Card R = Card P(N), et que P(N) n'est pas équipotent à N. Donc Card N < Card R. f) Hypothèse du Continu... On définit aleph_1 comme étant le plus petit cardinal strictement supérieur à aleph_0 (pour une définition plus rigoureuse de aleph_1, voir l'article de David Madore : http://www.eleves.ens.fr:8080/home/madore/w/ordinals/ordinals.html) Le fait de savoir si Card R = aleph_1 est indécidable d'après la construction de R seule, c'est à dire qu'on peut arbitrairement décider que oui ou non. Habituellement, on fait l'hypothèse que c'est bien le cas (hypothèse du Continu) : aleph_1 = Card R. En termes plus simples, l'hypothèse du Continu dit que : toute partie de R est soit au plus dénombrable, soit équipotente à R. En termes intuitifs (!) : il n'existe pas d'ensemble "strictement plus gros" que N mais "strictement plus petit" que R. g) Opérations sur les cardinaux Toutes les opérations valables avec les cardinaux finis, sont extensibles aux cardinaux infinis, mais l'intérêt est moindre : Si A ou B est infini : Card (A Û B) = Card A + Card B = Max (Card A , Card B) Card (A × B) = Card A . Card B = Max (Card A , Card B) Card (P(A)) = 2^Card(A) L'hypothèse du Continu "dit" ainsi que aleph_1 = 2^aleph_0. h) Références -- Initiation à la théorie des ensembles, J. Breuer Dunod, 1961 -- Théorie axiomatique des ensembles, Jean-Louis Krivine, Presses Universitaires de France, 1972 (niveau maîtrise) voir aussi : -- Théorie des ensembles, Jean-Louis Krivine, Vuibert, 1998