Constructing the lattice of subalgebras of the Dijkstra algebra (Q1264604)

We construct the lattice of subalgebras (closed classes) of a Dijkstra algebra (DA) as a continuation of our research on functional completeness in algebra [Kibern. Sist. Anal. 1995, No. 5, 28-40 (1995; Zbl 0854.68063)]. A Dijkstra algebra is a two-sorted algebraic system \(\text{DA}= \langle \text{ASS}, L(2) \rangle\); it may be regarded as the direct sum of the subalgebra of structure schemes ASS and the Boolean algebra \(L(2)\). The signature of operations in a DA consists of superposition, i.e., substitution of functions (for operator variables and (or) logical variables) into other functions. A family of maximal subalgebras in ASS is described in our earlier paper [loc. cit.], and a functional completeness criterion for DA is established in terms of these subalgebras. The present article constructs the surface of finitely generated subalgebras that are reachable from the root of the inclusion graph of subalgebras in ASS. The construction of the surface for ASS is nontrivial because the set of subalgebras included in ASS is a continuum. The main result of our article is the solution of problems of functional completeness and expressibility for the most interesting subalgebras. We also localize the continuum of subalgebras that have a continuum of closed classes.