Existence d'une bijection des parties finies de N dans N

[invite0b2b3045]

Hello
Je n'arrive pas à montrer qu'il n'existe pas de surjection de l'ensemble des fonctions de N dans N pour montrer la non dénombrabilité de cet ensemble...quelqu'un peut il m'aider?
Merci
-----

[invite6b1e2c2e]

Je ne comprends pas : Ta question et ton titre sont différents !
Cela dit, pour ton titre, il me semble que je sais le faire: Considère les nombres premiers p_n comme marqueurs.
Pour une partie A={a_1,...,a_n}, d'abord classer les éléments par ordre décroissant, afin d'avoir une définition précise, puis poser f(A) = produit des p_i^a_i.
On arrive dans une partie dénombrable de N, qu'il est facile de mettre en bijection avec N.
Pour ta question, il suffit de démontrer que [0,1[ s'injecte dans l'ensemble des fonctions de N dans N. Pour cela, tu peux par exemple regarder l'application qui à un nombre réél r = 0,a_1...a_n... associe la fonction f(r):N->N telle que f(r)(n)=a_n. Mais là, j'ai sans doute modifié ta question. La bonne question, à laquelle pour le coup, je n'ai pas de réponse, c'est : Est ce que l'ensemble des fonctions _bijectives_ de N dans N est dénombrable ? Je ne pense pas, mais je ne vois pas de preuve. Des idées ?

__rvz

[invite986312212]

La bonne question, à laquelle pour le coup, je n'ai pas de réponse, c'est : Est ce que l'ensemble des fonctions _bijectives_ de N dans N est dénombrable ? Je ne pense pas, mais je ne vois pas de preuve. Des idées ?

__rvz

pourquoi ne pas utiliser le procédé diagonal de Cantor?
si les bijections de N dans N étaient dénombrables, on pourrait les dénombrer : f1,f2,...
construisons maintenant une bijection f, telle que pour tout entier i, f(i) != fi(i) <je note != : différent de>
on prend f(1) = le plus petit entier différent de f1(1), puis par récurrence, f(i) = le plus petit entier différent de fi(i) et des f(1),...,f(i-1)
f est injective par construction. Il reste à montrer qu'elle est surjective. On le montre par récurrence. Soit k le plus petit entier tel que fk(1)!=1. Alors f(k)=1. Supposons que les entiers 1,..,(n-1) ont un antécédent par f. Soit k le plus petit entier tel que fk(n)!=n, etc.

[invite16e28998]

pourquoi ne pas utiliser le procédé diagonal de Cantor?
si les bijections de N dans N étaient dénombrables, on pourrait les dénombrer : f1,f2,...
construisons maintenant une bijection f, telle que pour tout entier i, f(i) != fi(i) <je note != : différent de>
on prend f(1) = le plus petit entier différent de f1(1), puis par récurrence, f(i) = le plus petit entier différent de fi(i) et des f(1),...,f(i-1)
f est injective par construction. Il reste à montrer qu'elle est surjective. On le montre par récurrence. Soit k le plus petit entier tel que fk(1)!=1. Alors f(k)=1. Supposons que les entiers 1,..,(n-1) ont un antécédent par f. Soit k le plus petit entier tel que fk(n)!=n, etc.

Salut,

Il me semble qu'il y a un petit problème quant à ta démonstration de la surjectivité. Pour que f(k)=1 il faut non pas que fk(1)!=1 mais plutôt que fk(k)!=1...
Ca rajoute une subtilité pour la construction de f.
Pour reprendre là où ca coince : l'existence de k le plus petit entier tel que fk(k)!=1 n'est pas certaine.
Mais s'il n'existe pas, tu peux construire une nouvelle bijection g en considérant par exemple g(2)=f1(3), g(3)=f1(2) et g=f1 partout ailleurs.
Bref, soit la récurrence est vraie et tu peux construire une nouvelle bijection, soit elle est fausse et tu peux tout de même construire une nouvelle bijection

[A voir en vidéo sur Futura]