Non-Standard Models of Arithmetic

Consider the ordinary natural numbers $\displaystyle 0,1,2,3,4,\ldots$ There is something reassuringly concrete about this sequence. Unlike the real numbers, whose elements may have infinitely complicated decimal expansions, every individual natural number can be written down using a finite string of digits. We can add and multiply natural numbers, compare them, divide them with remainders, and carry out finite calculations with them. Even if the numbers become extraordinarily large, nothing conceptually new seems to happen. We are simply repeating familiar operations more and more times. For this reason, one might expect the natural numbers to be among the easiest mathematical structures to characterize uniquely. Surely, if we describe zero, successor, addition, multiplication, and mathematical induction, there should be only one possible structure satisfying those rules: the natural numbers we already know.

Surprisingly, this is false. There are mathematical structures satisfying every first-order axiom of Peano Arithmetic that contain elements larger than every ordinary natural number. Such elements are called nonstandard natural numbers. They are not merely enormous finite integers. A nonstandard number $\displaystyle H$ can satisfy

$\displaystyle H>0,\quad H>1,\quad H>2,\quad\ldots$

simultaneously, where the numbers on the right are all the ordinary natural numbers. At first this seems contradictory. How can something be a natural number, obey all the familiar laws of arithmetic, and yet be larger than every natural number? The resolution is that we must distinguish the ordinary natural numbers from an arbitrary model of the axioms describing natural numbers. A model is a mathematical structure in which the axioms hold, but it may contain objects that the axioms do not distinguish from the intended ones.

Our goal is to understand this distinction concretely. We will actually construct several different arithmetic structures, beginning with a simple model made from polynomials and then building a much stronger model from sequences of natural numbers. We will see why ultrafilters arise naturally, why compactness makes such constructions possible, and why the resulting models satisfy induction despite containing infinitely large numbers. We will also discover that not all nonstandard models are alike. Some satisfy every first-order arithmetic statement true in the ordinary natural numbers. Others satisfy the axioms of Peano Arithmetic but disagree with ordinary arithmetic about particular statements, including statements asserting the existence of proofs or the termination of integer sequences. This distinction is closely related to Gödel’s incompleteness theorems.

Peano’s Axioms

Before constructing unusual models, we should be precise about what we are trying to preserve. We usually work with a mathematical structure $\displaystyle (\mathbb N,0,S,+,\times),$ where $\displaystyle S(n)=n+1$ is the successor operation. There are several natural rules that these operations satisfy. For instance, zero is not the successor of any number, and the successor operation is injective:

$\displaystyle S(x)\ne0,\qquad S(x)=S(y)\Longrightarrow x=y.$

Every nonzero number has a predecessor: $\displaystyle x=0\quad\text{or}\quad \exists y,(x=S(y)).$ Addition is characterized by the recursive equations

$\displaystyle x+0=x,\qquad x+S(y)=S(x+y),$

and multiplication by

$\displaystyle x\times0=0,\qquad x\times S(y)=x\times y+x.$

These equations describe how arithmetic behaves under the successor operation. They are elementary, and we can verify them directly in the usual natural numbers. But do they completely determine the natural numbers? Certainly not. They do not even imply many familiar elementary properties. For instance, we want to prove that every natural number is even or odd: $\displaystyle \forall x\ \exists y,(x=2y\ \lor\ x=2y+1).$ How would we ordinarily prove this? We begin with zero, which is even. Then we observe that the successor of an even number is odd, while the successor of an odd number is even. Mathematical induction allows us to conclude that every natural number is either even or odd.

Thus induction is doing something important that the recursive equations alone do not accomplish. Peano Arithmetic, abbreviated PA, adds a general induction principle.

Given a formula $\displaystyle P(x)$ expressing some arithmetic property, we have the axiom

$\displaystyle \big(P(0)\land\forall x(P(x)\Rightarrow P(S(x)))\big)\Rightarrow\forall x P(x).$

There is one such axiom for every first-order formula in the language of arithmetic, with parameters allowed. The phrase first-order matters. We may quantify over natural numbers, but not directly over arbitrary subsets of the natural numbers. For example, the formula

$\displaystyle \exists y (x=2y\lor x=2y+1)$

is a legitimate property for induction. So is a much more complicated formula involving many quantifiers, additions, and multiplications. But the expression “the set of all ordinary natural numbers” is not itself a first-order arithmetic formula inside a nonstandard model. We will eventually see that this is exactly what permits nonstandard numbers to exist.

Non-Standard Models

For now, let us try constructing a model using much more elementary mathematics. Suppose we want to introduce a new number $\displaystyle H$ that is larger than every ordinary natural number. One possible approach is simply to treat $\displaystyle H$ as an indeterminate. We could consider expressions such as

$\displaystyle H,\quad H+1,\quad 2H+3,\quad H^2,\quad H^3+5H+7.$

These look like ordinary polynomials, except that we want to compare them as if $\displaystyle H$ were an infinitely large positive integer. This suggests considering the polynomial ring $\displaystyle \mathbb Z[X]$ . For any nonzero polynomial $\displaystyle f(X)$ , the sign of $\displaystyle f(n)$ is eventually constant as $\displaystyle n\to\infty$ , because the leading term eventually dominates all the lower-degree terms. We can therefore define

$\displaystyle f<g\quad\Longleftrightarrow\quad f(n)<g(n)\text{ for all sufficiently large }n.$

Let $\displaystyle M_{\mathrm{poly}}$ consist of zero together with all integer polynomials that are eventually positive. Addition and multiplication are the usual polynomial operations. This gives a structure in which

$\displaystyle 0<1<2<\cdots<X<X+1<X+2<\cdots<X^2<\cdots.$

The element $\displaystyle X$ is larger than every ordinary natural number. Its square is larger still, and we can perform perfectly familiar algebraic calculations with these new elements. In fact, this structure satisfies the basic axioms of a weak arithmetic theory called Robinson Arithmetic, or $\displaystyle Q$ . To see why, notice that all the recursive equations for addition and multiplication are simply polynomial identities. Also, every nonzero element of $\displaystyle M_{\mathrm{poly}}$ has a predecessor: if $\displaystyle f(X)$ is eventually positive, then $\displaystyle f(X)-1$ is eventually nonnegative, and hence belongs to the structure.

So we already have a very concrete nonstandard arithmetic model. But is it a model of Peano Arithmetic? No. And the reason is instructive.

Consider the element $\displaystyle X$ . Is it even or odd? If it were even, we would have $\displaystyle X=2f(X)$ for some integer polynomial $\displaystyle f(X)$ . This is impossible because the coefficient of $\displaystyle X$ on the right must be even, whereas on the left it is one. Likewise, we cannot have $\displaystyle X=2f(X)+1.$ Thus $\displaystyle X$ is neither even nor odd in this structure. But we already know that PA proves every number is even or odd, by induction.

Therefore our polynomial model satisfies the elementary recursive rules of arithmetic, but not full induction. This is useful progress. We have learned that constructing infinitely large algebraic elements is easy. The difficulty is making them satisfy all the arithmetic properties that induction proves.

We need a better construction.

Compactness

Before introducing the next model, let us understand an important logical principle that will guide its construction. Suppose we want to choose an infinite binary sequence $\displaystyle x=(x_0,x_1,x_2,\ldots)$ subject to infinitely many requirements. For example, perhaps certain digits must agree, certain finite patterns are forbidden, and certain other finite patterns must occur. Assume that every finite collection of these requirements can be satisfied simultaneously.

Does there exist one infinite binary sequence satisfying all of them? When each requirement concerns only finitely many coordinates, the answer is yes. The reason is closely connected with infinite trees. Consider the full binary tree whose nodes are finite strings of zeros and ones. The first few levels contain $\displaystyle \varnothing,\qquad 0,1,\qquad 00,01,10,11,\qquad\ldots$ An infinite path through this tree determines an infinite binary sequence. Now retain only those finite strings that can occur as initial segments of assignments compatible with the requirements. Since every finite collection of requirements is satisfiable, we can find admissible strings of arbitrarily large length. More precisely, we may organize the construction so that a string at level $\displaystyle n$ is the prefix of an assignment satisfying the first $\displaystyle n$ requirements. The retained strings form an infinite tree with at most two children at each node.

Here we use König’s lemma: every infinite finitely branching tree has an infinite branch. Why is König’s lemma true? At the root, at least one child must have infinitely many descendants, since otherwise the entire tree would be finite. Choose such a child and repeat. At every stage, we preserve a subtree with infinitely many descendants, producing an infinite path. This path satisfies every requirement. Any particular finite-coordinate requirement is eventually included among those enforced, and the later approximations never contradict the earlier decisions. The underlying principle is that finite compatibility, together with the appropriate compactness, produces a global infinite solution.

There is a corresponding theorem for first-order logic:

Compactness theorem. If every finite subset of a collection of first-order sentences has a model, then the entire collection has a model.

The full proof involves more than the binary-tree argument, because a first-order sentence can assert that some object exists. We must ensure that suitable witnesses are introduced. The standard Henkin construction accomplishes this by adding names for witnesses and assembling a complete consistent collection of sentences. There is also a short logical way to understand why compactness should hold. By Gödel’s completeness theorem, if a theory has no model, then a contradiction can be formally proved from its axioms. But a formal proof is finite and therefore uses only finitely many axioms. Hence if every finite collection of axioms is satisfiable, the full collection cannot yield a contradiction. The tree construction gives the geometric intuition; the completeness theorem gives the general logical justification. Now let us apply this to arithmetic.

Take all the axioms of PA and introduce one new constant symbol $\displaystyle c$ . We want to impose the infinitely many requirements

$\displaystyle c>0,\qquad c>1,\qquad c>2,\qquad\ldots$

Every finite collection of these requirements can be satisfied in the ordinary natural numbers. If the largest numeral mentioned is $\displaystyle N$ , simply interpret $\displaystyle c$ as $\displaystyle N+1$ . Thus every finite subset of

$\displaystyle PA+{c>n=0,1,2,\ldots}$

has a model. By compactness, there exists a model $\displaystyle M$ satisfying all these statements at once. Consequently,

$\displaystyle M\models c>n\qquad\text{for every ordinary numeral }n.$

So $\displaystyle M$ contains an infinitely large integer while satisfying every axiom of PA. This is already a remarkable construction, but compactness has not told us much about what the elements of $\displaystyle M$ look like or how arithmetic is actually performed inside it.

For that, we turn to sequences. Consider the set of all sequences of natural numbers,

$\displaystyle \mathbb N^{\mathbb N}={(a_0,a_1,a_2,\ldots)\in\mathbb N}.$

We can add and multiply them coordinatewise:

$\displaystyle (a_n)+(b_n)=(a_n+b_n),\qquad (a_n)(b_n)=(a_nb_n).$

We represent an ordinary natural number $\displaystyle k$ by the constant sequence

$\displaystyle \overline{k}=(k,k,k,\ldots).$

Now consider the increasing sequence $\displaystyle h=(0,1,2,3,4,\ldots).$ This is a very natural candidate for an infinitely large integer. For every fixed $\displaystyle k$ , we have

$\displaystyle h_n>k\qquad\text{for all sufficiently large }n.$

If we could treat the sequence $\displaystyle h$ as a single mathematical number, it would have precisely the property we want. The difficulty is determining when two sequences should represent the same number. One tempting choice is to declare two sequences equivalent when they eventually agree:

