RPRobin PourtaudTokyo · près de l’eau
Retourner au courant
Mathématiques3 min de lecture

Montrer qu'un ensemble est dénombrable

A l'aide d'un exemple, nous allons montrer une méthode classique permettant de démontrer qu'un ensemble est dénombrable.

FR

Définition :

Un ensemble est dit dénombrable s’il existe une bijection (une application bijective) entre cet ensemble et l’ensemble des entiers naturels.

Ici nous utilisons la définition des ensembles dénombrables de Cantor. Nous considérons qu’un ensemble dénombrable est donc infini. Une seconde définition considère qu’il faut montrer qu’il existe une bijection entre une partie de l’ensemble des entiers naturels et cet ensemble.

La méthode

En guise d’exemple, démontrons que Z\mathbb{Z} est dénombrable.

Exposons une application bijective

Tout d’abord, cherchons instinctivement à associer chaque élément de Z\mathbb{Z} à N\mathbb{N}.

Dans notre cas, l’idée est la suivante :

  • Les nombres négatifs de Z\mathbb{Z} correspondent aux nombres impairs de N\mathbb{N}.
  • Les nombres positifs de Z\mathbb{Z} correspondent aux nombres pairs de N\mathbb{N}.

Nous avons donc :

f(x)={2xsi  x≥0−2x−1sinon.f(x) =\begin{cases}2x&\text{si}\; x\geq 0\cr-2x-1 &\text{sinon.}\end{cases}

Montrons que ff est une application bijective de Z\mathbb{Z} dans N\mathbb{N}.

Il existe bien sûr d’autres applications bijectives entre N\mathbb{N} et Z\mathbb{Z}. Ceci n’est qu’un exemple qui fonctionne.

Montrons que f est une fonction

ff est une fonction si tout élément de l’ensemble de départ est associé à, au maximum, un élément de l’ensemble d’arrivée.

Les deux cas de la définition sont disjoints et couvrent tous les entiers. Pour chaque x∈Zx\in\mathbb Z, une seule formule s’applique et produit une unique image : ff est donc une fonction.

Montrons que f est une application

ff est une application si tout élément de l’ensemble de départ possède une image par ff. Si ff est une application, alors son domaine de définition est donc égal à son ensemble de départ.

Le domaine de définition de ff est Z\mathbb Z : la première branche couvre les entiers x≥0x\geq0 et la seconde les entiers x<0x<0. Comme ces deux cas sont disjoints et exhaustifs, ff est définie sur tout son ensemble de départ.

Montrons que f est injective

f:X→Yf:X\rightarrow Y est une application injective si : ∀x,y∈X  (f(x)=f(y)⇒x=y)\forall x,y \in X \; (f(x) = f(y) \Rightarrow x = y)

Nous avons plusieurs cas à prendre en compte :

  • Si x et y sont positifs : f(x)=f(y)⇒2x=2y⇒x=yf(x) = f(y) \Rightarrow 2x = 2y \Rightarrow x = y (Injection OK)

  • Si x et y sont négatifs : f(x)=f(y)⇒−2x−1=−2y−1⇒x=yf(x) = f(y) \Rightarrow -2x - 1 = -2y - 1 \Rightarrow x=y (Injection OK)

  • Si l’un des deux est négatif et l’autre positif ou nul : l’une des images est impaire et l’autre paire. Elles ne peuvent donc pas être égales.

ff est donc injective.

Montrons que f est surjective

f:X→Yf: X \rightarrow Y est une application surjective si : ∀y∈Y  ∃x∈X  f(x)=y\forall y \in Y \; \exists x \in X \; f(x)=y

Autrement dit, tout élément de YY possède au moins un antécédent par ff.

Soit y∈Ny\in\mathbb N. Si yy est pair, il existe q∈Nq\in\mathbb N tel que y=2qy=2q, et f(q)=yf(q)=y. Si yy est impair, il existe q∈Nq\in\mathbb N tel que y=2q+1y=2q+1 ; en prenant x=−(q+1)x=-(q+1), on obtient f(x)=−2x−1=2q+1=yf(x)=-2x-1=2q+1=y.

Ainsi, tout y∈Ny\in\mathbb N possède un antécédent dans Z\mathbb Z. Donc Im⁡(f)=N\operatorname{Im}(f)=\mathbb N et ff est surjective.

Conclusion :

ff est bien une application bijective de Z\mathbb{Z} dans N\mathbb{N}. Z\mathbb{Z} est donc dénombrable.

Source :