Forum de mathématiques - Bibm@th.net

so456

Invité

ordre lexicographique

Bonsoir,
J'aimerais savoir pourquoi N² muni de l'ordre lexicographique est bien fondé.
Merci d'avance!

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : ordre lexicographique

Bonjour,

  Ce n'est pas si facile. Il suffit de démontrer par récurrence sur [tex]p\geq 0[/tex] la propriété suivante :

[tex]\mathcal P_p="[/tex]il n'existe pas de suite [tex](x_n=(a_n,b_n))\subset\mathbb N^2[/tex] strictement décroissante vérifiant [tex]a_0=p[/tex]".

Initialisation : Supposons par l'absurde qu'une telle suite existe. Alors, pour tout entier [tex]n\geq 1[/tex], on sait que [tex]a_n\leq a_0[/tex] et donc [tex]a_n=a_0[/tex]. Mais alors, la suite [tex](b_n)[/tex] doit être strictement décroissante, et c'est une suite d'entiers positifs.
C'est impossible!

Hérédité : Supposons la propriété démontrée jusqu'au rang [tex]p[/tex] et prouvons la au rang [tex]p+1[/tex]. Comme précédemment, on raisonne par l'absurde et on suppose qu'il existe une suite [tex](x_n=(a_n,b_n))\subset\mathbb N^2[/tex] strictement décroissante vérifiant [tex]a_0=p+1[/tex].  Alors, pour tout entier [tex]n\geq 1[/tex], on sait que [tex]a_n\leq a_0[/tex]. Si pour tout entier [tex]n[/tex], on avait [tex]a_n=a_0[/tex], alors on obtiendrait une contradiction en raisonnant exactement de la même façon que pour l'initialisation. Donc il existe un entier [tex]n_0[/tex] tel que [tex]a_{n_0}\leq p[/tex]. Mais alors la suite [tex](x_n)_{n\geq 0}[/tex] est une suite strictement décroissante de [tex]\mathbb N^2[/tex] dont le premier terme est inférieur ou égal à [tex]p[/tex]. Ceci contredit l'hypothèse de récurrence.

Remarque qu'on utilise un raisonnement par l'absurde à l'intérieur d'une récurrence forte!
Plus généralement, l'ordre lexicographique défini sur le produit fini d'ensembles ayant un ordre bien fondé est lui-même un ordre bien fondé.