METHODOLOGIE[COURS][ENSEMBLES FINIS]
5 pages
Français

METHODOLOGIE[COURS][ENSEMBLES FINIS]

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

6Ensembles finisNous supposons avoir une idée intuitive de l’ensembleN sur lequel il existe une relation d’ordre strict"<". Nous supposons de plus l’assertion suivante :Toute partie non-vide deN admet un plus petit élément pour < (1)Un tel élément est alors unique. Nous rappelons le théorème suivant :1Théorème 1 Soient E,F deux ensembles non-vides et f: E →F une application.1. Il y a équivalence entre(a) f est injective;(b) il existe une application g: f(E)→E telle que g◦f =Id .E2. Il y a équivalence entre(a) f est surjective;(b) il existe une application g: F →E telle que f ◦g =Id .F3. Il y a équivalence entre(a) f est bijective;(b) il existe une application g: E →F telle que f ◦g =Id et g◦f =Id .F E∗Rappelons que nous notons pour n∈N ,N = [1,n] =Z∩[1,n].nDéfinition 2 Soient E,F deux ensembles. On dit queE et F sont équipotents s’il existe une bijectionϕ: E →F.∗Lemme 3 Soient n,m∈N et ϕ:N →N .m n1. Si ϕ est injective m6n;2. Si ϕ est surjective n6m;3. Si ϕ est bijective alors n =m;preuve:∗1. Posons P(m) la propriété "Pour tout n ∈ N , si ϕ:N → N est une application injective alorsm nm6n".∗ 2 ∗P(1) est vraie car pour tout n∈N , 16n. Soit m> 1 tel que P(m) soit vraie. Soit n∈N tel qu’ilexiste une application ϕ:N →N injective.m+1 ner1 cas : Supposons ϕ(m + 1) = n. Alors ϕ(N ) ⊆ N , donc nous disposons d’une applicationm n−1injectiveψ : N → Nm n−1x 7! ϕ(x)et par l’hypothèse de récurrence nous concluons que m6n−1 c’est-à-dire m+16n.ème2 cas : ...

Sujets

Informations

Publié par
Nombre de lectures 45
Langue Français

Exrait

