Ensemble bien ordonné

[Clise]

Bonjour,

Je dois prouver que l'ensemble des suites d'entiers naturels ordonné par l'orde lexicographique est bien ordonné. Soit E, cette ensemble. Ainsi, si a est un élement de E, il s'exprime de la forme suivante : (a0,a1, ...., an, ...) avec ai des entiers naturels pour tout i.

Voila ce que j'ai fait, j'aimerais savoir si mon raisonnement est juste ou s'il y a des subtilités que je n'ai pas vu :S

Je vais supposer que E n'est pas bien ordonné, ainsi d'après la définition du bien ordonné, il existe donc un sous ensemble non vide F de E qui n'a pas d'éléments minimum. Comme E est composé d'une suite d'entiers positifs, F aussi. Ainsi, les différentes valeurs possibles que peuvent prendre les ai de la place i dans F est un sous ensemble Ai des entiers naturels qui est bien ordonné, donc les Ai admettent un minimum. Et ceci est vrai pour tout les i. Donc, comme F est bien ordonné selon l'ordre lexicographique, on peut donc construire un élément de F qui est donc le plus petit des éléments de F et qui est formé des minimums des Ai. Ainsi, il y a contradiction puisqu'on vient de construire le minimum de F qui n'avait pas de minimum par hyptothèse. Donc on peut en conclure que E est bien ordonné.

Merci pour votre réponse

[leon1789]

Bonjour

Le raisonnement par l'absurde a encore frappé :ptdr:

Je vais supposer que E n'est pas bien ordonné, ainsi d'après la définition du bien ordonné, il existe donc un sous ensemble non vide F de E qui n'a pas d'éléments minimum. Comme E est composé d'une suite d'entiers positifs, F aussi. Ainsi, les différentes valeurs possibles que peuvent prendre les ai de la place i dans F est un sous ensemble Ai des entiers naturels qui est bien ordonné, donc les Ai admettent un minimum. Et ceci est vrai pour tout les i. Donc, comme F est bien ordonné selon l'ordre lexicographique, on peut donc construire un élément de F qui est donc le plus petit des éléments de F et qui est formé des minimums des Ai. Ainsi, il y a contradiction puisqu'on vient de construire le minimum de F qui n'avait pas de minimum par hyptothèse. Donc on peut en conclure que E est bien ordonné.

Heu, pourquoi F est bien ordonné selon l'ordre lexicographique ?


Si j'étais toi, je ferais un bon vieux raisonnement "normal" plutôt qu'un truc par l' absurde...

Soit F un sous-ensemble de E. En regardant l'indice 0, quels sont les candidats de F pour être le plus élément de F ? Puis en regardant l'indice 1 ? etc. Ainsi tu construiras indice par indice l'élément minimal de F. :zen:

[Clise]

ok, mais dans ce cas je vois pas bien l'intéret de prendre un sous ensemble F de E alors qu'on doit le prouver pour tous F ? on en prend un quelconque et on généralise ?

Pour F bien ordonné ouais je me suis un peu embrouillée ... cependant comme F est ordonné par l'ordre lexicographique, cet ensemble admet donc un minimum, ce qui est quand même contradictoire avec la définition de F, non ?

[ThSQ]

Le raisonnement par l'absurde a encore frappé

Ils vont avoir sa peau !!

Soit F un sous-ensemble de E. En regardant l'indice 0, quels sont les candidats de F pour être le plus élément de F ? Puis en regardant l'indice 1 ? etc. Ainsi tu construiras indice par indice l'élément minimal de F. :zen:

Ca marche, faut juste pas oublier de préciser (et de dire pkoi) que le procédé s'arrête bien.

[leon1789]

Il vont avoir sa peau !!

:we:

ok, mais dans ce cas je vois pas bien l'intéret de prendre un sous ensemble F de E alors qu'on doit le prouver pour tous F ? on en prend un quelconque et on généralise ?

quand on dit >, il est sous-entendu qu'il est quelconque, sinon on dirait en quoi il est particulier : par exemple, >, etc.

Pour F bien ordonné ouais je me suis un peu embrouillée ... cependant comme F est ordonné par l'ordre lexicographique, cet ensemble admet donc un minimum, ce qui est quand même contradictoire avec la définition de F, non ?

Le problème, c'est qu'il faut prouver que F admet un plus petit élément.

Le "donc" de > est insuffisant. Il faut prouver ce "donc" !

Pour faire la preuve de ce "donc", il faut que tu penses un truc comme ça : Tu vois l'ensemble des mots de la langue française ? Il faut tu cherches le premier d'entre eux (pour l'ordre lexicographique) ? Comment fais-tu ?

Pour les suites, c'est pareil (mis à part qu'il y a une infinité de "lettres", mais c'est pas super grave...)

Ca marche, faut juste pas oublier de préciser (et de dire pkoi) que le procédé s'arrête bien.

il y a un truc à dire...

[Clise]

ok en regardant l'indice 0, le candidat pour être l'élément minimal est contenu dans l'ensemble des élements de F tel que a0 soit le plus petit élément de A0 (il en existe bien un car c'est un sous ensemble des entiers naturels). On se place dans les B0 tel que a0 soit le plus petit élément de A0 et on regarde les a1. La c'est le plus petit élément de A0 inter BO mais il existe encore, et nous avons ainsi B1, and so on ...

Mais comment on s'arrete ? :marteau:

parce que la je vais aller jusqu'a l'infinie et trouver que le plus petit élément appartient à l'intersection des Bi :mur:

[leon1789]

