1. Computability. The fact that there exists a reasonably robust theory of computability, and that this is intimately connected with the fact of the incompleteness of number theory (Goedel's Theorem, et al). It turns out that computability is even easier (in some respects) to present than arithmetic (at least if you know Lisp & EVAL).

I particularly like Barker's universal combinator \x.xSK where \ is lambda. -- Mike Stay staym@clear.net.nz http://www.cs.auckland.ac.nz/~msta039