Soit f une application de E dans F Montrer que f est une bijection (de E sur F) si et seulement Un ensemble E est dit dénombrable s'il a même cardinal que N
Previous PDF | Next PDF |
[PDF] Ensembles dénombrables
On montre par récurrence sur n ∈ N que le résultat est vrai pour E = [1,n] Pour n = 0 On dit d'un ensemble qu'il est dénombrable s'il est en bijection avec une
[PDF] 1 Tribus
est une union dénombrable d'ensembles dénombrables, donc est dénom- brable Exercice 3 Montrer que la tribu des boréliens sur R est engendrée par
[PDF] µ
Montrer que D est au plus dénombrable Cela reste-t-il vrai si on ne suppose plus que la mesure est finie? Et si on suppose que la mesure est σ-finie ? Exercice
[PDF] Ensembles équipotents (cardinaux ?)
Soit f une application de E dans F Montrer que f est une bijection (de E sur F) si et seulement Un ensemble E est dit dénombrable s'il a même cardinal que N
[PDF] Peut-on compter les nombres - Zeste de Savoir
12 août 2019 · Rappelez-vous également qu'un ensemble est dit dénombrable s'il existe une suite bijective à valeurs dans cet ensemble Pour montrer que Z
[PDF] 35 “plus déléments” que N : les ensembles non dénombrables
ensembles étaient dénombrables puisque Z est dé- nombrable et même Q l'est Cependant, nous allons Surjectivité Il faut démontrer que (∀B : P(A) : (∃f B
[PDF] MP1 Janson DM7 pour le 5 décembre 2014/2015 I Introduction
5 déc 2014 · Démontrer que l'application f est strictement croissante En déduire Montrer qu' un ensemble infini A est dénombrable si et seulement si il
[PDF] S3 : Sommabilité, sommes
Démonstration On veut montrer que toute partie infinie de N est en bijection Définition On dit qu'un ensemble A est dénombrable lorsqu'il existe une bi-
[PDF] partiel 2013/11 - Ceremade - Université Paris-Dauphine
15 nov 2013 · 0 si A est dénombrable 1 si Ac est dénombrable 2 Montrer que, dans une famille (Ai) de parties mesurables disjointes deux `a deux, il existe
[PDF] montrer que n(n+1)(n+2) est divisible par 6
[PDF] Montrer que pour tout entier c : =1
[PDF] montrer que q est dénombrable
[PDF] montrer que racine de 3 est irrationnel
[PDF] montrer que racine de n est irrationnel
[PDF] montrer que se sont des rationnels
[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 un défaut physique de plusieurs manières différentes comme Cyrano dans "la tirade du nez"
Chapitre 4 : Ensembles finis et infinis
1 Ensembles finis
Les notions que nous cherchons à formaliser dans la première partie de ce chapitre sont très simples, et les résultats
très intuitifs. Les preuves rigoureuses de ces résultats sont toutefois parfois un peu indigestes, et vous ne comprenez
pas bien pourquoi on se casse la tête à démontrer des choses qui semblent évidentes. C"et pourquoi nous admettrons
certains résultats, tout en invitant les lecteurs avides de rigueur à consulter, par exemple, le chapitre "ensembles finis"
du livre Algèbre 1 de Liret et Martinais, chez Dunod.Intuitivement, le fait qu"un ensemble aitnéléments signifie qu"on peut compter ses éléments, en attribuant
au premier élément de l"ensemble le numéro 1, au deuxième le numéro 2, etc., jusqu"à attribuer au dernier
élément le numéron. Ce faisant1, on établit implicitement une bijection entre cet ensembleet{1,2,...,n}.
Cela justifie la définition suivante.
Définition 1Soitn?N?. On dit qu"un ensembleEanéléments, ou est de cardinaln, s"il existe une
bijection deEdans{1,2,...,n}. On note alorsCard E=n.On peut réinterpréter cette définition ainsi : pourn?N?, un ensembleEanéléments si l"on peut écrireE
sous la formeE={x1,x2,...,xn}, où lesxisont deux à deux distincts. La définition 1 et sa réinterprétation
correspondent à ce que signifie intuitivement avoirnéléments. Elles ont en plus l"avantage d"être précises,
et donc de nous permettre de raisonner proprement. La définition suivante complète la définition 1.Définition 2L"ensemble vide a0éléments. Un ensemble est fini s"il anéléments pour un certain entier
natureln.A priori, la définition 1 n"interdit pas qu"un ensemble ait à la fois10et15éléments, ce qui serait ennuyeux.
La proposition ci-dessous montre que ce n"est pas possible. Proposition 3SoitEun ensemble, etnetpdes entiers naturels. S"il existe une bijection deEdans{1,2,...,n}et une bijection deEdans{1,2,...,p}alorsn=p. Le cardinal d"un ensemble fini est donc défini
de manière unique. Pour démontrer la proposition 3, nous avons besoin des résultats suivants :CardA=CardEsi et seulement siA=E.
Preuve.Le point a) est très intuitif mais sa preuve rigoureuse un peulourde, donc nous l"admettrons.
Voici la preuve du b) : supposons qu"il existe une injectionfde{1,2,...,n}dans{1,2,...,p}. PosonsA={f(1),f(2),...,f(n)}etB={1,2,...,p}. L"ensembleAanéléments (carfétant injective, les élémentsf(1),
Nous pouvons maintenant prouver la proposition 3 : supposons qu"il existe des applicationsf:E→{1,2,...,n}etg:E→ {1,2,...,p}bijectives. Alors l"applicationg◦f-1est une bijection, et en particulier
1Il n"y a pas forcément un élément qui se distingue comme étant"le premier", donc on a en fait en tête le processus suivant :
on choisit un élément de l"ensemble et on lui attribue le numéro 1, puis on choisit un élément qui n"a pas encore de numéro, et
on lui attribue le numéro 2, etc. jusqu"à ce que tous les éléments de l"ensemble soient numérotés.
2En fait, la vraie preuve de des résultats consiste à prouver d"abord le b) par récurrence surp, puis à déduire le a) du b).
Voir le livre de Liret et Martinais.
21Proposition 5SoientEetFdes ensembles, etf:E→F. SiEest fini, alors l"ensemblef(E)est fini.
Preuve.SiEest vide, le résultat est évident. SiEest de cardinaln?N?, alors on peut l"écrire sous la forme
E={x1,...,xn}, où lesxisont deux à deux distincts. En notantyi=f(xi)on a doncf(E) ={y1,...,yn}. Si
fest injective, alors lesyisont deux à deux distincts, doncf(E)anéléments etCardf(E) =CardE. Si
fn"est pas injective, alors certains desyisont égaux. Donc, intuitivement, et nous admettrons qu"on peut
rendre cette intuition rigoureuse,f(E)a strictement moins quenéléments. DoncCardf(E)< CardE. Proposition 6SoientEetFdes ensembles non vides, tels queEest fini. a) (Il existe une bijection deEdansF) si et seulement si (Fest fini etCardF=CardE). Preuve.Preuve du a) Soitn=CardE. Par définition, il existe une bijectionfdeEdans{1,2,...,n}. S"il existe une bijectiong:E→Falorsf◦g-1est une bijection deFdans{1,2,...,n}, doncFest fini etanéléments. Réciproquement, siFanéléments, alors par définition il existe une bijectionhdeFdans
{1,2,...,n}, eth-1◦fest une bijection deEdansF.Preuve du b) : s"il existe une injectionf:E→F, alors on aCardE=Cardf(E)d"après la proposition
Réciproquement, soientn=CardEetp=CardF. Par définition, il existe une bijection defdeEdans{1,2,...,p}telle que, pour toutkdans{1,2,...,n},h(k) =k, est bien définie et injective. L"application
g-1◦h◦fest donc une injection deEdansF, car composée d"injections. Une telle injection existe donc.
Proposition 7SoitEetFdes ensembles finis. Soitf:E→F. SiCardE=CardF(et en particulier siE=F) alors :finjective?fbijective?fsurjective.
Preuve.Faisons une preuve cyclique. Sifest injective, alorsCardf(E) =CardEd"après la proposition5. OrCardE=CardFpar hypothèse. DoncCardf(E) =CardF. Orf(E)?F, doncf(E) =Fd"après
la proposition 4, point a), doncfest surjective, donc bijective. Sifest bijective, alorsfest évidemment
surjective. Enfin, sifest surjective,f(E) =F, doncCardf(E) =CardF=CardE, doncfest injective d"après la proposition 5.2 Ensembles infinis
Définition 8Un ensemble est infini s"il n"est pas fini. Rappelons qu"une partieAd"un ensembleEest un sous-ensemble strict deEsiA?EetA?=E(on note parfoisA?E). Nous avons admis (et nous aurions pu prouver) que siEest un ensemble fini, etAunsous-ensemble strict deE, alorsAa strictement moins d"éléments queE. Ceci se traduit par la propriété
suivante : Proposition 9SoitEun ensemble fini. SiAest un sous-ensemble strict deE, il n"y a pas d"injection deEdansA.
respectivement d"après la proposition 6, point b), et parcequeA?E. DoncA=Ed"après la proposition
4, point a).
En particulier, un ensemble fini ne peut pas être mis en bijection avec une de ses parties strictes. Curieu-
sement, cette propriété ne se généralise pas aux ensembles infinis. C"est même une des manières de montrer
qu"un ensemble est infini.Proposition 10Nest infini.
22Preuve.N?est un sous-ensemble strict deN. Pourtant, l"applicationf:N→N?qui ànassocien+ 1est bijective, donc injective.
Définition 11Un ensemble infiniEest dénombrable s"il peut-être mis en bijection avecN, i.e., s"il existe
une application bijective deEdansN(ou deNdansE). Définition 12Un ensemble est au plus dénombrable s"il est fini ou dénombrable.Remarque :certains auteurs utilisent un vocabulaire différent, et appellent "dénombrables" les ensembles
que nous avons appelés "au plus dénombrables".Proposition 131) Un ensemble inclus dans un ensemble au plus dénombrable est au plus dénombrable.
2) SoientEetFdes ensembles. SiEest dénombrable etFen bijection avecE, alorsEest dénombrable.
Preuve.Le 1) est admis (résultat très intuitif, mais preuve un peu lourde). La preuve du 2) est laissée au
lecteur.Proposition 14Z,N×NetQsont dénombrables.
Preuve.Nous admettrons queN×NetQsont dénombrables (voir TD pourN×N). Voici la preuve queZ est dénombrable : soitf:N→Ztelle que pour tout entier natureln,f(2n) =netf(2n+1) =-n-1. On a doncf(0) = 0,f(1) =-1,f(2) = 1,f(3) =-2,f(4) = 2, etc. Cette application est bijective (exercice).L"ensembleZest donc dénombrable.
Commentaire :il y a plusieurs manières de comparer la "taille" d"ensembles. Une première façon est
de les comparer au sens de l"inclusion. En ce sens,Qest plus gros queZ, qui est plus gros queN, qui est
lui-même plus gros que l"ensemble des entiers pairs. En revanche, au sens des cardinaux, c"est à dire au sens
où ils peuvent être mis en bijection, ces ensembles ont la même "taille". C"est surprenant, mais c"est comme
ça. Ceci vu, de nombreuses questions se posent. En particulier, tous les ensembles infinis peuvent-ils être mis
en bijection avecN? La réponse est non : on peut montrer qu"il n"y a pas d"ensembles infinis plus petits que
N, mais il y a des ensembles plus gros. L"ensemble des réels, notamment, est vraiment plus gros queN.
Proposition 15P(N)etRne sont pas dénombrables.
Preuve.Ces résultats sont admis et nous donnons juste l"idée. Le fait queP(N)ne soit pas dénombrable
est une conséquence du résultat général suivant (voir TD) : il n"y a jamais de surjections d"un ensembleE
dans l"ensemble de ses partiesP(E). Ceci implique qu"il n"y a pas de surjections, donc de bijections, deN
dansP(N), donc queP(N)n"est pas dénombrable. Pour montrer queRn"est pas dénombrable, l"idée est de
montrer queRest en bijection avecP(N)en utilisant le développement décimal des nombres réels. Ceci fait,
il suit queRn"est pas dénombrable car sinonP(N)le serait. Le résultat suivant est un outil puissant pour montrer qu"unensemble est dénombrable.Proposition 16Une union dénombrable d"ensembles dénombrables est dénombrable. C"est à dire, siIest un
ensemble d"indices dénombrable, et si pour toutidansI,Aiest un ensemble dénombrable, alorsA=?i?IAi
est dénombrable.Preuve.(Hors programme) Nous donnons seulement la preuve dans le cas où les ensemblesAisont deux à
deux disjoints. L"idée est de montrer queAest en bijection avecN×N. CommeN×Nest dénombrable, et
qu"un ensemble en bijection avec un ensemble dénombrable l"est aussi, cela montrera queAest dénombrable.
Par hypothèse, il existe une bijectionf:N→Iet pour toutidansI, une bijectiongi:N→Ai. Montrons
que l"applicationh:N×N→Adéfini parh(n,p) =gf(n)(p)est bijective. Surjectivité : soity?A. Il existeidansItel quey?Ai. Soitn=f-1(i)etp=g-1i(y). On a h(n,p) =gi(p) =y, doncya au moins un antécédent parh, donchest surjective. Injectivité : soient(n,p)et(n?,p?)dansN×Ntels queh(n,p) =h(n?,p?). On ah(n,p)?Af(n)eth(n?,p?)?Af(n?). Orh(n,p) =h(n?,p?), doncAf(n)∩Af(n?)?=∅. Comme lesAisont deux à deux disjoints,
23on a doncf(n) =f(n?), et doncn=n?par injectivité def. Donch(n,p) =h(n,p?), doncgn(p) =gn(p?), et doncp=p?par injectivité degn. Donc(n,p) = (n?,p?)ethest injective.
On peut montrer que la proposition 16 reste vraie si l"on remplace partout dénombrable par "au plus
dénombrable". En particulier, l"union de deux ensembles dénombrables est dénombrable. Une conséquence
est que l"ensemble des irrationnelsR\Qn"est pas dénombrable. En effet, commeQest dénombrable, siR\Q
était dénombrable, alorsRle serait aussi.
3 Compléments (hors programme)
Voici pour les esprits curieux quelques résultats et preuves complémentaires sur les cardinaux. Commen-
çons par un résultat qui nous permettra de remplaçer si besoin l"hypothèse "il existe une injection deEdans
F" par "il existe une surjection deFdansE".
Proposition 17SoientEetFdes ensembles non vides. Il existe une injection deEversFsi et seulement s"il existe une surjection deFversE. Preuve.Supposons qu"il existe une injectionfdeEversF. Chaque élément def(E)a donc exactementun antécédent parf. Soitx0?E. Soitg:F→El"application définie ainsi : siy?f(E), alorsg(y)est
l"unique antécédent deyparf; siy /?f(E),g(y) =x0. L"applicationgest bien définie. Montrons qu"elle est
surjective. Soitx?E. Soityson image parf. Par définition,y?f(E), doncg(y)est l"unique antécédent
deyparf, doncg(y) =x. Doncxa au moins un antécédent parg, doncgest surjective. Donc il existe une surjection deFversE. (remarque : l"applicationgdépend du choix dex0, mais peu importe : pour n"importe quel choix dex0, elle est bien définie et surjective). Réciproquement, supposons qu"il existe une surjectiongdeFversE. Chaque élément deEa donc aumoins un antécédent parg. Pour chaque élémentxdeE, choisissons un de ses antécédents parg(peu importe
lequel), et appellons-lef(x). Cela définit une applicationf:E→F. Montrons que cette application est
injective. Soitx?E. Par définition,f(x)est un antécédent dexparg, doncg(f(x)) =x, doncg◦f=IdE,
doncg◦fest bijective, donc injective. Doncfest injective. Donc il existe une injection deEdansF.
Corollaire 18SoientEetFdes ensembles finis non vides. Il existe une surjection deEdansFsi et Preuve.Conséquence directe des propositions 17 et 6, point b).Essayons maintenant de généraliser la notion de cardinal d"un ensemble aux ensembles infinis, notamment
pour pouvoir expliquer de manière précise qu"il y a des infinis plus grand que d"autres. On a vu que quand
généralisation naturelle de la notion d" "avoir moins d"élements que" aux ensembles infinis est donc de dire
que le cardinal deEest plus petit que le cardinal deFsi et seulement s"il existe une injection deEdans
infini,CardEne désigne pas un entier, juste un nombre abstrait qui mesurerait le "nombre d"éléments" deE;
une injection deEdansF"). De même, une généralisation naturelle de la notion d" "avoir autant d"éléments
que" est de dire que deux ensembles ont le même cardinal si et seulement s"il existe une bijection entreE
etF, et c"est ce que signifiera la notationCardE=CardF. Pour que ces généralisations et ces notations
heureusement le cas, comme le montre le théorème suivant, que nous admettrons.Théorème 19(Théorème de Cantor-Bernstein) SoientEetFdes ensembles. S"il existe une injection
f:E→Fet une injectiong:F→Ealors il existe une bijectionh:E→F.Remarque :d"après la proposition 17, on aurait pu énoncer ce théorème ainsi : s"il existe une injection deE
dansFet une surjection deEdansFalors il existe une bijection deEdansF. 24Le théorème de Cantor-Bernstein est utile pour montrer qu"unensemble est dénombrable. Ainsi, pour
montrer queN×Nest dénombrable, on peut raisonner ainsi : l"applicationf:N→N×Nqui ànassocie
f(n) = (n,0)est injective. D"autre part, l"applicationg:N×N→Nqui à(n,p)associeg(n,p) = 2n3p
est injective (à cause de l"unicité de la décomposition d"unentier en produits de nombres premiers). Donc
d"après le théorème de Cantor-Bernstein, il existe une applicationh:N→N×Nbijective.Bien voir qu"en
revanche nifnigne sont bijectives. Voici une autre preuve, constructive cette fois, du fait qu"il existe une bijection entreN×NetN. Preuve.Soitf:N×N→N?telle que pour tout couple d"entier naturel(n,p),f(n,p) = 2n(2p+ 1). Montrons quefest bijective. Cela prouvera queN×Nest en bijection avecN?, et donc avecN. Montrons quefest injective. Soient(n,p)et(n?,p?)des couples d"entiers naturels tels quef(n,p) =f(n?,p?). On a donc2n(2p+1) = 2n?(2p?+1), donc2n-n?(2p+1) = 2p?+1. Sin > n?,2n-n?(2p+1)est pair, donc différent donc(n,p) = (n?,p?). Doncfest injective. Montrons quefest surjective. Soitq?N?. Soitnle plus grandentier tel queq/2nsoit entier. Nécessairement,q/2nest impair. Il existe donc un entier naturelptel que
q/2n= 2p+ 1. On a doncf(n,p) =q, doncqa au moins un antécédent parf, etfest surjective. Doncf est bijective. Une bijection explicite deN×NdansNest donc donnée parg(n,p) = 2n(2p+ 1)-1Le résultat suivant montre qu"au sens des cardinaux, il n"y apas d"ensembles infinis plus petits queN.
Proposition 20SiEest un ensemble infini, alors il existe une injection deNdansE.Preuve.La preuve consiste à construire l"injection pas à pas. SoitEun ensemble infini. Tout d"abord,E
est non vide. Je peux donc choisir un élément deE, que j"appellex0. Ensuite, commeEest infini, l"ensemble
E1=E\{x0}est non vide.E1contient donc au moins un élément. J"en choisis un, et je l"appellex1. On
continue en procédant ainsi. Supposons que j"ai construitnéléments deE,x0,x1,...,xn, tels que pour tout
k? {1,2,..,n},xk/? {x0,...,xk-1}. CommeEest infini, l"ensembleEn+1=E\{x0,...,xn}est non vide. Jepeux donc choisir un élément dansEn+1que j"appellexn+1. Par construction,xn+1/? {x0,...,xn}, si bien que
j"ai construitn+ 1éléments deE,x0,x1,...,xn+1, tels que pour toutk? {1,2,..,n+1},xk/? {x0,...,xk-1}.
Par une récurrence dont nous omettrons les détails, on peut donc construire une suite(xn)n?Nd"éléments de
Etelle que pour toutk?N,xk/? {x0,...,xk-1}. Posons alors, pour toutndansN,f(n) =xn. Cela définitune applicationf:N→E, et cette application est injective pour la raison suivante: sin?=p, alors soit
n < p, soitp < n. Ces cas étant symétriques, il suffit d"examiner le casn < p. On a alors par construction,
x p/?A={x0,...,xp-1}. Orxn?A, doncxn?=xp, doncf(n)?=f(p). Prouvons maintenant certain des résultats admis dans le cours. Montrons tout d"abord qu"une union dénombrable d"ensembles dénombrables est dénombrable dans le cas général. Preuve.SoitIun ensemble dénombrable, et pour toutidansI, soitAiun ensemble dénombrable. SoitA=?i?IAi. Dans le cas où les ensemblesAisont deux à deux distincts, nous avons montré qu"il existe une
bijectionf:N×N→A, et queAest donc dénombrable (voir la preuve de la proposition 16). Dans le cas où
lesAine sont pas deux à deux distincts, cette applicationfn"est plus injective, mais elle reste surjective. Il
existe donc une surjection deN×NdansA. Comme il existe une bijection deNdansN×N, il existe donc
une surjection deNdansA. Mais commeAest infini, il existe une injection deNdansA(proposition 20).Donc d"après le théorème de Cantor-Bernstein, il existe une bijection deNdansA, doncAest dénombrable.
Montrons maintenant queQest dénombrable.
Preuve.Par définition,Q={p/q|p?Z,q?N?}. Pour toutqdansN?, posonsAq={p/q,p?Z}.L"ensembleAqest à l"évidence en bijection avecZ, et donc dénombrable. De plusQ=?q?N?Aq. Comme
N?est dénombrable, l"ensembleQest donc une union dénombrable d"ensembles dénombrables. DoncQest
dénombrable.On peut aussi raisonner ainsi : l"applicationf:Z×N?→Qdéfinie parf(p,q) =p/qest surjective, par
définition deQ. De plus, en utilisant le fait queN×NetZsont dénombrables, on montre facilement que
Z×N?est dénombrable, et donc qu"il existe une bijectiongdeNdansZ×N?. L"applicationf◦gest alors
une surjection deNdansQ. Comme par ailleurs il existe à l"évidence une injection deNdansQ(n→n), il
suit du théorème de Cantor-Bernstein qu"il existe une bijection deNdansQ. 25quotesdbs_dbs47.pdfusesText_47