Mikhail Rybakov made a presentation at the workshop "Non-Standard Logics" at the S.L.Sobolev Institute of Mathematics SB RAS

On September 9, Mikhail Rybakov made a presentation on the topic of "The Undecidability of QLC with Two Variables" at the workshop "Non-Standard Logics"at the S.L.Sobolev Institute of Mathematics SB RAS in Novosibirsk

Abstract

We present a solution to the long-standing question about the decidability of the two-variable fragment of the superintuitionistic predicate logic QLC defined by the class of linear Kripke frames, which is also the ‘superintuitionistic’ fragment of the modal predicate logic QS4:3, under the Gödel translation. We show that the fragment is undecidable. The result remains true for the positive fragment. The proof is based on two techniques: a modification of the method proposed by M. Marx and M. Reynolds, which allows us to describe tiling problems using natural numbers rather than pairs of numbers within an enumeration of Cantor’s, and an idea of ‘double labeling’ the elements from the domains, which allows us to use only two individual variables in the proof when applying the former method.