$\displaystyle (a_n)\sim(b_n)\quad\Longleftrightarrow\quad a_n=b_n\text{ for all sufficiently large }n.$

But this leads to problems. Take the alternating sequence $\displaystyle a=(0,1,0,1,0,1,\ldots).$ It does not eventually agree with the constant zero sequence or with the constant one sequence. Thus its equivalence class is neither zero nor one. Yet coordinatewise, $\displaystyle a_n^2=a_n$ for every $\displaystyle n$ . Therefore, in the quotient, this element satisfies $\displaystyle a^2=a$ without being zero or one. That is impossible in the ordinary natural numbers, and PA proves it is impossible.

So eventual equality is too weak. We need a notion of agreement that makes a definite decision about the alternating sequence and, more generally, about every possible partition of the coordinates into finitely many cases. That is exactly what an ultrafilter supplies.

Ultrafilter

Suppose we wish to regard some subsets of $\displaystyle \mathbb N$ as large. The familiar example is the collection of cofinite sets: those sets whose complements are finite. This is a reasonable notion of largeness. If a property holds for all sufficiently large integers, the set of indices where it holds is cofinite. But it does not make decisions about every subset. For example, neither the even integers nor the odd integers form a cofinite set. If we want arithmetic statements about sequences to have definite truth values, we need a stronger notion of largeness.

An ultrafilter $\displaystyle U$ on $\displaystyle \mathbb N$ is a collection of subsets regarded as large, satisfying the following properties:

The empty set is not large, but $\displaystyle \mathbb N$ is large.
If a set is large, then every set containing it is large.
The intersection of two large sets is large.
For every subset $\displaystyle A\subseteq\mathbb N$ , exactly one of $\displaystyle A$ and its complement is large.

The fourth property is decisive. An ultrafilter makes a consistent yes-or-no decision about every subset. For instance, exactly one of the even and odd integers belongs to $\displaystyle U$ . An ultrafilter is called nonprincipal if it contains no finite set. Every nonprincipal ultrafilter contains all cofinite sets. This means that eventual truth is always regarded as truth on a large set, but the ultrafilter also makes additional decisions about sets that are neither finite nor cofinite.

There is no elementary formula that simply lists which subsets belong to a nonprincipal ultrafilter. In fact, obtaining one requires a nonconstructive existence principle. But compactness gives a beautiful explanation. For every subset $\displaystyle A\subseteq\mathbb N$ , introduce a propositional variable $\displaystyle P_A$ , meaning that $\displaystyle A$ is large. We want our truth assignments to satisfy

$\displaystyle P_{\mathbb N},\qquad \neg P_\varnothing,$

together with the rules $\displaystyle P_{A\cap B}\leftrightarrow(P_A\land P_B),\qquad P_{\mathbb N\setminus A}\leftrightarrow\neg P_A,$ and $\displaystyle P_C$ for every cofinite set $\displaystyle C$ .

Every finite collection of these requirements can be satisfied. Indeed, choose a natural number $\displaystyle m$ belonging to all the finitely many cofinite sets mentioned, and temporarily declare

$\displaystyle P_A\text{ true}\quad\Longleftrightarrow\quad m\in A.$

This satisfies the relevant Boolean rules and cofinite requirements.

The general propositional compactness theorem therefore gives a truth assignment satisfying all the requirements simultaneously. The subsets declared large form a nonprincipal ultrafilter. Equivalently, one can start with the filter of cofinite sets and use Zorn’s lemma to extend it to a maximal proper filter, which is an ultrafilter. The existence of $\displaystyle U$ is nonconstructive. But once an ultrafilter is chosen, our new arithmetic model has an explicit mathematical definition.

Construction

Fix a nonprincipal ultrafilter $\displaystyle U$ . Given two sequences $\displaystyle a=(a_n)$ and $\displaystyle b=(b_n)$ , define

$\displaystyle a\sim_U b\quad\Longleftrightarrow\quad{n=b_n}\in U.$

In words, two sequences represent the same number if they agree on an ultrafilter-large set of coordinates. Write $\displaystyle [a]$ for the equivalence class of $\displaystyle a$ . Our new structure is

$\displaystyle {}^*\mathbb N=\mathbb N^{\mathbb N}/U.$

Its elements are equivalence classes of sequences. We define addition and multiplication by

$\displaystyle [a]+[b]=[(a_n+b_n)],\qquad [a][b]=[(a_nb_n)].$

And we define the order by

$\displaystyle [a]<[b]\quad\Longleftrightarrow\quad{n<b_n}\in U.$

These operations are well-defined. If we replace one sequence by an equivalent sequence, any arithmetic equality that held on a large set still holds on the intersection of finitely many large sets, which is large. The ultrafilter also ensures that the order is total. For any two sequences, the coordinates split into three disjoint sets where $\displaystyle a_n<b_n$ , $\displaystyle a_n=b_n$ , or $\displaystyle a_n>b_n$ . Exactly one of these three sets belongs to $\displaystyle U$ .

This eliminates the ambiguity we encountered with eventual equality. For example, the alternating sequence $\displaystyle a=(0,1,0,1,\ldots)$ is now equivalent either to zero or to one. If the even indices belong to $\displaystyle U$ , its equivalence class is zero; otherwise, its class is one. There is no third possibility.

Consider $\displaystyle H=[(0,1,2,3,\ldots)].$ For every ordinary natural number $\displaystyle k$ , the set $\displaystyle {n>k}$ is cofinite and therefore belongs to $\displaystyle U$ . Consequently,

$\displaystyle H>k\qquad\text{for every ordinary }k.$

This time, we have a precise mathematical object representing an infinitely large integer.

