Introduction aux mathématiques/Exercices/Ensembles infinis

Exercice 1-1

Démontrer que $\mathbb {R} ^{\mathbb {N} }$ et $\mathbb {N} ^{\mathbb {N} }$ ont la puissance du continu.

Solution

D'après les propriétés des bijections canoniques,

$\left|\mathbb {R} \right|=\left|\{0,1\}^{\mathbb {N} }\right|\leq \left|\mathbb {N} ^{\mathbb {N} }\right|\leq \left|\mathbb {R} ^{\mathbb {N} }\right|=\left|\left(\{0,1\}^{\mathbb {N} }\right)^{\mathbb {N} }\right|=\left|\{0,1\}^{\mathbb {N} \times \mathbb {N} }\right|=\left|\{0,1\}^{\mathbb {N} }\right|=\left|\mathbb {R} \right|$.

 

On considère les sous-espaces vectoriels suivants (emboîtés) du $\mathbb {R}$-espace vectoriel $\mathbb {R} ^{\mathbb {N} }$ des suites réelles :

${\text{si }}1\leq p<\infty ,\quad \ell ^{p}=\{x=(x_{n})_{n\in \mathbb {N} }\in \mathbb {R} ^{\mathbb {N} }\mid \sum _{n=0}^{\infty }|x_{n}|^{p}<+\infty \}$,

$c_{0}=$ le sous-espace vectoriel des suites de limite nulle et $\ell ^{\infty }=B(\mathbb {N} ,\mathbb {R} )=$ le sous-espace vectoriel des suites bornées.

1. Vérifier que pour tout réel $t>0$, la suite $x(t)$ définie par $x(t)_{n}={\rm {e}}^{-tn}$ appartient à tous ces sous-espaces vectoriels.
2. On admettra (ou démontrera, en pensant aux matrices de Vandermonde) que la famille de suites $(x(t))_{t\in \mathbb {R} _{+}^{*}}$ est libre. En déduire que tous les sous-espaces vectoriels mentionnés sont de dimension au moins ${\rm {card}}(\mathbb {R} )$.
3. En déduire tous ces espaces de suites sont à la fois de dimension et de cardinal ${\rm {card}}(\mathbb {R} )$.

Solution

1. $x(t)$ appartient à $\ell ^{1}$ (donc à tous les autres espaces mentionnés) car $\sum _{n=0}^{\infty }{\rm {e}}^{-tn}={\frac {1}{1-{\rm {e}}^{-t}}}<\infty$.
2. Tous les sous-espaces vectoriels mentionnés contiennent donc la famille libre $(x(t))_{t\in \mathbb {R} _{+}^{*}}$. Leur dimension est donc au moins ${\rm {card}}(\mathbb {R} _{+}^{*})={\rm {card}}(\mathbb {R} )$.
3. Tous les sous-espaces vectoriels mentionnés sont de cardinal inférieur ou égal à ${\rm {card}}(\mathbb {R} ^{\mathbb {N} })={\rm {card}}(\mathbb {R} )$. On conclut grâce à la question précédente.

 

Exercice 1-2

