In this article we treat a notion of continuity for a multi-valued function $F$ and we compute the descriptive set-theoretic complexity of the set of all $x$ for which $F$ is continuous at $x$. We give conditions under which the latter set is either a $G_delta$ set or the countable union of $G_delta$ sets. Also we provide a counterexample which shows that the latter result is optimum under the same conditions. Moreover we prove that those conditions are necessary in order to obtain that the set of points of continuity of $F$ is Borel i.e., we show that if we drop some of the previous conditions then there is a multi-valued function $F$ whose graph is a Borel set and the set of points of continuity of $F$ is not a Borel set. Finally we give some analogous results regarding a stronger notion of continuity for a multi-valued function. This article is motivated by a question of M. Ziegler in [{em Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability with Applications to Linear Algebra}, {sl submitted}].

The descriptive set-theoretic complexity of the set of points of continuity of a multi-valued function

GREGORIADES, VASSILIOS
2011-01-01

Abstract

In this article we treat a notion of continuity for a multi-valued function $F$ and we compute the descriptive set-theoretic complexity of the set of all $x$ for which $F$ is continuous at $x$. We give conditions under which the latter set is either a $G_delta$ set or the countable union of $G_delta$ sets. Also we provide a counterexample which shows that the latter result is optimum under the same conditions. Moreover we prove that those conditions are necessary in order to obtain that the set of points of continuity of $F$ is Borel i.e., we show that if we drop some of the previous conditions then there is a multi-valued function $F$ whose graph is a Borel set and the set of points of continuity of $F$ is not a Borel set. Finally we give some analogous results regarding a stronger notion of continuity for a multi-valued function. This article is motivated by a question of M. Ziegler in [{em Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability with Applications to Linear Algebra}, {sl submitted}].
2011
7
4
1
22
http://arxiv.org/pdf/1108.0843
σ0nSet; Analytic set; Borel set; Descriptive set theory; Multi-valued function; Points of continuity; Computer Science (all); Theoretical Computer Science
Gregoriades, Vassilios
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/2318/1621513
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact