Ensembles dénombrables

Plan du chapitre "Dénombrements"
Définition (ensemble dénombrable)
Un ensemble {E} est dit dénombrable s’il existe une bijection de {\mathbb{N}} sur {E}.

Remarques

  • Les ensembles suivants sont, de façon évidente, dénombrables : l’ensemble {\mathbb{N}} lui-même, l’intervalle d’entiers {[[ a,\infty[} pour tout {a} de {\mathbb{Z}} (penser à l’application {n\mapsto a+n}), l’ensemble des entiers pairs (avec l’application {n\mapsto 2n}) et celui des entiers impairs (avec l’application {n\mapsto 2n+1}).
  • Soit {E} un ensemble dénombrable.
    Un ensemble {F} est en bijection avec {E} si et seulement si il est lui-même dénombrable.
  • Un ensemble dénombrable est infini.
    La réciproque est fausse : l’ensemble {\mathbb{R}} est infini mais n’est pas dénombrable (voir plus loin).
Proposition (les parties de ℕ sont finies ou dénombrables)
Toute partie de {\mathbb{N}} est soit finie, soit dénombrable.
Plus généralement toute partie d’un ensemble dénombrable est soit finie, soit dénombrable.
Démonstration
  Pour voir ce contenu, vous devez : 
Proposition (caractérisation des ensembles finis ou dénombrables)
Soit {E} un ensemble. Les deux propositions suivantes sont équivalentes :
— l’ensemble {E} est fini ou dénombrable;
— il existe une application surjective de {\mathbb{N}} sur {E};
Ainsi {E} est fini ou dénombrable {\iff} on peut le décrire “en extension” : {E=\{x_{n},\; n\in\mathbb{N}\}}.

Remarque : dans cette proposition, on peut remplacer {\mathbb{N}} par un ensemble dénombrable connu.

Démonstration
  Pour voir ce contenu, vous devez : 

Remarque : un ensemble {E} est fini ou dénombrable si on peut l’écrire {E=\{x_{n},\; n\in J\}}, où {J} est une partie de {\mathbb{N}} et où les {x_{n}} sont distincts deux à deux.

Proposition (l'ensemble ℤ est dénombrable)
L’ensemble {\mathbb{Z}} des entiers relatifs est dénombrable.
Démonstration
  Pour voir ce contenu, vous devez : 
Proposition (produit cartésien de deux ensembles dénombrables)
L’ensemble {\mathbb{N}\times\mathbb{N}} est dénombrable.
Plus généralement, si {E} et {F} sont dénombrables, alors {E\times F} est dénombrable.
Démonstration
  Pour voir ce contenu, vous devez : 
Proposition (non dénombrabilité de l'ensemble des suites à valeurs dans {0,1})
L’ensemble {\{0,1\}^{\mathbb{N}}} de toutes les suites à valeurs dans {\{0,1\}} n’est pas dénombrable.
Démonstration
  Pour voir ce contenu, vous devez : 
Proposition (non dénombrabilité de l'ensemble des réels)
L’ensemble {\mathbb{R}} est infini non dénombrable.
Démonstration
  Pour voir ce contenu, vous devez : 

Unions et intersections indicées par {\mathbb{N}}

Soit {(A_{n})_{n\in\mathbb{N}}}, une suite de parties d’un ensemble {E}.

On pose {\displaystyle\bigcap_{n=0}^{+\infty}A_n\displaystyle\bigcup_{n=0}^{+\infty}A_n=\displaystyle\bigcup_{n\in\mathbb{N}}A_{n}=\{x\in E,\;\exists\, n\in\mathbb{N},\;x\in A_{n}\}\;}.

De même, on note {\displaystyle\bigcap_{n=0}^{+\infty}A_n=\displaystyle\bigcap_{n\in\mathbb{N}}A_{n}=\{x\in E,\;\forall\, n\in\mathbb{N},\;x\in A_{n}\}}.

L’avantage des notations {\displaystyle\bigcup_{n\in\mathbb{N}}A_{n}} et {\displaystyle\bigcap_{n\in\mathbb{N}}A_{n}} est qu’elles font mieux ressortir que l’union ou l’intersection des {A_{n}} ne dépendent pas de l’ordre dans lequel on les énumère.

Avec ces notations, on a alors les propriétés suivantes :

  • Passage au complémentaire : {\;\overline{\displaystyle\bigcup_{n\in\mathbb{N}}A_{n}}=\displaystyle\bigcap_{n\in\mathbb{N}}\overline{A_{n}}\;} et {\;\overline{\displaystyle\bigcap_{n\in\mathbb{N}}A_{n}}=\displaystyle\bigcup_{n\in\mathbb{N}}\overline{A_{n}}\;}.
  • Distributivité : pour toute partie {B} de {E}, on a : {B\cap\Bigl(\displaystyle\bigcup_{n\in\mathbb{N}}A_{n}\Bigr)=\displaystyle\bigcup_{n\in\mathbb{N}}\bigl(B\cap A_{n}\bigr)\;\text{et}\;B\cup\Bigl(\displaystyle\bigcap_{n\in\mathbb{N}}A_{n}\Bigr)=\displaystyle\bigcap_{n\in\mathbb{N}}\bigl(B\cup A_{n}\bigr)}
  • Union croissante, et intersection décroissante :

    On pose {\;C_{n}=\displaystyle\bigcup_{0\le k\le n}A_{k}\;} et {\;D_{n}=\displaystyle\bigcap_{0\le k\le n}A_{k}\;}.

    Alors {\;\displaystyle\bigcup_{n\in\mathbb{N}}A_{n}=\displaystyle\bigcup_{n\in\mathbb{N}}C_{n}\;\;\text{et}\;\;\displaystyle\bigcap_{n\in\mathbb{N}}A_{n}=\displaystyle\bigcap_{n\in\mathbb{N}}D_{n}}.

    Démonstration
      Pour voir ce contenu, vous devez : 

Page précédente : p-listes et combinaisons
Retour au début : cardinal d’un ensemble fini