RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2018 Volume 15, Pages 35–47 (Mi semr896)

This article is cited in 1 paper

Mathematical logic, algebra and number theory

Strong computability of slices over the logic $\mathrm{GL}$

L. L. Maksimovaab, V. F. Yunba

a Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
b Novosibirsk State University, Pirogova Str., 2, 630090, Novosibirsk, Russia

Abstract: In [2] the classification of extensions of the minimal logic $\mathrm{J}$ using slices was introduced and decidability of the classification was proved. We will consider extensions of the logic $ \mathrm{GL} = \mathrm{J} + (A \vee \neg A) $. The logic $\mathrm{GL}$ and its extensions have been studied in [8, 9]. In [6], it is established that the logic $\mathrm{GL}$ is strongly recognizable over $\mathrm{J}$, and the family of extensions of the logic $\mathrm{GL}$ is strongly decidable over $\mathrm{J}$. In this paper we prove strong decidability of the classification over $\mathrm{GL}$: for every finite set $ Rul $ of axiom schemes and rules of inference, it is possible to efficiently calculate the slice number of the calculus obtained by adding $ Rul $ as new axioms and rules to $\mathrm{GL}$.

Keywords: The minimal logic, slices, Kripke frame, decidability, recognizable logic.

UDC: 510.6

MSC: 03B45

Received December 29, 2016, published January 18, 2018

DOI: 10.17377/semi.2018.15.005



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024