Salut

Euh avec l'application 2^x.3^y je ne vois pas... par contre si on prend g(x,y)=2^x(2y+1) là ça devient super simple en utilisant la décomposition en facteur premier d'un nombre.

Salut

Bien sûr

Il est clair que g est surjective.

On se donne un entier n quelconque (bon, non nul, on s'en fiche), il admet une décomposition en facteur premier du type , ie il s'écrit sous la forme donc (p,q) est un antécédent de n par g.

L'injectivité c'est du Gauss :
On suppose que g(x,y)=g(x',y')

Alors On a par exemple 2^x premier avec (2y'+1) donc d'après Gauss il divise 2^x' d'où x < x'
Par symétrie, x' > x. Ainsi x=x'

On a alors 2y+1=2y'+1 soit y=y'.

g est injective.

Au final elle est bijective donc N² est dénombrable.

ah oué!

mais n différent de 0 et 1! non?


par contre l'histoire de la décomposition en facteur premier ça marche pas pour ma fonction?

parce que 3^quelque chose, c'est toujours un nombre impair non?

Ta fonction n'est clairement pas surjective, ca se voit tout de suite ...

Il suffit de prendre un nombre premier distinct de 2 et 3.

Sinon un nombre qui n'est pas multiple de 2 ou 3 fait l'affaire.

et en plus dans les deux cas, la surjectivité ne sert à rien vu qu'on va dans N...l'injectivité suffit non?

parce que 3^quelque chose, c'est toujours un nombre impair non?
Et c'est bien connu que tout nombre impair est de la forme 3^n ?

Bonjour Otto, c'est ce que je voyais à l'instant..mais je crois qu'on a pas besoin...si?
dans mon autre post, j'avais un exo qui disait que si f:E->F était injective et F dénombrable,alors e est au plus dénombrable...

si f:E->F était injective et F dénombrable,alors e est au plus dénombrable...
Oui tu as raison.

Pour 1 on a pas de problème on prend x=0 et y=0

Pour 0, on en a un petit mais on le règle on considèrant g(x,y)=2^x(2y+1)-1

ah oui, c'est pour ma fonction que y'a un soucis pour 0...

donc comme N est dénombrable,ne suffit-il donc pas de montrer que g est injective?

Si effectivement si on admet ton exercice précédent, mais sans celui-ci le plus rapide est la question que je t'ai donné.

donc comme N est dénombrable,ne suffit-il donc pas de montrer que g est injective?
Presque, il faut aussi montrer que l'ensemble n'est pas fini, mais il y'a une injection canonique de N dans N*N donc c'est bon.

Cela dit on a beaucoup plus rapide : NxN est le produit cartésien de deux ensembles dénombrable => il est dénombrable.

Otto>D'accord

Nightmare>oui, mais ça c'est la question qui suit mon exercice

Merci à tout les deux!

Je t'en prie.

Rebonjour!

La démonstration de Nightmare est très propre.

A titre de curiosité, la démonstration qu'on donnait jadis (je vous parle d'un temps que les moins de vingt ans...):

On fabrique g(x,y) en prenant alternativement un chiffre dans l'écriture de x en base 10 et un chiffre dans l'écriture de y.
C'est difficile à mettre au propre (notamment à cause des zéros) mais cela donne une bijection très "visuelle".

Bonjour.

si t'as le temps Rogerd, je veux bien voir de plus prés ton idée:D

Tiens j'ai eu cet exo en khôlle

il est sympa je trouve cet exo(enfin en kholle moins... )

enfin, j'ai pas fait de théorie des ensembles depuis 2 bonnes longues années alors bon, comme c'est au programme du capes,je revois les bases

Bonjour à tous.

robby3: Je crois avoir trouvé (ou retrouvé).

Pour fabriquer g(x,y), on fait précéder le plus petit  des deux nombres x et y de suffisamment de zéros pour que les deux écritures aient la même longueur et on puise alternativement un chiffre dans l'un puis dans l'autre. Ainsi g(46000,2548)=4062050408.
Tout entier n est alors l'image par g d'un couple et d'un seul.
Par exemple:
5274070001 est l'image de (57000,24701) et ne peut être l'image d'autre chose.
205041000 est l'image de (10,25400) et ne peut être l'image d'autre chose.
Ces exemples se généralisent de façon évidente.
(Avant de décoder, on fait précéder n d'un 0 si le nombre de chiffres de n est impair.)

D'accord?

j'ai pas trés bien compris

Pour qu'ils aient la même longueur, on les écrit
46000 et 02548. Cela ne change pas leur valeur.
On fabrique ensuite g(x,y) en prenant le 4 dans x, puis le 0 dans y puis le 6 dans x puis le 2 dans y etc.

Ce n'est toujours pas clair?

Si!
là c'est ok!

Oui.
C'est pour récupérer x et y quand on connaît g(x,y).

ok d'accord, et pour décoder donc?



parce que pour montrer qu'elle est bijective, faut montrer l'application réciproque là,c'est ça?

Bonjour robby3.

Pour montrer que g est bijective de NxN dans N, il n'est pas nécessaire de trouver la bijection réciproque. Il suffit de prouver que tout n dans N est l'image par g d'un unique couple (x,y).
Cela prouvera d'un coup que g est surjective et injective.
Autrement dit,il faut montrer que, étant donné n , on peut déterminer x et y convenables, et ceci de façon unique. Je l'ai fait précédemment en me limitant à deux exemples de valeurs de n, mais on voit bien que la méthode marcherait pour n'importe quel n.
D'accord?