-1
$\begingroup$

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:

  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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .