Six Classical Theorems in -Recursion Categories

Let be a -recursion category, and let : × → be a weak Turing morphism in . We say that is idempotent if every morphism → in has an idempotent -index. We prove that every -recursion category contains an idempotent weak Turing morphism , together with an algebraic operation which sends -indices to idempotent -indices. Using this fact, we prove categorical analogs of classical theorems of recursion theory, such as Cantor's Diagonal Theorem, the Kleene fixed-point theorem, and the existence of a creative set. Using idempotent index morphisms subject to an additional algebraic constraint, we show there exists a domain with no complement, the formal analog of a recursively enumerable, non-recursive set. The proof is valid in a -recursion category with coproducts and ranges, but which may not have point-like morphisms (e.g., connected domains), such that there exists a -category with coproducts, ranges and appropriate point-like morphisms, together with a functor : → ; i.e., a functor which preserves coproducts, domains, ranges and zero-morphisms; it is crucial that need not preserve the near-product of C. We give conditions for the existence in a -category of a shift arrow in the sense of Germano and Mazzanti. Using idempotent indexes and connected domains, we produce a pair of recursively inseparable domains. Finally, we show that a -recursion category can express internally its own law of composition. The results hold in prodominical, but not necessarily dominical categories