[PDF] denombrabilite.pdf 14 mai 2005 Et des

View - Download denombrabilite.pdf

Previous PDF

Next PDF

DENOMBRABILITE

P. Pansu

14 mai 2005

1 Motivation

Il y a t"il plus de r´eels dans ]1,+∞[ ou dans l"intervalle ]0,1[? Oui, bien sˆur. Des droites passant

par l"origine dans le plan, il y en a-t-il autant en dessus ou en dessous de la bissectrice{x=y} (voir figure)? Par sym´etrie, il y en a clairement autant.

Or toute droite passant par l"origine (`a l"exception de l"axeOy) est repr´esent´ee par une ´equation

de la formey=ax, o`uaest lapente. Les droites situ´ees au dessus de la bissectrice correspondent

aux pentesa >1, celle situ´ees au dessous aux pentes 0< a <1. Il y aurait donc autant de r´eels

]1,+∞[ ou dans l"intervalle ]0,1[?

Et des rationnels, il y en a t"il plus dansR? dans ]0,1[? dans [0,1]? Il y a t"il plus de r´eels que

de rationnels? On va voir que tous les ensembles infinis ne sont pas ´equivalents, certains sont plus

grands que d"autres. On commence par ´etudier les plus petits d"entre eux, ce sont les ensembles d´enombrables.

2 Ensembles d´enombrables

2.1 D´efinition

Rappel.Une applicationf:A→Bentre deux ensembles est unebijectionsi, pour tout y?B, l"´equationf(x) =yposs`ede une et une seule solutionx?A. Dans ce cas, on note la solutionx=f-1(y), et l"applicationf-1:B→As"appellel"application r´eciproquedef. Elle satisfaitf◦f-1= idBetf-1◦f= idA. Pour v´erifier qu"une applicationf:A→Best une bijection, il suffit souvent de deviner son

application r´eciproque. En effet, s"il existeg:A→Btelle quef◦g= idBetg◦f= idA, alorsf

est une bijection etg=f-1. 1 D´efinition 1Un ensembleEest ditd´enombrables"il existe une bijection deEsur un sous- ensemble de l"ensembleNdes entiers naturels. Exemple 2Tout ensemble fini est d´enombrable. L"ensemble des entiersnaturels pairs est d´enom- brable. Remarque 3Une bijection sur un sous-ensemble deN, c"est la mˆeme chose qu"une application

injectiveE→N. Plus g´en´eralement, s"il existe une application injective deEdans un ensemble

d´enombrable, alorsEest d´enombrable. Proposition 4SoitEun ensemble d´enombrable infini. Alors il existe une bijection deNsurE. Autrement dit, on peut num´eroter les ´el´ements deE, i.e. ´ecrireE={e0,e1,...,en,...}. Preuve.SoitAun sous-ensemble infini deN. Notonsa0son plus petit ´el´ement, puisa1le

plus petit ´el´ement deA\ {a0}, puisa2le plus petit ´el´ement deA\ {a0,a1}, etc... Par r´ecurrence

surn, on construit un ´el´ementandeA, len-`eme par ordre croissant, tel que les ´el´ements deAqui

sont inf´erieurs `aansont exactementa0< ... < an-1. CommeAest infini, le proc´ed´e ne s"arrˆete

jamais.

Montrons qu"il ´epuise tous les ´el´ements deA. Six?A, l"ensemble des ´el´ements deAqui sont

inf´erieurs ou ´egaux `axest fini. Soitnle nombre de ses ´el´ements. Alorsx=an. L"application

N→A,n?→anest donc une bijection.

Soit maintenantEun ensemble d´enombrable infini. Par d´efinition, il existe un sous-ensemble AdeNet une bijectionf:A→E.Aest infini, donc il existe une bijectiong:N→A. Alorsf◦g est une bijection deNsurE. Exemple 5L"applicationfpair:n?→2nest une bijection deNsur l"ensemble des entiers naturels pairs.

2.2 Exemples

Exercice 6Montrer queN×Nest d´enombrable. En d´eduire que le produit d"un nombre fini d"ensembles d´enombrables est d´enombrable.

Fin du cours n08

Solution de l"exercice 6. N×Nest d´enombrable. On se prom`ene dans un quadrant diagonale par diagonale. On poseg(0) = (0,0),g(1) = (1,0), on poseg(n(n+1)

2+k) = (n,k). On num´erote ainsi tous les couples d"entiers naturels.

On d´efinith:N×N→N×N×Npar la formuleh(n,m) = (n,g(m)). On obtient ainsi une bijection deN2=N×NsurN3. Par r´ecurrence surk, on montre ainsi queNkest d´enombrable. SoientE1,...,Ekdes ensembles d´enombrables. Soitfi=Ei→Nune bijection sur un sous-

ensemble deN. AlorsE1× ··· ×Ek→Nk, (x1,...,xk)?→(f1(x1),...,fk(xk)) est injective, donc

c"est une bijection sur son image, un sous-ensemble deNk, qui est d´enombrable, doncE1×···×Ek

est d´enombrable.

Exercice 7Montrer queQest d´enombrable.

Solution de l"exercice 7. Qest d´enombrable.

Tout rationnel s"´ecrit de fa¸con unique comme fraction r´eduitex=p/qo`uq≥1 etp?q= 1. L"applicationf:Q?→Z×N,f(x) = (p,q) est injective, c"est une bijection sur son image, un sous-ensemble deZ×N. CommeZ×Nest d´enombrable (exercice 6),Qest d´enombrable. 2 Exercice 8Soit(En)n?Nune famille d´enombrable de sous-ensembles d´enombrablesd"un ensemble

E. Montrer que la r´eunion?

n?NEnest d´enombrable. Solution de l"exercice 8.Unions d´enombrables de d´enombrables.

NotonsFn=En\(E1? ··· ?En-1). Alors?

n?NEn=? n?NFn, et lesFnsont deux `a deux disjoints. Soitfn:En→Nune injection. Pourx?Fn, posonsf(x) = (n,fn(x)). En juxtaposant lesfn, on obtient une injection de? n?NFndansN×N. Par cons´equent,? n?NEnest d´enombrable.

Exercice 9Montrer que l"ensemble des polynˆomes `a coefficients entiers est d´enombrable. Montrer

que l"ensemble des sous-ensembles finis deNest d´enombrable. Solution de l"exercice 9.Polynˆomes `a coefficients entiers. Z

d+1, qui est d´enombrable. Comme l"ensemble des polynˆomes `a coefficients entiers est la r´eunion?

d?NPd, il est d´enombrable, d"apr`es l"exercice 8. SoitFnl"ensemble des sous-ensembles `an´el´ements deN. A un tel sous-ensemble, on associe

la suite de ses ´el´ements, rang´es par ordre croissant. On obtient ainsi une injection deFndansNn.

D"apr`es l"exercice 6,Fnest d´enombrable. L"ensemble des sous-ensembles finis deNest la r´eunion?

n?NFn, donc il est d´enombrable, d"apr`es l"exercice 8. On peut aussi plonger cet ensemble dans l"ensemble des polynˆomes `a coefficients entiers, en associant `a chaque sous-ensemble finiAdeN le polynˆome? i?Ati. Exercice 10SoitA=Q∩[0,1]etB=Q∩]0,1[. Existe-t"il une bijection deAsurB? Solution de l"exercice 10. Q∩[0,1]n"est pas plus grand queQ∩]0,1[. AetBsont des sous-ensembles deQ, donc ils sont d´enombrables. Ils sont tous les deux infinis. D"apr`es la proposition 4, il existe une bijectionf:N→Aet une bijectiong:N→B. Alors g◦f-1est une bijection deAsurB. Voici un proc´ed´e pour construire explicitement une bijection deAsurB. SoitC?Bl"ensemble des nombres de la forme 2 -n,n≥1, etD=C? {0,1}. Pour construire une bijection deDsur C, il suffit de poserf(0) = 1/2,f(1) = 1/4 et, pourn≥1,f(2-n) = 2-n-2. On prolongefpar l"identit´e surA\D=B\C.

3 Ensembles non d´enombrables

3.1 La droite r´eelle

Th´eor`eme 1(Cantor).Rn"est pas d´enombrable. Preuve.Il suffit de trouver un sous-ensembleAdeRqui n"est pas d´enombrable. SoitA

l"ensemble des r´eels compris entre 0 et 1 et dont le d´eveloppement d´ecimal ne comporte, apr`es la

virgule, que des 1 et des 8, comme 0.88118188881111818881181888881.... On raisonne par l"absurde. Supposons qu"il existe une bijectionf:N→A. Pour chaquen?N, notons f(n) = 0.an,1an,2an,3...an,k... o`uan,kvaut 1 ou 8. Soitxle r´eel dont le d´eveloppement d´ecimal est x= 0.a1,1a2,2a3,3...ak,k... ety= 1-x. Alorsy?A, car le d´eveloppement d´ecimal deypr´esente un 1 (resp. un 8) l`a o`u celui dexpr´esente un 8 (resp. un 1). Il existe doncn?Ntel quef(n) =y. Or le n-`eme chiffre 3 deyvaut 9-an,n, alors que celui def(n) vautan,n, contradiction. On conclut queAn"est pas d´enombrable, donc queRn"est pas d´enombrable.

Fin du cours n09

Corollaire 11L"ensemble des nombres irrationnels n"est pas d´enombrable. Preuve.Par l"absurde. CommeQest d´enombrable, siR\Q´etait d´enombrable, la r´eunionR serait d´enombrable, contradiction.

D´efinition 12Un nombre r´eel ou complexexestalg´ebriques"il existe un polynˆomePnon nul,

`a coefficients entiers, tel queP(x) = 0. Un nombre qui n"est pas alg´ebrique est dittranscendant.

Exemple 13

2,⎷2 +⎷3sont alg´ebriques.

En effet,

2 est racine deP(x) =x2-2,⎷2+⎷3 est racine deQ(x) =x4-10x2+1. Il est moins

facile de donner un exemple de nombre transcendant. Proposition 14Il existe des nombres r´eels transcendants. Preuve.Montrons que l"ensemble des nombres alg´ebriques est d´enombrable. D"apr`es l"exer-

cice 9, l"ensemble des polynˆomes non nuls, `a coefficients entiers, est d´enombrable. On peut donc

num´eroter ses ´el´ementsP0,P1,...,Pk,.... Pour chaque entierk, notonsZkl"ensemble fini des racines dePk. Alors l"ensemble des nombres alg´ebriques est? k?NZk. D"apr`es l"exercice 8, il est d´enombrable. A fortiori, l"ensemble des nombres r´eels alg´ebriques est d´enombrable. CommeRn"est pas

d´enombrable (th´eor`eme 1), il existe des nombres r´eels non alg´ebriques, i.e. transcendants.

3.2 Equipotence

Les exemples qui pr´ec`edent donnent envie de poser des questions plus g´en´erales. D´efinition 15SoientEetFdeux ensembles. On dit queEetFsont´equipotentss"il existe une bijection deEsurF. Exemple 16Deux ensembles finis sont ´equipotents si et seulement si ilsont le mˆeme nombre d"´el´ements. Deux ensembles d´enombrables infinis sont toujours ´equipotents (proposition 4).

Rn"est pas ´equipotent `aQ(th´eor`eme 1).

Deux intervalles deR, non r´eduits `a un point, sont ´equipotents (voir exercice17 et la feuille

d"exercices). Exercice 17Soit[a,b[un intervalle semi-ouvert. Montrer que[a,b[est ´equipotent `aR. Solution de l"exercice 17.Les intervalles sont ´equipotents. SoitC?]a,b[ l"ensemble des nombres de la formea+ 2-n(b-a),n≥1, etD=C? {a}. Pour construire une bijection deDsurC, il suffit de poserf(a) = (a+b)/2 et, pourn≥1, f(a+ 2-n(b-a)) =a+ 2-n-1(b-a). On prolongefpar l"identit´e sur [a,b[\D=]a,b[\C. On obtient une bijection de [a,b[ sur ]a,b[, lequel est ´equipotent `aR. Voici un th´eor`eme qui va aider `a prouver que deux ensembles sont ´equipotents. Th´eor`eme 2Cantor-Bernstein).SiEest ´equipotent `a un sous-ensemble deFetFest ´equipotent `a un sous-ensemble deE, alorsEetFsont ´equipotents. 4 Preuve.On traite d"abord le cas particulier o`uFest un sous-ensemble deEcontenant un

sous-ensembleA´equipotent `aE. On a d´ej`a fait ce travail `a plusieurs reprises, dans le cas o`uFest

le compl´ementaire d"un ou deux points dansE(exercices 10 et 17). Soitg:E→Aune bijection. SoitC0=E\F. AlorsC1=g(C0) est disjoint deC0puisqu"il est contenu dansF. De mˆeme,C2=f(C1) est disjoint deC0et deC1. En effet, il est contenu dansg(g(E))?g(A)?g(F)?Falors queC0est disjoint deFetC1disjoint deg(F). Posant C i+1=g(Ci), on construit ainsi une suite d"ensembles deux `a deux disjoints. On poseC=? i?NCi etD=? i≥1Ci. Alorsginduit une bijection deCsurD. On compl`ete avec l"identit´e deE\C= F\D. Le cas g´en´eral se ram`ene au cas particulier.

3.3 Davantage d"ensembles ´equipotents `a R

Exercice 18Montrer que l"ensembleNNdes suites d"entiers est ´equipotent `aR.

Solution de l"exercice 18. N

Nest ´equipotent `aR.

On code un r´eel par son signe (0 ou 1), le nombre de chiffres avant la virgule, puis la suite des

chiffres du d´eveloppement d´ecimal (lorsqu"il y en a deux, on choisit celui qui ne se termine pas par

une suite de 9). Cela donne une bijection deRsur un ensemble de suites d"entiers. Inversement, ´etant donn´ee une suite d"entiers (un), on convertit chaqueunen en une suite, v n,i= 0 sinon. On code donc les suites d"entiers par des suites doubles de 0 et de 1, i.e. des suites index´ees parN×Net `a valeurs dans{0,1}. En utilisant une bijectionf:N→N×N(exercice

6), une suite double devient une suite simple (vf(n))n?N. On code enfin cette suite en un r´eel,

celui dont le d´eveloppement d´ecimal est 0.vf(0)vf(1)...vf(n).... Comme les r´eels construits n"ont

pas de 9 dans leur d´eveloppement d´ecimal, il n"ont qu"un seul d´eveloppement d´ecimal, donc deux

suites distinctes donnent deux r´eels distincts. On obtient ainsi une bijection entre l"ensembleNN

des suites d"entiers et un sous-ensemble deR. En appliquant le th´eor`eme 2, on conclut queNNetRsont ´equipotents.

3.4 Des ensembles tr`es grands

Th´eor`eme 3(Cantor).SoitEun ensemble. AlorsEn"est pas ´equipotent `a l"ensembleP(E)des sous-ensembles deE. Preuve.Par l"absurde. Supposons qu"il existe une bijectionf:E→P(E). SoitF={x? E|x /?f(x)}. AlorsFest un sous-ensemble deE, donc il existee?Etel queF=f(e). Supposons quee?F. Alorse?f(e), donc, par d´efinition deF,e /?F, contradiction. Par cons´equent,e /?F. Mais alorse /?f(e), donc, par d´efinition deF,e?F, contradiction `a nouveau. On conclut queE etP(E) ne sont pas ´equipotents. Corollaire 19L"ensemble des parties deRn"est ni d´enombrable, ni ´equipotent `aR. Exercice 20Montrer que l"ensembleRRdes fonctions deRdansRn"est ni d´enombrable, ni

´equipotent `aR.

Solution de l"exercice 20. R

Rest plus grand queR.

On code chaque sous-ensembleAdeRpar sa fonction caract´eristique, d´efinie par

A(x) = 1 six?A, χA(x) = 0 sinon.

On obtient une bijection de l"ensemble des parties deRsur un sous-ensemble de l"ensemble des

fonctionsRR. SiRR´etait ´equipotent `a un sous-ensemble deR, il en serait de mˆeme de l"ensemble

des parties deR, d"apr`es le th´eor`eme 2, or ce n"est pas vrai, th´eor`eme 3. On conclut queRRn"est

pas ´equipotent `aRou `a un sous-ensemble deR.5

3.5 L"hypoth`ese du continu

Un sous-ensemble deNqui n"est pas fini est ´equipotent `aN(proposition 4). Un sous-ensemble deRqui n"est pas d´enombrable est-il ´equipotent `aR? Ce n"est pas certain.

On appelle cet ´enonc´ehypoth`ese du continu. La question de savoir si l"hypoth`ese du continu est

vraie ou non d´epend des axiomes sur lesquels on s"accorde pour fonder la th´eorie des ensembles.

Cohen a d´emontr´e en 1963 qu"il est impossible de d´emontrer l"hypoth`ese du continu, et qu"il est

impossible de d´emontrer son contraire, `a partir de l"axiomatique diteZFC(pour Zermelo-Frenkel +

axiome du choix), qui est le cadre admis par la plupart des math´ematiciens. Il n"en est sans doute

