Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-03T02:37:05.140Z Has data issue: false hasContentIssue false

Well-quasi-orderings and sets of finite sequences

Published online by Cambridge University Press:  24 October 2008

Richard Laver
Affiliation:
University of California, Los Angeles, U.S.A.

Extract

Section 1 contains a list of the facts about well-quasi-orderings (wqo's) which were established in (1), (4), (7), (10), and (13), with proofs given except for the last three theorems. The theory of well-quasi-orderings is a precursor to Nash–Williams' theory of better-quasi-orderings (10, 11, 12, 6, 7). Section 1 of this paper may be viewed as a beginning to Section 1 of a forthcoming paper, in which an explication of bqo theory is given.

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 1976

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Higman, G.Ordering by divisibility in abstract algebras. Proc. London Math. Soc. 2 (1952), 326336.Google Scholar
(2)Jenkyns, T. A. and Nash-Williams, C. ST J. A.Counter examples in the theory of wellquasi-ordered sets. Univ. of Waterloo (minimeographed).Google Scholar
(3)Kruskal, J. The theory of well-partially-ordered sets. Thesis. (Princeton, 1954.)Google Scholar
(4)Kruskal, J.Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture. Trans. Amer. Math. Soc. 95 (1960), 210225.Google Scholar
(5)Kruskal, J.The theory of well-quasi-ordering: a frequently discovered concept. J. Combinatorial Theory 13 (1972), 297305.CrossRefGoogle Scholar
(6)Laver, R.On Fraissé's order type conjecture. Ann. of Math. 93 (1971), 89111.Google Scholar
(7)Laver, R.An order type decomposition theorem. Ann. of Math. 98 (1973), 96119.Google Scholar
(8)Mader, W.Wohlquasigeordnete Klassen endliche graphen. J. Combinatorial Theory 12 (1972), 105122.Google Scholar
(9)Nash-Williams, C. ST J. A.On well-quasi-ordering finite trees. Proc. Cambridge Philos. Soc. 59 (1963), 833835.Google Scholar
(10)Nash-Williams, C.ST J. A. On well-quasi-ordering tranafinite sequences. Proc. Cambridge Philos. Soc. 61 (1965), 3339.CrossRefGoogle Scholar
(11)Nash-Williams, C.ST J. A. On well-quasi-ordering infinite trees. Proc. Cambridge Philos. Soc. 61 (1965), 697720.Google Scholar
(12)Nash-Williams, C. ST J. A.On better-quasi-ordering transfinite sequences. Proc. Cambridge Philos. Soc. 64 (1968), 273290.Google Scholar
(13)Rado, R.Partial well ordering of sets of vectors. Mathematika 1 (1954), 8995.Google Scholar
(14)Watkins, M. E.A theorem on Tait colorings with an application to the generalized Petersen graphs. J. Combinatorial Theory 6 (1969), 152164.CrossRefGoogle Scholar