1. Montrer que si $D$ est un ensemble dénombrable et $d\in D$, alors $D\setminus \{d\}$ est dénombrable.
2. En déduire que toute partie cofinie (c'est-à-dire de complémentaire fini) d'un ensemble dénombrable est dénombrable.

Solution

1. À bijection près, il suffit de montrer que pour tout $n\in \mathbb {N}$, $\mathbb {N} \setminus \{n\}$ est dénombrable. L'application $\mathbb {N} \to \mathbb {N} \setminus \{n\},\,k\mapsto {\begin{cases}k&{\text{si }}k<n\\k+1&{\text{si }}k\geq n\end{cases}}$ est bijective.
2. Montrons par récurrence sur $n\in \mathbb {N}$ que pour tout ensemble dénombrable $D$ et toute partie finie $F\subset D$ de cardinal $n$, le complémentaire $D\setminus F$ est dénombrable. L'initialisation est immédiate. Montrons l'hérédité. Supposons la propriété vraie pour un certain $n\in \mathbb {N}$. Soient $D$ un ensemble dénombrable, $F\subset D$ une partie de cardinal $n+1$, et $d$ un élément de $F$. L'ensemble $F':=F\setminus \{d\}$ est alors de cardinal $n$ donc par hypothèse de récurrence, $D':=D\setminus F'$ est dénombrable. L'ensemble $D\setminus F=D'\setminus \{d\}$ est donc dénombrable d'après la question 1.

 

Exercice 1-3

Un ensemble $E$ est dit :

• infini au sens (faible) usuel s'il n'est pas fini, c'est-à-dire s'il n'est équipotent à $\mathbb {N} _{n}$ pour aucun $n\in \mathbb {N}$ ;
• infini au sens (fort) de Dedekind s'il est équipotent à l'une de ses parties propres, c'est-à-dire à une partie $A\subset E$ différente de $E$.

Bien que ce ne soit pas utile ici, rappelons (cf. cours) qu'avec une version faible de l'axiome du choix, tout ensemble infini au sens usuel contient un ensemble dénombrable. Dans le présent exercice, on ne suppose aucun axiome du choix.

1. Montrer que tout ensemble infini au sens de Dedekind est infini au sens usuel.
2. Montrer que si $E$ contient un ensemble dénombrable alors $E$ est infini au sens de Dedekind. Indication : utiliser la question 1 de l'exercice précédent.
3. Démontrer la réciproque. Indication : soit $E$ un ensemble équipotent à l'une de ses parties propres, $A$, via une bijection $f:E\to A$, soit $a\in E\setminus A$, et soit $(x_{n})_{n}$ la suite définie par récurrence par $x_{0}=a{\text{ et }}\forall n\in \mathbb {N} \quad x_{n+1}=f(x_{n})$ ; montrer par descente infinie qu'il n'existe aucun $p\in \mathbb {N}$ tel que : $\exists q<p\quad x_{q}=x_{p}$.

Solution

1. Démontrons la contraposée. Soit E un ensemble fini. D'après le cours, pour toute partie propre A de E, on a card(A) < card(E), donc E n'est pas équipotent à A.
2. Soit $E$ un ensemble contenant une partie dénombrable $D$, et soit $d\in D$. D'après la question 1 de l'exercice précédent, il existe une bijection $g$ de $D$ dans $D\setminus \{d\}$. L'ensemble $E$ est alors infini au sens de Dedekind car équipotent à la partie propre $A:=E\setminus \{d\}$. En effet, $g$ s'étend en une bijection $f:E\to A$ en posant : $\forall x\in E\quad f(x)={\begin{cases}g(x)&{\text{si }}x\in D\\x&{\text{si }}x\notin D.\end{cases}}$
3. Réciproquement, soit $E$ un ensemble infini au sens de Dedekind. Avec les notations de l'indication, supposons qu'il existe $p,q\in \mathbb {N}$ tels que $q<p$ et $x_{q}=x_{p}$. On aurait alors $p>0$ et, pour $p':=p-1\in \mathbb {N}$ : $x_{q}=f\left(x_{p'}\right)\in A$ donc $q\neq 0$ puis, pour $q':=q-1\in \mathbb {N}$ : $f\left(x_{q'}\right)=f\left(x_{p'}\right)$ donc (par injectivité de $f$) $x_{q'}=x_{p'}$ ; de plus, $q'<p'$ (car $q<p$). On a donc montré que s'il existe un entier naturel $p$ tel que $\exists q<p\quad x_{q}=x_{p}$, alors il existe un entier naturel $p'<p$ vérifiant la même propriété. Par descente infinie, ceci prouve qu'il n'existe aucun tel $p$, c'est-à-dire que $\forall p,q\in \mathbb {N} \quad \left(q<p\Rightarrow x_{q}\neq x_{p}\right)$. Autrement dit : l'application $n\mapsto x_{n}$ est injective. Par conséquent, elle réalise une bijection de $\mathbb {N}$ sur son image, $\{x_{n}\mid n\in \mathbb {N} \}$, qui est donc une partie dénombrable de $E$.

 

Exercice 1-4

Soit X un ensemble contenant une partie dénombrable et soit N un ensemble fini ou dénombrable. Montrer que X∪N est équipotent à X.

Solution

Quitte à remplacer N par N\X (ce qui ne modifie ni l'hypothèse sur N, ni l'ensemble X∪N), on peut supposer que N est disjoint de X.

Soit D une partie dénombrable de X. Alors, D∪N est dénombrable donc il existe une bijection $g:D\to D\cup N$.

Elle s'étend en une bijection $f:X\to X\cup N$ en posant $f(x)={\begin{cases}g(x)&{\text{si }}x\in D\\x&{\text{si }}x\in X\setminus D.\end{cases}}$

 

Exercice 1-5

On rappelle que l'ensemble $\mathbb {N} ^{\mathbb {N} }$ des applications de $\mathbb {N}$ dans $\mathbb {N}$ est équipotent à $\mathbb {R}$, et que $S_{\mathbb {N} }$ désigne le sous-ensemble des bijections de $\mathbb {N}$ dans $\mathbb {N}$. On note $I{\overline {S}}$, $S{\overline {I}}$ et ${\overline {I}}{\overline {S}}$ les parties de $\mathbb {N} ^{\mathbb {N} }$ constituées respectivement des injections non surjectives, des surjections non injectives et des applications ni injectives, ni surjectives.

1. Montrer que $I{\overline {S}}$ et $S{\overline {I}}$ sont non vides.
2. Soient $g\in I{\overline {S}}$ et $h\in S{\overline {I}}$. Expliquer rapidement pourquoi $f\mapsto g\circ f$, $f\mapsto f\circ h$ et $f\mapsto g\circ f\circ h$ sont des injections de $S_{\mathbb {N} }$ dans (respectivement) $I{\overline {S}}$, $S{\overline {I}}$ et ${\overline {I}}{\overline {S}}$. (On rappellera, sans les démontrer, les propriétés utilisées reliant injectivité, surjectivité et composition.)
3. Pour toute partie $A$ de $\mathbb {N}$, on définit $f_{A}:\mathbb {N} \to \mathbb {N}$ par : pour tout $n\in A$, $f_{A}(2n)=2n+1$ et $f_{A}(2n+1)=2n$ et pour tout $n\in \mathbb {N} \setminus A$, $f_{A}(2n)=2n$ et $f_{A}(2n+1)=2n+1$. Montrer que $f_{A}$ est bijective, en précisant sa bijection réciproque.
4. On considère l'application $F:{\mathcal {P}}(\mathbb {N} )\to S_{\mathbb {N} },\,A\mapsto F(A)=f_{A}$. Montrer qu'il existe une application $G:S_{\mathbb {N} }\to {\mathcal {P}}(\mathbb {N} )$ telle que $G\circ F=\operatorname {Id} _{{\mathcal {P}}(\mathbb {N} )}$.
5. Déduire des questions 4 et 2 que $S_{\mathbb {N} }$, $I{\overline {S}}$, $S{\overline {I}}$ et ${\overline {I}}{\overline {S}}$ sont équipotents à $\mathbb {R}$.

Solution

1. Par exemple : $g:\mathbb {N} \to \mathbb {N} ,\,n\mapsto 2n$ est une injection non surjective et $h:\mathbb {N} \to \mathbb {N} ,\,n\mapsto \lfloor n/2\rfloor$ est une surjection non injective.
2. Si $f,f'\in S_{\mathbb {N} }$ alors :
   • $g\circ f$ est injective (comme composée de deux injections) ; elle n'est pas surjective (car $g$ ne l'est pas). Si $g\circ f=g\circ f'$ alors $f=f'$ (par injectivité de $g$) ;
   • $f\circ h$ est surjective (comme composée de deux surjections) ; elle n'est pas injective (car $h$ ne l'est pas). Si $f\circ h=f'\circ h$ alors $f=f'$ (par surjectivité de $h$) ;
   • pour les mêmes raisons, $g\circ f\circ h$ n'est ni surjective, ni injective, et si $g\circ f\circ h=g\circ f'\circ h$ alors $f=f'$.