It is the equivalence class of the sequence $\displaystyle (0,1,2,3,\ldots)$ . We can calculate with it:

$\displaystyle H+1=[(1,2,3,4,\ldots)],\qquad 2H=[(0,2,4,6,\ldots)],$

and

$\displaystyle H^2=[(0,1,4,9,16,\ldots)].$

Notice that $\displaystyle H^2>H$ , and indeed $\displaystyle H^2>kH$ for every fixed ordinary positive integer $\displaystyle k$ .

So we have a rich collection of different infinite magnitudes, not just one additional number. But all these magnitudes are still elements of an arithmetic structure in which addition and multiplication work just as expected.

Let us explore this model through examples before proving its general properties. Consider the sequence

$\displaystyle K=[(1!,2!,3!,4!,\ldots)].$

For every fixed positive integer $\displaystyle m$ , we know that

$\displaystyle m\mid n!\qquad\text{whenever }n\ge m.$

Thus the set of indices where $\displaystyle m\mid n!$ is cofinite, and hence large. Therefore

$\displaystyle m\mid K\qquad\text{for every ordinary positive integer }m.$

We have constructed a positive integer divisible by every ordinary positive integer. It may help to see exactly what divisibility means here. The statement $\displaystyle m\mid K$ means that there is an element $\displaystyle L$ in our ultrapower satisfying

$\displaystyle K=mL.$

We obtain $\displaystyle L$ by representing it with a sequence that, for sufficiently large $\displaystyle n$ , equals $\displaystyle n!/m$ . There is no contradiction with ordinary arithmetic. This is not an ordinary natural number, and it is not divisible by every nonstandard positive integer. For example, $\displaystyle K+1$ does not divide $\displaystyle K$ .

Let $\displaystyle p_n$ denote the $\displaystyle n$ th prime. Form $\displaystyle P=[(p_1,p_2,p_3,\ldots)].$ Because the primes grow without bound, $\displaystyle P$ is larger than every ordinary natural number. Moreover, $\displaystyle P$ is prime in the ultrapower. Indeed, the first-order statement expressing primality holds for $\displaystyle p_n$ at every coordinate, so it holds for the corresponding equivalence class. Thus the ultrapower contains infinitely large primes.

Return to $\displaystyle H=[(0,1,2,3,\ldots)].$ The underlying sequence alternates between even and odd values. But the ultrafilter chooses exactly one of the sets of even and odd indices as large. If the even indices belong to $\displaystyle U$ , then $\displaystyle H$ is even. Otherwise it is odd.

More explicitly, consider $\displaystyle L=[(\lfloor n/2\rfloor)_{n<\omega}].$ Then either $\displaystyle H=2L$ or $\displaystyle H=2L+1,$ depending on the choice made by the ultrafilter. So every element is still even or odd, including infinitely large elements.

This already suggests that the ultrapower behaves much more like ordinary arithmetic than our earlier polynomial model. We have defined addition, multiplication, and order. But we have not yet justified the most important claim: that this structure satisfies all of PA, including every instance of induction. The key result is Łoś’s theorem.

Suppose $\displaystyle \varphi(x_1,\ldots,x_k)$ is any first-order formula in the language of arithmetic, and suppose $\displaystyle a_1,\ldots,a_k$ are sequences representing elements of the ultrapower. Łoś’s theorem states that

$\displaystyle {}^*\mathbb N\models\varphi([a_1],\ldots,[a_k])$

if and only if

$\displaystyle {n:\mathbb N\models\varphi(a_1(n),\ldots,a_k(n))}\in U.$

In other words, a first-order statement is true in the ultrapower exactly when it is true on an ultrafilter-large set of coordinates. Why is this plausible? For an equation, it is simply our definition of equality. For an inequality, it is our definition of order. If a formula is a conjunction $\displaystyle \varphi\land\psi$ , it is true exactly when both component formulas are true. The corresponding sets of coordinates must both be large, and their intersection is large. If a formula is a negation $\displaystyle \neg\varphi$ , we use the fact that exactly one of a set and its complement belongs to the ultrafilter.

The most interesting case is existential quantification. Suppose $\displaystyle {}^*\mathbb N\models\exists y,\varphi(y,[a]).$ Then some equivalence class $\displaystyle [b]$ witnesses the statement, and the formula $\displaystyle \varphi(b_n,a_n)$ is true on a large set of coordinates. Conversely, suppose there is a large set of coordinates where $\displaystyle \mathbb N\models\exists y,\varphi(y,a_n).$ At each such coordinate, choose the least natural number $\displaystyle b_n$ satisfying the formula. At the remaining coordinates, set $\displaystyle b_n=0$ . The sequence $\displaystyle (b_n)$ then represents a witness in the ultrapower.

By induction on the construction of formulas, all first-order formulas satisfy this correspondence. Now every axiom of PA holds in the standard natural numbers. Therefore it holds at every coordinate and hence in the ultrapower.

Indeed, something stronger is true: $\displaystyle {}^*\mathbb N\equiv\mathbb N.$ This notation means that the two structures satisfy exactly the same first-order arithmetic sentences. Our nonstandard structure is not merely a model of PA. It is an elementary extension of the standard natural numbers. This is an important distinction. The new structure contains infinitely large integers, but no first-order sentence without additional parameters can distinguish its arithmetic theory from that of $\displaystyle \mathbb N$ .

We should now confront the apparent contradiction. Surely induction says that every number can be reached from zero by repeatedly applying successor. And yet our number $\displaystyle H$ is larger than $\displaystyle 0,1,2,3,\ldots$ and cannot be reached by any ordinary finite number of successor operations. Why doesn’t induction rule it out?

The answer depends on understanding exactly what first-order induction says. It says that if an arithmetically definable property holds at zero and is preserved by successor, then it holds for all elements of the model.

