Cardinal d’un ensemble fini

Plan du chapitre "Dénombrements"

Pour tout entier naturel, on note {E_n=[[ 1,n]]=\{m\in\mathbb{N},1\le m\le n\}} (et donc {E_{0}=\emptyset}).

La fonction Python E ci-contre renvoie la liste ordonnée des éléments de {E_{n}} :

>>> def E(n) : return list(range(1,n+1))>>> E(10)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Proposition (existence d'injections, de surjections, de bijections, entre E_{n} et E_{p})
On se donne ici deux éléments {n} et {p} de {\mathbb{N}^{*}}.

  • il existe une injection de {E_n} dans {E_p} si et seulement si {n\le p}.
  • il existe une surjection de {E_n} sur {E_p} si et seulement si {n\ge p}.
  • il existe une bijection de {E_n} sur {E_p} si et seulement si {n=p}.

Démonstration
 Vous devez être abonné(e) et connecté(e) au site pour voir ce contenu 
Définition (notion d'ensemble fini)
Un ensemble non vide {A} est dit fini s’il existe une bijection de {E_n} sur {A}, avec {n\ge0}.
L’entier {n}, s’il existe, est unique et est appelé le cardinal de {A}. On note {n=\text{card}(A)}.
En particulier {\text{card}(\emptyset)=0}. Un ensemble non fini est dit infini.

Démonstration
 Vous devez être abonné(e) et connecté(e) au site pour voir ce contenu 

Notation :
le cardinal d’un ensemble fini {A} est également noté {\left|A\right|}, ou {\#A}.

On peut dire que {E_{n}=[[0,n-1]]} est l’ensemble “modèle” de tout ensemble fini de cardinal {n} (un peu comme {\mathbb{K}^{n}} est le modèle des espaces vectoriels de dimension {n}).

La bijection {f:E_{n}\to A} représente une “numérotation” des éléments de {A}. Cette numérotation est exhaustive (surjectivité de {f}), et à deux indices différents {i} et {j} correspondent deux éléments différents {a_{i}} et {a_{j}} de {A} (c’est l’injectivité de {f}).

Intuitivement, l’entier {\text{card}(A)} représente le “nombre d’éléments” de {A} (conformément au programme de la classe de MPSI, on en reste d’ailleurs le plus souvent à cette formulation intuitive).

Si {m\le n}, l’intervalle {A=[[ m,n]]} est fini de cardinal {n-m+1}. En effet l’application {f} définie par {f(k)=k+m-1} est bijective de {E_{n-m+1}=[[1,n-m+1]]} sur {A}.

Proposition (ensemble en bijection avec un ensemble fini)
Soit {A} un ensemble fini. S’il existe une bijection de {A} sur {B}, alors {B} est fini et {\text{card}(B)=\text{card}(A)}.
Réciproquement, si {B} est fini de même cardinal que {A}, il existe une bijection de {A} sur {B}.
Démonstration
 Vous devez être abonné(e) et connecté(e) au site pour voir ce contenu 

On peut caractériser les parties finies de {\mathbb{N}} :

Proposition (parties finies de ℕ)
Une partie {A} non vide de {\mathbb{N}} est finie {\Leftrightarrow} elle est majorée.
En particulier {\mathbb{N}} est infini.
Démonstration
 Vous devez être abonné(e) et connecté(e) au site pour voir ce contenu 

On en déduit le résultat suivant :

Proposition (cardinal d'une partie d'un ensemble fini)
Soit {A} un ensemble fini et {B} une partie de {A}.
Alors {B} est un ensemble fini et {\text{card}(B)\le\text{card}(A)}.
Plus précisément, on a {\text{card}(B)=\text{card}(A)} si et seulement si {B=A}.
Démonstration
 Vous devez être abonné(e) et connecté(e) au site pour voir ce contenu 
Proposition (bijection entre deux ensembles finis de même cardinal)
Soit {A,B} deux ensembles finis de même cardinal. Soit {f} une application de {A} dans {B}.
Alors {f} est bijective si et seulement si elle est injective, et si et seulement si elle est surjective.
Démonstration
 Vous devez être abonné(e) et connecté(e) au site pour voir ce contenu 

Si {E} est infini, il existe des applications de {E} dans {E} qui sont injectives et non surjectives, ou surjectives et non injectives. Par exemple, l’application {n\mapsto2n} est injective et non surjective de {\mathbb{N}} dans lui-même, et l’application {n\mapsto\lfloor n/2\rfloor} est surjective et non injective..

Page suivante : calculs de quelques cardinaux usuels