Sur les prémeilleurordres

Pouzet, Maurice

Annales de l'Institut Fourier, Tome 22 (1972) no. 2, pp. 1-19.

Cet article traite de certains préordres généralisant le bon ordre. On étudie les rapports entre la notion de préordre artinien d’incomparabilité finie (pour qui toute partie a des éléments minimaux incomparables en nombre fini) et deux notions de prémeilleur ordre introduites successivement par Hash-Williams en 1965 puis par Jullien en 1969. On montre que ces deux notions sont identiques (ce qui était conjecturé par Jullien) au moyen du résultant suivant :

Un préordre $X$ est un prémeilleur ordre (au sens de Nash-Williams) si et seulement si la classe des suites ordinales à valeur dans $X$ est artinienne d’incomparabilité finie (une suite $s$ étant antérieure à une suite $t$ lorsque l’on peut appliquer, en respectant l’ordre des indices, chaque terme de $s$ sur un terme de $t$ qui lui est postérieur).

Enfin, on annonce quelques résultats concernant la notion de $\alpha$prémeilleur ordre (notions intermédiaire modulo l’ordinal $\alpha$ entre celle d’artinien d’incomparabilité finie et celle de prémeilleur ordre) introduite par Fraissé en 1970.

The principal object of this paper is studying the connexion between well quasi ordering (every part of which has always a finite number of minimal elements) and two notions of better quasi ordering which were introduced first by Nash-Williams in 1965, then by Jullien in 1969.

It is proved those two notions are the same (what was a Jullien’s conjecture) by the following result:

A quasi ordered set $X$ is better quasi ordered (in Nash-Williams’ sense) iff the class of ordinal sequences on $X$ is well quasi ordered. (A sequence $s$ is said to be smaller than a sequence $t$ when each term of $s$ can be applied on one greater term of $t$, preserving the order of sequences.)

Finally some results concerning the notion of $\alpha$-better quasi ordering are announced (that last notion, which is intermediate (modulo $\alpha$) between well quasi ordering and better quasi ordering, was introduced by Fraisse in 1970).

[1] E. Corominas, Sur une application de l'algèbre ordinale à la théorie des groupes abéliens de torsion, C.R. Acad. Sci., 272 (1971), Série A, p. 1357-1359. | MR | Zbl

[2] A. Denis, Arbre et théorème de Corominas-Laver (mémoire Lyon, 1970).

[3] R. Fraisse, Sur la comparaison des types d'ordre, C.R. Acad. Sci., 226 (1948) Série A, 987-988 et 1 330-1 331. | Zbl

[4] R. Fraisse, Abritement entre relations et spécialement entre chaînes, Symposia Mathematica, 1970, vol. 5, p. 203-251. | MR | Zbl

[5] G. Higman, Ordering by divisibility in abstract algebra, Proc. London Math. Soc., (1952), 326-336. | MR | Zbl

[6] P. Jullien, Sur les types d'ordres dispersés (polycopié), Contribution à l'étude des types d'ordres dispersés (1969), Thèse Fac. Sc. Marseille.

[7] Kruskal, Well quasi ordering and Rado's conjecture, Non publié.

[8] Kruskal, Well quasi ordering, the tree theorem, and WAZSONYI'S conjecture, Transactions of AMS 95 (1960), 210. | Zbl

[9] R. Laver, űOn Fraisse'sƇ order type conjecture, Thèse Université de Californie (Berkeley), U.S.A. on Annal. of Math., vol. 93, N. 1 (1971), p. 89-111. | MR | Zbl

[10] C. St. J. A. Nash-Williams, On well quasi ordering transfinite sequences, Proc. Camb. Philos. Soc., 61 (1965), 33-39. | MR | Zbl

[11] C. St. J. A. Nash-Williams, On well quasi ordering infinite trees, Ibid., 61 (1965), 697-720. | MR | Zbl

[12] C. St. J. A. Nash-Williams, On better quasi ordering transfinite sequences, ibid., 64 (1968), 273-290. | MR | Zbl

[13] M. Pouzet, Sur des conjectures de Fraisse et les prémeilleurs ordres, C.R. Acad. Sci., 270, (1970), Série A, 1.3. | MR | Zbl

[14] M. Pouzet, Sur des conjectures de Fraisse ; Publications du Département de Mathématiques, Fac. Sc. Lyon, t. 7, fasc. 3, 1971, p. 55-104. | Numdam | MR | Zbl

[15] M. Pouzet, Sur certaines algèbres préordonnées, Thèse 3e Cycle, Avril 1970, n° 500, Université de Lyon.

[16] M. Pouzet, Algèbre ordinale prémeilleur ordonnée, C.R. Acad. Sci., 270 (1970), Série A, 300-303. | MR | Zbl

[17] R. Rado, Partial well ordering of sets of vectors, Mathematika 1 (1954), 89-95. | MR | Zbl