A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata

A deterministic finite automaton (DFA) M is a 5-tuple, (Q, \Sigma, \delta, q_0, F), consisting of

  • a finite set of states Q
  • a finite set of input symbols \Sigma
  • a (partial) transition function \delta:Q\times \Sigma \to Q
  • an initial state q_0\in Q
  • a set of accept states F \subset Q

An isomorphism between two DFAs M = (Q, \Sigma, \delta, q_0, F) and M' = (Q', \Sigma, \delta', q'_0, F') is a bijection p:Q\to Q' such that \delta'(\cdot,s) = p \circ \delta(\cdot,s) \circ p^{-1} \forall s\in\Sigma, q'_0 = p(q_0) and F' = p(F).

Isomorphism of DFA is GI complete

Without further restrictions, the problem of testing whether two DFAs M and M' are isomorphic is as difficult as testing whether two graphs G and G' are isomorphic, i.e. the problem is GI complete. A simple construction shows that the problem of testing whether two digraphs G and G' are isomorphic reduces to DFA isomorphism testing.

For a digraph G=(V,E), construct the DFA M_G=(Q_G, \Sigma, \delta_G, q_0, F) with Q_G:=V \sqcup E \sqcup \{*\}, \Sigma := \{0,1\}, q_0:=*, F:=\{ \} and \delta_G defined for e\in E by \delta_G(e,0)=\text{tail}(e), \delta_G(e,1)=\text{head}(e) and for v\in V\sqcup \{*\} by \delta_G(v,0)=\delta_G(v,1)=*.
Digraph and corresponding DFA
Obviously, the digraphs G and G' are isomorphic iff the DFAs M_G and M_{G'} are isomorphic.

A canonical labeling technique

A reasonable restriction is to require that every state in Q is reachable from q_0. Let \Sigma:=\{s_1,\ldots,s_d\}. Then a unique labeling \ell(q_0) of Q can be produced by a breadth first search of M starting at q_0 as follows: You have a queue (first-in, first-out store), initially containing only q_0. Repeatedly do this: remove the state at the head of the queue, say x, then push into the queue (at the tail) those of \delta(x,s_1),\ldots,\delta(x,s_d) (in that order) which have never previously been put into the queue. Since every state is reachable from q_0, every state is put into the queue eventually. Stop when that has happened and define \ell(q_0) to be the order in which states were put into the queue. Since this labeling is independent of any ordering or labeling of Q, it fixes the only bijection between Q and Q' that can possibly lead to an isomorphism between M and M'. It is easy then to check whether they are actually isomorphic.

Attributing that algorithm to Brendan McKay would be misleading, because it is so obvious. For example J.-E. Pin described the same algorithm (using depth first search instead of breadth first search) earlier, as an answer to a question about finding an isomorphism between finite automata.

Brendan McKay’s canonical labeling technique

The context in which Brendan McKay described his canonical labeling technique was actually slightly more complicated, because there was no distinguished state q_0, and the state space of the automaton wasn’t required to be weakly connected. But instead, \delta(\cdot,s) was injective for all s\in S. If we drop the requirement that \delta(\cdot,s) is a total function and allow it to be partial, then we end up exactly with the reversible deterministic finite automata, described earlier on this blog. Brendan McKay’s technique generalizes effortlessly to this setting, as does the original context (where group actions are replaced by inverse semigroup actions).

Above are some colored digraphs corresponding to reversible deterministic finite automata (the initial state q_0 and the final states F are ignored). We continue to describe the canonical labeling technique in terms of deterministic finite automata. For each state q\in Q, we can produce a unique labeling \ell(q) (of the weakly connected component containing q) by a breadth first search of M starting at q as above, expect when we remove the state x from the head of the queue, (instead of \delta(x,s_1),\ldots,\delta(x,s_d)) we have to push into the queue (at the tail) those of \delta(x,s_1),\delta^{-1}(x,s_1),\ldots,\delta(x,s_d),\delta^{-1}(x,s_d) (in that order) which are defined and have never previously been put into the queue.

