Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T22:59:28.741Z Has data issue: false hasContentIssue false

Erdős Graphs Resolve Fine's Canonicity Problem

Published online by Cambridge University Press:  15 January 2014

Robert Goldblatt
Affiliation:
Centre for Logic, Language and Computation, Victoria University, Po Box 600, Wellington, New Zealand E-mail: , Rob.Goldblatt@vuw.ac.nz
Ian Hodkinson
Affiliation:
Office for Logic, Language and Computation, 426 Huxley Building, Department of Computing, Imperial College London, South Kensington Campus, London SW7 2AZ, UK E-mail: , imh@doc.ic.ac.uk
Yde Venema
Affiliation:
Institute for Logic, Language and Computation, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, Netherlands E-mail: , yde@science.uva.nl

Abstract

We show that there exist 2ℵ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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2004

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable