The focus of this paper is the incomputability of some topological functions (with respect to certain representations) using the tools of Borel computability theory, as introduced by V. Brattka in [3] and [4]. First, we analyze some basic topological functions on closed subsets of Rn, like closure, border, intersection, and derivative, and we prove for such functions results of Sigma02-completeness and Sigma03-completeness in the effective Borel hierarchy. Then, following [13], we re-consider two well-known topological results: the lemmas of Urysohn and Urysohn-Tietze for generic metric spaces (for the latter we refer to the proof given by Dieudonné). Both lemmas define Sigma02-computable functions which in some cases are even Sigma02-complete.

Effective Borel degrees of some topological functions

GHERARDI, GUIDO
2006

Abstract

The focus of this paper is the incomputability of some topological functions (with respect to certain representations) using the tools of Borel computability theory, as introduced by V. Brattka in [3] and [4]. First, we analyze some basic topological functions on closed subsets of Rn, like closure, border, intersection, and derivative, and we prove for such functions results of Sigma02-completeness and Sigma03-completeness in the effective Borel hierarchy. Then, following [13], we re-consider two well-known topological results: the lemmas of Urysohn and Urysohn-Tietze for generic metric spaces (for the latter we refer to the proof given by Dieudonné). Both lemmas define Sigma02-computable functions which in some cases are even Sigma02-complete.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/104201
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 4
social impact