Logica Universalis 4 (1):31-39 (2010)
We consider structures of the form, where Φ and Ψ are non-empty sets and is a relation whose domain is Ψ. In particular, by using a special kind of a diagonal argument, we prove that if Φ is a denumerable recursive set, Ψ is a denumerable r.e. set, and R is an r.e. relation, then there exists an infinite family of infinite recursive subsets of Φ which are not R -images of elements of Ψ. The proof is a very elementary one, without any reference even to e.g. the -theorem. Some consequences of the main result are also discussed
|Keywords||Diagonalization double frames incompleteness|
|Categories||categorize this paper)|
References found in this work BETA
Theory of Recursive Functions and Effective Computability.H. Rogers - 1987 - MIT Press.
Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers.Piergiorgio Odifreddi - 1989 - Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co..
Computability, an Introduction to Recursive Function Theory.Nigel Cutland - 1980 - Cambridge University Press.
Fundamentals of Mathematical Logic.Peter G. Hinman - 2007 - Bulletin of Symbolic Logic 13 (3):363-365.
Citations of this work BETA
No citations found.
Similar books and articles
From 1984 to One-Dimensional Man: Critical Reflections on Orwell and Marcuse.Douglas Kellner - unknown
Decidability, Partial Decidability and Sharpness Relation for L-Subsets.Giangiacomo Gerla - 1987 - Studia Logica 46 (3):227-238.
A Recursion Theoretic Analysis of the Clopen Ramsey Theorem.Peter Clote - 1984 - Journal of Symbolic Logic 49 (2):376-400.
Shifting Frames: From Divided to Distributed Psychologies of Scientific Agents.Peter J. Taylor - 1994 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1994:304-310.
Effective Versions of Ramsey's Theorem: Avoiding the Cone Above 0'.Tamara Lakins Hummel - 1994 - Journal of Symbolic Logic 59 (4):1301-1325.
Added to index2010-02-20
Total downloads18 ( #261,079 of 2,146,888 )
Recent downloads (6 months)1 ( #385,700 of 2,146,888 )
How can I increase my downloads?
There are no threads in this forum
Nothing in this forum yet.