The Setting
A boundary diagram describes a block of a two-way computation by its passages: each edge enters the block at a label on one side and leaves it at a label on the same side or the other. Gluing blocks side by side multiplies diagrams, and an idempotent diagram is a block that is unchanged when doubled. The forward or backward traversals of , closed up by its returns at the boundary, carry labels around cycles, and the labels on a common cycle form the recurrent classes of .
When is replaced by an idempotent nested in it, some classes of may lose every cycle through their labels; these are the classes missing at . The question is how many classes a chain of idempotents , each nested in the one before, can lose in total, step by step, when everything lost from the top lies in one set . A second statement treats a single step: how the classes lost from to compare with the classes of and of that a given set of labels, each carrying a sign, leaves unprotected.
Boundary Diagrams
Relations compose in path order: when and for some . The reflexive transitive closure of a relation on a set is the relation on , where is the identity relation on and .✦
A sign is or , and and are two copies of a set of labels. A boundary diagram on labels is a quadruple of relations: the forward relation , whose edges enter on the left and exit on the right; the backward relation , whose edges enter on the right and exit on the left; the left relation , whose edges enter and exit on the left; and the right relation , whose edges enter and exit on the right.✦ The set of boundary diagrams on labels is .
The product of diagrams is the diagram obtained by gluing to the left of : (1)✦ A diagram is idempotent when . The corner of a diagram is the set of diagrams with and .✦ The nesting order is the relation on in which when and are idempotents and .✦
Recurrent, Missing and Unprotected Classes
The through relation of a diagram at a sign is the relation on of its traversals in the direction of : and .✦ The loop closure of a diagram at a sign is the relation on that closes up the alternating returns of at the boundary: and .✦ The recurrence relation of at is the relation on (2)✦
A signed recurrent class of a diagram is a pair of a sign and a set of labels such that, for some label with , (3)✦ the signed recurrent classes of form the set .
For diagrams , the surviving through relation of relative to at is the relation on ✦, and a loop of it at a label is a pair in it. The set of classes missing from at is the set of classes of none of whose labels carries a loop of the surviving through relation at the class’s sign: (4)✦
A signed label is a pair of a sign and a label. For a diagram and a set of signed labels, the set of classes of unprotected by is the set of classes of none of whose labels lies in with the class’s sign: (5)✦
The Claim
Theorem 1. (i) Let be idempotent boundary diagrams on labels with for , and let be a set of pairs of a sign and a set of labels that contains for . Then (6)✦
(ii) Let be an idempotent boundary diagram on labels, an idempotent in the corner of , and a set of signed labels such that every class missing from at is unprotected by . Then (7)✦
In the paper, the result reads: if are idempotents with and is a single set with for , then .
What Is Checked
Both inequalities are stated over boundary diagrams on labels under the product (1), with idempotents, the corner of an idempotent and the nesting order, and over the sets and of missing and unprotected classes (4) and (5), cut out of the signed recurrent classes (3) of the recurrence relation (2).