Whenever a structure with a particularly interesting computability-theoretic property is found, it is natural to ask whether similar examples can be found within well-known classes of algebraic structures, such as groups, rings, lattices, and so forth. One way to give positive answers to this question is to adapt the original proof to the new setting. However, this can be an unnecessary duplication of effort, and lacks generality. Another method is to code the original structure into a structure in the given (...) class in a way that is effective enough to preserve the property in which we are interested. In this paper, we show how to transfer a number of computability-theoretic properties from directed graphs to structures in the following classes: symmetric, irreflexive graphs; partial orderings; lattices; rings ; integral domains of arbitrary characteristic; commutative semigroups; and 2-step nilpotent groups. This allows us to show that several theorems about degree spectra of relations on computable structures, nonpreservation of computable categoricity, and degree spectra of structures remain true when we restrict our attention to structures in any of the classes on this list. The codings we present are general enough to be viewed as establishing that the theories mentioned above are computably complete in the sense that, for a wide range of computability-theoretic nonstructure type properties, if there are any examples of structures with such properties then there are such examples that are models of each of these theories. (shrink)

This is a review of those aspects of the theory of varieties of Boolean algebras with operators that emphasise connections with modal logic and structural properties that are related to natural properties of logical systems.It begins with a survey of the duality that exists between BAO's and relational structures, focusing on the notions of bounded morphisms, inner substructures, disjoint and bounded unions, and canonical extensions of structures that originate in the study of validity-preserving operations on Kripke frames. This duality is (...) then applied to polymodal propositional logics having finitary intensional connectives that generalise the Box and Diamond connectives of unary modal logic. Issues discussed include validity in canonical structures, completeness under the relational semantics, and characterisations of logics by elementary classes of structures and by finite structures.It turns out that a logic is strongly complete for the relational semantics if the variety of algebras it defines is complex, which means that every algebra in the variety is embeddable into a full powerset algebras that is also in the variety. A hitherto unpublished formulation and proof of this is given that applies to quasi-varieties. This is followed by an algebraic demonstration that the temporal logic of Dedekind complete linear orderings defines a complex variety, adapting Gabbay's model-theoretic proof that this logic is strongly complete. (shrink)

This paper shows that non-normal modal logics can be simulated by certain polymodal normal logics and that polymodal normal logics can be simulated by monomodal (normal) logics. Many properties of logics are shown to be reflected and preserved by such simulations. As a consequence many old and new results in modal logic can be derived in a straightforward way, sheding new light on the power of normal monomodal logic.