# Can a language have $\Sigma^{*}$ as its syntactic monoid?

As per the title I was wondering if it's possible for a language $L \subseteq \Sigma^{*}$ to have $\Sigma^{*}$ as its syntactic monoid and if so could one give an example of such a language? I first thought that this was probably an easy question with a simple answer but I haven't been able to make much progress with it, maybe it has a simple answer and I am just overlooking it?

If we look at the syntactic congruence $\sigma_L = \{(w,z) \in \Sigma^{*} \times \Sigma^{*}: (\forall u, v \in \Sigma^{*}) \; uwv \in L \Leftrightarrow uzv \in L\}$ we see that in order to have $w \cong_{\sigma_{L}} z \Leftrightarrow w = z$ we must have that $(\forall w, z \in \Sigma^{*} \; w \not = z) \; (\exists u, v \in \Sigma^{*})\; uwv \in L \Leftrightarrow uzv \notin L$. Which seems like quite a strong condition. It's also clear that such a language couldn't be regular as it is known that a language is regular if and only if it has a finite syntactic monoid.

• There is a mistake in your last statement: you just need the existence of a pair (u,v) to distinguish 2 elements (w,z), not all possible pairs. The negation of $\forall$ is $\exists$. The precise statement is: $(\forall w\neq z)(\exists (u,v)) uwv\in L \Leftrightarrow uzv\notin L$ May 8 '13 at 13:44
• Yes, you're right. I have edited my question to fix that. May 13 '13 at 15:45
• The language of palindromes over a non-unary alphabet works: cs.stackexchange.com/a/33417/683. May 6 '18 at 8:21

Consider $\{i\#a\#w: w_i = a\}$, where $i$ is an integer indicating index in a word (say, written in unary), $a$ is a single letter and $w$ is a word. This language says that at $i$-th place the word $w$ has letter $a$.

If $a \neq b$ then $a,b$ differ at some position $i$ and you can say $i \# a_i \# a \in L$ while $i \# a_i \# b \notin L$. Or, they can differ at length, but then you talk about the longer string.

This works for any alphabet with at least two characters; for unary alphabets you can use powers of two, squares etc. 

• I don't think it works: as soon as you use three #, then you are out of the language, and all words become equivalent. More generally, any language assuming a particular number of occurence of some letter cannot have A* as syntactic monoid. May 13 '13 at 22:13
• dkuper: No, $w$ can contain many $\#$. Only the first two $\#$ count in a word, they indicate division to $i,a$ and $w$ (in fact, the $\#$ between $a$ and $w$ is unneccessary). May 13 '13 at 22:18
• ah ok then it works, thanks (I cannot cancel the downvote until the answer is edited...) May 13 '13 at 22:24

It seems to work to take $L=\{ww: w\in\Sigma^* \text{and$|ww|$is a power of$2$}\}$.

First, we can show that if $|u|>|v|$ then they are not equivalent. Indeed, there is $x$ such that $|uxux|$ is a big power of $2$, say $2^{|u|+|v|}$. Therefore, $uxux\in L$.

But then the length of $vxux$ cannot be power of $2$, because its difference to $2^{|u|+|v|}$ is only $|u|-|v|$. Therefore, if we take $y=xux$, we have $uy\in L$ and $vy\notin L$.

Now it suffices to show that words of the same length are not equivalent. Let $u\neq v$ with $|u|=|v|$, and let $x$ such that $|ux|$ is a power of $2$ (and then so is $|uxux|$). Then you can see that $(u,v)\notin\sigma_L$ because $uxux\in L$ and $uxvx\notin L$.

• Could you explain why $uu \in L$, I'm not sure that the length of $uu$ has to be a power of 2. May 13 '13 at 15:46
• oups sorry, yes you're right we first need to complete u with a word x to reach a power of 2, I edit the answer May 13 '13 at 22:09