pas de mˆeme si on admet les axiomes suppl´ementaires sur lesquels s"accordent les sp´ecialistes de

th´eorie des ensembles.

Fin du cours n010

4 Familles sommables

On a appris `a sommer des s´eries, i.e. `a additionner tous les termes d"une suite infinie de r´eels. On

va voir quepour les s´eries `a termes positifs, l"ordre dans lequel on somme n"a pas d"importance.

En fait, on peut consid´erer des familles de nombres num´erot´es par un ensemble d´enombrable

quelconque.

D´efinition 21SoitEun ensemble d´enombrable. Soit(ue)e?Eune famille de r´eelspositifs ou nuls

index´ee parE, i.e. une applicatione?→uedeEdansR+. On dit que la famille(ue)e?Eest sommablesi l"ensemble des sommes finies de la forme? e?Fo`uFest un sous-ensemble fini de

E, est major´e. Si c"est le cas, on pose

e?Eu e= sup{? e?Fu e|F?E, Ffini}. Exemple 22Soit(un)n?Nune suite de r´eels positifs ou nuls. Alors(un)est une famille sommable

si et seulement si la s´erie de terme g´en´eral(un)est convergente, et les deux d´efinitions de la somme

co¨ıncident.

Ce que la d´efinition 21 fait apparaˆıtre, c"est que l"ordre dans lequel on prend les termes ne joue

