3
$\begingroup$

Let $M = \langle a, b \rangle$ be the free monoid on two generators. Let $<$ be a strict partial order on $M$ compatible with its multiplication. (It suffices to require that for all $x < y$, we have $ax < ay$, $bx < by$, $xa < ya$, $xb < yb$.) Can $<$ be extended to a compatible linear order on $M$? (Does such a linear order even exist?)

The best I was able to do:

  • It would be sufficient to show that if we can linearly order words of length $\leq n$, then the implications this has for words of length $n+1$ (via the 4 axioms outlined earlier) never creates a cyclic relation.
  • WLOG we can assume $a < b$ and from there this implies that words of length $n$ agree with powerset lattice via treating them as subsets of $n$.
$\endgroup$
1
  • 1
    $\begingroup$ If $A$ is a finite, totally ordered alphabet, the shortlex order on $A^*$ is a linear order compatible with the multiplication. $\endgroup$ Commented 9 hours ago

1 Answer 1

Reset to default
2
$\begingroup$

This is not always possible. For example, there is a multiplication-compatible partial order $<$ on $M$ such that $aa < ab$ and $bb < ba$. In any multiplication-compatible extension of this order, $a$ and $b$ must be unrelated, so this order cannot be extended to a total order.

It's not totally obvious that there is such a partial order. The relation generated by the two inequalities $aa < ab$ and $bb < ba$, as well as the requirements of transitivity and compatibility with multiplication is "$w < w'$ if $w$ can be transformed to $w'$ in at least one step using the string rewriting rules $aa \to ab$ and $bb \to ba$".

To verify that this is actually a strict partial order, we need to check it's irreflexive, which amounts to showing that the string rewriting system always terminates (since the length is never increased).

One way to see this is to observe that once you've applied the rule to the first two characters of any string, they will remain different from that point forward. So, given some string of length $n$, any sequence of rewrites is eventually a sequence of rewrites of just the tail of the string. By induction on $n$, that sequence must terminate, so we are done. QED.

Addressing "Does such a linear order even exist?":

Yes, there are many. As J.E. Pin says, the shortlex order is one.

You can also mix and match in all sorts of ways. Here's one broad way to do that, which I'm sure can be generalised further.

Given a finite family of functions $f_i: M \to X_i$ from $M$ to totally ordered sets $X_i$, with the properties

  • if $f_i(x) < f_i(y)$ then $f_i(zx) < f_i(zy)$ and $f_i(xz) < f_i(yz)$
  • if $f_i(x) = f_i(y)$ then $f_i(zx) = f_i(zy)$ and $f_i(xz) = f_i(yz)$
  • the function $w \mapsto (f_1(w), \dotsc, f_n(w))$ is injective

then the ordering induced on $M$ from $X_1 \times \dotsc \times X_n$ (with the lexicographic order) is a multiplication-compatible total order.

Some example of such functions $f_i(w)$ are "count the number of $a$s in $w$", "take the length of $w$", "subtract the number of $a$s in $w$ from twice the number of $b$s in $w$".

$\endgroup$
2
  • 1
    $\begingroup$ This is a very good answer! Just a note, I don't think lex works, and this is why I started spiraling and asked this question in the first place: WLOG $a < b$ and in lex $1 < a$ so $b < ab$ (not true in lex). But shortlex does fix this issue, just FYI I think that part of your answer is wrong. $\endgroup$ Commented 3 hours ago
  • 1
    $\begingroup$ @KeithJ.Bauer, eek! You're right of course, thank you for pointing that out. I was being sloppy/rusty and forgot to check the prefix case properly! $\endgroup$ Commented 3 hours ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.