Hostname: page-component-7b7567c8c-w7t8q Total loading time: 0 Render date: 2026-11-19T04:19:52.249Z Has data issue: false hasContentIssue false

POLYHEDRAL COMPLETENESS OF INTERMEDIATE LOGICS: THE NERVE CRITERION

Published online by Cambridge University Press:  14 November 2022

SAM ADAM-DAY*
Affiliation:
MATHEMATICAL INSTITUTE UNIVERSITY OF OXFORD OXFORD, UK
NICK BEZHANISHVILI
Affiliation:
INSTITUTE FOR LOGIC, LANGUAGE AND COMPUTATION UNIVERSITY OF AMSTERDAM AMSTERDAM, THE NETHERLANDS E-mail: N.Bezhanishvili@uva.nl
DAVID GABELAIA
Affiliation:
A. RAZMADZE MATHEMATICAL INSTITUTE OF I. JAVAKHISHVILI TBILISI STATE UNIVERSITY TBILISI, GEORGIA E-mail: gabelaia@gmail.com
VINCENZO MARRA
Affiliation:
DIPARTIMENTO DI MATEMATICA ‘FEDERIGO ENRIQUES’ UNIVERSITÀ DEGLI STUDI DI MILANO MILAN, ITALY E-mail: Vincenzo.Marra@unimi.it
Rights & Permissions [Opens in a new window]

Abstract

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.

Information

Type
Article
Copyright
© The Author(s), 2022. Published by Cambridge University Press on behalf of The Association for Symbolic Logic
Figure 0

Figure 1Examples of elementary stellar subdivisions.

Figure 1

Figure 2Examples of barycentric subdivision. Each simplex in the simplicial complex is divided at its barycentre, proceeding in decreasing order of dimension. The bottom right tetrahedron is drawn without filled-in faces to aid clarity.

Figure 2

Figure 3An example showing that the $\operatorname {{\mathrm {Frames}_{\mathrm {fin}}}}(\mathbf {SL})$ is not closed under $\mathcal {N}$, even though $\mathbf {SL}$ is polyhedrally complete.

Figure 3

Figure 4Some examples of starlike trees.

Figure 4

Figure 5The set-up when X has more than one gap.

Figure 5

Figure 6An example of gradification in the presence of Scott’s tree.

Figure 6

Figure 7The form of the paths in $ {\Uparrow} ({\mathsf {last}(x)})^F$ and $ {\Uparrow} (x)^{F'}$.

Figure 7

Figure 8The technique in the proof of Theorem 6.29 does not work in general.

Figure 8

Figure 9An example of gradification in the absence of Scott’s tree.

Figure 9

Figure 10The relations between the zigzag points in case $l=3$.

Figure 10

Figure 11The zigzag path and the ladder structure in place.

Figure 11

Figure 12The form of the paths in $ {\Uparrow} ({\mathsf {last}(x)})$ and $ {\Uparrow} (x)$.

Figure 12

Figure 13An example of nervification, using the graded structure of F.

Figure 13

Figure 14The chevron structure in a case with two branches.

Figure 14

Figure 15The chevron structure in a more complex case involving three branches.