Fonction injective et ensemble bien ordonné

par **Clise** » 12 Juil 2008, 19:50

Bonjour a tous,

J'ai un problème a vous soumettre (car je ne sais comment commencer). Je pense avoir toutes les hypothèses cette fois ;) :ptdr:

Il faut trouver la démonstration de la proposition suivante :
Si (S,<) est un ensemble bien ordonné et si S est dénombrable, alors il existe une fonction injective f de S dans R tel que f(x)
Si vous avez des idées de comment partir. N'hésitez pas...

Merci pour vos réponses.

par **leon1789** » 12 Juil 2008, 20:01

si S est dénombrable, tu peux indexer ses éléments, en partant du plus petit, etc.
S = x_0, x_1, ....

Une fois que tu as fait ça, vois-tu une fonction strictement croissante apparaître ? (une fonction qui va de S dans N...)

par **miikou** » 12 Juil 2008, 20:02

je me permet un 'mdr'

par **leon1789** » 12 Juil 2008, 20:03

miikou a écrit:je me permet un 'mdr'

Oui, à condition que S soit inclus dans R ! :id:

par **leon1789** » 12 Juil 2008, 20:04

miikou a écrit:je me permet un 'mdr'

pourquoi ?

(en plus tu as changé ton message ... :ptdr: )

par **miikou** » 12 Juil 2008, 20:16

parce que j'ai limpression que des fois les gens ne prennent meme pas le tps de reflechir aux exo qu'ils postent..
et j'ai changé en voyant que tu avais répondu avec moi si tu veux tt savoir ;)

par **leon1789** » 12 Juil 2008, 20:18

miikou a écrit:parce que j'ai limpression que des fois les gens ne prennent meme pas le tps de reflechir aux exo qu'ils postent..

tu es dur là :we:

PS.
Attention, f(x) = x ne fonctionne que si S est inclus dans R :id:

par **miikou** » 12 Juil 2008, 20:21

exact, mais etant donné le 'difficulté ' de l'exercice jai supposé que la relation d'odre etait forcement celle des reels ;)

par **Clise** » 12 Juil 2008, 20:25

déja miikou je te permets pas, j'y ai réfléchis et je suis tombé sur votre réponse cependant comme léon 1789 l'a dit :

leon1789 a écrit:Attention, f(x) = x ne fonctionne que si S est inclus dans R :id:

Ca ne marche pas si S n'est pas inclus dans R, or je travaille avec des ordinaux donc des ensembles bien ordonnés dont chaque terme est l'ensemble de ces prédésséseurs qui peuvent être plus grand que N...

donc voila, je pensais comme vous, mais après je me suis rendu compte que c'était peut être pas aussi simple qu'il n'y paraissait :S

Alors vous avez des idées ?

par **aviateurpilot** » 12 Juil 2008, 22:28

leon1789 a donné la solution,
puisque S est denombrable, on prend

et

dans ce cas on a

et

et pour

on trouve facilmeent que

fini et que

avec

donc

maintenant on peux prendre

tel que

qui est bien monotone

par **Clise** » 13 Juil 2008, 00:19

ok, merci pour ta réponse..
Décidément c'est toujours vous deux qui répondez a mes posts ;) :we:

par **Daniel-Jackson** » 13 Juil 2008, 21:37

aviateurpilot a écrit:leon1789 a donné la solution,
puisque S est denombrable, on prend

Et qu'en est il des ensemble S qui sont dénombrables et qui n'ont pas de min ? Exemple

Je pense plutôt procéder de cette façon:

S est bien ordonné et dénombrable donc il y a une bijection de S sur Z , on dénombre les éléments de S par l'ordre :

, avec

pour tout i .
Et la fonction est celle donnée par aviateurpilot

par **leon1789** » 13 Juil 2008, 21:47

Daniel-Jackson a écrit:S est bien ordonné et dénombrable donc il y a une bijection de S sur Z , on dénombre les éléments de S par l'ordre : , avec pour tout i .
Et la fonction est celle donnée par aviateurpilot

