Math Woods | Free Mathematics Problems and Concepts

Solution

Solution by budleya · FR

Notons $2^\N$ l’ensemble des listes infinies à valeurs dans $\{0,1\}$ ; le sous-ensemble $C$ des listes constantes à partir d’un certain rang est dénombrable, donc $\bar C=2^{\N}-C$ n’est pas dénombrable.
A toute $f\in\mathcal S_{\N}$ on associe la liste $u=\big(f(n) \mod 2\big)_{n\in \N}=f\mod 2$ ; $f\mapsto u$ surjecte ainsi $\mathcal S_{\N}$ sur $\bar C$ qui n’est pas dénombrable ; donc $\mathcal S_{\N}$ n’est pas dénombrable.

Une preuve possible que

f\mapsto u

surjecte

\mathcal S_{\N}

sur

\bar C

Pour antécédent de toute suite $u\in\bar C$ on peut par exemple proposer $f:\N\rightarrow\N$ définie par
$f(n)=(2s_{n}-1)u_{n} + 2(n-s_{n})(1-u_{n}) {\rm\ avec}\ s_{n}=\sum_{i=0}^{n}u_{i}$ On a
a) $f\mod 2=u$
b) $f$ est bijective car elle entrelarde les entiers impairs qu’elle positionne là où il y a des $1$ dans $u$ et les entiers pairs là où il y a des 0 dans $u$ : Vérifiez si vous n’y croyez pas que la liste
$u=$ $(0, 1,1,0,0,0,1,0,1,0,0,...)$ produit $f=(0,1,3,2,4,6,5,8,7,10,12...)$

ou rédigez proprement une récurrence : $f(0)=u_{0},f(1)=u_{1}$ et entre deux "1" (resp. "0") successifs séparés par un nombre quelconque de "0" (resp. "1") dans la suite $u$ , la valeur de $f$ augmente de 2.