More existence theorems for recursion categories

Annals of Pure and Applied Logic 125 (1-3):1-41 (2004)
  Copy   BIBTEX


We prove a generalization of Alex Heller's existence theorem for recursion categories; this generalization was suggested by work of Di Paola and Montagna on syntactic P-recursion categories arising from consistent extensions of Peano Arithmetic, and by the examples of recursion categories of coalgebras. Let B=BX be a uniformly generated isotypical B#-subcategory of an iteration category C, where X is an isotypical object of C. We give calculations for the existence of a weak Turing morphism in the Turing completion Tur of B when C is separated; i.e., when connected domains in C are jointly epimorphic. Our proof generalizes as follows. Let D be a separated iteration category and let L : C → D be an iteration functor; i.e., a functor which preserves domains, coproducts, zero morphisms and the iteration operator; it is crucial for the generalization that an iteration functor need not preserve products. If L is faithful, then Tur is a recursion category



    Upload a copy of this work     Papers currently archived: 74,213

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Weak Cardinality Theorems.Till Tantau - 2005 - Journal of Symbolic Logic 70 (3):861 - 878.
An Existence Theorem for Recursion Categories.Alex Heller - 1990 - Journal of Symbolic Logic 55 (3):1252-1268.
Recursion Theory for Metamathematics.Raymond Merrill Smullyan - 1993 - Oxford, England: Oxford University Press.
Coherence in Substructural Categories.Zoran Petrić - 2002 - Studia Logica 70 (2):271 - 296.
Recursion Theorems and Effective Domains.Akira Kanda - 1988 - Annals of Pure and Applied Logic 38 (3):289-300.
Axiomatizing a Category of Categories.Colin McLarty - 1991 - Journal of Symbolic Logic 56 (4):1243-1260.
Splitting Theorems in Recursion Theory.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 65 (1):1-106.
Categories and Levels of Reality.Jorge J. E. Gracia - 2009 - Axiomathes 19 (2):179-191.
A Relativization Mechanism in Recursion Categories.Stefano Stefani - 1993 - Journal of Symbolic Logic 58 (4):1251-1267.


Added to PP

6 (#1,095,876)

6 months
1 (#414,449)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Florian Lengyel
City University of New York

Citations of this work

Introduction to Turing Categories.J. Robin B. Cockett & Pieter Jw Hofstra - 2008 - Annals of Pure and Applied Logic 156 (2):183-209.

Add more citations