We discuss the complexity of completions of partial combinatory algebras, in particular, of Kleene’s first model. Various completions of this model exist in the literature, but all of them have high complexity. We show that although there are no computable completions, there exist completions of low Turing degree. We use this construction to relate completions of Kleene’s first model to complete extensions of $\mathrm{PA}$. We also discuss the complexity of pcas defined from nonstandard models of $\mathrm{PA}$.

The authors’ primary goal in this paper is to enhance the study of $T_0$ topological spaces by using the order of specialization of a $T_0$-space to introduce the lower topology (with a subbasis of closed sets $\mathord{\uparrow } x$) and studying the interaction of the original topology and the lower topology. Using the lower topology, one can define and study new properties of the original space that provide deeper insight into its structure. One focus of study is the property R, which asserts that if the intersection of a family of finitely generated sets $\mathord{\uparrow } F$, $F$ finite, is contained in an open set $U$, then the same is true for finitely many of the family. We first show that property R is equivalent to several other interesting properties, for example, the property that all closed subsets of the original space are compact in the lower topology. We then find conditions under which these spaces are compact, well-filtered, and coherent, a weaker variant of stably compact spaces. We also investigate what have been called strong $d$-spaces, develop some of their basic properties, and make connections with the earlier considerations involving spaces satisfying property R. Two key results we obtain are that if a dcpo $P$ with the Scott topology is a strong $d$-space, then it is well-filtered, and if additionally the Scott topology of the product $P\times P$ is the product of the Scott topologies of the factors, then the Scott space of $P$ is sober. We also exhibit connections of this work with de Groot duality.

Computability on uncountable sets has no standard formalization, unlike that on countable sets, which is given by Turing machines. Some of the approaches to define computability in these sets rely on order-theoretic structures to translate such notions from Turing machines to uncountable spaces. Since these machines are used as a baseline for computability in these approaches, countability restrictions on the ordered structures are fundamental. Here, we show several relations between the usual countability restrictions in order-theoretic theories of computability and some more common order-theoretic countability constraints, like order density properties and functional characterizations of the order structure in terms of multi-utilities. As a result, we show how computability can be introduced in some order structures via countability order density and multi-utility constraints.

In this paper, we introduce a new class of $T_0$ spaces called wb-sober spaces, which is strictly larger than the class of open well-filtered spaces. Unlike open well-filtered spaces, wb-sober spaces are defined more intuitively by requiring certain special subsets, termed wb-irreducible closed sets, to have singleton closures. We establish several key results about these spaces, including (1) every open well-filtered space is wb-sober, but not vice versa; (2) every strongly core-coherent wb-sober space is open well-filtered; (3) a space is core-compact iff its irreducible closed sets are wb-irreducible, providing a characterization of core-compactness; (4) every core-compact wb-sober space is sober, thereby generalizing the Jia-Jung problem. In addition, we investigate the core-coherence of the Xi-Zhao model. We prove that a $T_1$ space contains finite number of isolated points iff its Xi-Zhao model is core-coherent iff its Xi-Zhao model is strongly core-coherent. Based on this result, we then propose a general approach to constructing a non-routine open well-filtered but not well-filtered dcpo.