Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-26T21:40:20.268Z Has data issue: false hasContentIssue false
  • English
  • Français

On better-quasi-ordering transfinite sequences

Published online by Cambridge University Press:  24 October 2008

C. St. J. A. Nash-Williams
C. St. J. A. Nash-Williams
Affiliation:
University of Aberdeen
Get access Rights & Permissions [Opens in a new window]

Abstract

Let Q be a quasi-ordered set, i.e. a set on which a reflexive and transitive relation ≤ is defined. If, for every finite sequence q1, q2, … of elements of Q, there exist i and j such that i < j and qi ≤ qj then we call Q well-quasi-ordered. For any ordinal number α the set of all ordinal numbers less than α is called an initial set. A function from an initial set into Q is called a transfinite sequence on Q. If ƒ: I1 → Q, g: I2 → Q are transfinite sequences on Q, the statement ƒ ≤ g means that there is a one-to-one order-preserving function ø:I1 → I2 such that f(α) ≤ g(ø(α)) for every α ∈ I1. Milner has conjectured in (3) that, if Q is well ordered, then any set of transfinite sequences on Q is well-quasi-ordered under the quasi-ordering just defined. In this paper, we define so-called ‘better-quasi-ordered sets’, which are well-quasi-ordered sets of a particularly ‘well-behaved’ kind, and we prove that any set of transfinite sequences on a better-quasi-ordered set is better-quasi-ordered. Milner's conjecture follows a fortiori, since every well ordered set is better-quasi-ordered and every better-quasi-ordered set is well-quasi-ordered.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 64 , Issue 2 , April 1968 , pp. 273 - 290
Copyright
Copyright © Cambridge Philosophical Society 1968

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)Erdös, P. and Rado, R.A theorem on partial well-ordering of sets of vectors, J. London Math. Soc. 34 (1959), 222–224.CrossRefGoogle Scholar
(2)Higman, G.Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3) 2 (1952), 326–336.CrossRefGoogle Scholar
(3)Milner, E. C.Well-quasi-ordering of transfinite sequences of ordinal numbers. J. London Math. Soc. (to appear).Google Scholar
(4)Nash-Williams, C. St. J. A.On well-quasi-ordering finite trees. Proc. Cambridge Philos. Soc. 59 (1963), 833–835.CrossRefGoogle Scholar
(5)Nash-Williams, C. St. J. A.On well-quasi-ordering lower sets of finite trees. Proc. Cambridge Philos. Soc. 60 (1964), 369–384.CrossRefGoogle Scholar
(6)Nash-Williams, C. St. J. A.On well-quasi-ordering transfinite sequences. Proc. Cambridge Philos. Soc. 61 (1965), 33–39.CrossRefGoogle Scholar
(7)Nash-Williams, C. St. J. A.On well-quasi-ordering infinite trees. Proc. Cambridge Philos. Soc. 61 (1965), 697–720.CrossRefGoogle Scholar
(8)Rado, R.Partial well-ordering of sets of vectors. Mathematika 1 (1954), 89–95.CrossRefGoogle Scholar