# Cancellable elements of a power semigroup

For a semigroup $S,$ its power semigroup $P(S)$ is the semigroup of all non-empty subsets of $S$ with the operation given by $AB=\{ab\,|\,a\in A,b\in B\}.$ I would like to know about the cancellable elements of $P(S)$ given some knowledge of cancellability in $S.$

If $s\in S$ is left-cancellable in $S,$ then $\{s\}$ is also left-cancellable in $P(S)$ because if $sA=sB$ and $a\in A,$ then $sa=sb$ for some $b\in B,$ and $a=b\in B$ follows.

There can be cancellable elements of $P(S)$ with more than one element: for a free semigroup $F,$ any set of the free generators is cancellable from both sides, since from its product with any set $A$ we can recover $A$ by looking at the first letters of each word in the product and removing the letters. This is also an example with $S$ two-sided cancellative.

The first question that comes to mind here is whether

we can find $S$ and a cancellable $A\subseteq S$ such that $A$ has an element not cancellable in $S.$

Another question is what happens for cancellative semigroups. For the commutative ones, we can show that only the singletons are (left-)cancellable in $P(S)$ (let's call this property $(P)$.) That is because then, if $x,y\in A,\,x\neq y,$ we have $A(S\setminus\{xy\})=AS,$ which is easy to check using commutativity and cancellation laws in $S.$ With regard to the first question, I don't see if it can be done without the cancellation laws.

Actually, this is in a sense a "good" method of showing that the only cancellable elements of $P(S)$ are singletons. That is, the following two conditions are equivalent for any semigroup $S$ and $A\subseteq S.$

• $A$ is not left-cancellable.
• There exists $c\in S$ such that $A(S\setminus\{c\})=AS.$

Suppose $A$ is not left-cancellable. Then we have $AB=AC$ for some $B\neq C.$ Without loss of generality, take $c\in C\setminus B.$ Then $A(S\setminus\{c\})=AB\cup A(S\setminus\{c\})=AC\cup A(S\setminus\{c\})=AS.$

So to check that a left-cancellative semigroup has the property $(P),$ we need to find such a $c$ for every $A$.

Can this criterion be simplified further? Can we just look for the $c$ for any two given elements of $A$ as in the commutative case? We can in every example I can think of. Can we just use two-element sets $A$ to check it?

The commutative cancellative semigroups are not the only ones satisfying $(P)$. Groups satisfy it as well. Also, the multiplicative structure of non-zero Lipschitz quaternions does.

We also have that any left-cancellative semigroup satisfying $(P)$ will have to satisfy the right Ore condition. Suppose $S$ is left-cancellative and satisfies $(P).$ Let $x,y\in S.$ Then we have $A\neq B$ such that $\{x,y\}A=\{x,y\}B.$ Without loss of generality, let $b\in B\setminus A.$ Then $yb=xa$ for some $a\in A$ since $yb=ya$ is impossible if $y$ is left-cancellable and $b\not\in A.$

However, this semigroup is both two-sided Ore and two-sided cancellative, but doesn't seem to satisfy $(P).$ $\{x,y\}$ seems to be a cancellable subset.

So what is $(P)$ really?

The class of left-cancellative semigroups satisfying it is clearly globally determined, which is why I started to think about this in the first place.

• Oh, and also... Is $(P)$ closed under finite products? – Michał Masny Jan 5 '15 at 3:37
• One more example is a right zero semigroup: it is left-cancellative, and since its power semigroup is again a right zero semigroup, it is again left-cancellative. I didn't post it in the question, because I have really been thinking about two-sided cancellativity. This formulation of the question is a concession due to the fact that I haven't been able to say anything special about the two-sided version of the problem. – Michał Masny Jan 5 '15 at 4:27
• OK, this is most likely pushing it, but I remembered one more question: for a two-sided cancellative $S,$ can we have a left-cancellable subset $A$ that's not right-cancellable? – Michał Masny Jan 5 '15 at 7:19
• I can construct non cancellative semigroups with a 3-element cancellable set whose 2-element subsets are not. – Benjamin Steinberg Jan 11 '15 at 14:46
• @Benjamin If it's not too much trouble, could you show an example? It sounds interesting. – Michał Masny Jan 11 '15 at 15:56

Here is an example of a cancellable set with a non cancellable element. Take the semigroup with presentation $S=\langle a,b,c\mid ab=ac, ba=ca\rangle$

One checks that $ac\to ab$ and $ca\to ba$ is a complete rewriting system. The normal forms are elements with no $c$ next to an $a$. Notice that $b$ is cancellable since left and right multiplication by it preserves normal forms, $a$ is not cancellable and multiplying a normal form on the left by $a$ or $b$ results in a word whose normal form begins with $a$ or $b$ respectively. Thus $\{a,b\}$ is cancellable.

Indeed, $\{a,b\}X=\{a,b\}Y$ implies $bX=bY$ by the remark above about first letters. But then $X=Y$ since $b$ is cancellable. The argument on the other side is dual.

Added. This technique can be modified to produce more interesting examples. If we add two new generators $d,e$ and relations $bd=be$ and $eb=db$, then we get a complete rewriting system by adding $be\rightarrow bd$ and $eb\rightarrow db$. Then $a,b$ are both not cancellable but $\{a,b\}$ is. The point is if $S$ is the semigroup then $aS$ and $bS$ are disjoint and left multiplication by $a$ is injective on elements with normal form beginning with $d,e$ and left multiplication by $b$ is injective on elements with normal form starting with $a,b,c$. One can build similarly examples with $n$ elements such that no proper subset is cancellable.

• Basically you just need elements a,b with a not cancellable, b cancellable and aS, bS disjoint and same on the other side. – Benjamin Steinberg Jan 9 '15 at 9:14
• Thanks! That's a great observation; I hadn't noticed it. I will award the bounty when it's close to expiring :) – Michał Masny Jan 11 '15 at 15:54
• Thank you for this answer. I'll accept it now since there's little chance someone will notice the thread and answer the remaining questions :) I guess it would have been better to split it or maybe just not ask all those questions at all :) – Michał Masny Jan 21 '15 at 22:58
• Maybe separate out the remaining questions. – Benjamin Steinberg Jan 21 '15 at 23:50
• I've done it now: follow-up – Michał Masny Feb 3 '15 at 0:02