Bijection de $\N^\N$ dans $P(\N^2)$

Ce que tu décris est une injection de $\N^\N$ dans $P(\N^2)$ (la donnée du graphe détermine la fonction). En effet, elle n'est pas surjective.

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$.

Je pense – disons, pour $X$ infini – mais c'est un peu plus cher.
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...