Carl's answer is correct. 

There is also a more direct way to achieve the same thing. The Tennenbaum's theorem holds for much weaker theories, e.g. $I\Delta_0$ (even far weaker theories $IOpen$ plus some number theoretic principles). $I\Delta_0+Exp$ is finitely axiomatization due to a result by Haim Gaifman and Constantine Dimitracopoulos in their paper "Fragments of Peano's Arithmetic and the MRDP Theorem" and it is also a sub-theory of $PA$.

###Edit

Take a look at [this](http://arxiv.org/abs/1003.2117) paper for what is known about the weak theories and Tennenbaum's theorem: <br/>
Shahram Mohsenipour, "Hierarchies of Subsystems of Weak Arithmetic", <br/>
to appear in Set theory, Arithmetic, Philosophy: Essays in Memory of Stanley Tennenbaum (edited by J. Kennedy and R. Kossak), Cambridge University Press.