Naming and Diagonalization, from Cantor to Godel to Kleene |
| |
Authors: | Gaifman Haim |
| |
Institution: | Philosophy Department, Columbia University, New York, NY 10027, USA. |
| |
Abstract: | We trace self-reference phenomena to the possibility of namingfunctions by names that belong to the domain over which thefunctions are defined. A naming system is a structure of theform (D, type( ),{ }), where D is a non-empty set; for everya D, which is a name of a k-ary function, {a}: Dk D is thefunction named by a, and type(a) is the type of a, which tellsus 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 underlyingGödel's proof, Kleene's recursion theorem and many othertheorems of this nature, including the solution to simultaneousfixed point equations. Partial functions are accommodated byincluding "undefined" values; we investigate different systemsarising out of different ways of dealing with them. Many-sortednaming systems are suggested as a natural approach to generalcomputatability with many data types over arbitrary structures.The first part of the paper is a historical reconstruction ofthe way Gödel probably derived his proof from Cantor'sdiagonalization, through the semantic version of Richard. Theincompleteness proofincluding the fixed point constructionresultfrom a natural line of thought, thereby dispelling the appearanceof a "magic trick". The analysis goes on to show how Kleene'srecursion theorem is obtained along the same lines. |
| |
Keywords: | Self-reference Gö del the incompleteness theorem fixed point theorem Cantor's diagonal proof Richard's paradox the liar paradox Kleene the recursion theorem simultaneous fixed points equations partial functions gap logic naming general computability |
本文献已被 Oxford 等数据库收录! |
|