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 dans le cas contraire que E est infini.    Explication Idée fondamentale du chapitre : 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 et qu’ainsi E et F ont le même « nombre d’éléments ». On pourrait aussi parler des ensembles infinis avec cette idée, mais ce n’est pas au programme et c’est plus compliqué — cf. le paragraphe « Equipotence » du chapitre « Injections, surjections, bijections ». 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. Par convention, l’ensemble vide est de cardinal 0. Hélas il se pourrait bien, à ce stade, qu’un ensemble fini possède plusieurs cardinaux ! Le théorème suivant montre que non. Théorème (Unicité du cardinal) (i) Soient m, n ∈N∗. S’il existe une bijection de J1, mK sur J1, nK, alors m = n. (ii) Soit E un ensemble fini. Il existe un et un seul cardinal de E, noté |E| (ou card E ou #E). Démonstration (i) Pour tout n ∈N∗, nous allons montrer par récurrence la proposition Pn : « pour tout m ∈N∗, s’il existe une bijection de J1, mK sur J1, nK, alors m = n ». Initialisation : Facile. Hérédité : Soit n ∈N∗. On suppose Pn vraie, qu’en est-il de Pn+1 ? Soit m ∈N∗. Faisons l’hypothèse qu’il existe une bijection f de J1, mK sur J1, n + 1K. Il s’agit de montrer que m = n + 1. • Premier cas : f(m) = n + 1. b b b b b m m −1 m −2 2 1 . . . f b b b b b n + 1 n n −1 2 1 . . .                Alors f J1,m−1K est bijective de J1, m−1K sur J1, nK, donc m−1 = n par hypothèse de récurrence, et enfin m = n + 1. • Deuxième cas : f(m) ̸= n + 1. Posons a = f −1(n + 1) et b = f(m) et notons τ la transposition (b n + 1) de Sn+1. b b b b m . . . a 2 1 . . . f b b b b n + 1 . . . b 2 1 . . . τ b b b b n + 1 . . . b 2 1 . . . La composée τ◦f est alors bijective de J1, mK sur J1, n + 1K et envoie m sur n + 1. Nous sommes ainsi ramenés au cas précédent. (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, donc aussitôt m = n d’après (i). ■ 1 c ⃝Christophe Bertault - MPSI Exemple Soient m, n ∈Z tels que m ⩽n. Alors Jm, nK est fini de cardinal n −m + 1. En effet La fonction k 7− →k + m −1 est bijective de J1, n −m + 1K sur Jm, nK de réciproque k 7− →k −m + 1. Théorème Soient E et F deux ensembles. Si E est fini et s’il existe une bijection de E sur F, alors F est fini et |E| = |F|. Démonstration Si E est vide, alors F l’est aussi. Supposons donc E non vide, et puisque E est fini, donnons- nous une bijection g de q 1, |E| y sur E. Par hypothèse il existe par ailleurs une bijection de E sur F, disons f. Alors f ◦g est une bijection de q 1, |E| y sur F donc F est fini et, par unicité du cardinal, |F| = |E|. ■ Théorème (Parties d’un ensemble fini) Soient E un ensemble fini et A une partie de E. Alors A est finie et |A| ⩽|E|. De plus A = E si et seulement si |A| = |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 |A| = |B|. Démonstration Pour tout n ∈N∗, nous allons montrer par récurrence la proposition Pn : « pour tout ensemble fini E de cardinal n et toute partie A de E, A est finie et |A| ⩽|E|, et de plus A = E si et seulement si |A| = |E| ». • Initialisation : Facile. • Hérédité : Soit n ∈N. On suppose Pn vraie, qu’en est-il de Pn+1 ? Soient E un ensemble fini de cardinal n + 1 et A une partie de E. Nous pouvons supposer A ̸= E et nous donner du coup un élément ω de E \ A. Par hypothèse, il existe une bijection f de J1, n + 1K sur E. Quitte à composer f par une transposition de J1, n + 1K, nous pouvons même supposer que f(n + 1) = ω, et donc en particulier que f(n + 1) / ∈A. b b b b b n + 1 n n −1 2 1 . . . f E A b ω Alors f J1,nK est bijective de J1, nK sur E \  ω , donc en particulier E \  ω est de cardinal n, et comme A est une partie de E \  ω , |A| ⩽n < n + 1 = |E|. Au passage, l’inégalité stricte prouve l’implication « |A| = |E| = ⇒ A = E ». ■ 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 |E| ⩽|F|. Si de plus |E| = |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 |F| ⩽|E|. Si de plus |E| = |F|, f est en fait bijective de E sur F. (iii) Si E et F sont finis de même cardinal : 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′), i.e. que deux points distincts dans E sont envoyés par f sur deux points distincts de F. Cela veut dire aussi que f(E) est comme une copie de E dans F. Une telle copie n’est possible que si F est assez gros, en l’occurrence « plus gros » que E, i.e. si |E| ⩽|F|. • L’assertion (iii) vous rappelle certainement un théorème du chapitre « Es- paces 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érati- vement besoin de la condition « dim E = dim F », on a dans le cas présent besoin de la condition « |E| = |F| ». E F Im f b b x f(x) f f est injective, Im f est comme une copie de E à l’intérieur de F. 2 c ⃝Christophe Bertault - MPSI Démonstration (i) Supposons f injective de E sur F. Comme f(E) est une partie de F, f(E) est fini et f(E) ⩽|F|. Or f est bijective de E sur son image f(E), donc la finitude de f(E) implique celle de E et de plus f(E) = |E|. Finalement : |E| ⩽|F|. (ii) Supposons f surjective de E sur F et donnons-nous ϕ une bijection de q 1, |E| y sur E. Alors f ◦ϕ est surjective de q 1, |E| y sur F par composition, donc nous pouvons nous donner pour tout y ∈F un antécédent µ(y) de y par f ◦ϕ dans q 1, |E| y . Nous héritons ainsi d’une application µ de F dans q 1, |E| y , injective car pour tous y, y′ ∈F tels que µ(y) = µ(y′) : y = f ◦ϕ µ(y)  = f ◦ϕ µ(y′)  = y′. Aussitôt, d’après (i), F est fini et |F| ⩽|E|. (iii) Supposons E et F finis de même cardinal. Alors bien sûr, si f est uploads/Philosophie/ cours-ensembles-finis-et-denombrement-34.pdf

Tags
Philosophieensemble alors bijection cardinal éléments
Documents similaires
  • 28
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager