Nombresentiersnaturels –Combinatoire
COURS
9
2.3 • Notions sur les cardinaux desensembles infinis
ATTENTION
Pour lese nsembles infinis, les points
4) et 5) du corollaire 2.1 ne sontplus
vérifiés :ilpeut exister une application
d’un ensemble infini dans lui-même
qui soit injective sans être surjective,
et réciproquement.
Exemple :
L’application
N → N
n → 2n
est
injective, mais pas surjective. Une inverse àgauche de cette application (en
imaginer une) est surjective, mais pas
injective.
IMPORTANT
Ce paragraphe est hors programme. Il
est donné àtitre documentaire.
Un ensemble qui n’est pas fini estd it infini.Lem athématicien allemand Georg
Cantor ae ul ’idée d’étendre aux ensembles infinis les définitions précédentes, et
de continuer àdire que, pour tous ensembles E et F :
• Card E = Card F , s’il existe une bijection de E dans F .
Exemple:Si P estl’ensemble des entiers naturels pairs,
Card P = Card N, car l’application
N → P
n
→ 2n
est bijective (N alemême
cardinal qu’une de ses parties strictes, ce qui serait impossible pour un ensemble
fini...).
• Card E Card F , s’il existe une injection de E dans F .
Exemple: Card N Card R (penser àl’injection canonique de N dans R).
Cantor démontra les résultats suivants :
• Card N = Card Z = Card Q (ensembles dénombrables);
• Card R = Card C = Card R
n
(ensemblesayant la puissance du continu),
maisque Card N
= Card R.
3 Dénombrement
Voyons concrètement comment calculer le cardinald ’un ensemble construit sur
des ensembles finis donnés.
3.1 • Partie d’un ensemblefini
Théorème 3
Toutepartie A d’un ensemble fini E est finie et Card A Card E.
Démonstration
Soit n = Card E. Il existe une bijection f de [[ 1 , n ]] dans E. La partie A
est l’image par cette bijection d’une partie I de [[ 1 , n ]] qui est finie, de cardinal
p n (cf. exemples d’ensembles finis). Il existe donc une bijection de I dans A,
ce qui prouve que A est finie et Card A = Card I = p n.
3.2 • Réunion disjointe
Théorème 4
Si E et F sont deux ensembles finis disjoints (E ∩ F = ∅), E ∪ F est fini
et Card(E∪F)=Card E +Card F .
Hachette Livre –HPrépa /Math –Laphotocopie non autorisée est un délit
171
COURS
9
2.3 • Notions sur les cardinaux desensembles infinis
ATTENTION
Pour lese nsembles infinis, les points
4) et 5) du corollaire 2.1 ne sontplus
vérifiés :ilpeut exister une application
d’un ensemble infini dans lui-même
qui soit injective sans être surjective,
et réciproquement.
Exemple :
L’application
N → N
n → 2n
est
injective, mais pas surjective. Une inverse àgauche de cette application (en
imaginer une) est surjective, mais pas
injective.
IMPORTANT
Ce paragraphe est hors programme. Il
est donné àtitre documentaire.
Un ensemble qui n’est pas fini estd it infini.Lem athématicien allemand Georg
Cantor ae ul ’idée d’étendre aux ensembles infinis les définitions précédentes, et
de continuer àdire que, pour tous ensembles E et F :
• Card E = Card F , s’il existe une bijection de E dans F .
Exemple:Si P estl’ensemble des entiers naturels pairs,
Card P = Card N, car l’application
N → P
n
→ 2n
est bijective (N alemême
cardinal qu’une de ses parties strictes, ce qui serait impossible pour un ensemble
fini...).
• Card E Card F , s’il existe une injection de E dans F .
Exemple: Card N Card R (penser àl’injection canonique de N dans R).
Cantor démontra les résultats suivants :
• Card N = Card Z = Card Q (ensembles dénombrables);
• Card R = Card C = Card R
n
(ensemblesayant la puissance du continu),
maisque Card N
= Card R.
3 Dénombrement
Voyons concrètement comment calculer le cardinald ’un ensemble construit sur
des ensembles finis donnés.
3.1 • Partie d’un ensemblefini
Théorème 3
Toutepartie A d’un ensemble fini E est finie et Card A Card E.
Démonstration
Soit n = Card E. Il existe une bijection f de [[ 1 , n ]] dans E. La partie A
est l’image par cette bijection d’une partie I de [[ 1 , n ]] qui est finie, de cardinal
p n (cf. exemples d’ensembles finis). Il existe donc une bijection de I dans A,
ce qui prouve que A est finie et Card A = Card I = p n.
3.2 • Réunion disjointe
Théorème 4
Si E et F sont deux ensembles finis disjoints (E ∩ F = ∅), E ∪ F est fini
et Card(E∪F)=Card E +Card F .
Hachette Livre –HPrépa /Math –Laphotocopie non autorisée est un délit
171