Canonicity
Go to home page
| Axiomatisation, canonicity in modal logic
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.
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.
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.
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.
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; item 2 above) 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.