Ensembles finis (1/2)

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}} :

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}.

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.

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}} sur {A}.

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}.

Une partie {A} non vide de {\mathbb{N}} est finie {\Leftrightarrow} elle est majorée. En particulier {\mathbb{N}} est infini!

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}.

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.

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.