Non-standard models of arithmetic

The quest to capture the essence of the natural numbers—0, 1, 2, and so on—in a formal set of rules led to the development of Peano Arithmetic (PA). These axioms were intended to provide an unshakable foundation for mathematics, a blueprint so precise that any structure built from it would be identical to our familiar number system. However, when these rules are expressed in the standard language of first-order logic, a subtle but profound gap emerges. The very axiom meant to ensure completeness, the principle of induction, reveals a weakness that prevents it from ruling out mathematical impostors.

This article delves into the strange and fascinating worlds that arise from this logical loophole: non-standard models of arithmetic. These are structures that follow every rule of Peano Arithmetic yet contain "infinite" numbers that lie beyond all the standard integers we can count. First, in "Principles and Mechanisms," we will explore how these models are constructed using tools like the Compactness Theorem and what their bizarre internal landscape, governed by principles like Overspill, looks like. Then, in "Applications and Interdisciplinary Connections," we will see how these seemingly abstract fantasies are indispensable tools for understanding the very real limits of proof, computation, and truth, providing concrete insights into Gödel's and Tarski's foundational theorems.

Imagine you want to describe the natural numbers—$0, 1, 2, 3,$ and so on—to an alien, a computer, or even just a very skeptical philosopher. You can't just show them the numbers; you have to write down a set of rules, or ​​axioms​​, that capture their essence so perfectly that anyone who follows them will inevitably be thinking about the same structure you are. This was the quest of mathematicians like Giuseppe Peano, and the rules they devised form the bedrock of what we call ​​Peano Arithmetic (PA)​​.

The rules seem simple enough. There's a starting point, $0$. Every number has a unique 'next number', or ​​successor​​, which we get by applying a function $S$ (think of it as '$+1$'). There are rules for how addition and multiplication work. But the most ingenious, and as we shall see, the most slippery of these rules, is the ​​Principle of Induction​​.

The principle of induction is the engine of mathematical proof. It’s like a line of an infinite number of dominoes. If you can prove two things:

1. The first domino falls (a property is true for $0$).
2. For any domino, if it falls, it knocks over the next one (if the property is true for a number $n$, it must also be true for its successor, $S(n)$).

Then you know that all the dominoes will fall. The property must be true for every single natural number. It’s a beautifully powerful idea that lets us prove things about an infinite set with a finite amount of work.

But here comes the catch. When we try to write this rule down in the precise language of ​​first-order logic​​—the standard language for modern mathematics where we can talk about numbers but not about abstract "properties" or "sets of numbers"—we hit a snag. We can't write a single sentence that says, "For any property...". Instead, we are forced to create an ​​axiom schema​​. This means we write down a separate induction axiom for every single property that we can define with a formula in our language.

This might seem like a minor technicality, but it's a crack in the very foundation. We have an induction axiom for the property "is an even number," another for "is a prime number," and so on, for the countably infinite list of properties we can formally write down. But what about properties we can't write down? Are there any? Absolutely! There are uncountably many subsets of the natural numbers (properties), but only countably many formulas to describe them. Our first-order induction schema, as vast as it seems, covers only a sliver of all possible properties. It’s this gap between "all properties" and "all definable properties" that opens a door to a world of mathematical strangeness. This limitation is precisely why first-order PA is not ​​categorical​​—it cannot force all its models to be structurally identical to the familiar natural numbers.

Let's exploit this loophole. We're going to play a game of logical construction. We'll start with all the rules of Peano Arithmetic, which we know are true for our standard numbers. Now, let's add a new player to the game, a mysterious number we'll call $c$. And we'll add a few new rules about $c$:

• $c$ is greater than $0$.
• $c$ is greater than $1$.
• $c$ is greater than $2$.
• ...and so on, adding an infinite list of axioms, $c > \overline{n}$, for every standard natural number $n$.

Is this new, infinitely expanded rulebook consistent? Can a universe exist where all these rules hold true at once? Here, logic provides us with a powerful, almost magical tool: the ​​Compactness Theorem​​. It states that if every finite collection of your rules is consistent (i.e., has a model), then the entire infinite set of rules is also consistent and has a model.

