En raison de limitations techniques, la typographie souhaitable du titre, «
Exercice : Ensembles infinis
Introduction aux mathématiques/Exercices/Ensembles infinis », n'a pu être restituée correctement ci-dessus.
Démontrer que et ont la puissance du continu.
Solution
D'après les propriétés des bijections canoniques,
- .
On considère les sous-espaces vectoriels suivants (emboîtés) du -espace vectoriel des suites réelles :
- ,
le sous-espace vectoriel des suites de limite nulle et le sous-espace vectoriel des suites bornées.
- Vérifier que pour tout réel , la suite définie par appartient à tous ces sous-espaces vectoriels.
- On admettra (ou démontrera, en pensant aux matrices de Vandermonde) que la famille de suites est libre. En déduire que tous les sous-espaces vectoriels mentionnés sont de dimension au moins .
- En déduire tous ces espaces de suites sont à la fois de dimension et de cardinal .
- Montrer que si est un ensemble dénombrable et , alors est dénombrable.
- En déduire que toute partie cofinie (c'est-à-dire de complémentaire fini) d'un ensemble dénombrable est dénombrable.
Un ensemble est dit :
- infini au sens (faible) usuel s'il n'est pas fini, c'est-à-dire s'il n'est équipotent à pour aucun ;
- infini au sens (fort) de Dedekind s'il est équipotent à l'une de ses parties propres, c'est-à-dire à une partie différente de .
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.
- Montrer que tout ensemble infini au sens de Dedekind est infini au sens usuel.
- Montrer que si contient un ensemble dénombrable alors est infini au sens de Dedekind. Indication : utiliser la question 1 de l'exercice précédent.
- Démontrer la réciproque. Indication : soit un ensemble équipotent à l'une de ses parties propres, , via une bijection , soit , et soit la suite définie par récurrence par ; montrer par descente infinie qu'il n'existe aucun tel que : .
Solution
- 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.
- Soit un ensemble contenant une partie dénombrable , et soit . D'après la question 1 de l'exercice précédent, il existe une bijection de dans . L'ensemble est alors infini au sens de Dedekind car équipotent à la partie propre . En effet, s'étend en une bijection en posant :
- Réciproquement, soit un ensemble infini au sens de Dedekind. Avec les notations de l'indication, supposons qu'il existe tels que et . On aurait alors et, pour : donc puis, pour : donc (par injectivité de ) ; de plus, (car ). On a donc montré que s'il existe un entier naturel tel que , alors il existe un entier naturel vérifiant la même propriété. Par descente infinie, ceci prouve qu'il n'existe aucun tel , c'est-à-dire que . Autrement dit : l'application est injective. Par conséquent, elle réalise une bijection de sur son image, , qui est donc une partie dénombrable de .
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 .
Elle s'étend en une bijection en posant
On rappelle que l'ensemble des applications de dans est équipotent à , et que désigne le sous-ensemble des bijections de dans . On note , et les parties de constituées respectivement des injections non surjectives, des surjections non injectives et des applications ni injectives, ni surjectives.
- Montrer que et sont non vides.
- Soient et . Expliquer rapidement pourquoi , et sont des injections de dans (respectivement) , et . (On rappellera, sans les démontrer, les propriétés utilisées reliant injectivité, surjectivité et composition.)
- Pour toute partie de , on définit par : pour tout , et et pour tout , et . Montrer que est bijective, en précisant sa bijection réciproque.
- On considère l'application . Montrer qu'il existe une application telle que .
- Déduire des questions 4 et 2 que , , et sont équipotents à .
Solution
- Par exemple : est une injection non surjective et est une surjection non injective.
- Si alors :
- est injective (comme composée de deux injections) ; elle n'est pas surjective (car ne l'est pas). Si alors (par injectivité de ) ;
- est surjective (comme composée de deux surjections) ; elle n'est pas injective (car ne l'est pas). Si alors (par surjectivité de ) ;
- pour les mêmes raisons, n'est ni surjective, ni injective, et si alors .
- est bijective, de réciproque elle-même, car .
- Par exemple, l'application définie par convient car .
- D'après 4, est injective donc le cardinal de est minoré par . D'après 2, il est majoré par , et , qui sont eux-mêmes majorés par . Tous ces cardinaux sont donc égaux.
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 est bijective.
Pour tous réels , les applications
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).
On rappelle (pour les questions 2 et 3) que pour tous cardinaux :
- .
Dans chacune des trois listes suivantes, comparer entre eux les cardinaux des 5 ensembles, par des inégalités strictes ou des égalités.
- .
- .
- .
Solution
- D'après le théorème de Cantor, et .
D'après la bijection canonique entre et (pour tout ensemble ), .
Enfin, nous savons que .
En résumé : .
- est dénombrable donc .
Par définition de la somme de deux cardinaux, donc d'après le premier rappel, .
est dénombrable donc , donc .
En résumé : .
Enfin, et donc (d'après le théorème de Cantor-Bernstein) .
Les cinq ensembles de cette liste ont donc la puissance du continu.
- est dénombrable donc .
D'après le second rappel, .
De même, donc (puisque , cf. question précédente) .
.
En résumé : .