1) Smith's Introduction to Godel's Theorems http://www.logicmatters.net/igt/ is a great book, with all the mathematics but willing to go into the philosophy.
2) Franzen's Gödel's Theorem: An Incomplete Guide to Its Use and Abuse http://www.ams.org/notices/200703/rev-raatikainen.pdf is enlightening in a different way.
I'll also mention a favorite author around here http://www.scottaaronson.com/blog/?p=710 .
One goal was to come up with a collection of axioms for the Natural numbers (capital letter to denote the Natural numbers we all know and love). What was wanted was a collection of axioms that are recursively enumerable. Think computable. The goal was to find a mechanistic process to check theorems and to prove new theorems. In some sense too alleviate the field from human error. In modern language we'd say to find a way to have a computer check/discover theorems in number theory.
There are two axiom systems for the Natural numbers. Both are Peano axioms and one system is first order and recursively enumerable. The other system is second order and not recursively enumerable. There are infinitely many models of the first order Peano axioms. For each such model we call them natural numbers (lower case) to signify they are a model of the first order axioms.
The Incompleteness Theorem: There are statements that are true in the Natural numbers (upper case!) that are not true in all models of the natural numbers. Furthermore, this will always be the case no matter what system of recursively enumerable axioms you have for describing the Natural numbers.
Consequence: The Natural numbers can not fully be described by a nice set of axioms. Whatever recursively enumerable system of axioms you have to describe the Natural numbers will be insufficient to prove all true statements of the Natural numbers. Hence, such systems of axioms are incomplete.
One can always find a complete system of axioms by taking as the collection of axioms the collection of all true statements. This isn't helpful because there would no effective way to determining whether or not a statement is an axiom just by looking at it or comparing it to a finite set of axiom schema. Such a collection of axioms is wholly impractical and not useful. But it is wrong to say that a complete axiom system can not be found.
Some people falsely claim that the Incompleteness theorem says that there are statements of the Natural numbers that are neither provable or disprovable. What the theorem says is that for a given recursively enumerable set of axioms that the Natural numbers are a model of there will be statements of the Natural numbers that are true but not provable in that system. All true statements of the Natural numbers are provable in the second order system of axioms but the things get dicey from a logic point of view when working with the second order Peano axioms.
"But Z2 is usually studied with first-order semantics, and in that context it is an effective theory of arithmetic subject to the incompleteness theorems. In particular, Z2 includes every axiom of PA, and it does include the second-order induction axiom, and it is still incomplete.
"Therefore, the well-known categoricity proof must not rely solely on the second-order induction axiom. It also relies on a change to an entirely different semantics, apart from the choice of axioms. It is only in the context of these special 'full' semantics that PA with the second-order induction axiom becomes categorical."
From: https://math.stackexchange.com/questions/617124/peano-arithm...
"So, even though Z2 with full second-order semantics is categorical, for any sound effective deductive system there are still true formulas of Z2 that are neither provable nor disprovable in that system."
The key is sound and effective deductive system. Think computable or mechanistic process for deduction. The second order Peano axioms with second order semantics are not and effective deduction system.
In all proofs you have to start with (or end up with depending on the direction your proofs go) axioms. In the second order Peano axioms with second order semantics you can end up in a situation where you don't know if a given statement is an axiom! Making that determination can be quite hard.
When you say "small agreed upon set" you are in essence talking about a recursively enumerable set of axioms. A collection of axioms that is "small" enough so that one could easily determine if a statement is an axiom.
If you have time for another question, I'm still confused about how it applies to second-order arithmetic, though, since the Peano axioms are well-known and easily listed on a single piece of paper. What difficulty is there be in determining whether a statement is a second-order Peano axiom?
It seems particularly strange since there are apparently fewer axioms than in first-order Peano arithmetic (by replacing an axiom schema with a single induction axiom).
[1] https://math.stackexchange.com/questions/106635/why-does-the...
"A bit more precisely, the Incompleteness Theorem shows that human beings can never formulate a correct and complete description of the set of natural numbers, {0, 1, 2, 3, . . .}."
The second order Peano Axioms are categorical and thus, up to isomorphism, the only model for this axiom system are the Natural numbers {0, 1, 2, 3, ...}. This is a complete system. We can't happen is a recursively enumerable axiomatic description of the Natural numbers that is complete.
Another way to get a complete description of the Natural numbers is to take the collection of all true statements of the Natural numbers and make that our axiomatic system. It's just not a useful axiomatic system but it is a complete description of the Natural numbers.