Remarks on formalized arithmetic and subsystems thereof

Abstract

In a famous paper of 1931, Gödel proved that any formalization of elementary Arithmetic is incomplete, in the sense that it contains statements which are neither provable nor disprovable. Some two years before this, Presburger proved that a mutilated system of Arithmetic, employing only addition but not multiplication, is complete. This essay is partly an exposition of a system such as Presburger's, and partly an attempt to gain insight into the source of the incompleteness of Arithmetic, by linking Presburger's result with Gödel's.