Logic Journal of the IGPL 14 (5):709-728 (2006)

Haim Gaifman
Columbia University
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 (categorize this paper)
DOI 10.1093/jigpal/jzl006
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,379
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

On Ontology and Realism in Mathematics.Haim Gaifman - 2012 - Review of Symbolic Logic 5 (3):480-512.
Paradoxical Hypodoxes.Alexandre Billon - 2019 - Synthese 196 (12):5205-5229.
On the Diagonal Lemma of Gödel and Carnap.Saeed Salehi - 2020 - Bulletin of Symbolic Logic 26 (1):80-88.
A Brief Critique of Pure Hypercomputation.Paolo Cotogno - 2009 - Minds and Machines 19 (3):391-405.
Alonzo Church.Oliver Marshall & Harry Deutsch - 2021 - Stanford Encyclopedia of Philosophy.

View all 8 citations / Add more citations

Similar books and articles


Added to PP index

Total views
81 ( #144,828 of 2,519,659 )

Recent downloads (6 months)
1 ( #406,756 of 2,519,659 )

How can I increase my downloads?


My notes