TY - JOUR

T1 - First order theories of some lattices of open sets

AU - Kudinov, Oleg

AU - Selivanov, Victor

PY - 2017/8/25

Y1 - 2017/8/25

N2 - 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.

AB - 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.

KW - Decidability

KW - Effectively open set

KW - First order theory

KW - Interpretation

KW - Lattice

KW - M-reducibility

KW - Open set

KW - Topological space

UR - http://www.scopus.com/inward/record.url?scp=85041794599&partnerID=8YFLogxK

U2 - 10.23638/LMCS-13(3:16)2017

DO - 10.23638/LMCS-13(3:16)2017

M3 - Article

AN - SCOPUS:85041794599

VL - 13

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

SN - 1860-5974

IS - 3

ER -