Montrer que N x N est dénombrable

Posté par robby3 robby3

Bonjour tout le monde,
dans un exercice que montre que est dénombrable via l'application:



et dans la correction,on me dit qu'on aurait pu le faire avec une autre application et plus rapidement...

ma question n'est donc pas comment montreriez-vous que est dénombrable avec
mais pourquoi est-ce plus rapide?

Posté par Nightmare Nightmare

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.

Posté par robby3 robby3

Salut

??
la décomposition en facteur premier...?
as-tu le temps de me montrer un peu s'il te plait?

Posté par Nightmare Nightmare

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.

Posté par robby3 robby3

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?

Posté par robby3 robby3

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

Posté par otto otto

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.

Posté par robby3 robby3

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

Posté par otto otto

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 ?

Posté par robby3 robby3

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

Posté par robby3 robby3


>non pas du tout

Posté par otto otto

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

Posté par Nightmare Nightmare

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

Posté par robby3 robby3

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?

Posté par Nightmare Nightmare

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

Posté par otto otto

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.

Posté par Nightmare Nightmare

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

Posté par robby3 robby3

Otto>D'accord

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

Merci à tout les deux!

Posté par Nightmare Nightmare

Je t'en prie.

Posté par rogerd rogerd

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

Posté par Arkhnor Arkhnor

Bonjour.


Ca me fait penser à l'application qu'on utilise pour montrer que est en bijection avec .

Posté par robby3 robby3

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

Posté par infophile infophile

Tiens j'ai eu cet exo en khôlle

Posté par robby3 robby3

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

Posté par robby3 robby3


>quelqu'un voit-il comment rédiger la démo de Rogerd??
(merci d'avance si vous avez le temps! )

Posté par rogerd rogerd

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?

Posté par robby3 robby3

j'ai pas trés bien compris

>
pour etre franc j'ai rien pigé!

46000 et 2548,le plus petit c'est 2548...aprés on fait quoi?

Posté par rogerd rogerd

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.

Posté par rogerd rogerd

Ce n'est toujours pas clair?

Posté par robby3 robby3

Si!
là c'est ok!


>ça c'est pour aprés?

Posté par rogerd rogerd

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

Posté par robby3 robby3

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?

Posté par rogerd rogerd

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?