Тип публикации: статья из журнала
Год издания: 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 important 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)
Вхождение в базы данных
Информация о публикациях загружается с сайта службы поддержки публикационной активности СФУ. Сообщите, если заметили неточности.