Exercices cardinalité
Exercice 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.
- Montrer en détail que l'ensemble des entiers naturels (noté N) impairs est dénombrable.
- Montrer en détail que l'ensemble des entiers relatifs est dénombrable.
- 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
- Montrer que l'ensemble des fonctions totales
de N vers N n'est pas dénombrable.
- 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.
- Visualiser sur le plan et justifier
informellement que l'on tient bien une bijection de NxN vers N.
- Déterminer une expression algébrique de cette bijection.
Proposer un algorithme pour son inverse.
- Soit k un entier ≥ 1. Montrer que Nk est dénombrable.
- Montrer que N* (l'ensemble des suites finies d'entiers naturels)
est dénombrable.
Exercice 4
- 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)
.
- Généraliser pour un alphabet non vide de cardinal donné.