Exercices cardinalité

Exercice 1

  1. Rappeler les définitions informelles (par exemple graphiques) puis formelles d'injection, de surjection et de bijection. Donner deux exemples significatifs pour chaque cas.
  2. Montrer en détail que l'ensemble des entiers naturels (noté N) impairs est dénombrable.
  3. Montrer en détail que l'ensemble des entiers relatifs est dénombrable.
  4. Montrer en détail tout sous-ensemble infini d'un ensemble dénombrable est dénombrable. Application : montrer que l'ensemble des entiers premiers est dénombrable.

Exercice 2

  1. Montrer que l'ensemble des fonctions totales de N vers N n'est pas dénombrable.
  2. Montrer que l'ensemble des rééls compris entre 0 largement et 1 strictement n'est pas dénombrable.

Exercice 3

On se propose d'énumérer les éléments de NxN par somme croissante, puis en cas de somme identique, par ordre décroissant sur la première coordonnée.
  1. Visualiser sur le plan et justifier informellement que l'on tient bien une bijection de NxN vers N.
  2. Déterminer une expression algébrique de cette bijection. Proposer un algorithme pour son inverse.
  3. Soit k un entier ≥ 1. Montrer que Nk est dénombrable.
  4. Montrer que N* (l'ensemble des suites finies d'entiers naturels) est dénombrable.

Exercice 4

  1. On énumère les mots librement construits sur Σ={a,b} comme suit : ε est étiqueté 0, a 1, b, 2, aa 3, ab 4, ba 5, bb 6, aaa 7, etc. Donner le code de la procédure mot(in : N, out : W) où W est la représentation du N-ième mot sur Σ*.
    Donner le code de la procédure réciproque indice(in : W, out : N).
  2. Généraliser pour un alphabet non vide de cardinal donné.