Hereditarily structurally complete superintuitionistic deductive systems

DOI10.1007/S11225-017-9769-1MaRDI QIDQ1790607zbMATH OpenOpenAlexFDO

Publication date 2 October 2018

Published in Studia Logica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.04809

admissible rule deductive system hereditary structural completeness Heyting algebra primitive quasivariety structural completeness superintuitionistic logic

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Intermediate logics (03B55)

Abstract: The paper studies hereditarily complete superintuitionistic deductive systems, that is, the deductive system which logic is an extension of the intuitionistic propositional logic. It is proven that for deductive systems a criterion of hereditary structurality - similar to one that exists for logics - does not exists. Nevertheless, it is proven that many standard superintuitionistic logics (including Int) can be defined by a hereditarily structurally complete deductive system.

Review text

A deductive system \(\langle Ax,R\rangle\) is defined by a set of (schemes of) axioms \(Ax\) and a set of rules \(R\). Any deductive system \(\mathsf S=\langle Ax,R\rangle\) defines in a natural way a consequence relation \(\vdash_{\mathsf S}\) and a logic \(\mathsf L(\mathsf S)\) (the set of formulas derivable from \(Ax\) by means of rules in \(R\)). A deductive system \(\mathsf S_2\) is a deductive extension of \(\mathsf S_1\) if \(\vdash_{\mathsf S_1}\subseteq\vdash_{\mathsf S_2}\). A deductive system \(\mathsf S\) is called structurally complete if every rule admissible in \(\mathsf S\) is derivable in \(\mathsf S\). A structurally complete system \(\mathsf S\) is hereditarily structurally complete (h.s.c.) if every deductive extension of \(\mathsf S\) is structurally complete. It is known that for any deductive system \(\mathsf S\), there is a structurally complete deductive system \(\widetilde{S}\) (the structural completion of \(\mathsf S\)) such that \(\mathsf L(\mathsf S)=\mathsf L(\widetilde{\mathsf S})\). Theorem~4.9 gives a necessary and sufficient condition for a system \(\widetilde{S}\) to be h.s.c. in terms of preserving a relative base of rules admissible in \(\mathsf S\) under deductive extensions of \(\mathsf S\). The following problem is studied in the paper: given a superintuitionistic deductive system (i.e., a deductive extension of intuitionistic propositional calculus \(\mathsf{IPC}\)) \(\mathsf S\), is the system \(\widetilde{S}\) h.s.c.? It is proved that there are continuum many h.s.c. superintuitionistic logics. On the other hand, there are continuum many superintuitionistic logics which are not h.s.c.. Some concrete intermediate logics are considered. Namely, structural completions of the intuitionistic logic, the Gödel-Dummett logic, the Gödel logics \(G_n\), the Yankov logic \(\mathsf{IPC}+\neg p\lor\neg\neg p\), the logic of Visser's rules, the logic of the Rieger-Nishimura ladder, the Smetanich logic are h.s.c.. At the same time, structural completions of the logics \(\mathsf{BD}_n\) of depth \(n\) for \(n>3\), the Kreisel-Putnam logic, the Medvedev logic of finite problems are not h.s.c.. For the negative results, the following statement is important: for a logic \(\mathsf L\), if the Lindenbaum algebra of formulas of one variable is finite and has at least 15 elements, then the structural completion of \(\mathsf L\) is not h.s.c.. There is no smallest h.s.c. deductive system extending \(\mathsf{IPC}\). A deductive system \(\mathsf S\) is said to have the finite model property relative to admissibility if for every rule \(\mathsf r\) not admissible in \(\mathsf S\), there exists a finite Heyting algebra in which all admissible rules are valid but \(\mathsf r\) is not valid. It is proved that there are continuum many h.s.c. deductive systems without the finite model property relative to admissibility. A correspondence between h.s.c. deductive systems and properties of quasivarieties of Heyting algebras plays an important role in getting some results.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Hereditarily structurally complete superintuitionistic deductive systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1790607)