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]).


  1. http://www.math.harvard.edu/~lurie/155notes/lecture19.pdf

  2. https://research-repository.st-andrews.ac.uk/bitstream/10023/7963/1/BCCpaperv9.pdf

  3. http://arxiv.org/pdf/1107.5070v2.pdf

Crossposted on MSE.

  • $\begingroup$ Did you mean to write that $A$ is infinite? $\endgroup$ – Andrej Bauer Feb 4 '16 at 7:36
  • $\begingroup$ @AndrejBauer Yes. I know that if $A$ is finite, then this is not possible. $\endgroup$ – Julian Rachman Feb 4 '16 at 7:37
  • $\begingroup$ Ok, I edited the question. $\endgroup$ – Andrej Bauer Feb 4 '16 at 7:38
  • $\begingroup$ 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$. $\endgroup$ – J.-E. Pin Feb 5 '16 at 9:04
  • $\begingroup$ @J.-E.Pin Actually, yes. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Even if A and A^* are infinite, the same situation results? $\endgroup$ – Julian Rachman Feb 4 '16 at 17:05
  • $\begingroup$ @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. $\endgroup$ – Joel David Hamkins Feb 4 '16 at 17:08
  • $\begingroup$ I do not quite understand. Would you be able to show me from a categorical stand-point? $\endgroup$ – Julian Rachman Feb 4 '16 at 17:11
  • $\begingroup$ And elaborate you on your statement? $\endgroup$ – Julian Rachman Feb 4 '16 at 17:33
  • $\begingroup$ 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. $\endgroup$ – Joel David Hamkins Feb 4 '16 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.