ok en regardant l'indice 0, le candidat pour être l'élément minimal est contenu dans l'ensemble des élements de F tel que a0 soit le plus petit élément de A0 (il en existe bien un car c'est un sous ensemble des entiers naturels). On se place dans les B0 tel que a0 soit le plus petit élément de A0 et on regarde les a1. La c'est le plus petit élément de A0 inter BO mais il existe encore, et nous avons ainsi B1, and so on ... Mais comment on s'arrete ? :marteau:

parce que l'a je vais allé jusqu'a l'infinie et trouvé que le plus petit élément appartient a l'intersection des Bi :mur:

Voilà... c'est bon, tu as compris.

Et maintenant, imagine que F soit formé des suites valant S_i du type 0,0,0,0,..0 (à l'indice i), 1,1,1,1,1, ......

F admet-il un plus petit élément ? si oui, lequel ? sinon, pourquoi ?

[Clise]

ben il admet un minimum qui est l'infinité de 0, non ?

Je suis d'accord avec ça, mais je vois pas pk ce cas particulier va permettre de généraliser a tous les F :S

[leon1789]

ok en regardant l'indice 0, le candidat pour être l'élément minimal est contenu dans l'ensemble des élements de F tel que a0 soit le plus petit élément de A0 (il en existe bien un car c'est un sous ensemble des entiers naturels). On se place dans les B0 tel que a0 soit le plus petit élément de A0 et on regarde les a1. La c'est le plus petit élément de A0 inter BO mais il existe encore, et nous avons ainsi B1, and so on ...

Ceci est faux : ce n'est pas A0 inter BO... c'est simplement l'ensemble les éléments de A0 qui ont le plus petit élément à l'indice 1

[Clise]

Attends reprenons, A0 est l'ensemble des valeurs possibles de a0 et B0 est l'ensemble des élément de F tel que le plus petit éléments de A0 soit a la place 0.

Donc je suis d'accord ce que j'ai écrit est faux, donc l'élément minimum appartient à B0 mais également a l'ensemble B1 (inclus dans B0) tel que min(A0)=a0 et min(A1)=a1 etc , c'est ça ?

Sinon le plus petit élément de F appartient bien a l'intersection des Bi ou je me suis encore trompée ? :briques:

[leon1789]

ben il admet un minimum qui est l'infinité de 0, non ?

Je suis d'accord avec ça, mais je vois pas pk ce cas particulier va permettre de généraliser a tous les F :S

Mais est-ce que cet élément avec une infinité de 0 appartient à F ?

[leon1789]

Je ne l'ai pas noté B0 cet ensemble ?
Mais je suis d'accord c'est faux c'est juste B0, mais l'élément minimum appartient bien a l'intersection des Bi ou je me suis encore trompée ? :briques:

Parce que tu veux peut-être (je ne sais pas) que l'élément minimum de F soit le minimum à chaque indice... mais c'est faux en général.

[Clise]

C'est faux en général ? :doh:

non je ne veux pas forcément que ça soit le plus petit a chaque indice, donc en fait je ne comprend pas très bien pourquoi prendre a chaque indice et faire une récurrence pourquoi ne pas prendre sur le plus grand ? (si on est dans un cas finit bien sur) et si on est dans un cas infinie ben on prend le cas finit et on généralise a l'infinie non ? il y a une subtilité ?

Sinon a priori non il apartient pas a F puisque i=infini, comment on fait alors :mur:

[leon1789]

Sinon a priori non il apartient pas a F puisque i=infini, comment on fait alors :mur:

Bon, résumons ce qui est utile :

On veut démontrer que E est bien ordonné, c'est-à-dire que toute partie F non vide admet un plus petit élément (...dans F !)

Ici, on a un cas particulier (le sous-ensemble des suites 00001111...) qui ne contient pas d'élément minimal.

Conclusion ?

[Clise]

Ben E n'est pas bien ordonnée ?

Pourtant c'est marqué prouver que E est bien ordonné :S

Je sais ça fait un moment que je tourne en rond avec ça.

Si on a un nombre finit de termes, il l'est n'est ce pas ?

[aviateurpilot]

Bonjour,

Je dois prouver que l'ensemble des suites d'entiers naturels ordonné par l'orde lexicographique est bien ordonné. Soit E, cette ensemble. Ainsi, si a est un élement de E, il s'exprime de la forme suivante : (a0,a1, ...., an, ...) avec ai des entiers naturels pour tout i.

je vien de voir les definition de (bien ordonné,ordre lexico..) si j'ai bien compri, alors il faut montrer que tt sous ensemble de E admet un plus petit element par rapport a l'ordre l'exico !!
deja d'apres toi
et tout element a\in E est represente sous la forme .

soient non vide.
et pour
soit la suite tel que
on a et
on suppose que pour un certain :

donc pour tt m, on a ===>
donc
ce est le plus petit element de

[leon1789]

Ben E n'est pas bien ordonnée ?

Pourtant c'est marqué prouver que E est bien ordonné :S

Il doit manquer une hypothèse sur la définition de E. :hein:

[leon1789]

je viens de voir les definitions (...)

oui, c'est ce que je proposais comme procédé ... pour arriver à montrer un contre-exemple !

aviateurpilot, tu as montré l'unicité de l'élément minimal de F, mais pas l'existence ... dans F !

[Clise]

Ben dans ce cas pourquoi aviateurpilot troue un élément minimum ?

[leon1789]

Ben dans ce cas pourquoi aviateurpilot troue un élément minimum ?

non, il ne prouve pas l'existence ...
regarde bien ce qu'il écrit : il arrive à définir une suite qui serait l'unique élément minimal (comme la suite nulle serait l'élément minimal du F particulier qu'on a regardé) mais il ne démontre pas que cette suite unique appartient à F