b) Caractérisations
Soit E un ensemble.
Fiche 15 • Combinatoire et dénombrement
• S'il existe u ne injection de E dans N, alors E est au plus dénombrable.
• S'il existe u ne surjection de N sur E, alors E estt au plus dénombrable.
c) Propriétés
1. Toute partie infinie A de N est en bijection avec N.
2. N est en bijection avec N 2 .
3. Le produit cartésien d' une famille finie d'ensembles dénombrables (respectivement au pl us
dénombrables) est dénombrable (respectivement au plus dénombrable).
4. La réunion d' une famille finie d'ensembles au plus dénombrables est au plus dénombrable.
Si l' un des ensembles de la famille finie est
dénombrables) est dénombrable (respectivement au plus dénombrable).
6. N, Z, Q N 2 , N",11 ;;. I, Q(X) sont dénombrables.
7. nt, C , P(N), jO, l fN, NN ne sont pas au plus dénombrables.
3. ENSEMBLE FINI ET CARDINAL
a) Définitions
• Ensemble fini
Un ens emble E est fini s'il est vide ou s'il existe un entier naturel non nul /1 et une bijection de
[ 1;11) dans E.
• Cantinai d ' nn ens emble
Si E * 0, /1 est appelé cantina i de E, noté indifféremment Card (E) ou IEI. Par convention
Card(0) =O.
b) Propriétés des cardinaux
1. Soit E un ensemble fini. Si Fest un ensemble tel qu 'il existe une bijection de E dans F,
alors Fest un ensemble fini et Card (F) = Card (E).
2. Soit E un ensemble fini. Toute partie A de E est finie et Card (A) .;; Card (E). Une partie A
de E est égale à E si et seulement si le cardinal de A est égal à celui de E.
3. Soit A et 8deux parties d' un ensemble fini E et Ac le complémentaire de A dans E.
a . Si A et 8 sont disjointes, Card (A u 8) = Card (A)+ Card (8).
b. Card (A \ 8) = Card (A) - Card (A n 8).
c. Card (A') = Card (E) - Card (A).
d. Card (A U 8) = Card (A) + Card (8) - Card (A n 8).
e. Card (AM)= Card (A)+ Card (8) - 2Card (An 8).
4. Formule dn cr ible on de Po incaré. Si (A;) 1 '°"~" est une famille de parties de lensemble
fini E, alors nous avons:
37
Soit E un ensemble.
Fiche 15 • Combinatoire et dénombrement
• S'il existe u ne injection de E dans N, alors E est au plus dénombrable.
• S'il existe u ne surjection de N sur E, alors E estt au plus dénombrable.
c) Propriétés
1. Toute partie infinie A de N est en bijection avec N.
2. N est en bijection avec N 2 .
3. Le produit cartésien d' une famille finie d'ensembles dénombrables (respectivement au pl us
dénombrables) est dénombrable (respectivement au plus dénombrable).
4. La réunion d' une famille finie d'ensembles au plus dénombrables est au plus dénombrable.
Si l' un des ensembles de la famille finie est
dénombrables) est dénombrable (respectivement au plus dénombrable).
6. N, Z, Q N 2 , N",11 ;;. I, Q(X) sont dénombrables.
7. nt, C , P(N), jO, l fN, NN ne sont pas au plus dénombrables.
3. ENSEMBLE FINI ET CARDINAL
a) Définitions
• Ensemble fini
Un ens emble E est fini s'il est vide ou s'il existe un entier naturel non nul /1 et une bijection de
[ 1;11) dans E.
• Cantinai d ' nn ens emble
Si E * 0, /1 est appelé cantina i de E, noté indifféremment Card (E) ou IEI. Par convention
Card(0) =O.
b) Propriétés des cardinaux
1. Soit E un ensemble fini. Si Fest un ensemble tel qu 'il existe une bijection de E dans F,
alors Fest un ensemble fini et Card (F) = Card (E).
2. Soit E un ensemble fini. Toute partie A de E est finie et Card (A) .;; Card (E). Une partie A
de E est égale à E si et seulement si le cardinal de A est égal à celui de E.
3. Soit A et 8deux parties d' un ensemble fini E et Ac le complémentaire de A dans E.
a . Si A et 8 sont disjointes, Card (A u 8) = Card (A)+ Card (8).
b. Card (A \ 8) = Card (A) - Card (A n 8).
c. Card (A') = Card (E) - Card (A).
d. Card (A U 8) = Card (A) + Card (8) - Card (A n 8).
e. Card (AM)= Card (A)+ Card (8) - 2Card (An 8).
4. Formule dn cr ible on de Po incaré. Si (A;) 1 '°"~" est une famille de parties de lensemble
fini E, alors nous avons:
37