aucun rˆole. Exemple 23Soit(um,n)((m,n)?N×Nla suite double de r´eels positifs ou nuls d´efinie parum,n= 2 -m-n. Alors(um,n)est sommable et sa somme vaut 4. (m,n)?Fu m,n N? m=0(N? n=02 -m-n) N? m=02 -m(N? n=02 -n) N? n=02

Les sommes partielles sont born´ees, donc la famille (um,n) est sommable. Elles sont inf´erieures `a 4,

N}, pour lesquelles la somme est arbitrairement proche de 4, donc la somme vaut 4. On termine par une proposition qui autorise `a sommer par paquets. 6 Proposition 24SoitEun ensemble d´enombrable, etE=? a?AEaune partition deEen sous- ensembles deux `a deux disjoints. Soit(ue)e?Eune famille sommable index´ee parE. Alors les sous-familles(ue)e?Easont sommables, la famille(sa)a?Ad´efinie parsa=? e?Eau eest sommable, et e?Eue=? a?Asa. Preuve.Soita?A. SiFest un sous-ensemble fini deEa, alors? e?Eue. Les sommes partielles de la famille (ue)e?Easont born´ees, donc cette famille est sommable, de somme s a. Soienta,a??A. SiFest un sous-ensemble fini deEa?Ea?, alors e?Fu e=? e?F∩Eau e+? e?F∩Ea?u e donc la famille (ue)e?Ea?Ea?est sommable, et? etF??Ea?sont des ensembles finis, e?Fu e+? e?F?u e=? e?F?F?u e e?Ea?Ea?u e, donc, en prenant la borne sup´erieure sur tous lesFpuis sur tous lesF?, squotesdbs_dbs47.pdfusesText_47

[PDF] montrer que si x appartient ? l'intervalle

[PDF] montrer que x appartient ? un intervalle

[PDF] montrer que xn 1 axn

[PDF] Montrer que y=

[PDF] MONTRER QUELQUE CHOSE SANS LE MONTRER POUR PEUT ÊTRE MONTRER TOUT AUTRE CHOSE

[PDF] Montrer registre tragique

[PDF] Montrer si le nombre A est un entier ou pas

[PDF] montrer une inégalité avec valeurs absolues

[PDF] montrer une relation d'ordre

[PDF] montrer verbe

[PDF] Montres que le lycée est un lieu régit par le Droit

[PDF] montrez

[PDF] montrez comment la structure de l'adn explique sa fonction de support de l'information génétique

[PDF] montrez comment le progrès technique stimule la croissance économique

[PDF] Montrez comment un pouvoir est politique et comment une question devient politique