Cycle d'injections

Tu aurais pu choisir le sens :

$$ \R \leq P(\N)==2^\N \leq \N^\N \leq \R $$

Et à part si tu as en même temps je gout (tout à fait respectable!!) de faire des révisions d'analyse de $L1-L2$, l'écriture en sommes convergentes parait excessivement snob (enfin ce n'est pas le bon mot, , disons plutôt excessivement importateur d'autres chapitres pour cette question-là).

Tout ça m'a l'air presque parfait, à la formulation près, surtout au début.

Quand tu écris $\{1,0,\dots\}$ et $\{0,1,1,\dots\}$, tu n'exprimes pas ce que tu voudrais. Vu le contexte, ce que tu écris, tu penses aux suites $(u_n)_{n\ge1}=(1,0,0,\dots)$ et $(v_n)_{n\ge1}=(0,1,1,\dots)$ sont distinctes, qui sont les suites de chiffres en base $2$ de $f(A)$ et $f(B)$ : les $1$ codent les emplacements des entiers qui appartiennent à $A$ et $B$. Cependant, il ne faut pas considérer cette suite comme un ensemble. Les deux ensembles qui sont écrits, $\{1,0,\dots\}$ et $\{0,1,1,\dots\}$, sont égaux à $\{0,1\}$ (l'ordre et la répétition ne comptent pas entre des accolades), ce qui n'est pas intéressant. En revanche, les suites $(u_n)$ et $(v_n)$ codent les ensembles $A=\{1\}$ et $B=\{2,3,4,5,\dots\}=\N^*\setminus\{1\}$. En effet, ces deux ensembles ont la même image par l'application $X\mapsto\sum_{i\in X}2^{-i}$, ce que tu voulais dire.

Deux remarques de plus sur cet exemple. D'une part, ils te donnent deux développements dyadiques du même réel $1/2$, à savoir $0,1$ et $0,01111\cdots$. C'est la même situation que les deux développements en base dix $0,1=0,0999\cdots$. Cela arrive aussi en base $3$ mais avec des suites qui stationnent à $2$, par exemple : $0,01222222\cdots=0,02$. On a vérifié hier qu'il n'y avait pas d'ambiguïté avec des suites de $0$ et de $1$ en base $3$ (i.e. l'application $f$ d'hier est injective).

D'autre part, la suite des chiffres en base $b$ ($2$, $3$, dix ou autre) de $f(A)=\sum_{i\in A}b^{-i}$ est précisément l'élément de $\{0,1\}^\N$ qui a pour image $A$ dans la dernière application de ta chaîne (cf. ci-dessous).

Pour le développement en base deux de $1/3$ et $2/7$, on peut écrire :
\begin{align*}\frac13&=\frac14\times\frac1{1-\frac14}=\frac14\sum_{j\ge0}\frac1{4^j}
=\sum_{k\ge1}2^{2k}=0,01\,01\,01\,01\,01\cdots\\
\frac27&=\frac{1}4\frac{1}{1-\frac18}=\sum_{k\ge1}\frac1{2^{3k-1}}=0,010\,010\,010\end{align*}mais c'est un gadget. Pour trouver systématiquement le développement de $a/b$ avec $b$ impair, il est utile de s'intéresser à l'ordre de $2$ dans le groupe $(\Z/n\Z)^\times$ des inversibles modulo $b$. C'est une autre histoire.


C'est difficile de savoir quel est la bonne quantité de rédaction que l'on souhaite, cela dépend tellement du contexte. Ici, le constat c'est que si on connaît le signe de $x$ et les parties entières de $2^i|x|$, alors on connaît le développement dyadique de $x$ et donc, en principe, on connaît $x$ en effet. Une justification courte : si $E(2^i|x|)=E(2^i|y|)=K$ alors $K\le 2^i|x|<K+1$ et $K\le2^i|y|<K+1$ donc $-1\le2^i|x|-|y|\le1$ et donc $\bigl||x|-|y|\bigr|\le2^{-i}$ ; si c'est vrai pour tout $i$, alors $|x|=|y|$.


Pour le mot infini, on « voit » bien que ça marche, on peut écrire une récurrence : si $S(f)=S(g)$ et si $f(k)=g(k)$ pour $k\le n$, alors $f(n+1)=g(n+1)$. L'initialisation : $f(0)$ est le minimum des indices des lettres de $S(f)$ égales à $0$. L'hérédité vient du même argument en regardant le plus petit indice supérieur ou égal à $f(0)+1+f(1)+1+\cdots+f(n)+1$ (à une unité près peut-être ?).

Une remarque en passant : je trouve cette injection jolie – simple et immédiatement convaincante. J'avais pensé à quelque chose de plus compliqué : une application de $\N$ dans $\N$ est déterminée par son graphe qui est une partie de $\N^2$, ce qui donne une injection « graphe » de $\N^\N$ dans $\mathfrak{P}(\N^2)$, lequel est en bijection avec $\mathfrak{P}(\N)$ puisque $\N^2$ et $\N$ le sont. La conclusion vient du paragraphe ci-dessous.


Ta dernière application est particulièrement remarquable. À une application $h$ de $\N$ dans $\{0,1\}$, on associe l'ensemble des $i$ tels que $h(i)=1$. C'est par définition $h^{-1}(\{1\})$ (l'image réciproque du singleton $\{1\}$). Ce qui est remarquable, c'est que cette application est une bijection. À toute partie $A$ de $\N$, on associe l'application $\mathbf{1}_A:\N\to\{0,1\}$ qui à $i$ associe $1$ si $i\in A$ et $0$ si $i\notin A$. Tu reconnais l'application caractéristique de $A$. Autrement dit, les ensembles $\{0,1\}^\N$ et $\mathfrak{P}(\N)$ sont en bijection et en plus, on a des bijections explicites.

Cette partie est vraie pour tout ensemble $X$ à la place de $\N$ : $\{0,1\}^X\simeq\mathfrak{P}(X)$ (même preuve, que je n'ai pas faite d'ailleurs).

De mon téléphone : tu ne m'as pas répondu mais le sens que tu as choisi est plus long. Essaie (si tu veux) celui que je t'ai suggéré.

Une autre activité qui peut t'être utile est de construire directement des bijections sans passer par CB. Tout dépend évidemment de ce que tu veux faire de ça.

Sinon, je te donne une injection d $\R$ dans $P(\N)$, pour t'éviter d'êre tenté par cet exo in fine qui relève plus de la rédaction d'algos que de la compréhension: $x\in \R\mapsto \{q\in \Q\mid q<x\}\in P(\Q)\}$ est injective. Comme $\N$ n'est pas $\Q$, il te reste à t'assurer que, pour toi, la suite est blanche, gris claire, gris foncé, noire???

Evidemment on peut faire tout un tas d'autres algos, mais à part si tu veux te lancer dans l'IA :-D (clin d'oeil), sinon, ce n'est pas "très TDE" comme entrainement.

De mon téléphone : j'avoue que l'écran qui m'affiche tes "moins" en indice ne me facilite pas la lecture mais de toute façon tu avais déjà construit toi même une autre injection puisque en écriture décimale un réel n'est qu'une application particulière de IN dans IN (précisément de IN dans 12 en comptant la virgule et le signe)