RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2018, том 15, страницы 35–47 (Mi semr896)

Эта публикация цитируется в 1 статье

Математическая логика, алгебра и теория чисел

Сильная вычислимость слоев над логикой $\mathrm{GL}$

Л. Л. Максимоваab, В. Ф. Юнba

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

Аннотация: 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}$.

Ключевые слова: The minimal logic, slices, Kripke frame, decidability, recognizable logic.

УДК: 510.6

MSC: 03B45

Поступила 29 декабря 2016 г., опубликована 18 января 2018 г.

DOI: 10.17377/semi.2018.15.005



Реферативные базы данных:


© МИАН, 2024