À toute partie A de N, on attribue la fonction σ_A : N → N définie comme suit : pour tout k N, σ_A (2k) = 2k et σ_A(2k + 1) = 2k + 1 si k A, et σ_A(2k) = 2k + 1 et σ_A (2k + 1) = 2k sinon ; elle vérifie évidemment σ = id_N et c’est donc une permutation de N.

Notons que pour tout A ⊂ N, on retrouve A = {k N : σ_A(2k) = 2k}, si bien que la fonction A (N) σ_A 𝔖(N) est injective. Par suite, si 𝔖(N) était fini ou dénombrable alors (N) le serait également.

On conclut que 𝔖(N) est indénombrable puisque, classiquement, (N) est indénombrable. Ce résultat dernier ne figurant pas explicitement au programme, redémontrons-le. Pour toute fonction f : N → (N), l’ensemble A := {n N : n ⁄ f(n)} est hors de l’image de f (en effet si c’était l’image d’un entier k par f on aurait k A si et seulement si k f(k) ce qui contredirait la définition de A), si bien que f n’est pas surjective. Comme (N) est évidemment non vide, la conclusion s’ensuit.

Il existe une bijection σ : N → Q ; la fonction φ 𝔖(N)σ • φ • σ^-1 𝔖(Q) est alors clairement une bijection. Il suffit donc de montrer que 𝔖(Q) est indénombrable. Pour cela, il suffit de construire une injection de R dans 𝔖(Q), l’indénombrabilité - connue - de R impliquant alors celle de 𝔖(Q).

Soit x un réel. Les ensembles Q := {y Q : y ≥ x} et Q := {y Q : y < x} sont évidemment infinis, donc dénombrables car ils sont inclus dans Q qui est dénombrable. Il existe donc une bijection g_x : Q → Q. On peut alors définir une permutation (involutive) f_x : Q → Q par la formule f_x (y) = g_x(y) si y Q, et f_x(y) = g(y) sinon. On notera en particulier que f_x (y) < y si y Q, et f_x(y) > y sinon.

Montrons pour finir que x Rf_x est injective. Soit a < b dans R. Par densité de Q dans R, il existe un rationnel y dans . Alors g_a(y) < y et g_b(y) > y, donc g_a≠g_b. Cela achève la démonstration.

[Liste des corrigés]