Nonstandard Models of Arithmetic

Compactness builds a model of arithmetic with an infinite number.

The idea

A nonstandard model of arithmetic is a structure that satisfies every first-order sentence true in the natural numbers, yet is not isomorphic to them. Such structures exist, and their existence measures what first-order logic cannot express.

Write $\mathfrak{N}$ for the standard structure $(\mathbb{N}; +, \cdot, <, 0, 1)$, and let $\text{Th}(\mathfrak{N})$ be the set of all first-order sentences true in $\mathfrak{N}$ — for every sentence, either it or its negation belongs. This is the most complete description first-order logic can give, and still it does not determine the structure.

Theorem (Existence of nonstandard models).

There is a structure $\mathfrak{M}$ satisfying every sentence of $\text{Th}(\mathfrak{N})$ and containing an element larger than every element named by a numeral $0, 1, 1+1, \ldots$ In particular, $\mathfrak{M}$ is not isomorphic to $\mathfrak{N}$.

In $\mathfrak{M}$ the standard numbers form an initial segment, and the nonstandard elements lie above all of them.

Every theorem of arithmetic still holds in $\mathfrak{M}$, because every true sentence does. What separates $\mathfrak{M}$ from $\mathfrak{N}$ is not a sentence but an element: sentences quantify over elements, and no sentence can assert that the numerals name all of them. Structures satisfying the same first-order sentences are elementarily equivalent, and elementary equivalence is strictly weaker than isomorphism.

Ways to work on it

• Walkthrough. Build a nonstandard model via compactness and read off its structure.
• Practice. Reason about the order structure of an infinite element.
• Hardest. Why first-order induction cannot exclude the nonstandard model.

Not sure where to start? Take the ten-question placement test.