\documentclass{rtaloop}
\rtalabel{kong}

\begin{document}
\begin{solvedproblem}{H.-C. Kong}{}{December 1991}

\begin{abstract}
Is embedding a well-quasi-ordering on strings?
\end{abstract}

Consider the following relation on strings over an infinite set
${\cal X}$ of variables:
$x_1 x_2 \cdots x_m \hookrightarrow y_1 y_2 \cdots y_n$ if there exists a
renaming $\rho : {\cal X} \rightarrow {\cal X}$ such that
$x_i \rho = y_{j_i}$ for $1 \leq j_1 < j_2 < \cdots < j_m \leq n$.
Is this ``embedding'' relation $\hookrightarrow$ a well-quasi-ordering (that
is, must every infinite sequence of strings contain two strings, such that the
first embeds in the second)?

\begin{remark}
The answer is ``yes''. (Map each variable to the position of its leftmost
occurrence and use the fact that strings of natural numbers are
well-quasi-ordered by the embedding extension of $\leq$ to strings.)
\end{remark}

\end{solvedproblem}
\end{document}