Inscription / Connexion Nouveau Sujet
Ensemble des fonctions injectives de N dans N
Bonjour à tous.
En refaisant les examens des années précédentes, je suis tombé sur un exercice dont je ne vois pas le bout par lequel le prendre, le voici:
L'ensemble infini des fonctions injectives de N dans N est-il dénombrable?
Il me semble pouvoir comparer cet ensemble à celui des suites strictement croissantes à valeur dans N, mais pour l'instant ça ne m'a pas servi à grand chose.
Une indication?
Merci d'avance.
Bonjour ;
une idée :
L'ensemble des applications injectives de
dans
contient celui des applications strictement croissantes de
dans
.
Ce dernier est équipotent à l'ensemble des parties infinies de
.
L'ensemble des parties finies de
est dénombrable .
L'ensemble des parties de
n'est pas dénombrable .
sauf erreur bien entendu
Bonjour.
Les point 3 et 4 de la démonstration de elhor_abdelali me posent malgré tout quelques problèmes:
"L'ensemble des parties finies de N est dénombrable."
J'imagine qu'il s'agit d'étendre au cas de l'infini la proposition qui affirme "qu'une réunion finie d'ensembles dénombrables est dénombrable", mais comment effectue-ton cette extension? Et quelle serait une méthode pour indicer les parties de l'ensemble des parties finies de N (dans le genre de celles qui permettent d'indicer Z ou Q, si une telle méthode existe)?
Enfin, pour le dernier point de la démonstration:
"L'ensemble des parties de N n'est pas dénombrable."
Est-ce une application du théorème de Cantor (que l'on a pas (encore?) vu en cours)?
Merci d'avance, et bonne journée.
Bonjour (et salut elhor)
Pour les parties finies, en effet, on dit que c'est une réunion dénombrable (pas finie) d'ensembles dénombrables. On commence par montrer par récurrence sur k que l'ensemble des parties ayant k éléments est dénombrable, puis on prend la réunion de tout ça.
Pour montrer que l'ensemble de toutes les parties n'est pas dénombrable, il y a une méthode générale.
Si X est un ensemble, il n'existe aucune fonction surjective (donc pas de bijection) de X sur P(X).
L'astuce est de prendre quelconque, de poser
et de montrer que A n'est pas dans l'image de f.
Bonjour
"L'ensemble des parties finies de N est dénombrable."
Je tente une démonstration:
On numérote toutes les parties finies de IN en les regroupant par leur élément le plus grand, noté n, dans des regroupements notés En.
Chaque regroupement de parties ayant n pour sup a un nombre fini d'éléments, noté en. Les regroupements ont entre eux une intersection vide.
L'ensemble des parties finies de IN est la réunion des En, et a pour cardinal la somme des cardinaux finis des ensembles En, cad
en, qui m'a tout l'air d'être dénombrable.
Qu'en pensez-vous?
De rien Stylex 
Bonjour Camélia et jeanseb 
On peut aussi penser à injecter , dans , l'ensemble des parties finies de
:
par exemple via l'application en utilisant l'unicité de l'écriture décimale d'un entier naturel
sauf erreur bien entendu
Salut tout le monde 
Sinon, on peut faire un argument diagonal bête et méchant. Par l'absurde, on suppose qu'il y en a un nombre dénombrable. On en prend une numérotation, disons (f_n).
Et après on construit par récurrence g tel que g(n) ne soit pas dans {g(0),...,g(n-1),f(n)}. g est injective et n'est pourtant pas l'un des f_n...
On peut donner une jolie démonstration de ça. L'ensemble des parties finies de N est certainement plus petit que l'ensemble des n-uplets finis d'elements pour n de 1 a l'infini. A chacu de ces n-uplets (a_1,...a_n) on peut associer le produit 2^a_1.3^a_2...p_n^a_n.
Où p_n designe le n-ieme nombre premier, on donc une bijection de l'ensemble de tous les n-uplets finis de N, dans N, par l'existence et l'unicité de la décomposition en nombre en premiers!
Annuler
connectez vous
analyse en post-bac