Now consider the collection of standard elements inside our ultrapower:

$\displaystyle S={\overline{0},\overline{1},\overline{2},\ldots}.$

This collection contains zero and is closed under successor. Yet it does not contain $\displaystyle H$ . If $\displaystyle S$ were definable inside the ultrapower by some first-order arithmetic formula $\displaystyle P(x)$ , then induction applied to $\displaystyle P$ would force every element to satisfy $\displaystyle P$ .

But $\displaystyle H$ would not satisfy it. Therefore the collection of standard natural numbers is not first-order definable inside a nonstandard model of PA, even when parameters from the model are allowed. This is one of the most important ideas in the subject. From outside the model, we can clearly distinguish the standard part from the nonstandard part. Inside the model, the arithmetic language does not have the expressive power to make that distinction. We may write the informal infinite disjunction $\displaystyle x=0\lor x=1\lor x=2\lor\cdots,$ but this is not a single first-order formula. First-order formulas are finite strings. Thus induction can apply to every first-order formula and still fail to single out the standard natural numbers.

This leads to a useful principle called overspill. Suppose $\displaystyle P(x)$ is an arithmetic formula, possibly involving parameters from the nonstandard model, and suppose $\displaystyle P(0),P(1),P(2),\ldots$ all hold for the ordinary natural numbers. Then $\displaystyle P(x)$ must also hold for at least one nonstandard element.

Why? If it held for precisely the standard elements, the formula would define the standard part. We have just seen that this is impossible. So any definable property true of all ordinary natural numbers must spill over into the nonstandard region. This is often useful in proofs. It allows us to pass from a family of standard finite assertions to a statement at some nonstandard stage. Notice, however, that the nonstandard stage is obtained by a logical existence argument. Overspill does not usually provide a computable procedure for finding it.

Nonstandard arithmetic gives us a fascinating distinction between two meanings of finiteness. Consider the interval

$\displaystyle I_H=\{x\in{}^*\mathbb N\le H\}.$

Inside the model, this is the interval from zero to the number $\displaystyle H$ . The model regards it as finite, with $\displaystyle H+1$ elements. But from our external perspective, this interval contains every ordinary natural number, $\displaystyle 0,1,2,3,\ldots,$ so it is infinite. There is no contradiction because the model’s assertion that the interval has $\displaystyle H+1$ elements is an internal arithmetic statement. Externally, $\displaystyle H+1$ is a nonstandard number, not an ordinary finite cardinality.

Objects such as $\displaystyle I_H$ are often called hyperfinite. More formally, hyperfinite sets arise naturally when we extend the construction to an ultrapower of a larger set-theoretic structure, where finite sets themselves can be represented by sequences.

For example, the sequence of finite sets $\displaystyle {0},\quad{0,1},\quad{0,1,2},\ldots$ gives rise to a hyperfinite set containing every standard natural number while having a nonstandard finite size internally. This distinction is especially useful in nonstandard analysis, where one can work with hyperfinite partitions, sums, and approximations before translating the results back into ordinary analysis.

Other models

Our ultrapower is one particular nonstandard model, but it is far from the only one. We can already construct a large variety by changing the ultrafilter, the underlying index set, or the theory we require the model to satisfy. A more elementary source of variety comes from compactness.

Introduce a new constant $\displaystyle c$ and require $\displaystyle c>0,\quad c>1,\quad c>2,\quad\ldots$ together with the statement that $\displaystyle c$ is prime. Every finite collection of requirements is satisfiable in the ordinary natural numbers, because there are arbitrarily large primes. Compactness therefore gives a model of PA containing a prime larger than every ordinary natural number.

Our ultrapower already supplied such an element through the sequence of successive primes, but compactness gives an independent existence proof.

Instead, require that $\displaystyle c>n$ for every ordinary numeral $\displaystyle n$ , and that $\displaystyle m\mid c$ for every ordinary positive integer $\displaystyle m$ . Every finite collection is satisfiable: if the requirements mention divisibility by $\displaystyle 1,\ldots,N$ , choose $\displaystyle c$ to be a sufficiently large multiple of $\displaystyle N!$ . Compactness again produces a model containing such an element.

These examples illustrate an important construction principle: if a family of arithmetic requirements can be satisfied in the standard natural numbers a finite number at a time, compactness can produce a model in which all the requirements hold simultaneously.

But the resulting models need not agree about every arithmetic sentence. To understand this distinction, we must examine the hierarchy of arithmetic theories.

Axiomatic Systems

There is no single natural boundary between weak and strong arithmetic. One can begin with a very small collection of algebraic rules, add restricted forms of induction, and gradually obtain theories capable of proving increasingly complicated statements. It is useful to distinguish some of the most important systems.

Robinson Arithmetic: This theory contains the basic successor, addition, and multiplication axioms, but no general induction principle. It is weak enough that our polynomial model satisfies it, even though that model contains an element that is neither even nor odd. Yet $\displaystyle Q$ is surprisingly expressive. It can represent enough elementary computation to support important incompleteness and undecidability results. This is worth emphasizing. A theory does not need to prove sophisticated mathematics in order to encode complicated questions about mathematical proofs. The ability to represent finite computations already creates substantial logical complexity.

Instead of allowing induction for every arithmetic formula, we can restrict it to formulas of particular logical forms. For example, a $\displaystyle \Sigma^0_1$ formula has the form $\displaystyle \exists y,R(x,y),$ where $\displaystyle R$ is a formula with only bounded quantifiers, possibly with additional parameters. The theory $\displaystyle I\Sigma_1$ permits induction for such formulas. Similarly, one defines $\displaystyle I\Sigma_2,I\Sigma_3,\ldots$ by allowing more alternating blocks of unbounded quantifiers.