Si S est bien ordonné alors S possède un min.
Et si de plus S et dénombrable alors il y a une bijection de S sur N !
(Et la fonction est celle donnée par aviateurpilot.)

par **leon1789** » 13 Juil 2008, 21:53

Daniel-Jackson a écrit:Et qu'en est il des ensemble S qui sont dénombrables et qui n'ont pas de min ? Exemple

Si S n'est pas bien ordonné mais dénombrable, comment justifier qu'on peut indexer ses éléments sur Z de manière croissante ???

par **aviateurpilot** » 14 Juil 2008, 00:10

leon1789 a écrit:Si S n'est pas bien ordonné mais dénombrable, comment justifier qu'on peut indexer ses éléments sur Z de manière croissante ???

on prend

qui est denombrable et n'est pas bien ordonné
mais on peut pas indexer ses éléments sur Z de manière croissante.

par **leon1789** » 14 Juil 2008, 11:10

Oui, la dénombrabilité seule ne suffit pas pour indexer de manière croissante sur Z.

aviateurpilot a écrit:on prend qui est denombrable et n'est pas bien ordonné
mais on peut pas indexer ses éléments sur Z de manière croissante.

...à cause de son élément minimal, oui :we:

par **Clise** » 14 Juil 2008, 12:29

ok, merci pour vos réponses, mais j'ai regardé ce que vous proposez a tête reposée, et j'ai peur que ce ne soit pas suffisant. En effet, comme je vous l'ai dit, je travaille avec des nombres ordinaux, donc des ensembles bien ordonnés...

Cependant, ceux ci peuvent être plus grand que N, par exemple w...
donc si je prend comme ensemble S = w+w = w.2... On peut effectivement "compter" les nombres compris dans w avec la méthode proposé par aviateurpilot, mais on n'arrivera jamais a w, w+1, w+2... On peut dire qu'on compte de manière a ce que les nombres pairs soient dans w et les nombres impairs dans w+w\w... mais dans ce cas comment faire si on prend S = w.3, w.n, ou enore w^w...

page wikipedia sur les nombres ordinaux et l'arithmétie ordinale :
http://fr.wikipedia.org/wiki/Nombre_ordinal
http://fr.wikipedia.org/wiki/Nombre_transfini

par **leon1789** » 14 Juil 2008, 12:42

nous avons prouvé ce que tu demandais, à savoir

Clise a écrit:Si (S,<) est un ensemble bien ordonné et si S est dénombrable, alors il existe une fonction injective f de S dans R tel que f(x)<f(y) pour tout x,y appartenant a S tel que x<y (en gros monotone quoi).

Maintenant, si S n'est pas dénombrable, mais équipotent à R, c'est autre chose...

par **Clise** » 14 Juil 2008, 12:45

Si j'ai comme hypothèse S dénombrable... Un nombre ordinal peut être ou ne pas être dénombrable. Dans mes hyptohèses il n'était fait aucune mention qu'on pouvait compter tous les éléments les uns a la suite des autres... on "peut" les compter mais l'ordre est particulier a chaque S...

Par contre c'est vrai que je n'ai fait aucune mention de la puissance de mon ensemble... milles excuses... :triste:

par **leon1789** » 14 Juil 2008, 14:50

Heu, j'ai un gros doute maintenant sur un passage de la démo :

aviateurpilot a écrit:pour on trouve facilement que fini

Ca ne fonctionne pas :

bien ordonné, dénombrable, mais l'ensemble des éléments strictement inférieurs à

est infini...

Clise a écrit:Cependant, ceux ci peuvent être plus grand que N, par exemple w...
donc si je prend comme ensemble S = w+w = w.2... On peut effectivement "compter" les nombres compris dans w avec la méthode proposé par aviateurpilot, mais on n'arrivera jamais a w, w+1, w+2...

exactement.

Fonction injective et ensemble bien ordonné

fonction injective et ensemble bien ordonné

Qui est en ligne