Ensembles finis (1/2)

⇧ ① 2

Ensembles finis

R. Contexte

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]

P. Applications entre E_n et E_p

On se donne ici deux éléments

{n}

{p}

{\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. 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.

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

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

P. Parties finies de ℕ

Une partie

{A}

non vide de

{\mathbb{N}}

est finie

{\Leftrightarrow}

elle est majorée. En particulier

{\mathbb{N}}

est infini!

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

P. Bijections et ensembles 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.

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.

Calcul de quelques cardinaux

Ce contenu nécessite une souscription active

E. Exercices conseillés

⇧ ① 2