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

Logic Journal of the IGPL 14 (5):709-728 (2006)
Authors
Haim Gaifman
Columbia University
Abstract
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
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


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

Paradoxical Hypodoxes.Alexandre Billon - forthcoming - Synthese 83.
A Brief Critique of Pure Hypercomputation.Paolo Cotogno - 2009 - Minds and Machines 19 (3):391-405.

Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total downloads
57 ( #107,499 of 2,263,077 )

Recent downloads (6 months)
2 ( #214,635 of 2,263,077 )

How can I increase my downloads?

Monthly downloads

My notes

Sign in to use this feature