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
 Pour voir ce contenu, vous devez avoir souscrit au site
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
 Pour voir ce contenu, vous devez avoir souscrit au site

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
 Pour voir ce contenu, vous devez avoir souscrit au site

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
 Pour voir ce contenu, vous devez avoir souscrit au site

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
 Pour voir ce contenu, vous devez avoir souscrit au site
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
 Pour voir ce contenu, vous devez avoir souscrit au site

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