But how can we create a canonical labeling of M from the unique labelings \ell(q)? Just take (one of) the lexicographically smallest labelings of each block, and sort the block lexicographically based on those labelings. The lexicographical order in this context is defined by encoding a labeled block in some reasonable (unique) way as a string, and comparing those strings lexicographically. It’s a good idea to modify this lexicographical order to first compare the lengths of the strings, but this is already an optimization, and there are more possible optimizations, as described in Brendan’s answer. These optimizations are the context of the following remark at the end of his answer:

The graph is actually a deterministic finite automaton (at most one edge of each colour leaves each vertex). There could be faster isomorphism algorithms out there for DFAs, though I’m dubious that anything would work faster in practice than a well-tuned implementation of the method I described.

This remark was actually the main motivation of this blog post, i.e. to investigate the relation of Brendan’s technique to isomorphism testing for DFAs. If there were really faster isomorphism algorithms out there for DFAs, then either they would not be applicable to the problem which Brendan had solved there (if they rely on reachability from q_0), or they would also solve GI itself in polynomial time (which is highly unlikely).


The truth is I have been yak shaving again, even so I explicitly told vzn that I didn’t want to get too involved with GI. How did it happen? Fahad Mortuza (aka Jim) asked me for help refuting his attempts to solve GI in quasipolynomial time. (This is completely unrelated to the recent breakthrough by László Babai, except maybe that he triggered some people to spend time on GI again.) While working with him, I realized that permutation group isomorphism might be more difficult than group isomorphism, and asked some questions to get a better feeling for the relation of permutation group isomorphism to GI. The idea to consider the case where the group is fixed came from reading an introduction to category theory, because those morphisms of left M-sets felt like cheating (or oversimplifying) to me. So I guessed that this case should be easy to solve, if I would only understand how Brendan McKay handles automorphisms of graphs efficiently. Then Brendan McKay himself explained his technique (for this case) and I discovered the interesting connection to inverse semigroups and finite automata, so I decided I had to write a blog post on this. Now I have written this post, just to avoid having another item on my ToDo list which never gets done.

Posted in automata, inverse semigroups, isomorphism, partial functions | 4 Comments

On Zeros of a Polynomial in a Finite Grid: the Alon-Furedi bound

This paper is a great achievement. Not just that it formulates and proves a very appropriate common generalization of Alon-Furedi, Schwartz-Zippel and other theorems, it is well organized, easy to read, and very inspiring.

Anurag's Math Blog

My joint paper with Aditya Potukuchi, Pete L. Clark and John R. Schmitt is now up on arXiv: arXiv:1508.06020.

This work started a few months back when I emailed Pete and John, pointing out an easy generalization of Chevalley-Warning theorem using something known as the punctured combinatorial nullstellensatz, after reading their paper on Warning’s second theorem: arXiv:1404.7793. They got pretty excited about it and we started discussing some related things. Finally, it’s not the generalization of Chevalley-Warning that this paper is about but the theorem of Alon-Füredi itself, which is the main tool they used in their paper to generalize Warning’s second theorem. In our discussions we found several unexplored connections between this elementary result on polynomials and results from different areas of maths. My friend Aditya joined us in between with his amazingly simple proof of Alon-Füredi which, along with the annoying realization that a result of DeMillo-Lipton-Zippel doesn’t…

View original post 124 more words

Posted in Uncategorized | Leave a comment


Annoying Precision

My current top candidate for a mathematical concept that should be and is not (as far as I can tell) consistently taught at the advanced undergraduate / beginning graduate level is the notion of a groupoid. Today’s post is a very brief introduction to groupoids together with some suggestions for further reading.

View original post 1,848 more words

Posted in Uncategorized | Leave a comment

Reversibility of binary relations, substochastic matrices, and partial functions

After the last post, I decided that the next post should contain images. Next I decided that the time to publish another post has come. Here is an image of an acceptor finite-state machine, parsing the string “nice”.

