[FOM] Exponentiation and Goedel's incompleteness theorems

A.P. Hazen a.hazen at philosophy.unimelb.edu.au
Sat Apr 3 05:23:13 EST 2004

     Gödel's coding of syntax used a Beta function that requires 
exponentiation, but this isn't inevitable.  The very simple coding 
based on conventional systems of numerals (choose a base for the 
numeral system which is prime  and larger than the number of 
primitive symbols in the object language, identify each symbol with a 
digit other than Zero, and take as code for a syntactic object the 
number the syntactic object itself denotes) does not require the 
assumption that exponentiation  is a total function; this coding is 
available for use in treating weak systems of arithmetic in which 
exponentiation is not provably total.
     Raymond Smullyan, "Gödel's Incompleteness Theorems" (Oxford 
1992), for an elementary presentation of this coding scheme.
     Edward Nelson, "Predicative Arithmetic" (Princeton 1986), for a 
detailed development of the syntax of arithmetic via this coding, 
working (with extreme formal precision) in a system in which 
exponentiation is not provably total.
     Samuel Buss, "Bounded Arithmetic" (Naples: Bibliopolis, 1986) for 
proofs of Gödel incompleteness theorems for systems havingmodels in 
whichexponentiation is not total.
Allen Hazen
Philosophy Department
University of Melbourne

More information about the FOM mailing list