Définition ordre sous-mot

Bonjour,
 J'ai appris il y a peu la notion de bel ordre (suite à un premier contact par le lemme de Dickson). Je me suis appliqué à en démontrer des propriétés basiques, puis ai étudié le théorème de Kruskal. Ensuite je suis allé voir ce qu'était le lemme de Higman , mais le problème, c'est que je n'ai pas la définition de l'ordre sous-mot, du coup, je suis bien embêté. Je suppose qu'il s'agit d'autre chose qu'un ordre lexicographique.
  Merci d'avance pour toute réponse.
 

Réponses

  • Foys
    Modifié (10 Jul)
    Selon toute vraisemblance étant donné un alphabet (i.e. un ensemble) $A$ et deux entiers $p,q$, un mot $x\in A^p$ est dit "sous-mot" d'un autre mot $y\in A^q$ s'il existe une fonction strictement croissante $f$ de $ \{1,...,p\}$ dans $\{1,...,q\}$ telle que $y_{f(k)} = x_k$ pour tout entier $k\in \{1,...,p\}$.

    "Etre un sous-mot" est évidemment une relation d'ordre sur l'ensemble $\bigcup_{n\in \N} A^n$ des mots sur $A$.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Titi le curieux
    Modifié (10 Jul)
    Bonjour,
      Merci beaucoup pour la réponse.
      Cependant, cette définition me semble trop restrictive pour que ça fonctionne. En effet si je prend $A=\mathbb{N}$ et que je prend une suite de singletons tous différents, ça ne fonctionne pas. Mais vu que l'idée a l'air très bonne, je vais la reprendre avec $y_{f(k)} \leq x_k$ au lieu de $y_{f(k)} = x_k$.
    Encore merci

    Edit: Sachant qu'une suite de mot sur $A$ possède une suite extraite dont la longueur des mots est croissante, à quelques développements près, ça tombe sous le coup du fait l'ensemble des mots d'une longueur donnée est bel ordonné.
  • Attention, pour Higman, l'alphabet doit être fini pour la définition de @Foys avec l'égalité. Les beaux pré-ordres sont en effet sans antichaîne infinie. 
    De manière général, si $(X,\leqslant_X)$ est un ensemble ordonné, l'ordre des sous-mots sur $X^*$ est défini par, pour tout $x,y \in X^*$ de longueurs respectives $p$ et $q$, $x \leqslant_{X^*} y$ ssi il existe $f : \{1,...,p\} \rightarrow \{1,...,q\}$ strictement croissante telle que $\forall k, x_k \leqslant_X y_{f(k)} $. Le lemme d'Higman énonce que $X$ est un bpo ssi $X^*$ est un bpo. Dans la définition précédente, l'ensemble en question était muni de l'égalité, qui est un bpo ssi $X$ est fini (via les antichaînes).
    Ta preuve d'Higman me semble un peu courte, je pense que tu sautes quelques arguments.

  • Il existe des preuves du lemme de Highman sans axiome du choix dépendant? Sur la page de Wikipédia, en raisonnant par l'absurde on construit une suite $(x_n)_{n\geq 0}$ en prenant pour tout $n\in \N$, $x_n$ parmi les éléments de longueur minimale tel qu'il y ait une "mauvaise suite $y$" (i.e. violant la condition de beau préordre) telle que $y|_{\{0,1,...,n\}} = x|_{\{0,1,...,n\}}$.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • J'ai effectivement cette preuve en tête. J'ai souvenir que la preuve de Higman nécessite quelques outils puissants, d'où mon étonnement devant l'idée de preuve de @Titi le curieux
  • Un ami qui travaille sur des preuves en Coq de différents théorèmes de bpo me souffle dans l'oreillette que, dans le cas où la relation $\leqslant_X$ est décidable, il doit y avoir moyen de s'en passer (sans en mettre sa main à couper pour autant).
  • Bonjour,
      Merci @Heuristique, notamment pour la confirmation de la définition.
       Je venais pour modifier mon edit, mais je vois que l'erreur a été remarqué. Je me suis complètement planté, l'idée de preuve ne fonctionne pas du tout (à la limite si la longueur des élément de la suite est majorée, mais dans ce cas, ça n'apporte rien à ce qu'on savait). Du coup, j'ai essayé par un autre moyen, sachant que la définition du bel ordre est équivalent à "la propriété de Dickson" (toute partie possède une quantité finie de minorant), mais je n'y suis pas parvenu non plus. Finalement j'ai trouvé ce document (ça se trouve page 5) et j'ai un peu buggué au début (pourtant j'avais lu un argument similaire hier), mais finalement, ça va.
  • Foys
    Modifié (11 Jul)
    La preuve du lemme de Highman donnée sur la page wikipédia anglaise est courte et intuitive.

    Le truc est qu'il s'agit d'une preuve dans ZF avec axiome du choix dépendant (on doit pouvoir rogner un peu mais il s'agit essentiellement de ça). Le lemme de Highman intéresse apparemment beaucoup de monde, de chapelles variées et en particulier des gens des "reverse mathematics" lui portent un intérêt sauf que pour eux ZF+ACdép est une théorie ultra forte qu'ils n'utilisent pas. Quand on se donne des axiomes forts c'est un peu normal qu'on ait des preuves courtes. Je me  demande dans quel sorte de fragment de Peano ce résultat est valide et jusqu'où on peut descendre mais dans ce cas il est normal que la preuve soit plus technique.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Foys
    Modifié (11 Jul)
    Ci-dessous je donne l'un des ingrédients essentiels de la preuve de Highman du wiki anglais (évoqué mais non prouvé sur ladite page; le reste de l'argument est à mon avis limpide mais je peux le détailler).

    Soit $(X,\leq)$ un ensemble muni d'un beau préordre. Alors pour toute suite $\left ( x(n)\right )_{n\in \N}$ d'éléments de $X$, on peut extraire de $x$ une sous-suite croissante $(*)$.

    Lemme: Soit $y$ une suite de $X$. Pour tout entier $n$, on pose $E(y,n):= \{p \in \N \mid p \geq 1+n \wedge y_p \geq y_n\}$. Alors il existe $n\in \N$ tel que $E(y,n)$ est infini.

    En effet, si ce n'est pas le cas, on définit par récurrence une suite strictement croissante d'entiers $(\mu(n))_{n\in \N}$ de la manière suivante: on pose $\mu(0):=0$. Puis pour tout $n\in \N$, comme $E(y,\mu(n))$ est fini, on prend pour $\mu(n+1)$ le plus petit entier supérieur à $1+\mu(n)$ tel que pour tout entier $q \geq \mu(n+1)$, $q \notin E(y, \mu(n))$. 
    La suite ainsi définie a alors par construction la propriété suivante: pour tous $p<q$, $y_{\mu(q)} \notin E(y, \mu(p))$ (et donc on n'a pas $y_{\mu(q)} \geq y_{\mu(p)}$ $(\dagger)$): en effet, pour tout $r\geq \mu(p+1) $, $y_r \notin E(y, \mu(q))$.
    Or $(\dagger)$ contredit le fait que $\leq$ est un beau préordre sur $X$. Le résultat en découle.

    ##########################

    Le lemme permet de démontrer la proposition $(*)$. Soit $x\in X^{\N}$. On construit une suite de fonctions $\varphi_n: \N \to \N$ strictement croissantes et une suite d'entiers $(m_n)_{n \in \N}$ de la façon suivante:
    On prend pour $m_0$ le plus petit entier $k$ tel que $E(x,k)$ est infini et $\varphi_0$ l'unique bijection strictement croissante de $\N$ dans $E(x,m_0)$.

    On suppose $\varphi_0, \varphi_1,... , \varphi_n$ construites. On prend pour  $m_{n+1}$ le plus petit entier $k$ tel que $E(x \circ \varphi_0 \circ \varphi_1 \circ ... \circ \varphi_n, k )$ est infini; et on prend pour $\varphi_{n+1}$ l'unique bijection strictement croissante de $\N$ dans $E(x \circ \varphi_0 \circ \varphi_1 \circ ... \circ \varphi_n, m_{n+1} )$.
    On pose alors $\beta_0:= m_0$ et $\beta_{n+1}:= \varphi_0 \circ \varphi_1 \circ ... \circ \varphi_n(m_{n+1})$.

    On a alors $\beta$ strictement croissante (car pour tout entier $n$, $m_n < \varphi_n (k)$ pour tout $k$ par définition de $E$ et en particulier $m_n < \varphi_n (m_{n+1})$ et par croissance stricte des $\left (\varphi_i \right)_{ i \in \N}$ on obtient $\beta_n = \varphi_0 \circ ... \circ \varphi_{n-1} (m_n) < \varphi_0 \circ ... \circ \varphi_{n-1} \circ \varphi_n (m_{n+1}) = \beta_{n+1}$).

    Enfin, pour tous entiers $n,k$, $\varphi_{n} (k) \in E(x \circ \varphi_0 \circ ... \circ \varphi_{n-1}, m_n) = \{p \in \N \mid p \geq 1+\beta_n \mid x \circ \varphi_0 \circ ... \circ \varphi_{n-1} (k) \geq x (\beta_n)\} $ et donc $x(\beta_{n+1}) \geq  x (\beta_n)$. En particulier $x \circ \beta$ est alors croissante par construction et $(*)$ est démontré.

    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
Connectez-vous ou Inscrivez-vous pour répondre.