Basic wqo- and bqo-theory. (English) Zbl 0573.06002

Milner, E. C.

Graphs and order. The role of graphs in the theory of ordered sets and its applications, Proc. NATO Adv. Study Inst., Banff/Can. 1984, NATO ASI Ser., Ser. C 147, 487-502 (1985).

[For the entire collection see Zbl 0549.00002.]
A well-ordered set is linearly ordered; it is a chain. The notion of well-ordering has been extended to partially ordered and quasi-ordered sets. This paper is mostly expository, and describes the work that has been done by G. Higman, R. Rado, J. B. Kruskal, C. St. J. A. Nash- Williams, R. Laver and others on well-quasi-ordered sets. A well-quasi- ordered set has finite width and contains no infinite descending chain. Kruskal proved that the class of finite trees is well-quasi-ordered. Nash-Williams defined a stronger condition than well-quasi-order, that of better-quasi-order. He proved that Q is better-quasi-ordered iff there is no bad Q-pattern. The author generalizes some of the results of others. He shows that any block contains a barrier, and any Q-pattern contains either a bad or a perfect sub-pattern.

Reviewer: O.Frink

MSC:

06A06	Partial orders, general
06A05	Total orders

Keywords:

well-ordered set; quasi-ordered sets; well-quasi-ordered sets; better- quasi-ordered

Citations:

Zbl 0549.00002