Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours ensembles finis et denombrement 34

c Christophe Bertault - MPSI Ensembles ?nis et dénombrement Dé ?nition Ensemble ?ni in ?ni Soit E un ensemble On dit que E est ?ni s ? il est vide ou si pour un certain n ?? N ? il existe une bijection de l ? ensemble n sur E On dit dans le cas contraire que E est in ?ni 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 in ?nis 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 ? Cardinal d ? un ensemble ?ni Dé ?nition Cardinal d ? un ensemble ?ni Soit E un ensemble ?ni 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 n sur E Par convention l ? ensemble vide est de cardinal Hélas il se pourrait bien à ce stade qu ? un ensemble ?ni 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 m sur n alors m n ii Soit E un ensemble ?ni 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 m sur n alors m n ? Initialisation Facile Hérédité Soit n ?? N ? On suppose Pn vraie qu ? en est-il de Pn Soit m ?? N ? Faisons l ? hypothèse qu ? il existe une bijection f de m sur n Il s ? agit de montrer que m n ? Premier cas f m n F FC m ?? f n ?? F F F F F F F F F F F F F FD Alors f est bijective de m ?? sur n donc m ?? n m ?? F F F FEF F F F F F F F F F par hypothèse de récurrence et en ?n m n m ?? n m n ? Deuxième cas f m n Posons a f ?? n et b f m et notons la transposition b n de Sn La composée f est alors bijective de m sur n et envoie m sur n Nous f sommes ainsi ramenés au cas précédent a b b m n n ii Soient m et n deux cardinaux de E i e deux entiers naturels non nuls pour lesquels existent une bijection f m ?? ? E et