Construction d'une bijection entre w^w et N

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Clise
Membre Relatif
Messages: 221
Enregistré le: 16 Mai 2008, 22:59

construction d'une bijection entre w^w et N

par Clise » 17 Juil 2008, 14:17

Bonjour,

Je travaille sur les nombres ordinaux et je dois construire une bijection entre w^w et N (on sait qu'il en existe au moins une puisque l'ordinal w^w est dénombrable).

w^w = l'union sur tous les n des w^n
Sur wikipedia, il y a un très belle illustration de ce peut être w^w http://fr.wikipedia.org/wiki/Ordinal

Voila comment j'ai commencer, je me suis dit que si un ordinal x est compris dans (donc strictement inférieur a) w^w, il peut être écrit de manière unique sous la forme suivante (forme normal de Cantor) x=a0+a1*w+a2*w^2+....+an*w^n avec n un entier naturels et les ai égalements. En extrayant les ai dans une séquence infinie auxquelle on rajoute des 0, j'ai donc pour tout x dans w^w une suite unique de la forme Sx=(a0,a1,a2,....,an,0,0,....).

Cependant maintenant il faut que je fasse correspndre a chaque suite un nombre n unique et je ne vois pas trop comment faire... J'ai testé des manières ressemblant a la diagonale de Cantor, mais j'ai rien trouvé de convainquant. Si vous avez des idées ?

Merci pour vos réponses



ThSQ
Membre Complexe
Messages: 2077
Enregistré le: 10 Oct 2007, 19:40

par ThSQ » 17 Juil 2008, 18:30

Une fois (sommairement) digéré (burp) le vocabulaire, je pense que c'est une conséquence directe de la définition :



mais tous les sont dénombrables oeuf corse !

Remarquable comme les ordinaux différent des cardinaux ... comme cardinal.

Clise
Membre Relatif
Messages: 221
Enregistré le: 16 Mai 2008, 22:59

par Clise » 17 Juil 2008, 18:43

ThSQ a écrit:Une fois (sommairement) digéré (burp) le vocabulaire, je pense que c'est une conséquence directe de la définition :



mais tous les sont dénombrables oeuf corse

Merci pour ta réponse, mais je ne dois pas prouver la dénombrabilité de w^w qui est évidente compte tenue de ce que tu viens de dire :we:
Je dois construire formellement une bijection dire qu'a l'ordinal 0 j'associe 0, a w 1, par ex etc ....

ThSQ a écrit:Remarquable comme les ordinaux différent des cardinaux ... comme cardinal.

Je n'ai pas compris ... :mur:

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

par mathelot » 17 Juil 2008, 19:03

Bonjour,

injectons le maximum d'injectivité...








où p_i est le ième nombre premier

voilà comment ça marche:

1) on dédouble la suite finie d'entiers avec leur numéro de place
pour distinguer les doublons
2) avec un couple (entier,numéro de place) on fabrique un nouvel entier
grâce à la factorisation d'un entier par sa plus grande puissance de 2
cette suite devient un arrangement (sans répétition) de n entiers.
3) avec ces n entiers devenus distincts, on utilise la décomposition en facteurs premiers pour construire injectivement l'entier naturel N final...
les entiers deviennent les différents exposants des facteurs premiers

la composée de 4 injections est une application injective.

aviateurpilot
Membre Irrationnel
Messages: 1772
Enregistré le: 01 Juin 2006, 23:33

par aviateurpilot » 17 Juil 2008, 19:13

on prend eme nombre premier
on prend la fonction tel que
f est bien bijective.
en effet, on peux ecrire
avec
donc est l'unique anticident de

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

par mathelot » 17 Juil 2008, 19:16

j'ai été plus rapide mais Aaviateurpilot (que je salue) a fait plus simple :zen:
moi, tous mes exposants sont différents.
Par ailleurs, la méthode n'est malheurement pas implémentable vû l'extrême difficulté de factoriser un grand entier.

aviateurpilot
Membre Irrationnel
Messages: 1772
Enregistré le: 01 Juin 2006, 23:33

par aviateurpilot » 17 Juil 2008, 19:32

mathelot a écrit:j'ai été plus rapide mais Aaviateurpilot (que je salue) a fait plus simple :zen:
moi, tous mes exposants sont différents.
Par ailleurs, la méthode n'est malheurement pas implémentable vû l'extrême difficulté de factoriser un grand entier.

salut mathelot,
j'ai rien fait, c'est toi qui m'a guider vers la solution,avec l'idée des :++:

Clise
Membre Relatif
Messages: 221
Enregistré le: 16 Mai 2008, 22:59

par Clise » 17 Juil 2008, 19:33

Pourtant j'avais cru entendre qu'il existait un algorithme de décomposition en facteurs premiers :S

Je suis impréssionnée, deux réponses basées sur le même principe ... les nombres premiers... J'ai du louper quelquechose en cours moi :marteau: Pourquoi je n'y ai pas pensé :mur: en tout cas merci

aviateurpilot a écrit:salut mathelot,
j'ai rien fait, c'est toi qui m'a guider vers la solution,avec l'idée des :++:

ok dans ce cas tout s'explique :ptdr:

ThSQ
Membre Complexe
Messages: 2077
Enregistré le: 10 Oct 2007, 19:40

par ThSQ » 17 Juil 2008, 19:41

Clise a écrit:Je dois construire formellement une bijection dire qu'a l'ordinal 0 j'associe 0, a w 1, par ex etc ....


Xcuze j'avais mal lu ....

aviateurpilot
Membre Irrationnel
Messages: 1772
Enregistré le: 01 Juin 2006, 23:33

par aviateurpilot » 17 Juil 2008, 19:44

mais je ne conprend tjrs pas, c'est quoi w^w ete cett histoire d'ordinaux, lol
j'ai vu lien de wikipedia, mais j'ai rien compris :marteau:

Clise
Membre Relatif
Messages: 221
Enregistré le: 16 Mai 2008, 22:59

par Clise » 17 Juil 2008, 19:49

aviateurpilot a écrit:mais je ne conprend tjrs pas, c'est quoi w^w ete cett histoire d'ordinaux, lol
j'ai vu lien de wikipedia, mais j'ai rien compris :marteau:


tu as compris ce que représentait w déja ? et ce qu'est un nombre ordinal ?

aviateurpilot
Membre Irrationnel
Messages: 1772
Enregistré le: 01 Juin 2006, 23:33

par aviateurpilot » 17 Juil 2008, 21:12

Clise a écrit:tu as compris ce que représentait w déja ? et ce qu'est un nombre ordinal ?

no, car ans wikipedia, il y a une explication qui utilise des notions que je ne connais pas

Clise
Membre Relatif
Messages: 221
Enregistré le: 16 Mai 2008, 22:59

par Clise » 18 Juil 2008, 01:45

Ben en gros, un ordinal est un ensemble bien ordonné (ie ensemble dont tous les éléments peuvent être ordoné) dont un élément est l'ensemble de ses prédécésseurs.

Les entiers naturels peuvent être vu comme des ordinaux donc des ensembles. Ainsi a 0 on associe l'ensemble vide qui est le plus petit ordinal, a 1 l'ensemble formé de 0, a 2 -> {0,1} et a n->{0,1,...,n-1}.

est alors définie comme l'ensemble de tous les entiers naturels... C'est donc le plus petit ordinal infinie. On peut également définir les notions d'addition, de multiplication et d'exponentiation chez les ordinaux. ainsi et et par suite on peut donc définir ...

Voilou j'espère que j'ai été claire... Parce que c'est quand même pas super évident a dire clairement :marteau:

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 27 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite