Gödel's result about induction

Question

In Artificial Intelligence: A Modern Approach there is a brief review of the history of logic, with a mention to Gödel's work.

It says:

1. In 1930, Kurt Gödel showed that there exists an effective procedure to prove any true statement in the first-order logic of Frege and Russell,
2. but that first-order logic could not capture the principle if mathematical induction needed to characterize the natural numbers.
3. In 1931, [...] his Incompleteness Theorem showed that limits on deduction do exist.

In 1. the authors reference Gödel's Completeness Theorem for first order logic, but what is the result they are alluding to in 2.?

Certainly not Incompleteness, since that is mentioned in 3 as a posterior result. What am I missing?

Answer 1

See Kurt Gödel (1934c), Review of Skolem, On the impossibility of a complete characterization of the number sequence by means of a finite axiom system (1933); reprinted into Kurt Gödel, Collected Works, Vol.I (1986), page 379:

The author [Skolem] proves that there is a system $N^*$ of entities, with two operations, $+$ and $-$, defined on it and with two relations, $>$ and $=$, that is not isomorphic to the system $N$ of natural numbers, but for which nevertheless all statements hold that are expressible by means of the symbols mentioned at the outset and hold for the system $N$. From this it follows that there is no axiom system [which presumably means no recursive (or possibly primitive recursive) set of axioms; from the introductory Note by Robert Vaught] employing only the notions mentioned at the outset (and therefore none at all employing only number-theoretic notions) that uniquely determines the structure of the sequence of natural numbers, a result that also follows without difficulty from the investigations of the reviewer [Kurt Gödel himself] in his 1931 [Über formal unentscheidbare Sätze der Principia mathematica und verwandter Systeme I].

From the Introductory note:

Gödel remarks that this consequence of [Skolem's result (1): "there exists a structure $\mathfrak N^*$ not isomorphic to $\mathfrak N$ which has the same true (first-order) sentences as $\mathfrak N$"] follows from his 1931 incompleteness theorem. Indeed, if $\Sigma$ is any, say, recursive, set of sentences true in $\mathfrak N$, the incompleteness theorem tells us there is even a model $\mathfrak N'$ of $\Sigma$ in which some sentence true in $\mathfrak N$ is false. (As Kleene [Introduction to metamathematics, 1952, page 430] notes, this argument in fact also uses Gödel's completeness theorem from 1930.)

However, the main result of Skolem's paper (as Skolem and Gödel both say) is certainly (1), that the set of all true sentences in $\mathfrak N$ does not characterize $\mathfrak N$. And the strange fact is that nowadays (1) is proved in a few lines by a "compactness argument", that is, from Gödel's compactness theorem (1930). [...]

Thus it seems extraordinary that Skolem and especially Gödel himself did not observe that (1) is a simple consequence of the compactness theorem. Nevertheless, it appears that the idea of such simple (but important) applications of the compactness theorem was probably unknown before 1936 — in particular to Gödel and Skolem, and also to Tarski. [...] It appears that A.Maltsev, in 1936 and 1941, was the first person to publish such applications to algebra via "compactness arguments". [...] By 1941, Maltsev was making some quite sophisticated compactness arguments. But it was only after the Second World War that other logicians began to exploit the compactness theorem.

__

In conclusion, result 2. can be credited to Gödel (1931) with insight.

Answer 2

One result they might be referring to is the Compactness Theorem of FOL, since it implies that every first order theory of arithmetic has models which are not isomorphic to True Arithmetic.

The timelines coincide indeed, as Wikipedia says that Gödel first proved the result for countable theories in 1930.