First order theories of some lattices of open sets | Sciact - Система учета научной деятельности ИМ СО РАН

First order theories of some lattices of open sets Научная публикация

Журнал

Logical Methods in Computer Science
ISSN: 1860-5974

Вых. Данные

Год: 2017, Том: 13, Номер: 3, Номер статьи : 16, Страниц : DOI: 10.23638/LMCS-13(3:16)2017

Ключевые слова

Decidability; Effectively open set; First order theory; Interpretation; Lattice; M-reducibility; Open set; Topological space

Авторы

Kudinov O. ^1,2,3 , Selivanov V. ^2,3

Организации

1	S.L. Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russian Federation
2	A.P. Ershov Institute of Informatics Systems, Siberian Branch of the Russian Academy of Sciences
3	Kazan (Volga Region) Federal University Russian Federation

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.

Kudinov O. , Selivanov V.
First order theories of some lattices of open sets
Logical Methods in Computer Science. 2017. V.13. N3. 16 . DOI: 10.23638/LMCS-13(3:16)2017 WOS Scopus OpenAlex

Web of science:	WOS:000419163000034
Scopus:	2-s2.0-85041794599
OpenAlex:	W2614098761

БД	Цитирований
Scopus	3
OpenAlex	2