c ⃝Christophe Bertault - MPSI Ensembles finis et dénombrement Définition (Ensemb
c ⃝Christophe Bertault - MPSI Ensembles finis et dénombrement Définition (Ensemble fini/infini) Soit E un ensemble. On dit que E est fini s’il est vide ou si, pour un certain n ∈N×, il existe une bijection de l’ensemble J1, nK sur E ; on dit sinon que E est infini. Explication Ce chapitre est intégralement dirigé par une idée : l’idée selon laquelle une bijection de E sur F établit une correspondance parfaite entre les éléments de E et les éléments de F ; c’est la manière qu’ont trouvé les mathématiciens pour décrire la taille, le nombre d’éléments des ensembles — appelé cardinal. Cette théorie nous permettrait de parler aussi des ensembles infinis si nous le voulions, mais cela n’est pas au programme — et c’est plus compliqué. 1 Cardinal d’un ensemble fini Définition (Cardinal d’un ensemble fini) Soit E un ensemble fini non vide. On appelle cardinal de E ou nombre d’éléments de E tout entier n ∈N× pour lequel il existe une bijection de J1, nK sur E. On convient que le vide est de cardinal 0, ce qu’on note : card(∅) = 0. Théorème (Unicité du cardinal) (i) Soient m, n ∈N. Il existe une bijection de J1, mK sur J1, nK si et seulement si m = n. (ii) Soit E un ensemble fini. Il existe un et un seul cardinal de E, noté card E (ou #E ou |E|). Démonstration (i) Résultat admis. (ii) Soient m et n deux cardinaux de E, i.e. deux entiers naturels non nuls pour lesquels existent une bijection f : J1, mK − →E et une bijection g : J1, nK − →E. Alors g−1 ◦f est une bijection de J1, mK sur J1, nK, et aussitôt m = n via l’assertion (i). ■ Exemple Soient m, n ∈Z tels que m ⩽n. Alors Jm, nK est fini et card Jm, nK = n −m + 1. En effet Soit f l’application J1, n −m + 1K − → Jm, nK k 7− → k + m −1 . Cette application est bijective car l’appli- cation Jm, nK − → J1, n −m + 1K k 7− → k −m + 1 en est la réciproque. Cela montre bien le résultat voulu. Théorème Soient E et F deux ensembles. On suppose que E est fini et qu’il existe une bijection de E sur F. Alors F est fini et card E = card F. Démonstration Si E est vide, le résultat est immédiat car F est alors vide lui aussi. Supposons donc que E n’est pas vide, et puisque E est fini, donnons-nous une bijection g de J1, card EK sur E. Soit alors f une bijection de E sur F, conformément à l’hypothèse du théorème. Alors f ◦g est une bijection de J1, card EK sur F, donc en effet F est fini, et card F = card E par unicité du cardinal. ■ Théorème (Parties d’un ensemble fini) Soient E un ensemble fini et A une partie de E. Alors A est finie et card A ⩽card E. De plus A = E si et seulement si card A = card E. En pratique Pour montrer que deux parties finies A et B d’un ensemble E sont égales, au lieu de montrer que A ⊆B et que B ⊆A, on peut se contenter de montrer, grâce au théorème précédent, que A ⊆B et que card A = card B. Cette remarque est très utile dans certains contextes. 1 c ⃝Christophe Bertault - MPSI Démonstration Récurrence sur n = card E. • Initialisation : Pour n = 0, E est vide, et donc A aussi. Ainsi A = E et il n’y a rien à montrer. • Hérédité : Soit n ∈N. On suppose que pour tout ensemble fini E de cardinal n et toute partie A de E, A est finie telle que card A ⩽card E, et que de plus A = E si et seulement si card A = card E. Donnons-nous alors E un ensemble fini de cardinal (n + 1) et A une partie de E. Si A = E, tout va bien. Supposons donc A ̸= E. Cette preuve étant abstraite, donnons-en rapidement l’idée. Partant d’une bijection f de J1, n + 1K sur E, nous allons restreindre celle-ci à l’ensemble J1, nK. Nous récupérerons ainsi une bijection de J1, nK sur E′ = E ∖ n f(n+1) o , ce qui montrera en particulier que card E′ = n. Nous espérons ainsi pouvoir appliquer l’hypothèse de récurrence à l’ensemble E′, mais pour que cela nous parle de A, il faut être sûr d’avoir A ⊆E′. Or cela n’est vrai que si f(n + 1) / ∈A. La question pertinente est donc la suivante : peut-on toujours choisir f de façon à avoir f(n + 1) / ∈A ? 1) Montrons qu’il existe une bijection f de J1, n + 1K sur E telle que f(n + 1) / ∈A. Ce qui est vrai en tout cas, c’est qu’il existe une bijection f de J1, n + 1K sur E, puisque card(E) = n + 1. Si f(n+ 1) / ∈A, nous sommes heureux. Supposons au contraire que f(n+ 1) ∈A. Comme A ̸= E, il existe un élément ω ∈E extérieur à A. Définissons alors l’application ˜ f : J1, n + 1K − →E en posant : ∀k ∈J1, n + 1K, ˜ f(k) = 8 < : f(k) si f(k) ̸= ω et k ̸= n + 1 ; ω si k = n + 1 ; f(n + 1) si f(k) = ω. En somme, ˜ f et f sont identiques à ceci près qu’on a échangé leurs valeurs ω / ∈A et f(n + 1) ∈A. Vous montrerez seuls, proprement, que ˜ f est bijective de J1, n + 1K sur E. Comme ˜ f(n + 1) = ω / ∈A, on a montré ce qu’on voulait montrer. 2) Conformément au point précédent, nous pouvons nous donner f une bijection de J1, n + 1K sur E telle que f(n + 1) / ∈A. Posons alors E′ = E ∖ n f(n + 1) o . Comme voulu, A est une partie de E′ car f(n + 1) / ∈A. Nous allons montrer que E′ est de cardinal n pour pouvoir lui appliquer notre hypothèse de récurrence. Or la restriction de f à J1, nK induit une bijection de J1, nK sur E′, par construction. Cela montre que E′ est fini de cardinal n. Par hypothèse de récurrence, A est donc un ensemble fini et de plus on a les inégalités card A ⩽card E′ = n < n + 1 = card E. Au passage, nous venons de montrer par contraposition l’implication « card A = card E = ⇒ A = E » grâce à l’inégalité stricte précédente. ■ Théorème (Injectivité, surjectivité et ensembles finis) Soient E et F deux ensembles et f : E − →F une application. (i) Si f est injective et si F est fini, alors E aussi est fini et card E ⩽card F. Si de plus card E = card F, f est en fait bijective de E sur F. (ii) Si f est surjective et si E est fini, alors F aussi est fini et card F ⩽card E. Si de plus card E = card F, f est en fait bijective de E sur F. (iii) Si E et F sont finis de même cardinal, on a l’équivalence suivante : f est bijective ⇐ ⇒ f est injective ⇐ ⇒ f est surjective. Explication • Tâchons de comprendre intuitivement l’assertion (i). Dire que f est injective, c’est dire que pour tous x, x′ ∈E, si x ̸= x′ alors f(x) ̸= f(x′). En français, ceci signifie que deux points distincts dans E sont envoyés par f sur deux points distincts de F. Ainsi f transporte les points de E dans F sans en faire disparaître aucun, sans qu’aucun se retrouve au même endroit qu’aucun autre. Dit autrement, ceci veut dire que f crée une copie de E dans F. Or une telle copie n’est possible que si F est « plus gros » que E, que s’il y a dans F assez de place pour accueillir une copie de E. Voilà pourquoi card E ⩽card F. E f(E) F b b b b b b f injective • Faites l’effort de comprendre intuitivement l’assertion (ii) tout comme nous venons de comprendre l’assertion (i). • L’assertion (iii) vous rappelle certainement un théorème du chapitre « Espaces vectoriels de dimension finie » que nous avons beaucoup aimé car il était très utile et facile à manipuler. De même qu’on avait alors impérativement besoin de la condition « dim E = dim F », on a dans le cas présent besoin de la condition « card E = card F ». 2 c ⃝Christophe Bertault - MPSI Démonstration (i) Supposons uploads/Marketing/ cours-ensembles-finis-et-denombrement.pdf
Documents similaires
-
44
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Oct 28, 2022
- Catégorie Marketing
- Langue French
- Taille du fichier 0.1525MB