Dénombrabilité de suites rationnelles presque nulles
Hier lors d’une séance de préparation à l’agrégation interne j’ai posé la question suivante:
L’ensemble \({\mathbb Q}^{({\mathbb N})}\) des suites suites rationnelles qui sont nulles à partir d’un certain rang est-il dénombrable?
Ce n’est pas un exercice difficile et il y a une preuve ensembliste très classique. J’étais surpris par un candidat qui a proposé une solution originale à laquelle je ne m’attendais pas. Je la donnerai ici sur ce blog mais d’abord j’aimerais connaître les preuves que vous feriez.
Je partirai du fait que l’ensemble des rationnels est dénombrables \({\mathbb Q}=\{q_0;q_1;q_2;\dots\}\) donc à chaque suite de rationnels nulle à partir d’un certain rang \(u=(q_{i_0},q_{i_1},q_{i_2},\dots,q_{i_n},0,0,\dots )\) je peux associer un entier en classant les dites suites suivant l’ordre "lexicographique" sur les n-uplets de la forme \((i_0,i_1,i_2,\dots,i_n)\) ce qui construit une injection (et même une bijection!) de cet ensemble vers \(\mathbb N\).
Je dirais que oui, il est dénombrable.
Si l’on définit \(E_n\) comme l’ensemble des suites rationnelles qui sont nulles à partir du rang n, alors cet ensemble est dénombrable car \(E_n \sim \mathbb{Q}^n \) et \(\mathbb{Q}\) est dénombrable. Il y a ensuite une bijection claire entre les \( E_n \) et \(\mathbb{N}\).
Je serais curieux d’entendre la démonstration originale !
@Philippe : je ne comprends pas « associer un entier en classant… ». Peux-tu expliciter davantage stp?
@MrAlabar : Oui, En est dénombrable, mais En n’est pas \({\mathbb Q}^{({\mathbb N})}\). Je dois avouer que mon énoncé n’est pas assez clair; en fait, le rang n’est pas fixé en avance.
Pour continuer la preuve de MrAlabar, il suffit de considerer une réunion dénombrable des ensembles dénombrables $E_n$.
Comme MrAlabar, je dirais qu’une union dénombrable d’ensembles dénombrables est dénombrable. Donc \(\bigcup_n \mathbf Q^n\) (qui s’identifie à \(\mathbf Q^{(\mathbf N)}\)) est dénombrable.
Oui, vous donnez le même preuve que je propose habituellement dans mon cours.
Voici l’idée que l’étudiant (ou plutôt collègue puisqu’il s’agit de l’agreg interne) avait et que nous avons formalisée après le cours parce qu’elle ne marchait pas toute de suite. On définit une injection de \(\mathbb{Q}^{(\mathbb{N})}\) dans \(\mathbb N\) par le codage suivant. Une suite rationnelle stationnaire s s’écrit sous la forme
\(s=\left(\frac{a_0}{a_1}\,,\:\frac{a_2}{a_3}\,,\:\ldots\,\:\frac{a_{2n}}{a_{2n+1}}\,,\:0\,,\:\ldots\right).\)
où les \(a_k\) sont dans \(\mathbb Z\) et les \(b_k\) dans \(\mathbb N\). Autrement dit, la suite s est entièrement codée par les nombres entiers
\((a_0,a_1,a_2,a_3,\ldots,a_{2n},a_{2n+1})\).
Problème: Comment coder ce (2n+2)-uplet par un seul entier? On a envie de procéder par concaténation, mais le problème est que par exemple les suites (2/3,13/5,0,…) et (2/31,3/5,0,…) seraient toutes les deux codés par 23135.
Remède: on note \(\alpha_k\) la notation binaire de la valeur absolu de \(a_k\). On associe à la suite s l’entier naturel suivant en base de 10:
\(*\,\alpha_0*\alpha_1*\alpha_2*\alpha_3\cdots*\alpha_{2n}*\alpha_{2n+1},\)
où l’étoile devant \(\alpha_k\) vaut 2 si \(a_k\geq0\) et 3 si \(a_k<0\). Par exemple, la suite \((\frac14,\frac23,\frac{-7}{10},0,\ldots)\) est codée par l'entier
212100210211311121010.
Remarque: Les deux preuves, la conventionnelle et l’alternative se généralisent facilement à l’ensemble de suites rationnelles stationnaires.
Question: On appelle suite rationnelle finie une application s de N dans Q telle que s(N) est un ensemble fini. L’ensemble de telles suites est-il dénombrable?
J’aime bien les codages à la Gödel utilisant la suite ordonnée des nombres premiers pour coder une suite finie d’entiers (a(i), i < n se code en somme (p(i)^a(i), i de à n) – désolé je ne maîtrise pas latex :/ ).
Pour la dernière question posée, si je ne me trompe pas, cet ensemble n’est pas dénombrable : il contient entre autre le sous-ensemble des suites formées de seulement 0 et 1, qui, à lui seul, a la puissance du continu (puisque [0, 1] s’y injecte – on conclut par Cantor-Bernstein).
Oui, Kliban a trouvé la bonne réponse à la dernière question, puisque tout nombre réel dans [0,1] admet une écriture en base deux de la forme .
Concernant le codage de Gödel dont parle Kliban: ça ne devrait pas être plutôt le produit des p(i)^a(i) ?
A la Gödel :
A la suite (\(\epsilon_ia_i/b_i\)) j’associe \(2^n\prod p_{2i}^{a_i}p_{2i+1}^{b_i}\) où les \(p_i\) sont les nombres premiers (et donc en nombre fini puisque la suite l’est)
\(n\) étant défini à l’aide des signe \(\epsilon_i\) par exemple en binaire.
On peut un peu simplifier la preuve par codage. On évacue en effet les problèmes liés à l’écriture fractionnaire en remplaçant \(\mathbb Q\) par l’ensemble des entiers positifs qui lui est équipotent. On est alors amené à montrer que l’ensemble des suites finies d’entiers est dénombrable, ce qui me semble facile avec le codage de Gödel.
@MathOMan Ma stratégie était la même que celle évoqué par Pierre Lecomte (i.e. se ramener à classer les suites finies d’entiers) mais je suis allé trop vite avec mon argument sur l’ordre "lexicographique" (qui est faux ici puisque ne marche que si la taille des suites est bornées apriori) alors que je pensais au codage de Gödel à l’origine 🙂
Si bien sûr, c’est le produit – Parfaitement corrigé – j’étais trop obnubilé par mes formules pas latex et le fait que je tapais sur un clavier américain… on a les excuses qu’on peut 😀