If first-order logic counts as "elementary mathematics", then I would like to suggest (the relevant chapters of) "[Godel, Escher, Bach][1]", by Douglas Hofstadter.  (As an aside: Hofstadter's puzzle of encoding "n is a power of 10" as a predicate in Peano arithmetic is a wonderful one, quite tough even for professional mathematicians, especially if one is to avoid any form of the Godel numbering trick.)


  [1]: http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach