### ?

## On existence of recursively-enumerable Kripke-complete first-order modal logics that are not Kripke complete with respect to a first-order definable class of frames

P. 45-45.

Rybakov M., Shkatov D.

We discuss an example of recursively-enumerable Kripke-complete first-order modal logics that are not Kripke complete with respect to a first-order definable class of frames.

Language:
English

### In book

М. : Современные тетради, 2017

Shehtman V. B., Annals of Pure and Applied Logic 2023 Vol. 174 No. 2 Article 103202

The paper studies completeness and incompleteness of modal predicate logics in
Kripke semantics, especially for logics of the form QL, minimal predicate extensions
of modal propositional logics. We show that QL is incomplete for a continual family
of logics above K + \Box(\Box p \rigtharrow p), in particular for well-known K5 and K45. On
the other hand, in some cases ...

Added: January 30, 2023

Rybakov M., Shkatov D., , in : Advances in Modal Logic. Vol. 12.: College Publications, 2018. P. 531-539.

It is well-known that every quantied modal logic complete with respect to a first-order definable class of Kripke frames is recursively enumerable. Numerous examples are also known of natural quantied modal logics complete with respect to a class of frames dened by an essentially second-order condition which are not recursively enumerable. It is not, however, known if these ...

Added: October 6, 2019

Marseille : [б.и.], 2011

Added: February 27, 2013

Beklemishev L. D., / Cornell University. Series math "arxiv.org". 2013. No. arXiv:1304.4396.

We deal with the fragment of modal logic consisting of implications of formulas built up from the variables and the constant `true' by conjunction and diamonds only. The weaker language allows one to interpret the diamonds as the uniform reflection schemata in arithmetic, possibly of unrestricted logical complexity. We formulate an arithmetically complete calculus with ...

Added: November 22, 2013

Khaitovich D., / Cornell University. Series arXiv "math". 2021. No. 2110.

Added: December 7, 2021

Kudinov A., Shehtman V. B., Shapirovsky I., , in : Advances in Modal Logic. Issue 9.: L. : College Publications, 2012. P. 395-410.

With a set S of words in an alphabet A we associate the frame (S; H), where sHt iff s and t are words of the same length and h(s; t) = 1 for the Hamming distance h. We investigate some unimodal logics of these frames. We show that if the length of words n ...

Added: February 21, 2013

Kudinov A., Shapirovsky I., , in : Topology, Algebra and Categories in Logic (TACL 2011). : Marseille : [б.и.], 2011. P. 261-264.

We consider propositional normal unimodal pretransitive logics, i.e., logics with expressible `transitive' modality. There is a long-standing open problem about the finite model property (fmp) and decidability of pretransitive logics, in particular - for the logics K^m_n = K+[]^m p -> []^n p, n>m>1. ...

Added: February 27, 2013

Zolin E., Notre Dame Journal of Formal Logic 2019

We introduce a modal operator of weak necessity, inspired by the canonical model construction for the non-contingency logic developed by Humberstone and Kuhn in 1995. This operator, when applied to a proposition, means that all consequences of a given proposition are non-contingent. We show that, although the weak necessity has many properties inherent to normal ...

Added: June 14, 2018

Kudinov A., , in : Advances in Modal Logic, Volume 6. : L. : College Publications, 2006. P. 319-332.

Added: February 27, 2013

Schang F., Al-Mukhatabat 2014 Vol. 9 No. 1 P. 230-242

The paper draws attention to the epistemological obstacles that prevented Wittgenstein from acknowledging the modern view of modal logic, including the so-called propositional attitudes. Whilst suggesting a retrospective overview of the logic of epistemic modalities, it is argued that such obstacles primarily rely upon the nature of the logical space depicted in the Tractatus Logico-Philosophicus as well as the ...

Added: October 30, 2014

Kikot S., Kudinov A., Mathematics 2022 Vol. 10 No. 19 Article 3701

We axiomatize strictly positive fragments of modal logics with the confluence axiom. We consider unimodal logics such
as K.2, D.2, D4.2 and S4.2
with unimodal confluence $\Diamond\Box p \to \Box\Diamond p$
as well as the products of modal logics
in the set {K, D, T, D4, S4}, which contain bimodal confluence
$\Diamond_1\Box_2 p \to \Box_2\Diamond_1 p$.
We show that the impact ...

Added: October 10, 2022

L. : College Publications, 2012

Advances in Modal Logic is a bi-annual international conference and book series in Modal Logic. The aim of the conference series is to report on important new developments in pure and applied modal logic, and to do so at varying locations throughout the world. The book series is based on the conferences. Please consult thebackground pages for further details. ...

Added: February 21, 2013

Shapirovsky I., Zolin E., , in : 7th International Conference on Topology, Algebra and Categories in Logic (TACL 2015). : [б.и.], 2015. P. 1-3.

We give a sufficient condition for Kripke completeness of the extension of a modal logic with the transitive closure modality. More precisely, we show that if a logic is canonical and admits what we call definable filtration (ADF), then such an extension is complete (and again ADF). ...

Added: June 14, 2018

