The Setting
A two-way automaton working on a block of its tape enters the block at one border and leaves it at one border: it crosses from left to right or from right to left, or it turns back at the left border or at the right one. A boundary diagram on labels is a quadruple of relations on two copies and of an -element set of labels, one for each of these kinds of edge: (1)✦ The edges of the forward relation enter on the left and exit on the right, those of the backward relation enter on the right and exit on the left, and those of the left relation and of the right relation enter and exit on the left and on the right respectively.
The boundary diagrams on labels form the set , which carries a product: the product of two diagrams is the diagram of the block obtained by placing a block of diagram next to a block of diagram . Edge inclusion is the relation on that holds, , when each of the four relations of is contained in the corresponding relation of .✦
The relation monoid of a set is the monoid of all binary relations on under the path-order product (2)✦ with the identity relation as its unit. The graph of a permutation of is the relation in .
Take a finite monoid with a multiplicative map into , under which its identity goes to a diagram , and a homomorphism from it onto , for a finite set of elements, that reverses edge inclusion. The question is how many of the recurrent classes of , defined below, an idempotent of the monoid must lose when its image in is with one pair , , added.
Recurrent and Missing Classes
A sign is or , and at a sign the through relation of a diagram is the relation on with and .✦ The reflexive transitive closure of a relation on a set is the relation on (3)✦ The loop closure of a diagram at is the relation on that closes up the returns at the borders: (4)✦
The recurrence relation of at is the relation on (5)✦ and the set of signed recurrent classes of is the set of pairs of a sign and a set of labels (6)✦
For a second diagram on labels, the surviving relation of relative to at is the relation on (7)✦ and the set of classes missing after is replaced by is the set of recurrent classes of none of whose labels lies on a loop of : (8)✦
The loss bound of a natural number is the power of two (9)✦
The Claim
Theorem 1. Let be a finite monoid, a natural number and a map from to with for all , and let . Let be a finite set with elements and a monoid homomorphism from onto that reverses edge inclusion, in that whenever , and under which every permutation of has a unit lift, a unit of with . If is an idempotent of with for distinct , then (10)✦
In the paper, the result reads: for , an idempotent , a submonoid of with identity , a finite set with elements and a unital surjective order-reversing homomorphism such that every permutation of has a lift that is a unit of , every idempotent with for distinct has .
The paper’s statement is the theorem with and the inclusion of in .
What Is Checked
The claim (10) is stated over the boundary diagrams of with their edge inclusion, the through relations, loop closures, recurrence relations and surviving relations of diagrams, built with the reflexive transitive closure, the recurrent classes and the missing classes , the relation monoid with the graphs of permutations of , and the loss bound .
For every permutation of , the library proves that is a unit of with inverse .✦