Non-Standard Models of Arithmetic

The natural numbers—0, 1, 2, and so on—form the bedrock of mathematics, a system so intuitive it seems unshakeable. This "standard model" of arithmetic, governed by familiar rules of addition and multiplication, appears to be the only one possible. However, the very language we use to formalize these rules, first-order logic, contains inherent limitations that open the door to other, far stranger, mathematical universes. These are the non-standard models of arithmetic, worlds that obey all the same axioms yet contain numbers so vast they lie beyond any integer we can name.

This article addresses the profound gap between our intuitive concept of "all numbers" and what can be captured by a finite set of formal rules. It explores how this gap is not a flaw, but a gateway to a deeper understanding of mathematical truth. Across the following chapters, you will discover the logical principles that give rise to these extraordinary structures and learn how they serve as an indispensable laboratory for testing the very limits of proof, computation, and truth itself.

The journey begins by examining the "Principles and Mechanisms" behind these models, from the foundational axioms of Peano Arithmetic to the logical sleight-of-hand of the Compactness Theorem that conjures them into existence. We will then explore their "Applications and Interdisciplinary Connections," revealing how these alternate realities of number provide a unique vantage point for understanding Gödel's incompleteness, the nature of computation, and Tarski's theorems on the undefinability of truth.

Imagine the natural numbers: $0, 1, 2, 3,$ and so on, marching single file into infinity. This ordered line of succession seems like the most solid, unshakeable foundation in all of mathematics. We learn its rules in childhood: how to add, how to multiply, how to compare. It is the "standard model" of arithmetic, the universe we call $\mathbb{N}$. But what if I told you that this familiar world is not the only possible one? What if there are other, stranger universes that obey all the same fundamental laws of arithmetic, yet contain numbers so vast they lie beyond our infinite horizon? These are the non-standard models of arithmetic, and their existence is not a mere fantasy, but a necessary and profound consequence of how we talk about mathematics. To understand them is to take a journey to the very limits of logic and language.

How would you describe the natural numbers to an alien intelligence that knows nothing of them? You can't just list them all. You have to provide a blueprint—a set of rules, or ​​axioms​​, from which all properties of numbers can be built. Mathematicians have done just this. A basic set of axioms, called ​​Robinson Arithmetic ($Q$)​​, lays down the most fundamental rules: zero is not the successor of any number, no two numbers have the same successor, and rules for how addition and multiplication work with the successor function.

But this isn't quite enough. The true power of arithmetic reasoning comes from a special rule, the principle of ​​mathematical induction​​. Think of it as the domino effect. If you have an infinite line of dominoes, how do you know they will all fall? You only need to know two things:

1. You can knock over the first domino (the base case).
2. The dominoes are set up so that each one will knock over the next one (the inductive step).

If both conditions are met, the entire infinite chain will topple. This powerful principle allows us to prove that a property holds for all natural numbers. To create a more robust system, we add this domino principle to our basic axioms, forming the celebrated ​​Peano Arithmetic ($PA$)​​.

Here we hit our first, subtle twist. How do we translate the domino principle into a formal, logical language? The most powerful and well-behaved system logicians have is ​​first-order logic​​. In this language, the induction principle becomes a schema, an infinite collection of axioms. For every property $P$ that we can write down as a formula in our language, we have an axiom that says: If $P$ is true for $0$, and if for every number $x$, the truth of $P(x)$ implies the truth of $P(x+1)$, then $P$ is true for all numbers.

This seems fine, until you realize the catch: "a property that we can write down as a formula". Our first-order language, for all its power, is limited. It can only describe a countably infinite number of properties. Yet, the total number of possible properties of numbers (which corresponds to the collection of all possible subsets of $\mathbb{N}$) is uncountably infinite. There are vastly more properties than our language has words for!

This is the crucial difference between first-order PA and its more powerful (and problematic) cousin, ​​second-order Peano Arithmetic ($PA_2$)​​. In second-order logic, we can state the induction principle with a single, mighty axiom: "For any set of numbers, if it contains $0$ and is closed under successor, it must be the set of all numbers". This version is so powerful it nails down the structure of the natural numbers completely; any model of $PA_2$ must be a perfect copy of our standard $\mathbb{N}$. We say $PA_2$ is ​​categorical​​. But this power comes at a great cost, as we shall see. For now, let's stick with the more modest, and more surprising, world of first-order PA. Its linguistic limitation is not a flaw; it's a doorway.

Enter the star of our show: the ​​Compactness Theorem​​ of first-order logic. In essence, it states: If you have an infinite list of logical demands (axioms), and every finite selection from that list can be satisfied, then the entire infinite list can be satisfied simultaneously. It’s a profound statement about consistency. A system doesn't collapse just because it's infinite, as long as it's locally consistent everywhere.

Now, let's perform a bit of logical magic. We'll start with all the axioms of Peano Arithmetic ($PA$). These axioms work perfectly in our standard model $\mathbb{N}$. Next, we introduce a new character into our language, a mysterious new constant symbol, let's call it $c$. Finally, we add an infinite list of new demands on $c$: $c > \overline{0}$ $c > \overline{1}$ $c > \overline{2}$ $c > \overline{3}$ ... and so on, for every standard natural number $\overline{n}$,.

Let's test this new, infinitely long list of axioms with the Compactness Theorem. Can any finite subset of these axioms be satisfied? Absolutely! Take any finite collection of our demands. It will include the axioms of PA and a finite number of statements like $c > \overline{100}$, $c > \overline{5000}$, and $c > \overline{10^6}$. Let's say the biggest number mentioned is $N$. We can easily satisfy these demands within our standard number system $\mathbb{N}$ by simply declaring that, for this limited set of demands, the symbol $c$ will be interpreted as the number $N+1$. All the rules of PA are still true, and all our finite demands about $c$ are met.

Since every finite subset of our infinite list has a model, the Compactness Theorem waves its wand and declares that the entire list must have a model! Let's call this model $\mathcal{M}$. What does $\mathcal{M}$ look like?

1. It must satisfy all the axioms of Peano Arithmetic. It has a $0$, a successor, addition, and multiplication that all behave as they should.
2. It contains an element, the interpretation of $c$, that is greater than $0, 1, 2, 3, \ldots$ and every other standard number we can name.

This element $c$ is a ​​non-standard number​​. It is an "infinite" integer. And once you have one, you have a whole new world of them: $c+1$, $c-1$, $2 \times c$, and even $c/2$ (if $c$ happens to be an "even" non-standard number!). This model $\mathcal{M}$ is a non-standard model of arithmetic.

These non-standard models are bizarre and beautiful structures. They begin with a perfect copy of our standard numbers, $\mathbb{N}$. But beyond all of them, there are new numbers. These non-standard elements are not just a chaotic jumble; they are organized into dense blocks that look like copies of the integers ($\mathbb{Z}$), stretching out infinitely in both positive and negative directions.

Why didn't our domino principle, induction, prevent these interlopers? The answer lies in that crack in the foundation: the limits of our language. The set of all standard numbers, $S^{\text{std}} = \{0, 1, 2, \ldots\}$, is an "inductive set": it contains $0$, and if a number $x$ is in $S^{\text{std}}$, so is $x+1$. Yet, in a non-standard model, this set is not the whole model. Induction seems to have failed! But it hasn't. The induction schema of PA only applies to properties that are definable by a formula. And it is a profound fact that the property "being a standard number" cannot be defined by any formula in the language of arithmetic. Our logical blueprint for induction is blind to the distinction between standard and non-standard numbers.

This blindness leads to fascinating phenomena. One is the ​​Overspill Principle​​: if a definable property holds for arbitrarily large standard numbers, it must "spill over" and be true for some non-standard number as well. If you can define a set that contains all of $\mathbb{N}$, it can't just stop there; it must continue on into the non-standard realm.

Furthermore, we can build these strange new worlds in different ways. The compactness argument we used creates a model that is an ​​end extension​​ of $\mathbb{N}$; all the new numbers are strictly greater than all the old ones. But it's also possible to construct elementary extensions that are not end extensions, where new numbers can be squeezed in between old non-standard numbers. In fact, using compactness and another powerful tool called the Löwenheim-Skolem theorem, we can show that for any infinite size you can imagine, there exists a non-standard model of arithmetic of that size. The arithmetic zoo is infinitely varied.

At this point, you might be thinking: this is a strange mess. Why don't we just use the powerful second-order version of induction, $PA_2$, which we know is categorical and describes only our beloved $\mathbb{N}$?

