Bijection de $\N^\N$ dans $P(\N^2)$
Bonjour,
Un probleme me taraude l’esprit
On m’a dit que ces deux ensembles sont en bijection grâce à la fonction qui associe à une fonction son graphe.
Or la surjectivité me dérange : si on prend deux points de même abscisse et d’ordonnées différentes, il m’est impossible de construire une fonction associée.
Merci.
Un probleme me taraude l’esprit
On m’a dit que ces deux ensembles sont en bijection grâce à la fonction qui associe à une fonction son graphe.
Or la surjectivité me dérange : si on prend deux points de même abscisse et d’ordonnées différentes, il m’est impossible de construire une fonction associée.
Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Il faut à présent trouver une injection dans l'autre sens. Une proposition : on commence par remarquer qu'une bijection de $\N^2$ sur $\N$ induit une bijection de $P(\N^2)$ sur $P(\N)$ ; puis on met $P(\N)$ en bijection avec $\{0,1\}^\N$ en associant à une partie sa fonction caractéristique. Enfin, on injecte $\{0,1\}^\N$ dans $\N^\N$ en considérant tout à coup qu'une suite à valeurs dans $\{0,1\}$ est à valeurs dans $\N$.
Dans un sens, $X^X$ s'injecte dans $P(X^2)$ de la même façon.
Dans l'autre, il faut comprendre pourquoi, lorsque $X$ est infini, on a une bijection entre $X^2$ et $X$. Après, l'injection de $P(X)$ dans $\{0,1\}^X$ et de $\{0,1\}^X$ dans $X^X$ vont de soi.
Ce me semble...