file.pdf (1.52 MB)
Number Theory and Elementary Arithmetic
journal contributionposted on 2002-06-19, 00:00 authored by Jeremy Avigad
Elementary arithmetic (also known as "elementary function arithmetic") is a fragment of first-order arithmetic so weak that it cannot prove the totality of an iterated exponential function. Surprisingly, however, the theory turns out to be remarkably robust. I will discuss formal results that show that many theorems of number theory and combinatorics are derivable in elementary arithmetic, and try to place these results in a broader philosophical context.