[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.
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
More information about the FOM
mailing list