We could. But we would pay a steep price. Second-order logic, in its standard interpretation, loses the very tools that make first-order logic so fruitful. It is not compact. The failure of compactness is precisely why $PA_2$ can be categorical; it evades the argument that would force it to have models of all infinite sizes. More devastatingly, second-order logic does not have a complete proof system. There is no algorithm that can list out all the true statements of second-order arithmetic. In first-order logic, we have Gödel's Completeness Theorem, which guarantees that if a statement is true in every model, it has a formal proof. In second-order logic, this crucial link between truth and provability is severed.

We face a fundamental trade-off. We can have a language that perfectly describes a single, unique universe of numbers, but at the cost of being unable to systematically explore its truths. Or, we can have a language with beautiful, powerful deductive properties like compactness and completeness, but we must accept that our descriptions will never be perfect. They will always admit strange, unintended, non-standard interpretations.

The existence of non-standard models is not a failure of logic. It is a testament to its honesty. It teaches us that our linguistic nets, no matter how finely woven, will always have holes. And through those holes, we get a glimpse of mathematical universes more vast and varied than we ever imagined.

Now that we have grappled with the strange and wonderful existence of nonstandard models of arithmetic, it is only natural to ask: What are they good for? Are these phantom universes, populated by numbers larger than any integer we can imagine, merely a logician's curious plaything? Or do they, like a prism revealing the hidden colors within white light, tell us something profound about the nature of mathematics, proof, and even reality itself?

The answer, perhaps unsurprisingly, is that they are extraordinarily useful. These peculiar models are not just a consequence of the limits of our logical language; they are a powerful tool for exploring those very limits. They form a laboratory in which we can test the boundaries of what is provable, what is computable, and what is true. By stepping into these alternate realities of number, we gain a perspective on our own that is otherwise impossible to achieve.

One of the most unsettling and beautiful discoveries of the 20th century was Gödel's Incompleteness Theorem, which revealed a fundamental gap between truth and provability. There are statements about numbers that are true, yet no formal proof of them can ever be constructed within our axiomatic system. Nonstandard models give us a way to see this gap.

Imagine a statement $\psi(x)$ that says, "There is no proof of a contradiction whose Gödel code is less than or equal to $x$." If we assume our system, Peano Arithmetic ($PA$), is consistent, then for any standard number you can name—say, $n = 10^{100}$—we can check all the numbers up to $n$ and verify that none of them code a proof of $0=1$. Our system $PA$ is powerful enough to formalize this finite check, so for every standard numeral $\overline{n}$, $PA \vdash \psi(\overline{n})$. We can prove it for 0, for 1, for 2, and so on, for every number you can reach.

But here is the magic trick. Can $PA$ prove the universal statement $\forall x, \psi(x)$? This statement is none other than a formal declaration of PA's own consistency! By Gödel's Second Incompleteness Theorem, a system cannot prove its own consistency. So, we have found a statement that is true for every single number we know, yet the system cannot generalize this to all numbers.

Where does the generalization fail? It fails in a nonstandard model! In a nonstandard model of the theory $PA + \neg \mathrm{Con}(PA)$, there exists a nonstandard number, let's call it $c$, which the model believes is the code for a proof of $0=1$. For this phantom number $c$, the statement $\psi(c)$ is false. This is a stunning revelation: nonstandard models are precisely the place where statements that hold for all finite integers can unravel. They are the concrete realization of the limits of formal proof.

This idea deepens when we consider the "Arithmetized Completeness Theorem." Our system $PA$ is powerful enough to talk about mathematical structures. It can prove that if a theory $T$ is consistent, then there exists a coded model for $T$. However, $PA$ can't prove that this model is the "real" standard world of numbers, $\mathbb{N}$. Why not? Because the model it constructs might be nonstandard! So even if $PA$ proves that a statement $\sigma$ is true in all its coded models, we cannot conclude that $\sigma$ is true in our standard world. The existence of a witness for $\sigma$ in a nonstandard model might be a nonstandard element, a ghost that has no counterpart among the integers we know and love. This illustrates the profound gap between proving something is true in some abstract "possible world" and proving it is true right here, in ours.

