Naming and Diagonalization, from Cantor to Gödel to Kleene

Logic Journal of the IGPL 14 (5):709-728 (2006)
We trace self-reference phenomena to the possibility of naming functions by names that belong to the domain over which the functions are defined. A naming system is a structure of the form ,{ }), where D is a non-empty set; for every a∈ D, which is a name of a k-ary function, {a}: Dk → D is the function named by a, and type is the type of a, which tells us if a is a name and, if it is, the arity of the named function. Under quite general conditions we get a fixed point theorem, whose special cases include the fixed point theorem underlying Gödel's proof, Kleene's recursion theorem and many other theorems of this nature, including the solution to simultaneous fixed point equations. Partial functions are accommodated by including “undefined” values; we investigate different systems arising out of different ways of dealing with them. Many-sorted naming systems are suggested as a natural approach to general computatability with many data types over arbitrary structures. The first part of the paper is a historical reconstruction of the way Gödel probably derived his proof from Cantor's diagonalization, through the semantic version of Richard. The incompleteness proof–including the fixed point construction–result from a natural line of thought, thereby dispelling the appearance of a “magic trick”. The analysis goes on to show how Kleene's recursion theorem is obtained along the same lines
Keywords No keywords specified (fix it)
Categories No categories specified
(categorize this paper)
DOI 10.1093/jigpal/jzl006
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 23,674
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

48 ( #100,257 of 1,903,042 )

Recent downloads (6 months)

6 ( #144,817 of 1,903,042 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.