Premium
Computability of graphs
Author(s) -
Iljazović Zvonko
Publication year - 2020
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201900025
Subject(s) - mathematics , computable analysis , computability , metric space , topological space , discrete mathematics , computable function , computable number , subspace topology , combinatorics , pure mathematics , mathematical analysis
We consider topological pairs ( A , B ) , B ⊆ A , which have computable type, which means that they have the following property: if X is a computable topological space and f : A → X a topological imbedding such that f ( A ) and f ( B ) are semicomputable sets in X , then f ( A ) is a computable set in X . It is known, e.g., that ( M , ∂ M ) has computable type if M is a compact manifold with boundary. In this paper we examine topological spaces called graphs and we show that we can in a natural way associate to each graph G a discrete subspace E so that ( G , E ) has computable type. Furthermore, we use this result to conclude that certain noncompact semicomputable graphs in computable metric spaces are computable.