On well-quasi-ordering finite sequences (Q1120606)

Let (Q,\(\leq)\) be a quasi-ordered set, F(Q) the set of all finite sequences of elements of Q. If \((a_ 1,...,a_ n)\) and \((b_ 1,...,b_ n)\) are sequences of equal length in F(Q), the first one is said to be \(\leq^*\) the second iff \(a_ i\leq b_ i\) for \(i=1,...,n\). Then \(\leq^*\) is a quasi-order on F(Q). In F(Q), \textit{G. Higman} [Proc. Lond. Math. Soc., III. Ser. 2, 326-336 (1952; Zbl 0047.034)] defined a quasi-order \(\leq^ F\) by \(f\leq^ Fg\) iff g has a subsequence h satisfying \(f\leq^*h\). The author generalizes this quasi-order as follows: If N is a subset of the set \({\mathbb{N}}\) of positive integers, \(\leq^ N\) denotes the coarsest quasi-order on F(Q) finer than \(\leq^*\) such that for any \((a_ 1,...,a_ m)\in F(Q)\) one has \((a_ 1,...,a_{i-1},a_{i+1},...,a_ m)\leq^ N(a_ 1,...,a_ m)\) for all \(i\in N\cap \{1,...,m\}\). (For \(N={\mathbb{N}}\) one has \(\leq^ N=\leq^ F.)\) Then the author proves the equivalence of the following two statements about a subset N of \({\mathbb{N}}:\) (i) N is infinite. (ii) For each well- quasi-ordered (wqo-) set (Q,\(\leq)\) the set \((F(Q),\leq^ N)\) is wqo. This generalizes Higman's theorem [loc. cit.]: If (Q,\(\leq)\) is wqo, then \((F(Q),\leq^ F)\) is wqo.