Let's check our new rules. Take any finite handful of them. This finite set will contain the axioms of PA and a finite list of demands on $c$, say, $c > 10$, $c > 500$, and $c > 10000$. The most demanding of these is $c > 10000$. Can we satisfy this little rulebook? Of course! We can use our ordinary natural numbers and just decide to interpret the symbol $c$ as, say, $10001$. All the rules of arithmetic hold, and $10001$ is indeed greater than $10000$. So, any finite subset of our new axioms is satisfiable.

By the miracle of the Compactness Theorem, this means our entire infinite collection of axioms must have a model. There must exist a mathematical structure that satisfies all the rules of Peano Arithmetic, but which also contains this number $c$ that is, by construction, larger than every standard natural number we can name. This $c$ is a ​​non-standard number​​, an "infinite" integer. And the model it lives in is a ​​non-standard model of arithmetic​​. This new model is a perfect impostor. It obeys every single first-order rule we laid down for the natural numbers, yet it contains entities that are profoundly different from the numbers we know and love.

What does this non-standard universe look like? It doesn't just contain the standard numbers $\{0, 1, 2, \ldots\}$ and then a single outlier $c$. If it's a model of arithmetic, it must be closed under arithmetic operations. If $c$ exists, then so must $c+1$, $c+2$, and $c-1$, $c-2$, and so on. There's not just one non-standard number, but an entire "galaxy" of them, arranged in chains that look like copies of the integers ($\mathbb{Z}$-chains), stretching out infinitely in both directions, all sitting beyond the standard numbers.

One of the most fascinating laws of these non-standard worlds is the ​​Overspill Principle​​. It's a beautifully intuitive idea. Imagine a property that can be defined by a formula in our language. If this property is true for every single standard number, it can't just abruptly stop at the boundary. It must "spill over" and be true for at least one non-standard number as well. A definable property cannot perfectly separate the standard from the non-standard.

Let's consider a profound example related to Gödel's Incompleteness Theorem. Let's define a property $\psi(x)$ as "There is no proof of a contradiction (like $0=1$) from the axioms of PA that uses a proof code smaller than $x$." Since PA is consistent (we believe!), this is true for $x=0$, $x=1$, $x=2$, and so on for every standard number $n$. PA can even prove each individual instance $\psi(\overline{n})$ because it just involves a finite check.

So, the property $\psi(x)$ is true for all standard numbers. By the Overspill Principle, there must be a non-standard number, let's call it $b$, for which $\psi(b)$ is also true in our non-standard model. This means that inside this model, it is believed that there is no proof of a contradiction with a code smaller than the non-standard number $b$. This gives rise to the fascinating notion of partial truth predicates—predicates that act like a truth definition, but only for a limited (though non-standardly large) part of the model.

The existence of non-standard models reveals something deep about the nature of proof and truth. Consider the statement $\forall x\, \psi(x)$ from our example above. Even though PA proves $\psi(\overline{n})$ for every single standard number $n$, it cannot prove the universal statement $\forall x\, \psi(x)$. Why? Because this universal statement is equivalent to saying "PA is consistent," and Gödel's Second Incompleteness Theorem tells us that PA cannot prove its own consistency.

So where does the universal statement fail? It fails in a non-standard model! There exist non-standard models where PA is "inconsistent." In such a model, there is a non-standard number $c$ which the model believes is the Gödel code for a valid proof of $0=1$. For this non-standard $c$, the statement $\psi(c)$ is false. This phantom proof, encoded by a non-standard number, is the counterexample that prevents PA from proving its own consistency. Non-standard models are the very place where these unprovable truths find their counterexamples.

This brings us to a final, profound question: if these non-standard numbers are so different, why can't we just write down a formula, $\text{IsStandard}(x)$, that picks out only the "true" natural numbers? The reason is as elegant as it is deep. If we could write such a formula, we could use it to build a "truth machine." We could define a formula $\text{True}(y)$ that could tell us whether any statement of arithmetic (with Gödel number $y$) is true in the standard model. We would simply formalize the recursive definition of truth, but carefully restrict every step—every subformula, every substitution—to the realm of numbers satisfying $\text{IsStandard}(x)$.

