Cours - Ensembles Finis Et Denombrement

c Christophe Bertault - MPSI

Ensembles finis et dnombrement

Dfinition (Ensemble fini/infini) Soit E un ensemble. On dit que E est fini sil est vide ou si, pour un certain n N, ilexiste une bijection de lensemble J1, nK sur E ; on dit sinon que E est infini.

Explication Ce chapitre est intgralement dirig par une ide : lide selon laquelle une bijection de E sur F tablitune correspondance parfaite entre les lments de E et les lments de F ; cest la manire quont trouv les mathmaticienspour dcrire la taille, le nombre dlments des ensembles appel cardinal. Cette thorie nous permettrait de parler aussi desensembles infinis si nous le voulions, mais cela nest pas au programme et cest plus compliqu.

1 Cardinal dun ensemble fini

Dfinition (Cardinal dun ensemble fini) Soit E un ensemble fini non vide. On appelle cardinal de E ou nombre dlmentsde 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 quon note : card() = 0.

Thorme (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|).

Dmonstration

(i) Rsultat admis.

(ii) Soient m et n deux cardinaux de E, i.e. deux entiers naturels non nuls pour lesquels existent une bijectionf : J1,mK E et une bijection g : J1, nK E. Alors g1 f est une bijection de J1,mK sur J1, nK, etaussitt m = n via lassertion (i).

Exemple Soient m,n Z tels que m 6 n. Alors Jm,nK est fini et card Jm,nK = nm+ 1.

En effet Soit f lapplication

J1, nm+ 1K Jm,nKk 7 k +m 1

. Cette application est bijective car lappli-

cation

Jm,nK J1, nm+ 1Kk 7 k m+ 1

en est la rciproque. Cela montre bien le rsultat voulu.

Thorme Soient E et F deux ensembles. On suppose que E est fini et quil existe une bijection de E sur F . Alors F est finiet card E = card F .

Dmonstration Si E est vide, le rsultat est immdiat car F est alors vide lui aussi. Supposons donc que Enest 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 , conformment lhypothse du thorme. Alors f g est une bijection deJ1, card EK sur F , donc en effet F est fini, et card F = card E par unicit du cardinal.

Thorme (Parties dun ensemble fini) Soient E un ensemble fini et A une partie de E.Alors A est finie et card A 6 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 dun ensemble E sont gales, au lieu de montrer queA B et que B A, on peut se contenter de montrer, grce au thorme prcdent, que A B et que card A = card B. Cetteremarque est trs utile dans certains contextes.

1

c Christophe Bertault - MPSI

Dmonstration Rcurrence sur n = card E.

Initialisation : Pour n = 0, E est vide, et donc A aussi. Ainsi A = E et il ny a rien montrer.

Hrdit : Soit n N. On suppose que pour tout ensemble fini E de cardinal n et toute partie A de E, Aest finie telle que card A 6 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 6= E.

Cette preuve tant abstraite, donnons-en rapidement lide. Partant dune bijection f de J1, n + 1K surE, nous allons restreindre celle-ci lensemble J1, nK. Nous rcuprerons ainsi une bijection de J1, nK sur

E = Ern

f(n+1)o

, ce qui montrera en particulier que card E = n. Nous esprons ainsi pouvoir appliquer

lhypothse de rcurrence lensemble E, mais pour que cela nous parle de A, il faut tre sr davoir A E.Or cela nest vrai que si f(n+1) / A. La question pertinente est donc la suivante : peut-on toujours choisirf de faon avoir f(n+ 1) / A ?

1) Montrons quil existe une bijection f de J1, n+ 1K sur E telle que f(n+ 1) / A.Ce qui est vrai en tout cas, cest quil 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 6= E, il existeun lment E extrieur A. Dfinissons alors lapplication f : J1, n+ 1K E en posant :

k J1, n+ 1K, f(k) =

8