These fragments form an important hierarchy of proof-theoretic strength. Many elementary combinatorial and number-theoretic arguments require only weak forms of induction, while others genuinely need stronger principles. This raises a useful question whenever we prove a theorem by induction: how complicated is the property on which we are inducting? The logical complexity of the induction formula can matter as much as the apparent simplicity of the mathematical problem.

Another system, called Primitive Recursive Arithmetic (PRA), formalizes reasoning about primitive recursive functions and finite computations. Primitive recursive functions are obtained from simple initial functions using composition and primitive recursion. This includes addition, multiplication, factorials, and many familiar computational procedures. But the class of primitive recursive functions does not include every computable function. The Ackermann function, for example, is computable but grows faster than every primitive recursive function in the appropriate sense. PRA is especially important in proof theory because it captures a substantial amount of elementary finitary reasoning while remaining much weaker than PA.

Peano’s Arithmetic: PA permits induction for all first-order arithmetic formulas. This additional strength allows it to prove termination and totality statements not available in weaker systems. Nevertheless, PA is incomplete. There are first-order arithmetic sentences that PA neither proves nor refutes, assuming PA is consistent. The fact that PA admits nonstandard models is related to this incompleteness, although nonstandard models themselves exist even for complete first-order arithmetic theories.

True arithmetic: We can consider the collection of all first-order arithmetic sentences true in the standard natural numbers:

$\displaystyle \text{Th}(\mathbb N)=\{\varphi:\mathbb N\models\varphi\}.$

This is called true arithmetic. By definition, it is complete: for every arithmetic sentence $\displaystyle \varphi$ , exactly one of $\displaystyle \varphi$ or $\displaystyle \neg\varphi$ belongs to it. Our ultrapower is a model of true arithmetic, by Łoś’s theorem.

But true arithmetic is not effectively axiomatizable. If there were a computable procedure listing all true arithmetic sentences, we could decide arbitrary arithmetic truth by searching for a sentence or its negation in the enumeration, contradicting the undecidability of arithmetic. This gives a striking combination: True arithmetic is complete but still has nonstandard models. Thus completeness of a theory and uniqueness of its model are entirely different properties.

Presburger arithmetic: There is another instructive comparison. If we remove multiplication from the language and study only addition and order, we obtain Presburger arithmetic. The full first-order theory of $\displaystyle (\mathbb N,0,1,+,<)$ is decidable and complete. There is an algorithm determining the truth of any sentence in this language. Nevertheless, it also has nonstandard models, by the same compactness argument. So even complete, decidable first-order theories of familiar infinite structures need not characterize those structures uniquely.

Second Order Arithmetic: What if we allow quantification not only over natural numbers but also over subsets of natural numbers? Then we can express the full second-order induction principle:

$\displaystyle \forall X\left[\big(0\in X\land\forall n(n\in X\Rightarrow n+1\in X)\big)\Rightarrow\forall n(n\in X)\right].$

Under full second-order semantics, the variable $\displaystyle X$ ranges over every subset of the domain. Now the collection of standard successor iterates can be considered as a subset. If the model contained additional nonstandard elements, that subset would contain zero and be closed under successor without containing every element, contradicting full induction. Consequently, the full second-order Peano axioms characterize the natural numbers uniquely up to isomorphism.

But this comes at a cost: full second-order logic does not have the ordinary first-order compactness theorem or a comparable effective complete proof system. There is an interesting tradeoff. First-order logic has strong general theorems about proofs and models, but permits nonstandard structures. Full second-order semantics can characterize the intended natural numbers uniquely, but requires a richer underlying conception of subsets and loses those convenient metalogical properties.

Countable Models

Our ultrapower $\displaystyle {}^*\mathbb N$ is uncountable. In fact, it has cardinality continuum. To see this, note first that there are continuum-many sequences of natural numbers, so $\displaystyle |{}^*\mathbb N|\le2^{\aleph_0}.$ Conversely, given any infinite binary sequence $\displaystyle x=(x_0,x_1,\ldots)$ , form a sequence of integers whose $\displaystyle n$ th term encodes the first $\displaystyle n$ bits: $\displaystyle a_n(x)=\sum_{k<n}x_k2^k.$ If $\displaystyle x\ne y$ , their first differing bit occurs at some position $\displaystyle k$ . For every $\displaystyle n>k$ , the integers $\displaystyle a_n(x)$ and $\displaystyle a_n(y)$ differ. Thus their sequences are not equivalent modulo a nonprincipal ultrafilter.

We have injected $\displaystyle 2^\omega$ into the ultrapower, proving $\displaystyle |{}^*\mathbb N|=2^{\aleph_0}.$ But the downward Löwenheim–Skolem theorem tells us that this ultrapower contains a countable elementary submodel, provided we choose the submodel to contain our infinitely large integer $\displaystyle H$ and the ordinary numerals. Thus we obtain a countable nonstandard model of true arithmetic.

The distinction between countability and standardness is important. The model is countable from the outside, but its elements include numbers larger than every standard natural number.

What does such a model look like as an ordered set? Surprisingly, all countable nonstandard models of PA have the same order type. Begin with the ordinary initial segment $\displaystyle 0<1<2<\cdots.$ After that come the nonstandard elements. Take one nonstandard element $\displaystyle H$ . Around it we have $\displaystyle \cdots<H-3<H-2<H-1<H<H+1<H+2<\cdots.$ This block has the order type of the integers $\displaystyle \mathbb Z$ .

Now define an equivalence relation on nonstandard elements by declaring $\displaystyle a\sim b$ if they differ by some ordinary finite integer. Every equivalence class is a copy of $\displaystyle \mathbb Z$ . There are many such blocks. For example, $\displaystyle H$ and $\displaystyle 2H$ cannot belong to the same block, since their difference is larger than every ordinary integer. Between any two distinct blocks there is another block. If $\displaystyle a<b$ and their difference is nonstandard, we can use division by two inside the model to choose an element near their midpoint, infinitely far from both endpoints in the standard-finite sense.

The blocks have no first or last block. Below any nonstandard $\displaystyle H$ lies a nonstandard element near $\displaystyle H/2$ , and above it lies $\displaystyle 2H$ . For a countable model, the collection of these blocks is therefore a countable dense linear order without endpoints, and hence order-isomorphic to $\displaystyle \mathbb Q$ . Thus every countable nonstandard model of PA has order type

$\displaystyle \omega+(\mathbb Z\cdot\mathbb Q),$

where $\displaystyle \mathbb Z\cdot\mathbb Q$ means a densely ordered family of copies of the integer order. This is an elegant result. The order structure is completely determined. But the addition and multiplication operations are not. Different countable nonstandard models of PA can have very different arithmetic structures even though their underlying orderings are isomorphic.

How many models?

One way to distinguish nonstandard models is to ask what subsets of the ordinary natural numbers their nonstandard elements can encode. Every ordinary natural number has a finite binary expansion. A nonstandard natural number can internally have a binary expansion of nonstandard finite length, and therefore determine a pattern of bits at every ordinary position.

For a model $\displaystyle M$ and an element $\displaystyle a\in M$ , consider the set

$\displaystyle A_a=\{n\in\mathbb N\models\text{the }n\text{th binary digit of }a\text{ is }1\}.$

This is an ordinary subset of the standard natural numbers, viewed from outside the model. The family of subsets obtained in this way is called the standard system of $\displaystyle M$ . Now fix any subset $\displaystyle A\subseteq\mathbb N$ . We can use compactness to construct a nonstandard model containing an element $\displaystyle c$ whose standard-position binary digits encode exactly $\displaystyle A$ .

Simply impose, for each ordinary natural number $\displaystyle n$ , the requirement that the $\displaystyle n$ th binary digit of $\displaystyle c$ equals one if $\displaystyle n\in A$ , and zero otherwise. We may also impose $\displaystyle c>n$ for every ordinary numeral. Every finite collection of these requirements can be satisfied by an ordinary integer: choose its finitely many specified binary digits, and use a sufficiently high additional digit to make it as large as needed. Compactness supplies a model containing an element satisfying all the requirements.

After taking a countable elementary submodel, we obtain a countable nonstandard model coding the prescribed set $\displaystyle A$ . Because a countable model has only countably many elements, it can code only countably many such subsets of $\displaystyle \mathbb N$ . But there are continuum-many subsets of $\displaystyle \mathbb N$ .

This leads to the theorem that there are continuum-many pairwise nonisomorphic countable models of PA. Their orderings all look the same, but their arithmetic structures can encode very different infinite information. This is an especially interesting example of the distinction between order structure, algebraic structure, and information content.

Nonstandard models and Gödel’s incompleteness theorem

We have so far constructed nonstandard models that preserve all true first-order arithmetic sentences. Our ultrapower, for instance, agrees with the ordinary natural numbers about every first-order sentence without parameters. But there are other nonstandard models of PA that disagree with the standard natural numbers about particular sentences. This is where Gödel’s incompleteness theorems become relevant. The basic insight behind Gödel’s work is that mathematical proofs can themselves be represented by natural numbers. A formal proof is a finite string of symbols. Such strings can be encoded by integers, and the process of checking whether a proposed string is a valid proof is mechanical. Consequently, we can construct an arithmetic formula

$\displaystyle \text{Proof}_{PA}(p,\varphi)$

expressing that $\displaystyle p$ encodes a valid PA proof of the formula $\displaystyle \varphi$ . Now consider the statement that PA is consistent:

$\displaystyle \text{Con}(PA)\equiv\forall p,\neg\text{Proof}_{PA}(p,0=1).$

It asserts that no natural number codes a proof of contradiction.

Assume PA is consistent. Then the statement is true in the ordinary natural numbers. But Gödel’s second incompleteness theorem tells us that PA cannot prove this statement. Therefore the theory $\displaystyle PA+\neg\text{Con}(PA)$ is consistent. By the completeness theorem, it has a model $\displaystyle M$ . Inside this model,

$\displaystyle M\models\exists p,\text{Proof}_{PA}(p,0=1).$

So the model believes that a proof of contradiction exists. How can that be possible if PA is consistent? The alleged proof code must be nonstandard. Every ordinary natural number encodes an actual finite string that can be checked externally. Since PA is consistent, none of those finite strings is a proof of contradiction. But the nonstandard model contains additional numbers. Some of those numbers may internally encode sequences of nonstandard finite length. Its arithmetic can regard such a sequence as a legitimate proof even though it does not correspond to any genuinely finite proof in the ordinary sense.

This is not a defect in the proof-checking algorithm. The algorithm works correctly on every standard finite input. The disagreement appears because the model quantifies over a larger collection of numbers, including nonstandard inputs. This gives us a concrete picture of how a false existential arithmetic statement can hold inside a nonstandard model while every ordinary candidate fails to witness it.

We should be careful about one distinction: our ultrapower $\displaystyle {}^*\mathbb N$ cannot be such a model, assuming PA is consistent. It satisfies every first-order sentence true in the standard natural numbers, including $\displaystyle \text{Con}(PA)$ .

Thus we have two genuinely different kinds of nonstandard models: those elementarily equivalent to the standard natural numbers, and those satisfying PA but disagreeing with the standard model about undecidable arithmetic statements.

There is an even more striking example because it involves elementary calculations with ordinary integers rather than statements about formal proofs. Consider a natural number written in base $\displaystyle b$ . Rewrite every exponent in base $\displaystyle b$ as well, recursively. This is called hereditary base notation.

