Algebraic characterizations of inverse semigroups and strongly regular rings

A good place to learn about inverse semigroups are Tero Harju’s Lecture Notes on Semigroups from 1996. (J.M. Howie’s, “Fundamentals of semigroup theory” from 1995 is claimed to be even better, but I can’t comment on that.) Learning about strongly regular rings is more difficult. The information is quite scattered, but the important elementary facts seem to be known, even if difficult to find. A simple request to give a link to the “well-known” signature and equations (for a commutative regular ring) made me realize how being scattered can make it difficult to refer to these “well-known” facts. The plan was to make a blog post which contains these elementary facts, together with proofs. But producing good looking math in wordpress is challenging, if you’ve never done it.

The real text is in a short pdf

The nice looking math is now presented in a short pdf produced using latex (lyx): Algebraic characterizations of inverse semigroups and strongly regular rings. The original proofs were mostly found via google, but after a conversation with a real guru, I realized that google may not be the best way for cheating in this case: This Google Drive folder contains prover9 and the-E-theorem-prover input files. The companion program mace4 to prover9 finds counterexamples, which really helped me to finish the text at all and streamline it nicely, even so none of the counterexamples is mentioned anywhere in the text.

Here is a condensed down excerpt from the short pdf

A semigroup S is a set S together with a binary operation \cdot:S\times S \to S which is associative: \forall x,y,z\in S\quad x\cdot(y\cdot z)=(x\cdot y)\cdot z. To simplify notation, concatenation is used instead of \cdot and parentheses are omitted.
We say that y\in S is a pseudoinverse of x\in S, if x=xyx. We call y an inverse element of x, if x=xyx and y=yxy. If y is a pseudoinverse of x, then yxy is an inverse element of x, because x=x(yxy)x and yxy=(yxy)x(yxy).
A regular semigroup S is a semigroup S where each element has a pseudoinverse: \forall x\in S\exists y\in S\quad x=xyx. An inverse semigroup is a regular semigroup where the inverse elements are unique, such that an inverse operation ^{-1} can be defined implicitly via x=xyx\land y=yxy\leftrightarrow y=x^{-1}.

Lemma 2 The idempotents E_S of an inverse semigroup S are a subsemigroup.

Theorem 1 The following characterizations are equivalent:

  1. S is an inverse semigroup, i.e. a semigroup with an operation ^{-1} satisfying the following quasi-equations

    x=xyx\land y=yxy \ \leftrightarrow \ y=x^{-1}

  2. S is a regular semigroup where idempotents commute, i.e. the following formulas hold

    \forall x\in S\exists y\in S \ x=xyx
    e^{2}=e \land f^{2}=f \rightarrow ef=fe

  3. S is a semigroup with an operation ^{-1} satisfying the following equations

    x=xx^{-1}x \ \land \ x^{-1}=x^{-1}xx^{-1}
    xx^{-1}\cdot y^{-1}y \ = \ y^{-1}y\cdot xx^{-1}

Proof
Case (1) implies Case (2): We have to show ef=fe for idempotent e,f\in S. From lemma 2 we have that ef and fe are idempotent. So ef is its own inverse, but fe is also an inverse element of ef: ef\cdot fe\cdot ef=efef=ef and fe\cdot ef\cdot fe=fefe=fe. By uniqueness of inverse elements, we have ef=fe.

Case (2) implies Case (1): Let x',x''\in S be two inverse elements of x. Then x=xx'x, x'=x'xx', x=xx''x, and x''=x''xx''. We have

x'=x'xx'=x'xx''xx' \ = \ x'xx''xx''xx'
x''=x''xx''=x''xx'xx'' \ = \ x''xx'xx'xx''

and x'xx''xx''xx'=x''xx'xx''xx'=x''xx'xx'xx'', because x'x, x''x, xx', and xx'' are idempotent and commute.

Case (1) and Case (2) imply Case (3): The existence of an operation ^{-1} satisfying x=xx^{-1}x and x^{-1}=x^{-1}xx^{-1} follows from (1). The remaining equation follows from (2), because xx^{-1} and y^{-1}y are idempotent and commute.

Case (3) implies Case (2): Let e,f\in S be idempotent. Then e^{-1}=e^{-1}ee^{-1}=e^{-1}e\cdot ee^{-1}=ee^{-1}\cdot e^{-1}e, so e=ee^{-1}e=e^{2}e^{-1}\cdot e^{-1}e^{2}=ee^{-1}\cdot e^{-1}e=e^{-1} and similarly f=f^{-1}. So ef=ee^{-1}\cdot f^{-1}f=f^{-1}f\cdot ee^{-1}=fe.
QED

