Erdos Graphs Resolve Fine's Canonicity Problem
Robert Goldblatt, Ian Hodkinson, and Yde Venema
We show that there exist $2^{\aleph_0}$ equational classes of Boolean
algebras with operators that are not generated by the complex algebras
of any first-order definable class of relational structures. Using a
variant of this construction, we resolve a long-standing question of
Fine, by exhibiting a bimodal logic that is valid in its canonical
frames, but is not sound and complete for any first-order definable
class of Kripke frames (a monomodal example can then be obtained using
simulation results of Thomason). The constructions use the result of
Erdos that there are finite graphs with arbitrarily large chromatic
number and girth.