4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh, and also... Is $(P)$ closed under finite products? $\endgroup$ – Michał Masny Jan 5 '15 at 3:37
  • $\begingroup$ 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. $\endgroup$ – Michał Masny Jan 5 '15 at 4:27
  • $\begingroup$ 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? $\endgroup$ – Michał Masny Jan 5 '15 at 7:19
  • $\begingroup$ I can construct non cancellative semigroups with a 3-element cancellable set whose 2-element subsets are not. $\endgroup$ – Benjamin Steinberg Jan 11 '15 at 14:46
  • $\begingroup$ @Benjamin If it's not too much trouble, could you show an example? It sounds interesting. $\endgroup$ – Michał Masny Jan 11 '15 at 15:56
3
+50
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Basically you just need elements a,b with a not cancellable, b cancellable and aS, bS disjoint and same on the other side. $\endgroup$ – Benjamin Steinberg Jan 9 '15 at 9:14
  • $\begingroup$ Thanks! That's a great observation; I hadn't noticed it. I will award the bounty when it's close to expiring :) $\endgroup$ – Michał Masny Jan 11 '15 at 15:54
  • $\begingroup$ 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 :) $\endgroup$ – Michał Masny Jan 21 '15 at 22:58
  • $\begingroup$ Maybe separate out the remaining questions. $\endgroup$ – Benjamin Steinberg Jan 21 '15 at 23:50
  • $\begingroup$ I've done it now: follow-up $\endgroup$ – Michał Masny Feb 3 '15 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.