The Boxdot Conjecture is shown to hold for a novel class of modal systems. Each system in this class is K plus an instance of a natural generalization of the McKinsey axiom. [Note from the editors: This paper was accepted for publication in 2011. It should have been published in 2014. The lateness of the appearance of the article is due entirely to an editorial oversight.].

In this paper we consider the normal modal logics of elementary classes defined by first-order formulas of the form \. We prove that many properties of these logics, such as finite axiomatisability, elementarity, axiomatisability by a set of canonical formulas or by a single generalised Sahlqvist formula, together with modal definability of the initial formula, either simultaneously hold or simultaneously do not hold.

We show that for finite n⩾3n⩾3, every first-order axiomatisation of the varieties of representable n-dimensional cylindric algebras, diagonal-free cylindric algebras, polyadic algebras, and polyadic equality algebras contains an infinite number of non-canonical formulas. We also show that the class of structures for each of these varieties is non-elementary. The proofs employ algebras derived from random graphs.

We define analogues of modal Sahlqvist formulas for the modal mu-calculus, and prove a correspondence theorem for them.