A regular ring R is a ring R where each element has a multiplicative pseudoinverse: \forall x\in R\exists y\in R\quad x=xyx. A strongly regular ring R is a ring R where each element has a strong multiplicative pseudoinverse: \forall x\in R\exists y\in R\quad x=x^{2}y. An inverse ring R is a ring R where the multiplicative semigroup is an inverse semigroup.

Theorem 3 The following characterizations are equivalent:

  1. R is a strongly regular ring, i.e. the following formula holds

    \forall x\in R\exists y\in R\quad x=x^{2}y

  2. R is a regular ring without nonzero nilpotent elements, i.e. the following formulas hold

    \forall x\in R\exists y\in R \ x=xyx
    x^{2}=0 \rightarrow x=0

  3. R is a regular ring where idempotents are central, i.e. the following formulas hold

    \forall x\in R\exists y\in R \ x=xyx
    e^{2}=e \rightarrow ex=xe

  4. R is a regular ring where idempotents commute, i.e. the following formulas hold

    \forall x\in R\exists y\in R \ x=xyx
    e^{2}=e\land f^{2}=f \rightarrow ef=fe

  5. R is an inverse ring, i.e. a ring with an operation ^{-1} satisfying the following quasi-equations

    x=xyx\land y=yxy\leftrightarrow y=x^{-1}

Proof
Case (1) implies Case (2): Let y be a strong pseudoinverse of x, then x=x^{2}y. If x^{2}=0, then x=x^{2}y=0y=0. Now (x-xyx)^{2}=x^{2}-x^{2}yx-xyx^{2}+xyx^{2}yx=x^{2}-x^{2}-xyx^{2}+xyx^{2}=0, hence x=xyx.

Case (2) implies Case (1): Let y be a pseudoinverse of x, then x=xyx. We have (x-x^{2}y)^{2}=x^{2}-x^{3}y-x^{2}yx+x^{2}yx^{2}y=x^{2}-x^{3}y-x^{2}+x^{3}y=0, hence x=x^{2}y.

Case (2) implies Case (3): Let e^{2}=e. We have (ex(1-e))^{2}=0, because (1-e)e=e-e^{2}=0. The same argument without the neutral element 1 reads (ex-exe)^{2}=(ex-exe)e(x-xe)=(exe-exe)(x-xe)=0. Similarly (xe-exe)^{2}=0. Hence ex=exe=xe.

Case (3) implies Case (4): This is trivial.

Case (4) implies Case (2): If x^{2}=0, then (x+xy)^{2}=x^{2}+x^{2}y+xyx+xyxy=0+0y+x+xy=x+xy for any pseudoinverse y of x. Hence x+xy is idempotent and commutes with xy, i.e. xy(x+xy)=(x+xy)xy. This simplifies to xyx=x^{2}y, and the conclusion is x=xyx=x^{2}y=0y=0.

Case (4) and Case (5) are equivalent according to theorem 1.
QED

Conclusions?

Why write about inverse semigroups and strongly regular rings, when good lecture notes and textbooks already exist? And why reformat a condensed down excerpt from the short pdf into a wordpress blog? After reading a preprint on skew meadows, I became unsure how much of the elementary facts about strongly regular rings are really “well-known”. And I found it difficult to try to explain background material on such things, when I really want to talk about more distantly related questions. And publishing it as a blog was a consequence on the time I already sank trying to produce good looking math in wordpress.
Here is a disclaimer that I can’t judge how useful inverse semigroups (and their categorification as inverse categories) really are, and that I first have to read more about partial functions (and their categorification as restriction categories) for myself. Also I don’t really care about non-commutative strongly regular rings. I find commutative regular rings useful, because having a total multiplicative inverse operation seems convenient, and I find it canonical to define it the way as implied by the relation to inverse semigroups. This turns Boolean algebras into a special case of commutative regular rings, the idempotents of a strongly regular ring are a Boolean algebra, and x\to xx^{-1} is the canonical projection into this Boolean algebra. I tried to stay non-commital as to whether the inverse operation is explicitly or implicitly defined, because nobody ever complains about whether the inverse operation for a group is explicitly defined or not. The fact that the free commutative regular ring (for a finite set of generators) exists indicates to me that they might sometimes be useful. Jan Bergstra told me that Komori and Ono proved that their equational theory is decidable.
But the point of this post is also to just finish the work on this for the moment, since I already spend a significant amount of time for this over the last three weeks. If you find this stuff interesting, do take a look at the short pdf. It is nicer than this blog post in many ways, and doesn’t try to dive into advanced material either. (Characterizations in terms of Green’s relation or ideals would be more advanced for example, but the advanced material only starts there.) Not sure how useful the input files for the theorem provers are, but part of the appeal of equational reasoning is that it lends itself for experiments with automated reasoning tools.

Advertisements

About gentzen

Logic, Logic, and Logic
This entry was posted in inverse semigroups and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s