Kudinov A., , in : Advances in Modal Logic. Volume 10. : College Publications, 2014. P. 373-386.

We consider modal logics of products of neighborhood frames and nd the modal logic of all products of normal neighborhood frames. ...

Added: November 7, 2014

Complexity function and complexity of validity of modal and superintuitionistic propositional logics

Rybakov M., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566-1595

We consider the relationship between the algorithmic properties of the validity problem for a modal or superintuitionistic propositional logic and the size of the smallest Kripke countermodels for non-theorems of the logic. We establish the existence, for every degree of unsolvability, of a propositional logic whose validity problem belongs to the degree and whose every ...

Added: January 6, 2023

Zakharyaschev M., Kurucz A., Savateev Y. et al., Springer, 2021

We prove that, similarly to known PSPACEPSPACE-completeness of recognising 𝖥𝖮(<)FO(<)-definability of the language 𝐿(𝔄)L(A) of a DFA 𝔄A, deciding both 𝖥𝖮(<,≡)FO(<,≡)- and 𝖥𝖮(<,𝖬𝖮𝖣)FO(<,MOD)-definability (corresponding to circuit complexity in AC0AC0 and ACC0ACC0) are PSPACEPSPACE-complete. We obtain these results by first showing that known algebraic characterisations of FO-definability of 𝐿(𝔄)L(A)can be captured by ‘localisable’ properties of the transition monoid of 𝔄A. Using our criterion, we then generalise the known proof ...

Added: November 6, 2021

Zolin E., Logic Journal of the IGPL 2015 Vol. 23 No. 6 P. 861-880

The celebrated theorem proved by Goldblatt and Thomason in 1974 gives necessary and sufficient conditions for an elementary class of Kripke frames to be modally definable. Here we obtain a local analogue of this result, which deals with modal definability of classes of pointed frames. Furthermore, we generalize it to the case of n-frames, which ...

Added: June 14, 2018

Shehtman V. B., Shapirovsky I., , in : Advances in Modal Logic. Vol. 11.: L. : College Publications, 2016. P. 520-534.

According to the classical result by Segerberg and Maksimova, a modal logic containing K4 is locally tabular iff it is of finite height. The notion of finite height can also be defined for logics, in which the master modality is expressible (‘pretransitive’ logics). We observe that any locally tabular logic is pretransitive of finite height. Then we prove some ...

Added: September 20, 2018

Beklemishev L. D., Fernandez-Duque D., Joosten J. J., Studia Logica 2014 Vol. 102 No. 3 P. 541-566

We introduce the logics GLPΛ, a generalization of Japaridze’s polymodal provability logic GLPω where Λ is any linearly ordered set representing a hierarchy of provability operators of increasing strength. We shall provide a reduction of these logics to GLPω yielding among other things a finitary proof of the normal form theorem for the variable-free fragment of GLPΛ and the decidability of GLPΛ for recursive ...

Added: November 21, 2013

Slavnov S. A., Moscow Mathematical Journal 2005 Vol. 5 No. 2 P. 477-492

Классический результат о топологической семантике модальных логик, принадлежащий МакКинси и Тарскому (и часто называемый теоремой Тарского), состоит в полноте логики S4 по отношению к интерпретациям в пространстве R^n
для любого n. В последнее время разные авторы рассматривали динамические топологические логики, которые интерпретируются в динамических пространствах (абстрактных динамических системах). Динамическое пространство – это топологическое пространство вместе с непрерывной функцией на нем. В работе Артёмова, Даворен и ...

Added: February 27, 2013

Rybakov M., Shkatov D., Studia Logica 2024

In the early 1960s, to prove undecidability of monadic fragments of sublogics of the predicate modal logic QS5 that include the classical predicate logic QCl, Saul Kripke showed how a classical atomic formula with a binary predicate letter can be simulated by a monadic modal formula. We consider adaptations of Kripke's simulation, which we call the Kripke trick, to various modal ...

Added: December 2, 2023

Kudinov A., Shehtman V. B., , in : Leo Esakia on Duality in Modal and Intuitionistic Logics. : Springer, 2014. Ch. 11. P. 291-334.

We study modal logics of topological spaces in the combined language with the derivational modality and the difference modality. We give axiomatizations and prove completeness for the following classes: all spaces, T1- spaces, dense-in-themselves spaces, a zero-dimensional dense-in-itself separable metric space, R^n (n>1). We also discuss the correlation between languages with different combinations of the ...

Added: March 5, 2014

Kudinov A., , in : Advances in Modal Logic. Issue 9.: L. : College Publications, 2012. P. 286-294.

We consider modal logics of products of neighborhood frames and prove that for any pair L and L' of logics from set {S4, D4, D, T} modal logic of products of L-neighborhood frames and L'-neighborhood frames is the fusion of L and L'. ...

Added: February 21, 2013

L. : College Publications, 2016

Logic deals with the fundamental notions of truth and falsity. Modal logic arose from the philosophical study of “modes of truth” with the two most common modes being “necessarily true” and “possibly true”. Research in modal logic now spans the spectrum from philosophy, computer science and mathematics using techniques from relational structures, universal algebra, topology, ...

Added: July 17, 2017