But such a truth machine is impossible. ​​Tarski's Undefinability of Truth Theorem​​ shows that no system of arithmetic can define its own truth. The very assumption that we can define "standardness" leads to a contradiction.

Here we see the beautiful unity of logic's limitations. The weakness of the first-order induction schema, the existence of non-standard models, the overspill principle, the non-definability of the set of standard numbers, and the undefinability of truth are not separate, isolated facts. They are all facets of the same fundamental truth: any formal language powerful enough to talk about its own structure is inherently limited in its ability to capture the full, intuitive reality of the concepts it seeks to describe. The blueprint of first-order arithmetic is simply not detailed enough to prevent impostors from being built, and in studying these impostors, we learn more about the blueprint itself than we ever could by only looking at the intended design.

Now that we have grappled with the principles and mechanisms behind non-standard models of arithmetic, a natural question arises: So what? Are these strange number systems, with their ghostly infinite integers, merely a logician's idle fantasy? Or do they, in fact, tell us something deep and useful about the world of numbers we thought we knew so well? The answer, perhaps surprisingly, is that these "unreal" worlds provide a powerful and indispensable lens for understanding the very real limits of mathematics, logic, and computation. Like a physicist studying the universe through the warped spacetime near a black hole, we can study our standard arithmetic by observing how it behaves in the strange neighborhood of non-standard models.

One of the most profound discoveries of the 20th century was Gödel's Incompleteness Theorem. It tells us that any sufficiently strong and consistent axiomatic system for arithmetic, like Peano Arithmetic ($PA$), must be incomplete. There will always be statements that are true in the standard model of the natural numbers, $\mathbb{N}$, but which cannot be proven from the axioms of $PA$.

Non-standard models give us a concrete, tangible way to see why this is the case. If a statement $\varphi$ is true in $\mathbb{N}$ but is not provable from $PA$, then by the rules of logic, its negation $\neg\varphi$ must be consistent with $PA$. The Completeness Theorem of first-order logic then guarantees that there must be a model where $PA$ and $\neg\varphi$ are both true. Since $\varphi$ is true in the standard model $\mathbb{N}$, this new model cannot be $\mathbb{N}$. It must be a non-standard model!

These models are the living embodiment of independence. For instance, Gödel's own sentence, $G_{PA}$, which asserts its own unprovability, is true in $\mathbb{N}$ but unprovable in $PA$. This means there must exist non-standard models of $PA$ in which $G_{PA}$ is false. What does it mean for $G_{PA}$ to be false? It means the model "believes" that $G_{PA}$ is provable. It contains an element that it thinks is the Gödel number of a proof of $G_{PA}$. But since we know $PA$ is consistent, no such standard proof can exist. The "proof" that this model sees is a non-standard number—an object that corresponds to an infinitely long sequence of logical steps, a derivation that would never terminate in our finite world. The model follows the rules of arithmetic perfectly, but its universe contains objects that lead it to "wrong" conclusions about provability.

This phenomenon is not limited to Gödel sentences. Consider a complex combinatorial statement like the Paris-Harrington Principle (PH), a variation of Ramsey's theorem that is known to be true in $\mathbb{N}$ but unprovable in $PA$. The independence of PH implies the existence of a non-standard model of arithmetic where the principle fails. In this world, there exists a "counterexample" to the Paris-Harrington principle—a coloring of a set that lacks the required monochromatic subset. But for this to happen, the set being colored must be of a non-standard, infinite size. For all standard, finite sizes, the principle holds, just as it does in our world. The failure only appears beyond the "horizon" of the standard numbers.

In this way, non-standard models act as a litmus test. If a statement is true in $\mathbb{N}$ but you can find a non-standard model of $PA$ where it is false, you have just proven that the statement is unprovable from the axioms of $PA$.

The insights gained from non-standard models extend beyond pure logic and into the heart of computer science. A key property of non-standard models is a wonderfully intuitive idea called the ​​Overspill Principle​​. It states that if a property is true for every single standard natural number, it must also be true for at least one non-standard number. Think of it like a line of dominoes: if you knock over all the finite ones, the first infinite one has to fall too.