finite-state-machine, parsing the string 'nice'

How can we revert this machine, such that it parses the string “ecin”? An easy way is to remove state “6 Error”, revert all remaining arrows, swap state “1 Start” and state “7 Success”, then add state “6 Error” again, and add arrows to it for all yet undefined cases. This post elaborates the observation that renouncing on the state “6 Error” altogether, and instead allow undefined cases, makes everything simpler and more symmetric. This is not just relevant for the deterministic case, but also for the nondeterministic and the probabilistic case. Time reversal is significantly different for (non-)deterministic and probabilistic machines. Using partial functions, binary relations, and substochastic matrices as transitions gives deceptively simple representations of this fact.

Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: “Diskrete algebraische Methoden: Arithmetik, Kryptographie, Automaten und Gruppen” is a very nice book. Its chapter 7 Automatentheorie gave me the idea that non-deterministic machines arise naturally if (arbitrary) binary relations are used instead of functions. If you read that chapter, you will realize that this post is a significant step back in terms of depth and generality. So the worst is yet to come…

What is the difference between non-determinism and randomness? This question asked for clarification of the following quote

A non-deterministic machine is not the same as a probabilistic machine. In crude terms, a non-deterministic machine is a probabilistic machine in which probabilities for transitions are not known

I gave a short answer trying to highlight the fact that the probabilities on the transitions make time reversal for a probabilistic machine significantly less trivial than time reversal for a non-deterministic machine. Niel de Beaudrap commented that even non-deterministic machines are not reversible without further constraints. I agree with him in a certain complicated technical sense, but I couldn’t really judge whether he had this complicated technical sense in mind. Maybe he just doubts the basic heuristic principle according to which non-deterministic machines are much more symmetry with respect to time than deterministic machines. So I took some time to elaborate my answer, and highlight in more detail the achievable time symmetry for non-deterministic and probabilistic machines. I want to try to reblog my answer here:

Stepping backwards during debugging as a motivation for non-determinism

The notion of a non-deterministic machine suggests itself when you wish to step backward (in time) through a program while debugging. In a typical computer, each step modifies only a finite amount of memory. If you always save this information for the previous 10000 steps, then you can nicely step both forward and backward in the program, and this possibility is not limited to toy programs. If you try to remove the asymmetry between forward steps and backward steps, then you end up with the notion of a non-deterministic machine.

Similarities and differences between non-determinism and randomness

While probabilistic machines shares some characteristics with non-deterministic machines, this symmetry between forward steps and backward steps is not shared. To see this, let’s model the steps or transitions of a deterministic machine by (total or partial) functions, the transitions of a non-deterministic machine by (finite) relations, and the transitions of a probabilistic machine by (sub)stochastic matrices. For example, here are corresponding definitions for finite automata

  • a finite set of states Q
  • a finite set of input symbols \Sigma
  • deterministic: a transition function \delta:Q\times \Sigma \to Q
  • non-deterministic: a transition function \Delta:Q\times \Sigma \to P(Q)
  • non-deterministic: a transition relation \Delta\subset Q\times \Sigma \times Q
  • non-deterministic: a function \Delta: \Sigma \to P(Q \times Q)
  • probabilistic: a function \delta: \Sigma \to ssM(Q)

Here P(Q) is the power set of Q and ssM(Q) is the space of substochatic matrices on Q. A right substochastic matrix is a nonnegative real matrix, with each row summing to at most 1.

There are many different reasonable acceptance conditions

