denombrabilite.pdf PDF 14 May 2005 Montrer que

denombrabilite.pdf

14 May 2005 Montrer que l'ensemble des sous-ensembles finis de N est dénombrable. Solution de l'exercice 9. Polynômes `a coefficients entiers. A chaque ...

Annexe A - Ensembles dénombrables

On dit que E est infini s'il n'est pas fini. Il est intuitivement clair qu'une partie d'un ensemble fini est elle-même finie de cardinal plus petit. Si l

Chapitre 4 : Ensembles finis et infinis 1 Ensembles finis

Pour montrer que R n'est pas dénombrable l'idée est de montrer que R est en bijection avec P(N) en utilisant le développement décimal des nombres réels. Ceci

Cardinalité des ensembles finis

Un ensemble est dénombrable s'il est fini ou s'il est en bijection N. Montrer que les ensembles suivants sont dénombrables : N {0} est dénombrable par la

Exercices cardinalité

Montrer que l'ensemble des rééls compris entre 0 largement et 1 strictement n'est pas dénombrable. Exercice 3. On se propose d'énumérer les éléments de NxN

Exercices corrigés pour le cours de Licence de Mathématiques

Montrer que M est la tribu engendrée par une partition dénombrable. On a X = ?n?NXn car pour x ? X f(x) > 0 et par conséquent f(x) > 1/(n + 1) pour.

Analyse hilbertienne

Dans un espace topologique séparé toute partie dénombrable est A U

Chapitre 3 Théorèmes Fondamentaux

toute famille dénombrable de sous-ensembles ouverts et denses dans E est dense dans E. Montrer que : (1) Tout fermé de E est un espace de Baire.

DM corrigé

Exercice # . Montrer que N[X] est dénombrable. Solution (TT). On rappelle que N[X] dénote l'ensemble de polynômes en

Université Paris-Dauphine DUMI2E Année 2015-2016 ALGEBRE

Pour montrer une proposition P on suppose que P est fausse

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?, s a+sa?=? e?Ea?Ea?u e?Eu e. Cette propri´et´e s"´etend par r´ecurrence `a tout sous-ensemble finiB={a1,...,an}deA, a?Bs e?Eu e. Cela prouve que la famille (sa)a?Aest sommable, avec? e?Eue. SoitFun sous-ensemble fini deE. AlorsFn"intersecte qu"un nombre fini desEa, lesEatels quea?B. Alors e?Fu e=? a?B? e?F∩Eau a?Bs a?As a.

Par cons´equent,

e?Eu e= sup

F?E,Ffini?

e?Fu a?As a.

On conclut que

e?Eue=? a?Asa. 7quotesdbs_dbs47.pdfusesText_47

[PDF] denombrabilite.pdf 14 May 2005 Montrer que