Let's see this principle in action on a famous problem. For any given Turing machine that we know halts, we can, in principle, run it and find out its halting time, which will be some standard number of steps. A natural question is: can $PA$ prove the general statement, "For every Turing machine that halts, its halting time is a standard number"? The answer is no, and overspill tells us why.

The problem is that the very concept of "being a standard number" is not something that can be defined by a formula within the language of arithmetic. Any formula you try to write that is true for all standard numbers will, by the Overspill Principle, inevitably be true for some non-standard numbers as well in a non-standard model. So, if we had a non-standard model of $PA$, it might contain a Turing machine (coded by a standard number) that halts, but only after a non-standard number of steps. From within the model, this halting time might satisfy your definition of a "small" number, but from our external perspective, it's infinite. Therefore, $PA$ cannot prove that all halting times are standard, because its axioms are satisfied by these bizarre models where computations can take an infinite amount of time and still be considered "to halt".

One of the most fascinating applications of non-standard models is in exploring the nature of truth itself. Tarski's Undefinability of Truth theorem shows that no arithmetical formula can define the set of all true arithmetic sentences. You cannot, from within the language of arithmetic, create a perfect "truth detector."

This limitation applies to any model of $PA$, standard or non-standard. No model can define its own truth predicate from within its own language. But here is where a remarkable twist occurs. While a truth predicate cannot be defined, it is sometimes possible for a model to be expanded with one. It has been shown that certain non-standard models (called recursively saturated models) can be equipped with a "satisfaction class". This is an external set that functions as a truth predicate for all sentences in the model's language, including sentences of non-standard, infinite length.

This might seem esoteric, but it has profound consequences. Logicians can use these special, truth-expanded non-standard models as laboratories. For instance, they can be used to prove that adding a simple, Tarskian-style compositional theory of truth to $PA$ does not allow one to prove any new arithmetical theorems. The new theory is "conservative" over the old one. The proof is a beautiful piece of model theory: if adding the truth axioms did prove a new arithmetic sentence $\psi$, then we could find a non-standard model of $PA$ where $\neg\psi$ is true, expand that model with a satisfaction class, and thereby create a model of the new, stronger theory where $\psi$ is false—a contradiction. This demonstrates that non-standard models are not just objects of study; they are crucial tools in the metamathematical toolkit.

We have seen what non-standard models do, but how does one even construct such a thing? The Compactness Theorem gives an abstract proof of their existence, but a more powerful and concrete method is the ​​ultraproduct construction​​. This technique is a cornerstone of modern model theory.

Imagine you have an infinite family of structures—say, infinitely many copies of our own standard model $\mathbb{N}$. To build a new universe, the ultraproduct, you hold a kind of cosmic election for every single possible statement. An ​​ultrafilter​​ is a mathematical tool that acts as the voting system. For any partition of the infinite set of voters into two camps (e.g., those for whom statement $\varphi$ is true and those for whom it's false), the ultrafilter definitively tells you which camp represents the "overwhelming majority".

The resulting ultraproduct model is then defined by this vote: a statement is declared true in the ultraproduct if and only if it was true for a "majority" of the original models. This powerful principle is known as ​​Łoś's Theorem​​. When you take an ultraproduct of infinitely many copies of the standard model $\mathbb{N}$ using a nonprincipal ultrafilter, the result is a non-standard model. It will contain "infinite" numbers represented by sequences that grow without bound (like the sequence $(0, 1, 2, 3, \dots)$), yet it will satisfy all the same first-order axioms as $\mathbb{N}$ itself.

The journey through the applications of non-standard models reveals a startling picture. These bizarre number systems, born from the abstract theorems of logic, are not pathologies to be ignored. They are a reflection of the inherent limitations of our formal systems. They provide the concrete settings in which the "unprovable" becomes "false," where the "finite" spills over into the "infinite," and where the nature of truth itself can be probed and tested. By daring to look beyond the comfortable horizon of the standard integers, we learn more about the structure, power, and ultimate boundaries of our own mathematical reasoning.