Erdős Graphs Resolve Fine's Canonicity Problem
Robert Goldblatt, Ian Hodkinson, Yde Venema · Bulletin of Symbolic Logic · 2004
Abstract We show that there exist 2ℵ0equational 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.