Canonicity

Go to home page   |  Axiomatisation, canonicity in modal logic

1. Erdös graphs resolve Fine's canonicity problem

Robert Goldblatt, Ian Hodkinson, and Yde Venema
Bull. Symbolic Logic 10 no. 2 (June 2004), 186-208.  ILLC preprint PP-2003-26
We show that there exist continuum-many 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 Erdös that there are finite graphs with arbitrarily large chromatic number and girth.

2. Canonical varieties with no canonical axiomatisation

Ian Hodkinson and Yde Venema
Trans. Amer. Math. Soc. 357 (2005), 4579-4605.
We give a simple example of a variety V of modal algebras that is canonical but cannot be axiomatised by canonical equations or first-order sentences.  This can be viewed modally as a canonical modal logic that cannot be axiomatised by canonical formulas.  We then show that the variety RRA of representable relation algebras, although canonical, has no canonical axiomatisation.  Indeed, we show that every axiomatisation of these varieties involves infinitely many non-canonical sentences.

Using probabilistic methods of Erdös, we construct an infinite sequence G0, G1, ... of finite graphs with arbitrarily large chromatic number, such that each Gn is a bounded morphic image of Gn+1 and has no odd cycles of length at most n. The inverse limit of the sequence is a graph with no odd cycles and hence is 2-colourable. It follows that a modal algebra (respectively, a relation algebra) obtained from the Gn satisfies arbitrarily many axioms from a certain axiomatisation of V (RRA), while its canonical extension satisfies only a bounded number of them. It now follows by compactness that V (RRA) has no canonical axiomatisation. A variant of this argument shows that there is no axiomatisation using finitely many non-canonical sentences.

Survey talk on this paper.

3. On canonicity and completions of weakly representable relation algebras

Ian Hodkinson and Szabolcs Mikulás
J. Symbolic Logic 77 (2012) 245-262.
We show that the variety of weakly representable relation algebras is not canonical, nor closed under Monk completions.

4. Bare canonicity of representable cylindric and polyadic algebras

Jannis Bulian and Ian Hodkinson
Ann. Pure Appl. Logic 164 (2013) 884-906, doi 10.1016/j.apal.2013.04.002.
We show that for finite n at least 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.

5. An application of first-order compactness in canonicity of relation algebras

Ian Hodkinson
in: Aventuras en el Mundo de la Lógica: Ensayos en Honor a María Manzano,
E. Alonso, A. Huertas, A. Moldovan (eds),
Cuadernos de lógica, epistemología y lenguaje, vol. 13, College Publications, 2019, pp. 205-222.
The classical compactness theorem is a central theorem in first-order model theory. It sometimes appears in other areas of logic, and in perhaps surprising ways. In this paper, we survey one such appearance in algebraic logic. We show how first-order compactness can be used to simplify slightly the proof of Hodkinson and Venema (2005) that the variety of representable relation algebras, although canonical, has no canonical axiomatisation, and indeed every first-order axiomatisation of it has infinitely many non-canonical sentences.