BURHAN.

Cardinal d'un ensemble fini : Cours de Mathématiques 1BAC Sciences Mathématiques, chapitre Dénombrement

Cardinal d'un ensemble fini : notion du chapitre Dénombrement du programme de maths 1BAC SM, expliquée pas à pas, avec 3 exemples guidés. Pour les élèves de 1BAC Sciences Mathématiques, option française (BIOF).

Notions du cours (10)

Apprendre avec Burhan

Ensembles finis, cardinal

Étape 1 sur 4

Numéroter pour compter

En clair. Pour compter les élèves d'une file, tu les numérotes : 11, 22, 33… Le dernier numéro donne leur nombre. Numéroter sans oubli ni répétition, c'est fabriquer une bijection entre {1,2,…,n}\{1, 2, \dots, n\} et l'ensemble compté. Par exemple, k↦2kk \mapsto 2k numérote les entiers pairs de 22 à 2020 : il y en a 1010. Rappel : une bijection est une application à la fois injective et surjective (chapitre « Ensembles et applications »). À toi de numéroter.

Devine : Numéroter des multiples

Combien d'éléments l'ensemble E={3,6,9,…,30}E = \{3, 6, 9, \dots, 30\} des multiples de 33 compris entre 33 et 3030 possède-t-il ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :3030

Faux.

3030 est le plus grand élément de EE, pas le nombre de ses éléments.

Choix B :1010

Juste.

Juste : 3k3k parcourt EE quand kk parcourt {1,2,…,10}\{1, 2, \dots, 10\}.

Choix C :2727

Faux.

30−3=2730 - 3 = 27 est l'écart entre le plus grand et le plus petit élément, pas leur nombre.

Choix D :99

Faux.

30−33=9\dfrac{30 - 3}{3} = 9 oublie le premier élément : il faut ajouter 11.

Voir la correction complète

On numérote les éléments de EE : le kk-ième est 3k3k. L'application k↦3kk \mapsto 3k, de {1,2,…,10}\{1, 2, \dots, 10\} dans EE, est une bijection : sa réciproque est x↦x3x \mapsto \dfrac{x}{3}. Donc EE a 1010 éléments.

Continuer : Cardinal ; une bijection le conserve →

Étape 2 sur 4

Cardinal ; une bijection le conserve

DéfinitionEnsemble fini, cardinal

Soit EE un ensemble et n∈N∗n \in \mathbb{N}^{*}. On dit que EE est fini de cardinal nn s'il existe une bijection de {1,2,…,n}\{1, 2, \dots, n\} sur EE : on peut numéroter les éléments de EE sous la forme x1,x2,…,xnx_1, x_2, \dots, x_n, deux à deux distincts. On note alors card(E)=n\mathrm{card}(E) = n, le cardinal de EE, c'est-à-dire son nombre d'éléments. Ce nombre ne dépend pas de la numérotation choisie : c'est le premier point d'un résultat admis, énoncé plus loin.

L'ensemble vide est fini, de cardinal 00 : card(∅)=0\mathrm{card}(\varnothing) = 0. Un ensemble qui n'est pas fini est dit infini.

Deux ensembles reliés par une bijection ont le même nombre d'éléments. Pourquoi est-ce vrai ? Une numérotation de EE, suivie de la bijection, numérote FF. La preuve vérifie que cette composée est encore une bijection.

Deux ensembles dessinés en patates, E à gauche et F à droite, reliés par une flèche nommée f au-dessus. E contient x₁, x₂, x₃ et x₄. F contient leurs images f(x₁), f(x₂), f(x₃) et f(x₄). Quatre flèches vont chacune d'un élément de E vers son image : aucun élément de F ne reçoit deux flèches, aucun n'en reçoit zéro. Les éléments de F se trouvent ainsi numérotés de 1 à 4 à leur tour.

Exemple avec quatre éléments : la bijection f fait correspondre à chaque élément numéroté de E un seul élément de F, et chaque élément de F est atteint une fois.

PropriétéCardinal et bijection

Soit EE un ensemble fini et FF un ensemble. S'il existe une bijection de EE sur FF, alors FF est fini et card(F)=card(E)\mathrm{card}(F) = \mathrm{card}(E).

Démonstration

Étape 1. Si E=∅E = \varnothing, une bijection de EE sur FF est surjective, donc FF n'a aucun élément : F=∅F = \varnothing, et les deux cardinaux valent 00.

Étape 2. Sinon, soit n=card(E)n = \mathrm{card}(E), φ\varphi une bijection de {1,2,…,n}\{1, 2, \dots, n\} sur EE (définition du cardinal) et ff une bijection de EE sur FF. La composée f∘φf \circ \varphi est une bijection de {1,2,…,n}\{1, 2, \dots, n\} sur FF, car la composée de deux bijections est une bijection (chapitre « Ensembles et applications »).

Étape 3. D'après la définition du cardinal, FF est fini et card(F)=n=card(E)\mathrm{card}(F) = n = \mathrm{card}(E).

À retenirCe qu'il faut retenir de la preuve

Pour transporter un cardinal, on compose : une numérotation de EE, puis la bijection de EE sur FF. Le résultat numérote FF avec les mêmes numéros. C'est ton premier outil : pour compter un ensemble inconnu, mets-le en bijection avec un ensemble que tu sais compter.

Vérifie : Quel résultat sert à l'étape 2 ?

Dans la preuve, quel résultat du chapitre « Ensembles et applications » permet de dire que f∘φf \circ \varphi est une bijection ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :La réciproque d'une bijection est une bijection.

Faux.

La preuve n'utilise aucune réciproque : elle compose φ\varphi, puis ff.

Choix B :L'image directe de EE par ff est incluse dans FF.

Faux.

Une inclusion ne dit rien sur l'injectivité ni sur la surjectivité.

Choix C :Une récurrence sur le cardinal de EE.

Faux.

La preuve ne fait aucune récurrence : une seule composée suffit.

Choix D :La composée de deux bijections est une bijection.

Juste.

Juste : φ\varphi et ff sont deux bijections, donc leur composée aussi.

Voir la correction complète

À l'étape 2, φ\varphi va de {1,2,…,n}\{1, 2, \dots, n\} sur EE, et ff va de EE sur FF. Ce sont deux bijections. D'après le chapitre « Ensembles et applications », leur composée f∘φf \circ \varphi est une bijection de {1,2,…,n}\{1, 2, \dots, n\} sur FF.

← Étape précédenteContinuer : Un cardinal bien défini →

Étape 3 sur 4

Un cardinal bien défini

ExempleExemple et contre-exemple

  • Soit FF l'ensemble des entiers pairs de 22 à 2424. L'application k↦2kk \mapsto 2k va de {1,2,…,12}\{1, 2, \dots, 12\} dans FF. Elle est bijective, de réciproque y↦y2y \mapsto \dfrac{y}{2}. Donc card(F)=12\mathrm{card}(F) = 12.
  • L'hypothèse compte. L'application x↦x2x \mapsto x^{2}, de {−2,−1,1,2}\{-2, -1, 1, 2\} dans {1,4}\{1, 4\}, est surjective mais pas injective : (−1)2=12(-1)^{2} = 1^{2}. Et les cardinaux diffèrent : 44 au départ, 22 à l'arrivée.

Une question reste ouverte. Si l'on numérote un ensemble de deux façons, trouve-t-on deux fois le même nombre d'éléments ? Et une partie d'un ensemble fini est-elle finie ? La réponse est oui. Ce n'est pas une évidence : on l'admet, et l'on s'en sert dans tout le chapitre.

PropriétéUnicité du cardinal ; parties d'un ensemble fini

  • Le cardinal d'un ensemble fini est bien défini : si nn et mm sont deux entiers naturels non nuls et s'il existe une bijection de {1,2,…,n}\{1, 2, \dots, n\} sur EE et une bijection de {1,2,…,m}\{1, 2, \dots, m\} sur EE, alors n=mn = m.
  • Toute partie d'un ensemble fini est un ensemble fini.

RemarqueAdmis

Ce résultat est admis. Sa preuve demande une récurrence plus fine, qui dépasse ce chapitre.

Exempleune partie d'un ensemble fini

L'ensemble P={2,3,5,7}P = \{2, 3, 5, 7\} des nombres premiers inférieurs à 1010 est une partie de {1,2,…,10}\{1, 2, \dots, 10\}. D'après ce résultat, PP est fini, et l'on compte ses éléments : card(P)=4\mathrm{card}(P) = 4. Grâce à l'unicité, ce nombre ne dépend pas de l'ordre dans lequel tu les comptes.

← Étape précédenteContinuer : Dénombrer par une bijection →

Étape 4 sur 4

Dénombrer par une bijection

Méthodedénombrer par une bijection

  1. Nommer l'ensemble FF à compter, en disant précisément quels sont ses éléments.
  2. Choisir un ensemble EE que tu sais compter, et une application de EE vers FF (ou de FF vers EE).
  3. Prouver qu'elle est bijective : injectivité et surjectivité, ou réciproque écrite explicitement.
  4. Conclure que FF et EE ont le même cardinal, en citant le résultat sur les bijections.

ExempleExemple guidé : les codes à deux chiffres

Énoncé. Soit CC l'ensemble des codes à deux chiffres, de 0000 à 9999. Montrons que card(C)=100\mathrm{card}(C) = 100.

Bijection. À l'entier k∈{1,2,…,100}k \in \{1, 2, \dots, 100\}, associons le code qui écrit k−1k - 1 avec deux chiffres. Par exemple, 11 donne 0000 et 5858 donne 5757.

Réciproque explicite. Au code de chiffres dd puis uu, associons 10d+u+110d + u + 1, qui est entre 11 et 100100. Les deux applications se défont l'une l'autre, dans les deux sens : la première est une bijection.

Conclusion. D'après le résultat sur les bijections, card(C)=100\mathrm{card}(C) = 100.

À toi : Les entiers impairs

Soit II l'ensemble des entiers impairs de 11 à 3939. Construis une bijection de {1,2,…,20}\{1, 2, \dots, 20\} sur II, et déduis-en card(I)\mathrm{card}(I). Écris ta réponse avant de dévoiler la correction.

Besoin d'aide ? Indice 1

Le premier impair est 11, le deuxième est 33 : quelle formule donne le kk-ième ?

Encore bloqué ? Indice 2

Essaie k↦2k−1k \mapsto 2k - 1, puis exprime kk en fonction de l'impair yy.

Encore bloqué ? Indice 3

Point délicat : vérifie que l'image de chaque kk est bien dans II, et que y+12\dfrac{y + 1}{2} est bien entre 11 et 2020.

Voir la solution complète

Soit φ:k↦2k−1\varphi : k \mapsto 2k - 1. Pour 1≤k≤201 \leq k \leq 20, 2k−12k - 1 est impair et 1≤2k−1≤391 \leq 2k - 1 \leq 39 : φ(k)∈I\varphi(k) \in I.

Soit ψ:y↦y+12\psi : y \mapsto \dfrac{y + 1}{2}. Pour y∈Iy \in I, y+1y + 1 est pair et 2≤y+1≤402 \leq y + 1 \leq 40, donc ψ(y)∈{1,2,…,20}\psi(y) \in \{1, 2, \dots, 20\}.

De plus, ψ(φ(k))=k\psi\big(\varphi(k)\big) = k et φ(ψ(y))=y\varphi\big(\psi(y)\big) = y. Donc φ\varphi est une bijection, de réciproque ψ\psi. D'après le résultat sur les bijections, card(I)=20\mathrm{card}(I) = 20.

← Étape précédenteFin de la notion

S'entraîner sur cette notion

Sources du cours

  • Référentiel BURHAN du chapitre « Dénombrement » (1bac · sciences-mathematiques · mathematiques)