concours de gros ordinal

J AI DECOCHE LA CASE LATEX CAR IL SEMBLE Y AVOIR UN PROBLEME A LA COMPILATION

On note $T$ l'ensemble des suites finies d'entiers $[a_1;a_2;...a_n>$. J'utilise la notation précédente par soucis d'esthétique.

Quand $s\in T$ et $n\in \N$, la notation "$s+n$" désigne la suite obtenue en rajoutant $n$ au bout de $s$ ie si $s=[a_1;..a_p>$ alors $s+n=[a_1;..a_p;n>$

Une partie $P$ de $T$ ($P$ peut être vue comme un "arbre") est dite bien fondée quand il n'existe aucune "branche infinie dans $P$".

Une branche infinie dans $P$ est une suite $u$ d'entiers telle que pour tout entier $n: [u_1;...u_n>\in P$

Nous nous intéressons aux $P$ bien fondées.

Pour fixer les idées, je vous donne 1 petite question (stylée comme des exercices):

{\it Soit $P$ bien fondée récursif. Montrer qu'il existe un $Q$ bien fondée easy-récursif de même hauteur (ou presque) que $P$}

L'avantage de "marier" bonne fondation et récursivité, c'est que:

1) on sait qu'on peut "aller très loin", ie obtenir des $P$ récursifs avec des hauteurs énormes. Et grace au lemme précédent, on sait qu'on peut obtenir de même avec des arbres easyrecursifs, ie très simples.

{\bf Je lance un concours: proposer des arbres bien fondés easyrecursifs avec des hauteurs les plus grandes possibles dans ce fil... }

ola oui en faisant des modif, j'ai efface la definition de hauteur etc

En l'absence de latex, j'avoue avoir la flemme, bon, mais allons-y:

si $P$ est bien fondé, il existe une et une seule application $g$ de $P$ dans un ordinal $O$ (pris le plus petit possible, et c'est ce $O$ la hauteur) avec la propriété suivante:

Pour $s\in P$: $g(s)$ est le plus petit ordinal strictement supérieur à tous les $g(s+n)$ tels que $s+n\in P$. La définition a un sens car $P$ est bien fondé.