Polyhedral completeness of intermediate logics: the Nerve Criterion

Sam Adam-Day, Nick Bezhanishvili, David Gabelaia, Vincenzo Marra

Published 2021-12-14, updated 2022-10-25Version 2

We investigate a recently-devised polyhedral semantics for intermediate logics, in which formulas are interpreted in n-dimensional polyhedra. An intermediate logic is polyhedrally complete if it is complete with respect to some class of polyhedra. The first main result of this paper is a necessary and sufficient condition for the polyhedral-completeness of a logic. This condition, which we call the Nerve Criterion, is expressed in terms of Alexandrov's notion of the nerve of a poset. It affords a purely combinatorial characterisation of polyhedrally-complete logics. Using the Nerve Criterion we show, easily, that there are continuum many intermediate logics that are not polyhedrally-complete but which have the finite model property. We also provide, at considerable combinatorial labour, a countably infinite class of logics axiomatised by the Jankov-Fine formulas of 'starlike trees' all of which are polyhedrally-complete. The polyhedral completeness theorem for these 'starlike logics' is the second main result of this paper.