Тип публикации: статья из журнала

Год издания: 2017

Идентификатор DOI: 10.23638/LMCS-13(3:16)2017

Ключевые слова: Decidability, Effectively open set, First order theory, Interpretation, Lattice, M-reducibility, Open set, Topological space

Аннотация: We show that the first order theory of the lattice of open sets in some natural topological spaces is m-equivalent to second order arithmetic. We also show that for many natural computable metric spaces and computable domains the first order theory of the lattice of effectively open sets is undecidable. Moreover, for several importПоказать полностьюant spaces (e.g., ℝn, n ≥ 1, and the domain Pω) this theory is m-equivalent to first order arithmetic. © Oleg Kudinov and Victor Selivanov.

Журнал: Logical Methods in Computer Science

Выпуск журнала: Vol. 13, Is. 3

Номера страниц: 16

ISSN журнала: 18605974

Издатель: Logical Methods in Computer Science

• Kudinov O. (S.L. Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russian Federation, A.P. Ershov Institute of Informatics Systems, Siberian Branch of the Russian Academy of Sciences, Kazan (Volga Region) Federal University, Novosibirsk, Russian Federation)
• Selivanov V. (S.L. Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russian Federation, A.P. Ershov Institute of Informatics Systems, Siberian Branch of the Russian Academy of Sciences, Kazan (Volga Region) Federal University, Novosibirsk, Russian Federation)

• Scopus