The transitions are only one part of a machine, initial and final states, possible output and acceptance conditions are also important. However, there are only very few non-eqivalent acceptance conditions for deterministic machines, a number of reasonable acceptance conditions for non-deterministic machines (NP, coNP, #P, …), and many possible acceptance conditions for probabilistic machines. Hence this answer focuses primarily on the transitions.

Reversibility is non-trivial for probabilistic machines

A partial function is reversible iff it is injective. A relation is always reversible in a certain sense, by taking the opposite relation (i.e. reversing the direction of the arrows). For a substochastic matrix, taking the transposed matrix is analogous to taking the opposite relation. In general, the transposed matrix is not a substochastic matrix. If it is, then the matrix is said to be *doubly substochastic*. In general P P^T P\neq P, even for a doubly substochastic matrix P, so one can wonder whether this is a reasonable notion of reversibility at all. It is reasonable, because the probability to reach state B from state A in k forward steps is identical to the probability to reach state A from state B in k backward steps. Each path from A to B has the same probability forward and backward. If suitable acceptance conditions (and other boundary conditions) are selected, then doubly substochastic matrices are an appropriate notion of reversibility for probabilistic machines.

Reversibility is tricky even for non-deterministic machines

Just like in general P P^T P\neq P, in general R\circ R^{op}\circ R \neq R for a binary relation R. If R describes a partial function, then R\circ R^{op}\circ R = R and R^{op}\circ R\circ R^{op} = R^{op}. Even if relations P and Q should be strictly reversible in this sense, this doesn’t imply that P\circ Q will be strictly reversible too. So let’s ignore strict reversibility now (even so it feels interesting), and focus on reversal by taking the opposite relation. A similar explanation like for the probabilistic case shows that this reversal works fine if suitable acceptance conditions are used.

These considerations also make sense for pushdown automata

This post suggests that one motivation for non-determinism is to remove that asymmetry between forward steps and backward steps. Is this symmetry of non-determinism limited to finite automata? Here are corresponding symmetric definitions for pushdown automata

  • a finite set of states Q
  • a finite set of input symbols \Sigma
  • a finite set of stack symbols \Gamma
  • deterministic: a partial transition function \delta:Q\times\Gamma\times (\Sigma\cup\{\epsilon\}) \to Q\times\Gamma^{\{0,2\}} such that \delta(q,\gamma,\epsilon)\neq\epsilon only if \delta(q,\gamma,\sigma)=\epsilon for all \sigma\in\Sigma
  • non-deterministic: a transition function \Delta:Q\times\Gamma^{\{0,1\}}\times (\Sigma\cup\{\epsilon\}) \to P(Q\times\Gamma^{\{0,1\}})
  • non-deterministic: a transition relation \Delta\subset Q\times\Gamma^{\{0,1\}}\times (\Sigma\cup\{\epsilon\}) \times Q\times\Gamma^{\{0,1\}}
  • non-deterministic: a function \Delta: \Sigma\cup\{\epsilon\} \to P(Q\times\Gamma^{\{0,1\}}\ \times\ Q\times\Gamma^{\{0,1\}})
  • probabilistic: a function \delta: \Sigma\cup\{\epsilon\} \to ssM(Q\times\Gamma^{\{0,1\}}) such that \delta(\epsilon)+\delta(\sigma)\in ssM(Q\times\Gamma^{\{0,1\}}) for all \sigma\in\Sigma

Here \epsilon is the empty string, \Gamma^{\{0,2\}}=\{\epsilon\}\cup\Gamma\cup(\Gamma\times\Gamma) and \Gamma^{\{0,1\}}=\{\epsilon\}\cup\Gamma. This notation is used because it is similar to \Gamma^*, which is used in many definitions for pushdown automata.

Diagramed verification of reversal for (non)advancing input and stack operations

An advancing input operation with b\in\Sigma\subset\Sigma\cup\{\epsilon\} gets reversed as follows

\begin{matrix}  a|bc \to a|\boxed{b}c \to ab|c\\  a|bc \leftarrow a\boxed{b}|c \leftarrow ab|c\\  c|ba \to c|\boxed{b}a \to cb|a  \end{matrix}

A non advancing input operation with \epsilon\in\Sigma\cup\{\epsilon\} that doesn’t read any input can be reversed

\begin{matrix}  a|bc \to a|bc \to a|bc\\  a|bc \leftarrow a|bc \leftarrow a|bc\\  cb|a \to cb|a \to cb|a  \end{matrix}

Here is a diagram of an advancing input operation whose reversal would look bad


For a stack operation (s,t) \in \Gamma^{\{0,1\}}\times\Gamma^{\{0,1\}}, there are the three cases (s,t)=(a,\epsilon), (s,t)=(\epsilon,a), and (s,t)=(a,b). The stack operation (a,\epsilon) gets reversed to (\epsilon,a) as follows

\begin{matrix}  ab\ldots \to \boxed{a}b\ldots \to |b\ldots\\  \boxed{a}b\ldots \leftarrow |b\ldots \leftarrow b\ldots\\  b\ldots \to |b\ldots \to \boxed{a}b\ldots  \end{matrix}

The stack operation (a,b) gets reversed to (b,a) as follows

\begin{matrix}  ac\ldots \to \boxed{a}c\ldots \to \boxed{b}c\ldots\\  \boxed{a}c\ldots \leftarrow \boxed{b}c\ldots \leftarrow bc\ldots\\  bc\ldots \to \boxed{b}c\ldots \to \boxed{a}c\ldots  \end{matrix}

A generalized stack operation (ab,cde)\in\Gamma^*\times\Gamma^* would be reversed to (cde,ab)

\begin{matrix}  abf\ldots \to \boxed{ab}f\ldots \to \boxed{cde}f\ldots\\  \boxed{ab}f\ldots \leftarrow \boxed{cde}f\ldots \leftarrow cdef\ldots\\  cdef\ldots \to \boxed{cde}f\ldots \to \boxed{ab}f\ldots  \end{matrix}

Reversibility for Turing machines

A machine with more than one stack is equivalent to a Turing machine, and stack operations can easily be reversed. The motivation at the beginning also suggests that reversal (of a Turing machine) should not be difficult. A Turing machine with a typical instruction set is not so great for reversal, because the symbol under the head can influence whether the tape will move left or right. But if the instruction set is modified appropriately (without reducing the computational power of the machine), then reversal is nearly trivial again.

A reversal can also be constructed without modifying the instruction set, but it is not canonical and a bit ugly. It might seem that the existence of a reversal is just as difficult to decide as many other question pertaining to Turing machines, but a reversal is a local construction and the difficult questions often have a global flavor, so pessimism would probably be unjustified here.

The urge to switch to equivalent instruction sets (easier to reverse) shows that these questions are less obvious than they first appear. A more subtle switch happened in this post before, when total functions and stochastic matrices were replaced by partial functions and substochastic matrices. This switch is not strictly necessary, but the reversal is ugly otherwise. The switch to the substochastic matrices was actually the point where it became obvious that reversibility is not so trivial after all, and that one should write down details (as done above) instead of taking just a high level perspective (as presented in the motivation at the beginning). The questions raised by Niel de Beaudrap also contributed to the realization that the high level perspective is slightly shaky.


Non-deterministic machines allow a finite number of deterministic transitions at each step. For probabilistic machines, these transitions additionally have a probability. This post conveys a different perspective on non-determinism and randomness. Ignoring global acceptance conditions, it focuses on local reversibility (as a local symmetry) instead. Because randomness preserves some local symmetries which are not preserved by determinism, this perspective reveals non-trivial differences between non-deterministic and probabilistic machines.

Posted in automata, partial functions | Tagged , | 1 Comment

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}

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.

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}

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.


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.

Posted in inverse semigroups | Tagged | Leave a comment

Gentzen’s consistency proof is more impressive than you expect

I recently said something about the impossibility to prove the consistency of PA, and that Gentzen proved just this in 1936. Because I got critizised quite a bit, and realized that even famous mathematicians get critizized if they dare to mention this, I decided to read the original papers of Gentzen. I was deeply impressed how well explained they are, and how much more perspective they add. But I also realized that they are written in German, and that it will probably be impossible to express the thoughts with the same clarity in English, at least for me. Still

Posted in logic | Tagged | 2 Comments