Ensembles finis
Nous supposons avoir une idée intuitive de l’ensembleNsur lequel il existe une relation d’ordre strict "<". Nous supposons de plus l’assertion suivante : Toute partie nonvide deNadmet un plus petit élément pour<(1) Un tel élément est alors unique. Nous rappelons le théorème suivant : 1 Théorème 1SoientE, Fdeux ensemblesnonvidesetf:EFune application. 1. Ily a équivalence entre (a)fest injective; (b) ilexiste une applicationg:f(E)Etelle quegf=IdE. 2. Ily a équivalence entre (a)f;est surjective (b) ilexiste une applicationg:FEtelle quefg=IdF. 3. Ily a équivalence entre (a)fest bijective; (b) ilexiste une applicationg:EFtelle quefg=IdFetgf=IdE. Rappelons que nous notons pournN,Nn=[1, n]=Z[1, n].
Définition 2SoientE, Fdeux ensembles. On dit queEetFsont équipotents s’il existe une bijection ϕ:EF. Lemme 3Soientn, mNetϕ:NmNn. 1. Siϕest injectivem6n; 2. Siϕest surjectiven6m; 3. Siϕest bijective alorsn=m; preuve: 1. PosonsP(m)la propriété "Pour toutnN, siϕ:NmNnest une application injective alors m6n". 2P(1)est vraie car pour toutnN,16n. Soitm>1tel queP(m)soit vraie. SoitnNtel qu’il existe une applicationϕ:Nm+1Nninjective. er 1cas :Supposonsϕ(m+ 1)=n. Alorsϕ(Nm)Nn1, donc nous disposons d’une application injective ψ:NmNn1 x7→ϕ(x) et par l’hypothèse de récurrence nous concluons quem6n1c’estàdirem+ 16n. ème 2cas :Supposonsϕ(m+ 1) =εavecε6=n. Posonsτla transposition définie par : τ:NnNn x7→xsix6∈ {n, ε} n7→ε ε7→n 1 L’applicationf:∅ →Fest toujours injective mais n’admet d’inverse à gauche uniquement siF=. 2 Il existe de tel entier; par exempleId:Nm+1Nm+1définie parId(x) =x.
1
2
er Alorsτϕvérifie les hypothèses du (1cas) ;nous avons doncm+ 16n. Par récurrence la propriété P(m)est vraie pour toutmN. 2. Soitϕ:NmNnune application surjective. 1 SoitkNn. Puisqueϕest surjective, l’ensembleϕ({k})n’est pas vide. D’après la propriété (1), 31 nous pouvons donc noterf(k)Nmle plus petit élémentdeϕ({k}). Nous disposons alors d’une application f:NnNm x7→f(x) ′ ′1 qui est injective; en effet, sik, kNnsont tels quef(k) =f(k), nous en déduisons queϕ({k})1′ ′ ϕ({k})6=; c’estàdire qu’il existexNntel quek=ϕ(x) =k. Nous appliquons alors le point 1. et concluons quen6m. 3. Cela découle des points1et2.
Définition 4SoitEun ensemble. On dit queEest un ensemble fini siE=ou s’il existe un entier nNet une bijection tel queϕ:ENn. LorsqueE=, on dit que le cardinal deEest0. SiE est un ensemble fini qui n’est pas vide, d’après le lemme précédent il existe ununiqueentiernN 1 tel queEsoit équipotent àNn; en effet, siψ:ENmest une autre bijection, alorsψϕest une bijection deNnsurNm, doncm=n. Cet unique entiernest appelé le cardinal deEet est noté|E| ou#E. Remarque: Dans la pratique, au lieu de dire qu’il existe une bijectionϕ:ENn, on "numérotera" l’ensembleE, c’estàdire que l’on noteraE={x1, x2, . . . , xn}. Cette notation signifie que pouriNn, 1 xi:=ϕ(i).
Remarque: Il est clair que siFest un ensemblefinietEun ensemble équipotent àFalorsEest fini.
Exemples: Nous avons de manière immédiate :|∅|= 0,|{x}|= 1et sixetysont deux éléments distincts l’ensemble{x, y}a pour cardinal 2 (parce que l’application qui envoiexsur1etysur2 est bijective). Dans la suite nous allons montrer comment se comporte le cardinal sous les opérations ensemblistes habituelles (réunion, intersection, produit cartésien).
Lemme 5SoitEun ensemble fini etFEun sousensemble deE. AlorsFest aussi un sous ensemble fini. preuve: SiF=, nous avons déjà terminé. SupposonsF6=; ceci impose queE6=. SoitωF. Posons n:=|E|. Il existe une applicationϕ:NnEbijective. Quitte à composerϕpar un transposition comme dans la preuve du lemme 3, nous pouvons supposer queϕ(1) =ω. Nous posons alors : ψ:NnNn l’application définie par :ψ(1) = 1et par récurrence pourk∈ {1, . . . , n1};ψ(k+ 1)=ψ(k)si ϕ(k+ 1)6∈Fetψ(k+ 1) =ψ(k) + 1siϕ(k+ 1)F. Posons alorsm:=ψ(n). SoitkNm. Sik= 1, on poseg(1) := 1et si26k6m, nous constatons que{jNn|ψ(j) =k}est une partie non vide de Nn; notonsg(k)son plus petit élément. Nous avons alors une applicationΨdéfinie par : Ψ :NmF k7→ϕ(g(k)) Cette application est bien définie; par définition deg(k), sik= 1alorsΨ(1) =ϕ(g(1)) =ϕ(1) =ωF et sinonϕ(g(k)1)6=kdoncψ(g(k))F. Montrons queΨest injective. Sik, kNmtels que 4′ ′ Ψ(k) = Ψ(k)alorsg(k) =g(k)ce qui imposek=ψ(g(k)) =ψ(g(k)) =k. Soit maintenant 5 6 yF. SoitjNntel queϕ(j) =y. Alorsψ(j1)< ψ(j)doncg(ψ(j)) =jet par suite 31 en particulier,f(k)ϕ({k}) 4 ϕest injective. 5 caryF. 6 ψest croissante.
3
    Ψ(ψ(j)) =ϕ g ψ(j) =ϕ(j) =yce qui prouve queΨest aussi surjective et termine la démonstration.
