[PDF] [PDF] Ensembles équipotents (cardinaux ?)

[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] µ

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] 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] 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] comment savoir si une fonction est bijective

[PDF] montrer qu'une fonction est injective

[PDF] bijection réciproque exercices corrigés

[PDF] montrer que f réalise une bijection

[PDF] baguier virtuel sans imprimer

[PDF] baguier gratuit

[PDF] controle francais 4eme poesie lyrique

[PDF] évaluation français entrée 4ème collège

[PDF] bilan exemple

[PDF] bilan définition

[PDF] le bilan comptable cours

[PDF] bilan ulis

[PDF] rapport d'activité ulis

[PDF] comment rédiger un bilan pédagogique

[PDF] rapport d'activité ulis collège

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.

21
Proposition 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 et

ané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 si

E=F) alors :finjective?fbijective?fsurjective.

Preuve.Faisons une preuve cyclique. Sifest injective, alorsCardf(E) =CardEd"après la proposition

5. 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, etAun

sous-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 de

EdansA.

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.

22
Preuve.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)et

h(n?,p?)?Af(n?). Orh(n,p) =h(n?,p?), doncAf(n)∩Af(n?)?=∅. Comme lesAisont deux à deux disjoints,

23
on 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 exactement

un 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 au

moins 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. 24

Le 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 grand

entier 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)-1

Le 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

E

1=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. Je

peux 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éfinit

une 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. Soit

A=?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. 25
quotesdbs_dbs27.pdfusesText_33