The Setting
A nondeterministic finite automaton with state set lets each input word act on as a binary relation, and reading two words one after the other composes their relations in the order the words are read. The behaviours of words therefore live in the monoid of all binary relations on , and an idempotent of , such as the behaviour of a word that acts the same when read twice, cuts out the corner .
Lemma 4.2 of the paper asks when a corner of is itself the full relation monoid of a smaller set. It takes a subset of such that relates every point of to itself and no point of to a different point of , and it looks at the relation that follows , stops at a point of and follows again.
Relations and Corners
The relation monoid of a set is the set of binary relations on under the path-order product, with the identity relation as unit: for relations and on , (1)✦
The restricted identity of a subset of is the relation on that relates each point of to itself and relates nothing else: (2)✦
An idempotent of a monoid is nested in an idempotent , written , when .
The corner of an idempotent of a monoid is the monoid of elements of fixed by multiplication with on both sides, (3) under the product of , with identity .
The Claim
Theorem 1. Let be a set, an idempotent relation on and a relation on with , and let . Then (4)✦ Every relation on with and every relation on with satisfy (5)✦ If is idempotent as well, any two relations and on with and satisfy (6)✦ If for a subset of , there is a monoid isomorphism from the corner onto that restricts each relation to : (7)✦
In the paper, the result reads: for an idempotent , a subset and with , the relation is idempotent, , and is a unital monoid isomorphism with inverse .
For , the map of (7) is with read as a relation on , and (5) makes its inverse.
What Is Checked
The claim is stated over the relation monoid of a set , with the path-order product (1) and unit , over the restricted identity (2) of a subset of , and over the corner (3) of the idempotent in , for an idempotent relation on and a relation on with .