Proposition 6SoitEun ensemble non vide. Il y a équivalence entre : 1.Eest fini; ′ ′ 2. ilexiste un ensemble finiEet une applicationf:EEinjective ; ′′ ′′ 3. ilexiste un ensemble finiEet une applicationg:EEsurjective ; preuve: L’implication (1.2.) est évidente. (2.3.) D’après le théorème 1, nous savons qu’il existe une applicationg:f(E)Etelle que gf=IdE. Et toujours d’après le même théorème nous en déduisons quegest surjective. Mais alors ′′ ′ d’après le lemme 5, nous savons queE:=f(E)Eest ensemble fini. ′′ (3.1.) D’après le théorème 1, nous savons qu’il existe une applicationf:EEtelle quegf= IdE. Et toujours d’après le même théorème nous en déduisons quefest injective. NotonsE:=f(E)′′ ′ E. D’après le lemme 5, nous savons queEest ensemble fini et venons de voir qu’il est équipotent à Epar : Ψ :EE x7→f(x)
Proposition 7SoientA, Bdeux parties finies d’un ensembleE. AlorsABetABsont des ensembles finis et |AB|=|A|+|B| − |AB|(2) preuve: SiAouBest, tout est clair. Supposons queA6=etB6=. Notonsn:=|A|etm:=|B| (n, mN). Nous pouvons donc écrireA={a1, . . . , an}etB={b1, . . . , bm}. er 1cas :Supposons queAB=. Posons alors l’application ϕ:ABNn+m isixAetx=ai x7→ n+jsixBetx=bj Il est alors clair queϕ; ce qui prouve d’une part queest bijectiveABest fini et d’autre part la formule (2). ème 2cas :SupposonsAB6=. Nous écrivons alors d’une partAB=A(B\(AB))et d’autre partB= (AB)(B\A), les réunions étant disjointes. D’après le lemme 5 nous savons queAB etB\(AB); nous pouvons donc appliquer le premier cas, pour trouver :sont des ensembles finis |AB|=|A|+|B\(AB)| |B|=|AB|+|B\(AB)| ce qui permet de conclure.
Corollaire 8Soit(Ai)iIune famille finie de sousensembles finis d’un ensembleE. Supposons que 2 pour tout couple(i, j)Itel quei6=jnous ayonsAiAj=. Alors [ X Ai=|Ai|   iI iI
4
preuve: Nous raisonnons par récurrence sur le cardinal deI. Si|I|= 1, c’est trivial, et si|I|= 2, c’est la proposition précédente. Soitn>2tel que la propriété soit vérifiée. Soit alors(Ai)iIune famille finie de sousensembles finis d’un certain ensembleEvérifiant les hypothèses du corollaire et telle que|I|=n+ 1. Puisque|I|>1nous pouvons choisiri0I. Considérons alors la sousfamille 7 (Ai)II\{i0}. Le cardinal deI\ {i0}estndonc nous pouvons appliquer l’hypothèse de récurrence 2 en remarquant que pour tout couple(i, j)(I\ {i0})tel quei6=jnous avonsAiAj=. Ainsi P   A=|A|. Maintenant en posantB:=AetB:=A, il apparaît que iI\{i0}i iI\{i0}i0iI\{i0}i1i0 la famille(Bi)i∈{0,1}est une famille qui vérifieB0B1=. Donc puisque la propriété est vraie au rang2, nous concluons que [ Ai=|B0B1|   iI =|B0|+|B1| [ =Ai+|Ai0|   iI\{i0} X =|Ai|+|Ai0| iI\{i0} X =|Ai| iI
Corollaire 9SoientE,Fdeux ensembles finis. Alors |E×F|=|E| ∙ |F| preuve: ÉcrivonsE={x1, . . . , xn}etF={y1, . . . , ym}. Nous pouvons supposer quem6n. Posons ϕ:E×FN(n+ 1)m (x, y)7→j(n+ 1) +isix=xiety=yj Cette application est injective doncE×Fest un ensemble fini. Maintenant la famille{(xi, y)|y S F}vérifie les hypothèses de la proposition précédente et bien sûr{(xi, y)|yF}= 16i6n 16i6n E×F; d’après la proposition précédente, nous avons le résultat désiré.
n Corollaire 10SoitEun ensemble fini de cardinaln. AlorsP(E)est un ensemble fini de cardinal2 preuve: 0 SiE=alorsP(E) ={∅}qui est bien de cardinal1 = 2. SupposonsE6=. PourAE, nous notonsϕAla fonction caractéristique deA. Nous notonsF(E,{0,1})l’ensemble des applications deE à valeurs dans{0,1}. Posons alors Φ :P(E)→ F(E,{0,1}) A7→ϕA Nous savons queΦest injective d’après un exercice. Et siϕ∈ F(E,{0,1}), nous lui associonsAϕ:= {xE|ϕ(x) = 1}. Il est alors clair queΦ(Aϕ) =ϕ. Maintenant en écrivantE={x1, . . . , xn}, nous posons n Ψ :F(E,{0,1})→ {0,1}   ϕ7→ϕ(x1), . . . , ϕ(xn) 7 ici nous utilisons la proposition précédente
il est immédiat queΨest une bijection; ce qui prouve la proposition.
5
Remarque: Il est immédiat d’après la proposition 7 que siEest un ensemble fini etFEalors |F|6|E|.
Lemme 11SoitEun ensemble fini etFE. Il y a équivalence entre : 1.E=F; 2.|E|=|F|.
preuve: (1.2.) c’est clair. c c (2.1.) Supposons queF(E. Alors nous écrivonsE=FFavecF6=et fini d’après le lemme 5. Alors d’après la proposition 7 nous avons|F|<|E|.
Proposition 12SoientE, Fdeux ensembles finis de même cardinal etf:EFune application. Il y a équivalence entre : 1.f;est injective 2.f;est surjective 3.fest bijective; preuve: SiE=F=tout est clair. Posonsn:=|E|=|F|et supposons maintenant quen6= 0. D’après un exercice, il nous suffit de raisonner sur une applicationf:NnNn. (1.2.) Supposonsfinjective. Notons f0:Nnf(Nn) x7→f(x) fest une bijection etf0(Nn) =f(Nn)est un ensemble fini grâce au lemme 5 donc|f(Nn)|=|Nn|. Nous concluons d’après le lemme 11 quef(Nn) =Nn. ′ ′(2.3.) Supposons quefn’est pas injective. Il existe alorsk, kNtels quek6=ketf(k)6=f(k). Donc l’application f0:Nn\ {k} →Nn x7→f(x) 8est encore surjective. Mais comme|Nn\ {k}|=n1, d’après le lemme 3 nous trouvonsn6n1; c’est absurde. (3.1.) C’est immédiat.
8 ici nous utilisons la proposition précédente