A Goodstein sequence is obtained by starting with a natural number, changing the base from $\displaystyle 2$ to $\displaystyle 3$ , then subtracting one, changing the base again, subtracting one, and repeating. The numbers can initially grow extremely rapidly. Nevertheless, Goodstein’s theorem asserts that every such sequence eventually reaches zero.

The proof has a beautiful transfinite interpretation. At each stage, replace the base by the infinite ordinal $\displaystyle \omega$ , retaining the formal arithmetic structure of the hereditary base expansion. This assigns an ordinal below $\displaystyle \varepsilon_0$ to each term of the sequence. The corresponding ordinals strictly decrease, even while the ordinary integers may become much larger. Since there is no infinite strictly decreasing sequence of ordinals, the process must eventually terminate. The remarkable fact, proved by Kirby and Paris, is that Goodstein’s theorem cannot be proved in PA. Assuming the consistency of PA, the theory

$\displaystyle PA+\neg\text{Goodstein's theorem}$

therefore has a model. In such a model, there is a starting value $\displaystyle a$ for which the model believes the Goodstein process never terminates. This $\displaystyle a$ must be nonstandard. For every particular standard starting value, the actual Goodstein sequence terminates after some standard finite number of steps, and PA can verify that particular finite computation.

The unprovability concerns the uniform statement that termination holds for every starting value. So we have a theorem that is true for all ordinary natural numbers, but PA cannot establish the universal assertion. The connection with the ordinal $\displaystyle \varepsilon_0$ is not accidental. The proof-theoretic strength of PA is closely related to transfinite induction below this ordinal. This is one reason ordinals are important even when studying purely finite arithmetic problems.

At this stage, one might ask a natural question. Our ultrapower consists of equivalence classes of ordinary integer sequences. We have described its addition and multiplication coordinatewise. Could we construct a countable nonstandard model whose arithmetic operations are computable? For example, could we list its elements as

$\displaystyle a_0,a_1,a_2,\ldots$

and provide algorithms that, given the indices of $\displaystyle a_i$ and $\displaystyle a_j$ , compute the index of their sum and product? For our simple polynomial model, the answer is yes. Polynomial addition and multiplication are completely computable. But that model does not satisfy induction. For a countable nonstandard model of PA, the answer is dramatically different. Tennenbaum’s theorem states that no countable nonstandard model of PA has a computable presentation of its addition and multiplication. This is surprising because the arithmetic operations in every such model satisfy all the ordinary first-order algebraic laws.

The obstruction arises from the complicated infinite information hidden inside nonstandard elements. The proof uses computability-theoretic constructions, particularly disjoint computably enumerable sets that cannot be separated by a computable set. A computable presentation of nonstandard arithmetic would allow one to extract forbidden computational information from certain nonstandard codes. Thus we see a sharp contrast. A nonstandard model of weak arithmetic can be constructed with very simple computable algebraic operations, as in our polynomial example. But requiring the full induction strength of PA imposes enough arithmetic structure that computable presentations become impossible. This is one of the clearest connections between model theory and computational resources.

We have now seen several distinct constructions. The polynomial model introduced a genuinely infinite element through an indeterminate. It preserved elementary arithmetic identities but failed induction. Compactness produced models satisfying full PA by arranging infinitely many individually finite requirements. The ultrapower construction used sequences of natural numbers and a nonprincipal ultrafilter to define new arithmetic objects explicitly. Łoś’s theorem then showed that every first-order arithmetic truth survives in the resulting structure. Countable elementary submodels gave us countable nonstandard structures. Their orderings have a uniform description, but their arithmetic operations can encode widely different collections of subsets of the natural numbers. Finally, Gödel’s incompleteness theorems and Goodstein’s theorem showed that some nonstandard models of PA disagree with the ordinary natural numbers about particular arithmetic statements, even though they satisfy every axiom of PA. The common principle is that a first-order description of an infinite mathematical structure need not determine a unique structure.

The distinction becomes particularly clear when we compare three mathematical questions:

Is a property true for every ordinary natural number?
Can that property be proved from a specified axiomatic theory?
Does that property hold for every element of every model of the theory?

These questions are related, but they are not equivalent. An ordinary arithmetic statement can be true without being provable in PA. If it is unprovable and its negation is consistent with PA, there will be a nonstandard model in which it fails. A theorem may require stronger induction principles than the axioms one initially assumes. And two mathematical structures can agree about every first-order arithmetic sentence while containing very different elements.

Perhaps the most useful insight comes from our ultrapower. We constructed an infinitely large integer using nothing more mysterious than the sequence $\displaystyle 0,1,2,3,\ldots$ and a rule for deciding which sets of coordinates count as large. The sequence itself was familiar. The algebraic operations were familiar. The new mathematical object appeared because we changed the notion of equality and interpreted entire sequences as individual elements. This is a recurring phenomenon in mathematics. Quotient constructions, completions, ultraproducts, and limit procedures allow familiar objects to be assembled into new structures whose individual elements possess properties unavailable in the original setting. Nonstandard models of arithmetic give an especially rich example because the new structures can preserve all the first-order rules of the old arithmetic while containing numbers that, from our external perspective, lie beyond every ordinary finite integer. The deeper lesson is not that arithmetic is unreliable or that ordinary integers somehow depend on arbitrary choices. Rather, it is that the rules we use to describe a mathematical structure and the structure we intend those rules to describe are not always the same thing. Understanding the gap between them is one of the central achievements of mathematical logic. It brings together the ideas of compactness, computability, induction, proof theory, ultrafilters, and the existence of different mathematical universes.

Share this:

Related

Leave a Reply Cancel reply