[FOM] Exponentiation and Goedel's incompleteness theorems

[A.P. Hazen]

     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.
     References:
     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