Abstract:
We prove that, for each non null countable ordinal alpha, there exist some Sigma^0_alpha-complete omega-powers, and some Pi^0_alpha-complete omega-powers, extending previous works on the topological complexity of omega-powers. We prove effective versions of these results. In particular, for each non null recursive ordinal alpha, there exists a recursive finitary language A such that A^omega is Sigma^0_alpha-complete (respectively, Pi^0_alpha-complete). To do this, we prove effective versions of a result by Kuratowski, describing a Borel set as the range of a closed subset of the Baire space by a continuous bijection. This leads us to prove closure properties for the classes Effective-Pi^0_alpha and Effective-Sigma^0_alpha of the hyperarithmetical hierarchy in arbitrary recursively presented Polish spaces. We apply our existence results to get better computations of the topological complexity of some sets of dictionaries considered by the second author in [Omega-Powers and Descriptive Set Theory, Journal of Symbolic Logic, Volume 70 (4), 2005, p. 1210-1232].

Abstract:
This report consists of two parts. The first part is a brief exposition of classical descriptive set theory. This part introduces some fundamental concepts, motivations and results from the classical theory and ends with a section on the important result of Addison that established the correspondence between classical and effective notions. The second part is about invariant descriptive set theory. It consists of a brief introduction to notions relevant to this branch of descriptive set theory and then describes in details some of the relatively recent results concerning equivalence relations between Polish metric spaces.

Abstract:
A dictionary is a set of finite words over some finite alphabet X. The omega-power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V. Lecomte studied in [Omega-powers and descriptive set theory, JSL 2005] the complexity of the set of dictionaries whose associated omega-powers have a given complexity. In particular, he considered the sets $W({\bf\Si}^0_{k})$ (respectively, $W({\bf\Pi}^0_{k})$, $W({\bf\Delta}_1^1)$) of dictionaries $V \subseteq 2^\star$ whose omega-powers are ${\bf\Si}^0_{k}$-sets (respectively, ${\bf\Pi}^0_{k}$-sets, Borel sets). In this paper we first establish a new relation between the sets $W({\bf\Sigma}^0_{2})$ and $W({\bf\Delta}_1^1)$, showing that the set $W({\bf\Delta}_1^1)$ is "more complex" than the set $W({\bf\Sigma}^0_{2})$. As an application we improve the lower bound on the complexity of $W({\bf\Delta}_1^1)$ given by Lecomte. Then we prove that, for every integer $k\geq 2$, (respectively, $k\geq 3$) the set of dictionaries $W({\bf\Pi}^0_{k+1})$ (respectively, $W({\bf\Si}^0_{k+1})$) is "more complex" than the set of dictionaries $W({\bf\Pi}^0_{k})$ (respectively, $W({\bf\Si}^0_{k})$) .

Abstract:
Descriptive set theory is mainly concerned with studying subsets of the space of all countable binary sequences. In this paper we study the generalization where countable is replaced by uncountable. We explore properties of generalized Baire and Cantor spaces, equivalence relations and their Borel reducibility. The study shows that the descriptive set theory looks very different in this generalized setting compared to the classical, countable case. We also draw the connection between the stability theoretic complexity of first-order theories and the descriptive set theoretic complexity of their isomorphism relations. Our results suggest that Borel reducibility on uncountable structures is a model theoretically natural way to compare the complexity of isomorphism relations.

Abstract:
Using ideas from synthetic topology, a new approach to descriptive set theory is suggested. Synthetic descriptive set theory promises elegant explanations for various phenomena in both classic and effective descriptive set theory. Presently, we mainly focus on developing the ideas in the category of represented spaces.

Abstract:
Given an equivalence class $[A]$ in the measure algebra of the Cantor space, let $\hat\Phi([A])$ be the set of points having density 1 in $A$. Sets of the form $\hat\Phi([A])$ are called $\mathcal{T}$-regular. We establish several results about $\mathcal{T}$-regular sets. Among these, we show that $\mathcal{T}$-regular sets can have any complexity within $\Pi^{0}_{3}$ (=$ \mathbf{F}_{\sigma\delta}$), that is for any $\Pi^{0}_{3}$ subset $X$ of the Cantor space there is a $\mathcal{T}$-regular set that has the same topological complexity of $X$. Nevertheless, the generic $\mathcal{T}$-regular set is $\Pi^{0}_{3}$-complete, meaning that the classes $[A]$ such that $\hat{\Phi}([A]) $ is $\Pi^{0}_{3}$-complete form a comeagre subset of the measure algebra. We prove that this set is also dense in the sense of forcing, as $\mathcal{T}$-regular sets with empty interior turn out to be $\Pi^{0}_{3}$-complete. Finally we show that the generic $[A]$ does not contain a $\Delta^{0}_{2}$ set, i.e., a set which is in $\mathbf{F}_\sigma\cap\mathbf{G}_\delta$

Abstract:
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.

Abstract:
We first consider three well-known chain conditions in the space of marked groups: the minimal condition on centralizers, the maximal condition on subgroups, and the maximal condition on normal subgroups. For each condition, we produce a characterization in terms of well-founded descriptive-set-theoretic trees. Using these characterizations, we demonstrate that the sets given by these conditions are co-analytic and not Borel in the space of marked groups. We then adapt our techniques to show elementary amenable marked groups may be characterized by well-founded descriptive-set-theoretic trees, and therefore, elementary amenability is equivalent to a chain condition. Our characterization again implies the set of elementary amenable groups is co-analytic and non-Borel. As corollary, we obtain a new, non-constructive, proof of the existence of finitely generated amenable groups that are not elementary amenable.

Abstract:
We study some natural sets arising in the theory of ordinary differential equations in one variable from the point of view of descriptive set theory and in particular classify them within the Borel hierarchy. We prove that the set of Cauchy problems for ordinary differential equations which have a unique solution is $\Pi^0_2$-complete and that the set of Cauchy problems which locally have a unique solution is $\Sigma^0_3$-complete. We prove that the set of Cauchy problems which have a global solution is $\Sigma^0_4$-complete and that the set of ordinary differential equation which have a global solution for every initial condition is $\Pi^0_3$-complete. We prove that the set of Cauchy problems for which both uniqueness and globality hold is $\Pi^0_2$-complete.

Abstract:
This is an extended abstract presenting new results on the topological complexity of omega-powers (which are included in a paper "Classical and effective descriptive complexities of omega-powers" available from arXiv:0708.4176) and reflecting also some open questions which were discussed during the Dagstuhl seminar on "Topological and Game-Theoretic Aspects of Infinite Computations" 29.06.08 - 04.07.08.