I am reading Gödel-Escher-Bach and a good dialogue by Eliezer Yudkowsky and I think I might have understood the nature of the Completeness and Incompleteness theorems (at least regarding Peano Arithmetic).
The Completeness Theorem tells us that any semantic implication can be syntactically derived in First Order Logic. The Compactness Theorem tells us that the axiom scheme of induction has a model, because every subset of it has models.
I know on authority that there exists “non-standard” numbers in first order PA and that if there exists a single non-standard such there must exist an infinity of infinite “successor chains” of non-standard numbers; one chain for each Rational and each chain being trivially isomorphic to the integers.
I am not quite sure how to prove that first order PA cannot disprove the existence of one non-standard number.
Question 1: What is a proof that first order PA cannot rule out at least one non-standard number?
Now, the Incompleteness Theorem states that in first order PA there exists a number which encodes — by an arbitrary formula encoding scheme — which is neither provable nor disprovable in first order PA.
As I understand it, this number is necessarily a non-standard integer, and given that first order PA cannot rule out it's existence, first order PA is incomplete.
Question 2: Is this explanation fullfilling?
It is true, as far as it goes, that if every finite subset of PA has a model, then the complete PA has a model. However, that in itself is not a very interesting observation, because essentially the only way we have to know that every finite subset of PA has a model is to point to the particular model $(\mathbb N,{+},{\times})$, which is already a model of all of PA.
For your question 1, the standard way to show that PA has models with nonstandard integers (if it has models at all), is this: Extend PA with a new constant letter $c$, and an infinitude of new axioms $$ c\ne 0 \qquad c\ne S(0) \qquad c\ne S(S(0)) \qquad c \ne S(S(S(0))) \qquad \cdots $$ The extended theory satisfies the hypothesis of the compactness theorem -- every finite subset of its axioms has $\mathbb N$ as a model, because there can be only finitely many numbers its axioms say are not $c$. Therefore, the entire extended theory has a model, and because all of the axioms are true in the model, the interpretation of $c$ must be a nonstandard integer -- we're explicitly requiring that it is different from each of the standard ones.
For your question 2: No, that seems to be wrong. The Gödel number of the Gödel sencence is an ordinary standard number which we could compute with pencil and paper given sufficient time and determination. (This will be somewhat easier if we choose a more economical Gödel numering, but never mind that).
Because the Gödel sentence is undecidable, there must exist a model of PA in which this sentence has an encoded proof, and the Gödel number of that proof is necessarily a non-standard number.