Modern civilization runs on computation. At its heart, every computer program is just an elaborate function that takes numbers as inputs and produces numbers as outputs. The theory of computation is therefore deeply connected to the theory of arithmetic. Nonstandard models offer a fascinating playground to explore the ultimate nature of computation.

Let's say we have a computer program that implements a function $f(x)$. Since the steps of any algorithm are simple and mechanical, we can describe them using basic arithmetic. For any standard input, say $n=17$, the computation of $f(17)$ takes a finite, standard number of steps. Because these steps are so elementary, all models of arithmetic—standard and nonstandard—must agree on the outcome. This property, known as the absoluteness of $\Sigma_1$ truths, is the bedrock of why our computers are reliable. The statement "this computation halts with this output" is a simple assertion of existence (there exists a computation trace...), and if it's true in our world, it's true in all of them. So for any standard input $\overline{n}$, the value of the function is the same standard value $\overline{f(n)}$ in every model.

But what happens if we feed a nonstandard number $c$ into our program? The laws of arithmetic still hold! The computation proceeds, but it might now take a nonstandard number of steps. The memory registers of our idealized computer might hold nonstandard numbers. The final output, $f(c)$, could very well be another nonstandard number. This allows us to reason about "hypercomputations"—computations that transcend the finite limits of standard Turing machines.

The strength of our axioms determines how well-behaved these computations are. If we can prove in $PA$ that our function $f(x)$ always produces a unique output for any input ($\forall x \exists! y$), then this must hold true even for nonstandard inputs in any nonstandard model. The logic is so rigid that it locks down the behavior in all possible universes. But if our proof of uniqueness is weaker—if we can only prove it for each standard number individually but not for all $x$ universally—then the door is open for strange behavior. In such a case, a nonstandard model could exist where a single nonstandard input $c$ might produce multiple different nonstandard outputs! The solidity of mathematical reality is directly tied to the power of what we can prove.

Perhaps the most profound application of these ideas lies in the philosophy of mathematics, in the quest to understand the nature of truth itself. Can a formal system like Peano Arithmetic define its own notion of truth? That is, can we write a formula, let's call it $\mathrm{True}(x)$, that holds if and only if $x$ is the Gödel code of a true statement of arithmetic?

The answer, delivered by Alfred Tarski, is a resounding no. The argument is as simple as it is devastating. If such a formula $\mathrm{True}(x)$ existed within the language of arithmetic, we could use diagonalization to construct a "Liar Sentence," $\lambda$, which asserts its own falsehood:

This sentence states, "I am not true." Is $\lambda$ true? If it is, then by the definition of our truth predicate, $\mathrm{True}(\ulcorner \lambda \urcorner)$ must hold. But the sentence itself says that $\neg \mathrm{True}(\ulcorner \lambda \urcorner)$ holds. Contradiction. So $\lambda$ must be false. But if it's false, then $\neg \mathrm{True}(\ulcorner \lambda \urcorner)$ holds, which is exactly what $\lambda$ asserts. So $\lambda$ must be true. Contradiction again. A system that can talk about its own truth in this way inevitably self-destructs.

A formal system cannot look itself in the mirror. To speak of a system's truth, we must step outside of it, into a "meta-language." But nonstandard models offer us another way out. While it is impossible to define a truth predicate for arithmetic within arithmetic, it has been shown that certain nonstandard models can be expanded to include a "satisfaction class." This is a new predicate, $S$, added to the model from the outside, which functions exactly like a truth predicate for that model.

This does not contradict Tarski's theorem, because the satisfaction class $S$ is not definable using a formula from the original language of arithmetic. It is an external object, a mirror we have brought into the room. This astonishing result shows that while the standard model $\mathbb{N}$ is "truth-blind" about itself, there are other possible universes of arithmetic that are not. These nonstandard models provide the external standpoint from which a notion of truth can be coherently viewed.

The journey into nonstandard arithmetic reveals a landscape far richer and stranger than we might have first imagined. The familiar whole numbers are but one island in a vast ocean of possible realities. These other worlds, far from being mere mathematical fictions, serve as an essential diagnostic tool. They are the proving ground where the limits of proof are laid bare, where computation can be pushed beyond the finite, and where the elusive concept of truth can be grasped in a formal setting. The fact that the simple, childlike rules of counting—one, two, three—contain within them the seeds of such cosmic complexity is a testament to the unending depth and beauty of the mathematical universe.