# Order-Perserving Bijection $f:A\to A^*$?

Let $A$ be a well-quasi-ordered infnite set. Does there exist an order-preserving bijection $f:A\to A^*$, where $A^*$ is the free monoid over $A$ under the subword ordering? Would this subword ordering make $A^*$ well-quasi-ordered as well (reference to Corollary $1.7$ of [2]).

References:

Crossposted on MSE.

• Did you mean to write that $A$ is infinite? – Andrej Bauer Feb 4 '16 at 7:36
• @AndrejBauer Yes. I know that if $A$ is finite, then this is not possible. – Julian Rachman Feb 4 '16 at 7:37
• Ok, I edited the question. – Andrej Bauer Feb 4 '16 at 7:38
• I suspect that the order you want to use on $A^*$ is not the subword ordering but the following order: $a_1 \cdots a_n \leqslant b_1 \cdots b_m$ if there exists $i_1 < \cdots < i_n$ such that $a_k \leqslant b_{i_k}$ for all $k$. – J.-E. Pin Feb 5 '16 at 9:04
• @J.-E.Pin Actually, yes. – Julian Rachman Feb 5 '16 at 9:39

Unless I have misunderstood, the answer seems to be no.

Let $A=\omega+1$ with the usual order, or indeed, any well-quasi-ordering with an object having infinitely many predecessors. Such an object would get mapped to an element of $A^*$, which we can think of as a finite term over $A$, and every such term has only finitely many subwords. So the map from $A$ to $A^*$ cannot be both order-preserving and bijective.

• Even if A and A^* are infinite, the same situation results? – Julian Rachman Feb 4 '16 at 17:05
• @JulianRachman No, because $\omega$ does biject with $2^{<\omega}$ in an order-preserving way. You can list out all words in countably many letters in an $\omega$ sequence, such that subwords come earlier. – Joel David Hamkins Feb 4 '16 at 17:08
• I do not quite understand. Would you be able to show me from a categorical stand-point? – Julian Rachman Feb 4 '16 at 17:11
• And elaborate you on your statement? – Julian Rachman Feb 4 '16 at 17:33
• You can make a list of all words in an $\omega$ sequence, such that subwords appear earlier. Like this: <>, a, b, aa, ab, ba, bb, c, ac, bc, ca, cb, cc, aaa, aab, ..., d, ad, .... There are various ways to do it. Now just map the nth symbol to the n^th word, and this is an order-preserving bijection. – Joel David Hamkins Feb 4 '16 at 18:18