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.
Réponses
-
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$. -
Merci beaucoup ! Peut-on généraliser ce résultat à X^X avec X ensemble quelconque et cette fonction qui à X^X associe son graphe?
-
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...
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres