Source author record

Vassilios Gregoriades

Vassilios Gregoriades appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.LO Logic in Computer Science math.FA math.GN

Catalog footprint

What is connected

7works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

On a Question of Jaegers

We show that there exists a positive arithmetical formula $ψ(x,R)$, where $x \in ω$, $R \subseteq ω$, with no hyperarithmetical fixed point. This answers a question of Gerhard Jäger. As corollaries we obtain results on the proof-theoretic strength of the Kripke-Platek set theory; the fixed points of monotone functions in chain-complete partial orders; the non-Borel uniformization of Borel sets; and the hyperdegrees of fixed points of positive formulae. Further we prove a Suslin-Kleene type result for the specific encoding of the hyperarithmetical sets that we are using.

preprint2020arXiv

Intersections of $\ell^p$ spaces in the Borel hierarchy

We show that if $Y$ is one of the spaces $\ell^q$, $c_0$, $\ell^\infty$ or ${\textstyle \bigcap_{p > b}} \ell^p$ where $0 < q,b < \infty$, and the Fréchet space $\textstyle \bigcap_{p > a} \ell^p$ is contained in $Y$ properly, then $\textstyle \bigcap_{p > a} \ell^p$ first shows up in the Borel hierarchy of $Y$ at the multiplicative class of the third level. In particular $\textstyle \bigcap_{p > a} \ell^p$ is neither an $F_σ$ nor a $G_δ$ subset of $Y$. This answers a question by Nestoridis. This result provides a natural example of a set in the third level of the Borel hierarchy and with its help we also give some examples in the fourth level.

preprint2016arXiv

One more recursive-theoretic characterization of the Topological Vaught Conjecture

We prove in ZF a recursive-theoretic characterization of the Topological Vaught Conjecture by revisiting the fact that orbits in Polish $G$-spaces are Borel sets.

preprint2016arXiv

Turing degrees in Polish spaces and decomposability of Borel functions

We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (\eg the Shore-Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on the Martin Conjecture on the degree preserving Borel functions between Polish spaces. Additionally we prove results about the transfinite version as well as the computable version of the Decomposability Conjecture, and we explore the idea of applying the technique of turning Borel-measurable functions into continuous ones.

preprint2015arXiv

A comparison of concepts from computable analysis and effective descriptive set theory

Computable analysis and effective descriptive set theory are both concerned with complete metric spaces, functions between them and subsets thereof in an effective setting. The precise relationship of the various definitions used in the two disciplines has so far been neglected, a situation this paper is meant to remedy. As the role of the Cauchy completion is relevant for both effective approaches to Polish spaces, we consider the interplay of effectivity and completion in some more detail.

preprint2012arXiv

Turning Borel sets into clopen sets effectively

We present the effective version of the theorem about turning Borel sets in Polish spaces into clopen sets while preserving the Borel structure of the underlying space. We show that under some conditions the emerging parameters can be chosen in a hyperarithmetical way and using this we prove a uniformity result.

preprint2011arXiv

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

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_δ$ set or the countable union of $G_δ$ 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}].