Big List of Fun Math Books

To be on this list the book must satisfy the following conditions:

1. It doesn't require an enormous amount of background material to understand.
2. It must be a fun book, either in recreational math (or something close to) or in philosophy of math.

Here are my two contributions to the list:

1. What is Mathematics? Courant and Robbins.
2. Proofs that Really Count. Benjamin and Quinn.

Solution 1:

Gödel, Escher, Bach: An Eternal Golden Braid, by Douglas Hofstadter. Very interesting read - details Gödel's Incompleteness Theorem, and manages to touch on a wide variety of topics, including genetics, reductionism/holism, programming, art, music, brains, zen, language, etc. The central idea is that a special kind of self-reference (which Hofstadter calls a strange loop) seems to pop up everywhere, and is perhaps at the heart of intelligence and the appearance of meaning in a structure made up of meaningless parts.

Solution 2:

A whole lot of books by Raymond Smullyan, but To Mock a Mockingbird, which presents combinatory logic is definitely on the list, as is one of the several books in which he presents Gödel's first incompleteness theorem as a knights-and-knaves puzzle.