Towards a descriptive set theory for domain-like structures (Q854185)

The classical descriptive set theory classifies definable sets and functions in Polish spaces. However, in some areas of theoretical computer science various classes of domains play a~prominent role and definable sets of different kind are important in many cases. The present paper is a~survey of results in descriptive set theory for domains and similar spaces. The subject of the paper is still in its beginning; therefore the author discusses in detail several open questions and possible future developments. Note that all interesting spaces in domain theory are not Hausdorff, and consequently not Polish. Let \(X\) be a~\(T_0\)-space. For \(x,y\in X\) let \(x\leq y\) denote that \(x\in U\) implies \(y\in U\) for all open sets~\(U\). The relation~\(\leq\) is known as the specialization order. If \(p\in X\) and the cone \(O_p=\{x:p\leq x\}\) is open, then \(p\)~is called a~finitary element and \(O_p\)~is called an \(f\)-set. \(X\)~is a~\(\varphi\)-space, if every open set in~\(X\) is a~union of \(f\)-sets. A~\(\varphi\)-space~\(X\) is complete if every non-empty directed set~\(S\) without greatest element has a~supremum in~\(X\) which is a~limit point of~\(S\). It is well-known that every \(\varphi\)-space is canonically embeddable into a~complete \(\varphi\)-space. The main results of the paper are stated mostly for complete \(\varphi\)-spaces with countable base. Such spaces correspond to the so called \(\omega\)-algebraic domains. A~\(\varphi\)-space~\(X\) is an \(f\)-space if any two finitary elements in~\(X\) which have an upper bound have a~least upper bound in the specialization order. There are two traditions in the terminology of domain theory: the first tends to use the language of partially ordered sets and the second, used also in the paper under the review, tends to use topological language. The material of the paper is divided into several sections. The second section follows a~short introduction. The main results of this section concern reflective spaces which in some sense resemble the structure of fractals. Important examples that are useful throughout the paper are introduced here. In the third section the notion of effective \(\varphi\)-space is introduced as a~pair \((X,\delta)\) where \(X\)~is a~complete \(\varphi\)-space and \(\{\delta(n):n\in\omega\}\) is an enumeration of all finitary elements of~\(X\) such that the relation \(\delta(x)\leq\delta(y)\) is computably enumerable. A~short discussion of this notion of effectiveness follows. The fourth section is a~discussion about the Borel hierarchy in \(\varphi\)-spaces. It presents basic results on the length of the hierarchy, reduction and separation properties of particular classes in the hierarchy. In the fifth section analytic sets are introduced as results of the Suslin operation~\(\mathcal A\). Only a~few results of classical descriptive set theory are known to hold also for domains. The sixth section is on the Hausdorff difference hierarchy of Borel sets, the seventh sections deals with the Wadge reducibility for arbitrary spaces with emphasis on the \(\varphi\)-spaces, and the eighth section presents some results for \(\omega\)-Boolean operations. The last, ninth, section presents a~discussion about the applications of the domain descriptive set theory to classical descriptive set theory, applications to computability theory, connections with computability in analysis, and with infinite computations.