Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-28T13:52:59.652Z Has data issue: false hasContentIssue false
  • English
  • Français

On well-quasi-ordering lower sets of finite trees

Published online by Cambridge University Press:  24 October 2008

C. St J. A. Nash-Williams
C. St J. A. Nash-Williams
Affiliation:
King's College, Aberdeen
Get access Rights & Permissions [Opens in a new window]

Abstract

A set Q is quasi-ordered if a reflexive and transitive relation ≤ is defined on Q. It is well-quasi-ordered if it is quasi-ordered and, for every infinite sequence u1, u2,… of elements of Q, there exist i, j such that i < j and ui ≤ uj. A lower set of Q is a subset P of Q such that, if x ≤ y ∈ P, then x ∈ P. The class of lower sets of Q, quasi-ordered by ⊂, is denoted by LQ, and L2Q = L(LQ), etc. The set (, say) of all finite trees is quasi-ordered by writing T1 ≤ T2 if T1 is homeomorphic to a subtree of T2. It is proved that is well-quasi-ordered for all n.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 60 , Issue 3 , July 1964 , pp. 369 - 384
Copyright
Copyright © Cambridge Philosophical Society 1964

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) Berge, C. The theory of graphs and its applications (1958), English translation by Alison Doig (London and New York, 1962).Google Scholar
(2) Higman, G. Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3), 2 (1952), 326–36.CrossRefGoogle Scholar
(3) Kruskal, J. B. Well-quasi-ordering, the tree theorem, and Vázsonyi's conjecture. Trans. American Math. Soc. 95 (1960), 210–25.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