Cardinal d'un ensemble

Comment montrer que \(\mathbb Z\)est dénombrable ?

\(\mathbb Z\) contient \(\mathbb N\)comme sous-ensemble, donc sa puissance est au moins celle des entiers naturels.

\(\mathbb Z\) peut être construit en établissant une relation d'équivalence sur les couples d'entiers positifs : \((a, b)\) est équivalent au couple \((c, d)\) si \(a + d = b + c.\) Chaque classe d'équivalence représente un entier relatif : la classe d'un entier positif \(n\) admet un représentant du type \((n, 0)\) et pour l'entier négatif \(- n\) un représentant \((0, n).\)

On peut ranger ces éléments en une suite de la façon suivante :

\((0, 0),~ (1, 0),~ (0, 1),~ (2, 0),~ (0, 2), ~\dots, (n, 0), ~(0, n), ~\dots\)

Cela montre que le cardinal de \(\mathbb Z\)est égal à \(\mathcal N_0,\) cardinal de \(\mathbb N.\)

La démonstration de la dénombrabilité de \(\mathbb Q\)fut faite par Cantor en 1874.

Comme l'ensemble \(\mathbb Q\)contient l'ensemble des entiers, le cardinal de cet ensemble est au moins \(\mathcal N_0.\)

Il est facile de voir d'après la démonstration précédente que si l'ensemble des nombres rationnels positifs \(\mathbb Q_+^*\)est dénombrable, l'ensemble \(\mathbb Q\)l'est aussi.

L'ensemble \(\mathbb Q_+^*\)peut être construit en établissant une relation d'équivalence sur l'ensemble des couples d'entiers relatifs \((a, b)\) avec \(a\in\mathbb N,\) \(b\in\mathbb N\) et \(b\neq 0\) :

\((a, b) \sim (c, d)\) si et seulement si \(a d = b c.\)

Ceci est la façon mathématique d'exprimer que des "fractions égales" représentent le même nombre rationnel qui admet donc pour représentants une infinité de couples (numérateur, dénominateur).

\(\mathbb Q_+^*\)est en bijection avec une partie de l'ensemble des couples, donc que son cardinal est inférieur ou égal à celui des couples d'entiers. On peut ranger ces couples d'entiers \((a,b),\) pour \(a\in\mathbb N^*\) et \(b\in\mathbb N^*,\) en une suite de la façon suivante. On range dans la première ligne les couples de premier terme 1 suivant l'ordre croissant du deuxième terme. Dans la deuxième ligne, les couples de premier terme 2, etc.

\((1, 1) (1, 2) (1, 3) (1, 4) (1, 5) \dots\\(2, 1) (2, 2) (2, 3) (2, 4) (2, 5)\dots\\(3, 1) (3, 2) (3, 3) (3, 4) (3, 5)\dots\\(4, 1) (4, 2) (4, 3) (4, 4) (4, 5)\dots\)

Ensuite on range tous les couples en les numérotant suivant des diagonales de ce tableau. Cela donne l'ordre :

\((1, 1), ~(1, 2), ~(2, 1), ~(1, 3), ~(2, 2), ~(3, 1),\dots\)

L'ensemble des couples d'entiers positifs est donc dénombrable. Donc\(\mathbb Q\) l'est aussi.

L'ensemble des nombres algébriques est l'ensemble des racines de polynômes à coefficients entiers. Pour un tel polynôme,

\(P = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n\)

nous définissons un entier positif appelé sa hauteur :

\(h(P) = n - 1 + | a_0 | + | a_1 | + | a_2 | + \dots + | a_n |\)

Avec un peu de réflexion, on voit qu'il n'existe qu'un nombre fini de polynômes de hauteur \(h.\) Chacun de ces polynômes n'a qu'un nombre fini de racines. Pour ranger tous les nombres algébriques en une suite, on commence à ranger les polynômes en une suite, en utilisant leur hauteur et en rangeant arbitrairement les polynômes (en nombre fini) qui ont une hauteur donnée. Pour chacun de ces polynômes, on range ses racines par le même procédé. On fabrique donc une suite formée de tous les nombres algébriques. L'ensemble des nombres algébriques est donc contenu dans une réunion dénombrable d'ensembles finis, cela permet de montrer que l'ensemble des nombres algébriques est dénombrable.