METHODOLOGIE[COURS][ENSEMBLES FINIS]

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 : ...

Informations

• Publié par: Irro
• Nombre de lectures: 31
• Langue: Français

Extrait

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:E→Fune application. 1. Ily a équivalence entre (a)fest injective; (b) ilexiste une applicationg:f(E)→Etelle queg◦f=Id E . 2. Ily a équivalence entre (a)f;est surjective (b) ilexiste une applicationg:F→Etelle quef◦g=Id F . 3. Ily a équivalence entre (a)fest bijective; (b) ilexiste une applicationg:E→Ftelle quef◦g=Id F etg◦f=Id E . ∗ Rappelons que nous notons pourn∈N,N n =[1, n]=Z∩[1, n].

Définition 2SoientE, Fdeux ensembles. On dit queEetFsont équipotents s’il existe une bijection ϕ:E→F. ∗ Lemme 3Soientn, m∈Netϕ:N m →N n . 1. Siϕest injectivem6n; 2. Siϕest surjectiven6m; 3. Siϕest bijective alorsn=m; preuve: ∗ 1. PosonsP(m)la propriété "Pour toutn∈N, siϕ:N m →N n est une application injective alors m6n". ∗2∗ P(1)est vraie car pour toutn∈N,16n. Soitm>1tel queP(m)soit vraie. Soitn∈Ntel qu’il existe une applicationϕ:N m+1 →N n injective. er 1cas :Supposonsϕ(m+ 1)=n. Alorsϕ(N m )⊆N n−1 , donc nous disposons d’une application injective ψ:N m →N n−1 x7→ϕ(x) et par l’hypothèse de récurrence nous concluons quem6n−1c’estàdirem+ 16n. ème 2cas :Supposonsϕ(m+ 1) =εavecε6=n. Posonsτla transposition définie par : τ:N n →N n 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:N m+1 →N m+1 dé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 toutm∈N. 2. Soitϕ:N m →N n une application surjective. −1 Soitk∈N n . Puisqueϕest surjective, l’ensembleϕ({k})n’est pas vide. D’après la propriété (1), 3−1 nous pouvons donc noterf(k)∈N m le plus petit élémentdeϕ({k}). Nous disposons alors d’une application f:N n →N m x7→f(x) ′ ′−1 qui est injective; en effet, sik, k∈N n sont tels quef(k) =f(k), nous en déduisons queϕ({k})∩ −1′ ′ ϕ({k})6=∅; c’estàdire qu’il existex∈N n tel 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 ∗ n∈Net une bijection tel queϕ:E→N n . 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 ununiqueentiern∈N −1 tel queEsoit équipotent àN n ; en effet, siψ:E→N m est une autre bijection, alorsψ◦ϕest une bijection deN n surN m , 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ϕ:E→N n , on "numérotera" l’ensembleE, c’estàdire que l’on noteraE={x 1 , x 2 , . . . , x n }. Cette notation signifie que pouri∈N n , −1 x i :=ϕ(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 etF⊆Eun 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ϕ:N n →Ebijective. Quitte à composerϕpar un transposition comme dans la preuve du lemme 3, nous pouvons supposer queϕ(1) =ω. Nous posons alors : ψ:N n →N n l’application définie par :ψ(1) = 1et par récurrence pourk∈ {1, . . . , n−1};ψ(k+ 1)=ψ(k)si ϕ(k+ 1)6∈Fetψ(k+ 1) =ψ(k) + 1siϕ(k+ 1)∈F. Posons alorsm:=ψ(n). Soitk∈N m . Sik= 1, on poseg(1) := 1et si26k6m, nous constatons que{j∈N n |ψ(j) =k}est une partie non vide de N n ; notonsg(k)son plus petit élément. Nous avons alors une applicationΨdéfinie par : Ψ :N m →F 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, k∈N m tels que ′4′′ ′ Ψ(k) = Ψ(k)alorsg(k) =g(k)ce qui imposek=ψ(g(k)) =ψ(g(k)) =k. Soit maintenant 5 6 y∈F. Soitj∈N n tel queϕ(j) =y. Alorsψ(j−1)< ψ(j)doncg(ψ(j)) =jet par suite 3−1 en particulier,f(k)∈ϕ({k}) 4 ϕest injective. 5 cary∈F. 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:E→Einjective ; ′′ ′′ 3. ilexiste un ensemble finiEet une applicationg:E→Esurjective ; 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 g◦f=Id E . 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:E→Etelle queg◦f= ′ Id E . 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 : ′ Ψ :E→E x7→f(x) 

Proposition 7SoientA, Bdeux parties finies d’un ensembleE. AlorsA∪BetA∩Bsont des ensembles finis et |A∪B|=|A|+|B| − |A∩B|(2) preuve: SiAouBest∅, tout est clair. Supposons queA6=∅etB6=∅. Notonsn:=|A|etm:=|B| ∗ (n, m∈N). Nous pouvons donc écrireA={a 1 , . . . , a n }etB={b 1 , . . . , b m }. er 1cas :Supposons queA∩B=∅. Posons alors l’application ϕ:A∪B→N n+m isix∈Aetx=a i x7→ n+jsix∈Betx=b j Il est alors clair queϕ; ce qui prouve d’une part queest bijectiveA∪Best fini et d’autre part la formule (2). ème 2cas :SupposonsA∩B6=∅. Nous écrivons alors d’une partA∪B=A∪(B\(A∩B))et d’autre partB= (A∩B)∪(B\A), les réunions étant disjointes. D’après le lemme 5 nous savons queA∩B etB\(A∩B); nous pouvons donc appliquer le premier cas, pour trouver :sont des ensembles finis |A∪B|=|A|+|B\(A∩B)| |B|=|A∩B|+|B\(A∩B)| ce qui permet de conclure.

Corollaire 8Soit(A i ) i∈I une famille finie de sousensembles finis d’un ensembleE. Supposons que 2 pour tout couple(i, j)∈Itel quei6=jnous ayonsA i ∩A j =∅. Alors [ X A i =|A i |   i∈I i∈I

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(A i ) i∈I une 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 choisiri 0 ∈I. Considérons alors la sousfamille 7 (A i ) I∈I\{i 0 } . Le cardinal deI\ {i 0 }estndonc nous pouvons appliquer l’hypothèse de récurrence 2 en remarquant que pour tout couple(i, j)∈(I\ {i 0 })tel quei6=jnous avonsA i ∩A j =∅. Ainsi P   ∪A=|A|. Maintenant en posantB:=∪AetB:=A, il apparaît que i∈I\{i 0 } i i ∈I\{i 0 } i0 i∈I\{i 0 } i1i 0 la famille(B i ) i∈{0,1} est une famille qui vérifieB 0 ∩B 1 =∅. Donc puisque la propriété est vraie au rang2, nous concluons que [ A i =|B 0 ∪B 1 |   i∈I =|B 0 |+|B 1 | [ =A i +|A i 0 |   i∈I\{i 0 } X =|A i |+|A i 0 | i∈I\{i 0 } X =|A i | i∈I 

Corollaire 9SoientE,Fdeux ensembles finis. Alors |E×F|=|E| ∙ |F| preuve: ÉcrivonsE={x 1 , . . . , x n }etF={y 1 , . . . , y m }. Nous pouvons supposer quem6n. Posons ϕ:E×F→N (n+ 1)m (x, y)7→j(n+ 1) +isix=x i ety=y j  Cette application est injective doncE×Fest un ensemble fini. Maintenant la famille{(x i , y)|y∈  S F}vérifie les hypothèses de la proposition précédente et bien sûr{(x i , y)|y∈F}= 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=∅. PourA⊆E, nous notonsϕ A la 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 ϕ := {x∈E|ϕ(x) = 1}. Il est alors clair queΦ(A ϕ ) =ϕ. Maintenant en écrivantE={x 1 , . . . , x n }, nous posons n Ψ :F(E,{0,1})→ {0,1}   ϕ7→ϕ(x 1 ), . . . , ϕ(x n ) 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 etF⊆Ealors |F|6|E|.

Lemme 11SoitEun ensemble fini etF⊆E. 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=F∪FavecF6=∅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:E→Fune 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:N n →N n . (1.⇒2.) Supposonsfinjective. Notons f 0 :N n →f(N n ) x7→f(x) fest une bijection etf 0 (N n ) =f(N n )est un ensemble fini grâce au lemme 5 donc|f(N n )|=|N n |. Nous concluons d’après le lemme 11 quef(N n ) =N n . ′ ′′ (2.⇒3.) Supposons quefn’est pas injective. Il existe alorsk, k∈Ntels quek6=ketf(k)6=f(k). Donc l’application ′ f 0 :N n \ {k} →N n x7→f(x) 8′ est encore surjective. Mais comme|N n \ {k}|=n−1, d’après le lemme 3 nous trouvonsn6n−1; c’est absurde. (3.⇒1.) C’est immédiat.

8 ici nous utilisons la proposition précédente