Article contents
On well-quasi-ordering transfinite sequences
Published online by Cambridge University Press: 24 October 2008
Abstract
. Let Q be a well-quasi-ordered set, i.e. a set on which a reflexive and transitive relation ≤ is defined and such that, for every infinite sequence q1,q2,… of elements of Q, there exist i and j such that i < j and qi ≤ qi. A restricted transfinite sequence on Q is a function from a well-ordered set onto a finite subset of Q. If f, g are restricted transfinite sequences on Q with domains A, B respectively and there exists a one-to-one order-preserving mapping μ of A into B such that f(α) ≤ h(μ(α)) for every α ∈ A, we write f ≤ g. It is proved that this rule well-quasi-orders the set of restricted transfinite sequences on Q. The proof uses the following subsidiary theorem, which is a generalization of a classical theorem of Ramsey (4). Let P be the set of positive integers, and A(I) denote the set of ascending finite sequences of elements of a subset I of P. If s, t∈A(P), write s ≺ t if, for some m, the terms of s are the first m terms of t. Let T1,…,Tn be disjoint subsets of A(P) whose union T does not include two distinct sequences s, t such that s ≺ t. Then there exists an infinite subset I of P such that T ∩ A(I)is contained in a single Tj.
- Type
- Research Article
- Information
- Mathematical Proceedings of the Cambridge Philosophical Society , Volume 61 , Issue 1 , January 1965 , pp. 33 - 39
- Copyright
- Copyright © Cambridge Philosophical Society 1965
References
REFERENCES
- 68
- Cited by