Action Algebra - Examples

Examples

Any Heyting algebra (and hence any Boolean algebra) is made an action algebra by taking • to be ∧ and a* = 1. This is necessary and sufficient for star because the top element 1 of a Heyting algebra is its only reflexive element, and is transitive as well as greater or equal to every element of the algebra.

The set 2Σ* of all formal languages (sets of finite strings) over an alphabet Σ forms an action algebra with 0 as the empty set, 1 = {ε}, ∨ as union, • as concatenation, L←M as the set of all strings x such that xM ⊆ L (and dually for M→L), and L* as the set of all strings of strings in L (Kleene closure).

The set 2X² of all binary relations on a set X forms an action algebra with 0 as the empty relation, 1 as the identity relation or equality, ∨ as union, • as relation composition, R←S as the relation consisting of all pairs (x,y) such that for all z in X, ySz implies xRz (and dually for S→R), and R* as the reflexive transitive closure of R, defined as the union over all relations Rn for integers n ≥ 0.

The two preceding examples are power sets, which are Boolean algebras under the usual set theoretic operations of union, intersection, and complement. This justifies calling them Boolean action algebras. The relational example constitutes a relation algebra equipped with an operation of reflexive transitive closure. Note that every Boolean algebra is a Heyting algebra and therefore an action algebra by virtue of being an instance of the first example.