First order theories of some lattices of open sets

First order theories of some lattices of open sets Full article

Journal

Logical Methods in Computer Science
ISSN: 1860-5974

Output data

Year: 2017, Volume: 13, Number: 3, Article number : 16, Pages count : DOI: 10.23638/LMCS-13(3:16)2017

Tags

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

Authors

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

Affiliations

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

DB	Citing
Scopus	3
OpenAlex	2