3. $f_{A}$ est bijective, de réciproque elle-même, car $f_{A}\circ f_{A}=\operatorname {Id} _{\mathbb {N} }$.
4. Par exemple, l'application $G$ définie par $\forall f\in S_{\mathbb {N} }\quad G(f)=\{n\in \mathbb {N} \mid f(2n)\neq 2n\}$ convient car $\forall A\in {\mathcal {P}}(\mathbb {N} )\quad \{n\in \mathbb {N} \mid f_{A}(2n)\neq 2n\}=A$.
5. D'après 4, $F$ est injective donc le cardinal de $S_{\mathbb {N} }$ est minoré par $\left|{\mathcal {P}}(\mathbb {N} )\right|=\left|\mathbb {R} \right|$. D'après 2, il est majoré par $\left|I{\overline {S}}\right|$, $\left|S{\overline {I}}\right|$ et $\left|{\overline {I}}{\overline {S}}\right|$, qui sont eux-mêmes majorés par $\left|\mathbb {N} ^{\mathbb {N} }\right|=\left|\mathbb {R} \right|$. Tous ces cardinaux sont donc égaux.

 

Exercice 1-6

Montrer que tout intervalle réel non trivial (c'est-à-dire contenant au moins deux réels) a la puissance du continu.

Solution

L'application $\left]0,1\right[\to \mathbb {R} ,\,t\mapsto {\frac {1}{t}}+{\frac {1}{t-1}}$ est bijective.

Pour tous réels $a<b$, les applications

${\begin{cases}\left]0,1\right[\to \left]a,b\right[,&t\mapsto (1-t)a+tb\\\left]0,1\right[\to \left]a,+\infty \right[,&t\mapsto a+{\frac {1}{t}}\\\left]0,1\right[\to \left]-\infty ,a\right[,&t\mapsto a-{\frac {1}{t}}\end{cases}}$

sont bijectives.

Donc tout intervalle ouvert non vide a la puissance du continu.

On en déduit que tout intervalle non trivial non ouvert a aussi la puissance du continu, car il s'obtient en ajoutant un ou deux points à un intervalle ouvert non vide I. Or, comme I est infini, cet ajout ne modifie pas son cardinal (cf. exercice 1-4 ci-dessus).

 

Exercice 1-7

On rappelle (pour les questions 2 et 3) que pour tous cardinaux $\alpha ,\beta ,\gamma$ :

$\alpha ^{\beta }\times \alpha ^{\gamma }=\alpha ^{(\beta +\gamma )}\quad {\text{et}}\quad \alpha ^{\beta \times \gamma }=(\alpha ^{\beta })^{\gamma }$.

Dans chacune des trois listes suivantes, comparer entre eux les cardinaux des 5 ensembles, par des inégalités strictes ou des égalités.

1. $\mathbb {N} ,\qquad \mathbb {R} ,\qquad {\mathcal {P}}(\mathbb {N} ),\qquad \{0,1\}^{\mathbb {N} },\qquad {\mathcal {P}}(\mathbb {R} )$.
2. $\mathbb {R} ,\qquad \{0,1\}^{\mathbb {Z} },\qquad \{0,1\}^{\mathbb {N} }\times \{0,1\}^{\mathbb {N} ^{*}},\qquad \mathbb {R} \times \mathbb {R} ,\qquad \mathbb {N} \times \mathbb {R}$.
3. $\{0,1\}^{\mathbb {N} },\qquad \{0,1\}^{\mathbb {N} \times \mathbb {N} },\qquad \mathbb {R} ^{\mathbb {N} },\qquad \{0,1\}^{\mathbb {R} },\qquad \mathbb {R} ^{\mathbb {R} }$.

Solution

1. D'après le théorème de Cantor, $|\mathbb {N} |<|{\mathcal {P}}(\mathbb {N} )|$ et $|\mathbb {R} |<|{\mathcal {P}}(\mathbb {R} )|$.
   D'après la bijection canonique entre $\{0,1\}^{E}$ et ${\mathcal {P}}(E)$ (pour tout ensemble $E$), $\left|\{0,1\}^{\mathbb {N} }\right|=|{\mathcal {P}}(\mathbb {R} )|$.
   Enfin, nous savons que $|\mathbb {R} |=|{\mathcal {P}}(\mathbb {N} )|$.
   En résumé : $|\mathbb {N} |<|\mathbb {R} |=|{\mathcal {P}}(\mathbb {N} )|=\left|\{0,1\}^{\mathbb {N} }\right|<|{\mathcal {P}}(\mathbb {R} )|$.
2. $\mathbb {Z}$ est dénombrable donc $\left|\{0,1\}^{\mathbb {Z} }\right|=\left|\{0,1\}^{\mathbb {N} }\right|=|\mathbb {R} |$.
   Par définition de la somme de deux cardinaux, $|\mathbb {N} |+|\mathbb {N} ^{*}|=|\mathbb {N} |+|-\mathbb {N} ^{*}|=|\mathbb {N} \cup (-\mathbb {N} ^{*})|=|\mathbb {Z} |$ donc d'après le premier rappel, $\left|\{0,1\}^{\mathbb {N} }\times \{0,1\}^{\mathbb {N} ^{*}}\right|=\left|\{0,1\}^{\mathbb {Z} }\right|$.
   $\mathbb {N} ^{*}$ est dénombrable donc $\left|\{0,1\}^{\mathbb {N} ^{*}}\right|=\left|\{0,1\}^{\mathbb {N} }\right|=|\mathbb {R} |$, donc $|\mathbb {R} \times \mathbb {R} |=\left|\{0,1\}^{\mathbb {N} }\times \{0,1\}^{\mathbb {N} ^{*}}\right|$.
   En résumé : $|\mathbb {R} |=\left|\{0,1\}^{\mathbb {Z} }\right|=\left|\{0,1\}^{\mathbb {N} }\times \{0,1\}^{\mathbb {N} ^{*}}\right|=|\mathbb {R} \times \mathbb {R} |$.
   Enfin, $|\mathbb {R} |=|\{0\}\times \mathbb {R} |\leq |\mathbb {N} \times \mathbb {R} |$ et $|\mathbb {N} \times \mathbb {R} |\leq |\mathbb {R} \times \mathbb {R} |=|\mathbb {R} |$ donc (d'après le théorème de Cantor-Bernstein) $|\mathbb {N} \times \mathbb {R} |=|\mathbb {R} |$.
   Les cinq ensembles de cette liste ont donc la puissance du continu.
3. $\mathbb {N} \times \mathbb {N}$ est dénombrable donc $\left|\{0,1\}^{\mathbb {N} \times \mathbb {N} }\right|=\left|\{0,1\}^{\mathbb {N} }\right|=|\mathbb {R} |$.
   D'après le second rappel, $\left|\{0,1\}^{\mathbb {N} \times \mathbb {N} }\right|=\left|\left(\{0,1\}^{\mathbb {N} }\right)^{\mathbb {N} }\right|=\left|\mathbb {R} ^{\mathbb {N} }\right|$.
   De même, $\left|\mathbb {R} ^{\mathbb {R} }\right|=\left|\left(\{0,1\}^{\mathbb {N} }\right)^{\mathbb {R} }\right|=\left|\{0,1\}^{\mathbb {N} \times \mathbb {R} }\right|$ donc (puisque $|\mathbb {N} \times \mathbb {R} |=|\mathbb {R} |$, cf. question précédente) $\left|\mathbb {R} ^{\mathbb {R} }\right|=\left|\{0,1\}^{\mathbb {R} }\right|$.
   $\left|\{0,1\}^{\mathbb {R} }\right|=|{\mathcal {P}}(\mathbb {R} )|>|\mathbb {R} |$.
   En résumé : $\left|\{0,1\}^{\mathbb {N} }\right|=\left|\{0,1\}^{\mathbb {N} \times \mathbb {N} }\right|=\left|\mathbb {R} ^{\mathbb {N} }\right|<\left|\{0,1\}^{\mathbb {R} }\right|=\left|\mathbb {R} ^{\mathbb {R} }\right|$.