Exercices cardinalité

On note N l'ensemble des entiers naturels. Par dénombrable, on entend infini dénombrable.

Exercice 1

Rappeler les définitions informelles puis formelles d'injection, de surjection et de bijection.
Donner un exemple et un contre-exemple pour chaque cas.
Montrer en détail que l'ensemble des entiers naturels 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.

Soient :

E un ensemble avec égalité décidable (i.e., un algorithme pour l'égalité entre deux éléments de E) et
h une bijection de N vers E elle aussi définie par un algorithme.

Déterminer un algorithme pour l'application h^-1, en argumentant sa correction partielle et sa terminaison.

Montrer que l'ensemble des parties de N (noté 2^N) n'est pas dénombrable.
Montrer que l'ensemble des fonctions totales de N vers N n'est pas dénombrable.
Montrer que l'ensemble des réels compris entre 0 largement et 1 strictement n'est pas dénombrable.

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, appelons la φ, de NxN vers N.
Combien vaut φ(n,0) ? Et φ(a,b) ? Déterminer une expression algébrique de φ.
Proposer un algorithme pour son inverse φ^-1.
Soit k un entier ≥ 1. Montrer que N^k est dénombrable en proposant une bijection nommée φ_k.
Montrer que N* (l'ensemble des suites finies d'entiers naturels) est dénombrable en proposant une bijection nommée φ^*.