Note on compatible well orders on a free monoid (Q1188318)

Let \(\Sigma\) be an alphabet with two elements. A total order \(\sigma\) on the free monoid \(\Sigma^*\) is said to be compatible if \(x \sigma y\) implies that \(zxw \sigma zyw\) for all strings \(w\) and \(z\) in \(\Sigma^*\). Such an order is said to be length-sensitive if \(| x| < | y|\) implies \(x \sigma y\), where \(| x|\) is the length of \(x\). In this paper it is proved that there are uncountably many length-sensitive compatible orders on \(\Sigma^*\).