Non-Standard Models of Arithmetic

For centuries, mathematicians sought to create a perfect axiomatic map for the natural numbers—a set of rules, like Peano Arithmetic, that would describe the world of 0, 1, 2, ... and nothing else. This quest for a unique, categorical description seemed attainable, yet a subtle but profound gap exists between our intuitive understanding of "all numbers" and what can be expressed in the practical language of first-order logic. This gap does not represent a failure but an opening into a vast, hidden mathematical landscape populated by "non-standard" numbers that lie beyond infinity yet still obey all the rules of arithmetic.

This article delves into these fascinating worlds. The first chapter, ​​Principles and Mechanisms​​, will uncover the logical crack in our map—the difference between first- and second-order logic—and reveal the powerful tools, like the Compactness Theorem, used to prove the existence of non-standard models. We will explore their strange structure, where our familiar numbers are just the beginning of an infinitely more complex reality. Following this, the chapter on ​​Applications and Interdisciplinary Connections​​ will demonstrate that these models are not mere curiosities but essential tools for understanding some of modern logic's deepest results, from Gödel's incompleteness to the limits of computation and the nature of truth itself. By journeying through these concepts, we begin to appreciate that the universe of numbers is far more mysterious and expansive than we ever imagined.

Imagine you are a cartographer, but instead of mapping a coastline, your task is to map the entire universe of numbers. Not just any numbers, but the most fundamental ones: $0$, $1$, $2$, $3$, and so on—the natural numbers, $\mathbb{N}$. You have a perfect piece of paper (formal logic) and the finest ink (a set of symbols like $0$, $+$, $\times$, and the successor function $S$ for "add one"). Your goal is to write down a set of rules, or ​​axioms​​, so precise that they describe the world of natural numbers perfectly, and nothing else. This was the dream of mathematicians for centuries.

The rules seem simple enough. There's a starting point, $0$. Every number has a unique next number (its successor). You can define addition and multiplication recursively, just as you learned in school. But the most powerful rule, the one that truly captures the "and so on" nature of the numbers, is the ​​principle of mathematical induction​​. Intuitively, it says: if you can prove a property is true for $0$, and you can prove that if it's true for some number $n$, it must also be true for $n+1$, then you've proven it's true for all natural numbers. It’s like setting up an infinite line of dominoes: if you can knock over the first one, and you know each one will knock over the next, then you know all of them will eventually fall.

Here we hit our first, and most profound, stumbling block. How do you write "for any property" in your formal language? There are two ways to try, and the difference between them is the secret key to unlocking worlds beyond our own.

One way, using a very powerful language called ​​second-order logic​​, is to do it directly. You can write a single, beautiful axiom that says: "For any set of numbers whatsoever, if that set contains $0$ and is closed under the successor function, then it is the set of all natural numbers." [@problem_id:2974903, 2974948]. This approach, called ​​Second-Order Peano Arithmetic​​ ($PA_2$), works perfectly. It is ​​categorical​​, meaning any world that satisfies these axioms must be a perfect, isomorphic copy of our familiar $\mathbb{N}$ [@problem_id:2974903, 2974948]. The map describes only one territory. But this power comes at a great price. Second-order logic is so expressive that it loses some of the beautiful, predictable properties of simpler logics. It doesn't have a complete proof system, and crucially, it lacks a property called ​​compactness​​. It's a perfect map, but one that is strangely difficult to work with.

Mathematicians, being practical people, usually prefer a more manageable language called ​​first-order logic​​. In this language, you cannot talk about "all sets of numbers." You can only talk about the numbers themselves. So, how do we state the induction principle? We cheat. We say that induction holds for any property that can be defined by a formula in our language. Instead of one grand axiom, we get an infinite ​​axiom schema​​. For every formula $\varphi(x)$ you can possibly write, you add an axiom that says: "If $\varphi(0)$ is true, and for all $x$, $\varphi(x)$ implies $\varphi(S(x))$, then for all $x$, $\varphi(x)$ is true." This is ​​First-Order Peano Arithmetic​​ ($PA$).

But look closely! Our language is countable; we can only write down a countably infinite number of formulas. Yet, the number of possible subsets of natural numbers is uncountably infinite. Our first-order induction schema is like a net that catches every fish we can name, but countless unnamed fish—properties we cannot describe with a first-order formula—slip through the holes. This is the crack in our map. One of the sets that slips through is the set of the "standard" numbers itself—the very numbers we thought we were describing!. The property of "being a number I can reach from $0$ in a finite number of steps" is not definable by a first-order formula.

This "flaw" in first-order logic is not a tragedy; it's an invitation. It allows for the existence of strange and wonderful mathematical universes that still obey all the rules of arithmetic we can write down. To find them, we don't need a spaceship, just a fantastically powerful tool called the ​​Compactness Theorem​​.

The Compactness Theorem is like a logical genie. It states: If you have a list of demands (axioms), and any finite selection from that list can be satisfied, then there is a world where the entire list is satisfied simultaneously.

So, let's make some wishes.

1. Our first wish is for all the axioms of Peano Arithmetic ($PA$) to be true. This ensures our new world looks like a plausible system of arithmetic.
2. Our second wish is for the existence of a special number, let's call it $c$.
3. Then we make an infinite list of further wishes: "$c$ is greater than $0$", "$c$ is greater than $1$", "$c$ is greater than $2$", "$c$ is greater than $3$", and so on, for every single standard natural number [@problem_id:2968359, 2974948, 2987470].

Now we ask the genie: is this possible? Let's check. Take any finite number of these wishes. For example, "PA is true, and $c > 1000$." Can we satisfy this? Easily! We can use our familiar world $\mathbb{N}$ and just decide that for this one instance, the symbol $c$ will represent the number $1001$. All the axioms of $PA$ are true in $\mathbb{N}$, and $1001 > 1000$ is also true. Since any finite subset of our wishes is satisfiable, the Compactness genie says, "Your wish is granted!"

There must exist a model, a mathematical universe, where all the axioms of $PA$ hold, and yet there is a number $c$ that is larger than every standard natural number. We have conjured a ​​non-standard model of arithmetic​​.

What do these worlds look like? They are not chaotic. They begin with a perfect, pristine copy of our own natural numbers: $0, 1, 2, 3, \ldots$. This is the ​​standard part​​ of the model. But beyond this infinite chain, where we thought there was nothing, there is more. There are "islands" of non-standard numbers. Our number $c$ lives out there. It has a successor, $c+1$, a predecessor, $c-1$ (which is also non-standard!), it can be doubled ($2c$), squared ($c^2$), and so on. It's a fully-fledged citizen of this larger universe, obeying all the laws of arithmetic.

The model we just built is called an ​​end extension​​, because all the new, non-standard elements are "at the end," larger than all the standard ones. But the zoology is even richer. It's possible to have models with non-standard numbers "between" other non-standard numbers, creating a structure far more complex and beautiful than a simple line. We can even build these models more concretely using a construction called an ​​ultrapower​​, where sequences of numbers are bundled together and "vote" on what properties are true—a process governed by a strange object called a non-principal ultrafilter and formalized by ​​Łoś's Theorem​​. In this construction, the simple sequence $(0, 1, 2, 3, \ldots)$ itself becomes a non-standard number!

The most mind-bending feature of these models is the ​​Overspill Principle​​. It states that if a definable property holds for arbitrarily large standard numbers, it must "spill over" and be true for some non-standard number as well. Imagine you define a property $P(n)$ that says "My computer can verify this arithmetic proof of complexity $n$." You find that it can handle proofs of ever-increasing standard complexities, with no upper bound. Overspill tells us there must be some non-standard number $b$ such that your computer, in this strange universe, can handle proofs of complexity $b$. This doesn't mean it can handle all proofs. Tarski's famous Undefinability of Truth theorem guarantees that any such definable verifier must eventually fail. But overspill promises that its success extends beyond the finite into the realm of the non-standard infinite.

These non-standard models, born from a subtle "crack" in our logical map, are not just mathematical curiosities. They are powerful tools. They show us the limits of formal language and reveal a hidden, majestic structure to the universe of numbers, a universe far vaster and more mysterious than we ever imagined. The map, it turns out, is not the territory. And the territories it allows are worlds beyond infinity.

Now that we have grappled with the principles and mechanisms behind non-standard models of arithmetic, a natural and pressing question arises: What are they for? Are they merely a logician's curious plaything, a gallery of bizarre mathematical worlds with numbers that go on forever? Or do they tell us something profound about the very nature of mathematics, computation, and truth itself? The answer, perhaps unsurprisingly, is the latter. These strange worlds are not just possible; they are in some sense necessary. They are the shadows cast by the limits of our logical language, and by studying them, we learn as much about our own world as we do about theirs.

Think of it this way. The axioms of Peano Arithmetic, which we use to pin down the properties of the natural numbers, are formulated in what we call first-order logic. This language is a powerful tool, but like any tool, it has its limits. It is subject to certain fundamental "metatheorems," such as the Compactness and Löwenheim-Skolem theorems, which have far-reaching consequences. These theorems, in essence, imply that if our set of axioms has one infinite model (like our familiar natural numbers), it must have a whole menagerie of other, non-isomorphic models—including models of different sizes and with different structures. This phenomenon is so fundamental that it appears even when we try to use more powerful languages, like second-order logic, if we interpret them in a way (known as Henkin semantics) that preserves these first-order metatheorems. So, the existence of non-standard models is not a peculiar flaw in Peano Arithmetic; it is a deep and unavoidable consequence of the logical framework we use to talk about mathematics. These models exist just beyond the horizon of what first-order logic can uniquely describe. Let's venture beyond that horizon and see what we can find.

One of the first and most stunning applications of non-standard models is in making sense of Gödel's Incompleteness Theorems. Gödel showed that any sufficiently powerful and consistent formal system, like Peano Arithmetic (PA), must contain statements that are true but unprovable within the system. Non-standard models give us a "place" for this incompleteness to live.

Consider a statement of the form "For every number $x$, property $P(x)$ is true." Suppose we can use PA to prove $P(0)$, $P(1)$, $P(2)$, and so on, for every single standard natural number we can name. We might naturally expect that we could then prove the universal statement $\forall x P(x)$. But this is not always the case! This curious situation, known as $ω$-incompleteness, is where non-standard models make their dramatic entrance. If $\forall x P(x)$ is not provable, then the theory $PA + \neg\forall x P(x)$ must be consistent. This means there must be a model where this theory is true—a world where PA's axioms hold, but where there is some "number" that does not have property $P$. Since we've already established that all standard numbers have property $P$, this counterexample must be a non-standard number!

A classic example of this involves the consistency of PA itself. Let's define a property $\Psi(x)$ as "There is no proof of a contradiction in PA whose Gödel code is less than or equal to $x$." Assuming PA is consistent, we can check for any standard number $n$ that no code up to $n$ represents a proof of contradiction. PA is powerful enough to formalize this finite check, so $PA \vdash \Psi(n)$ for every standard $n$. Yet, Gödel's second incompleteness theorem tells us that PA cannot prove its own consistency, which is the statement $\forall x \Psi(x)$. So, where is the counterexample? It lives in a non-standard model $M$ that believes PA is inconsistent. In this model $M$, there exists a non-standard element $c` that$M` considers to be the Gödel code of a proof of $0=1$. This non-standard "proof" $c$ is the witness that makes $\forall x \Psi(x)$ false in that world.

This same logic applies to Gödel's famous self-referential sentence $G$, which states, "This sentence is not provable in PA." We can reason that $G$ must be true in the standard model $\mathbb{N}$. But since $G$ is unprovable, the theory $PA + \neg G$ is consistent and must have a model, let's call it $M$. In this non-standard model $M$, the sentence $G$ is false. How can this be? Because $\neg G$ is equivalent to "This sentence is provable in PA." For $\neg G$ to be true in $M$, the model $M$ must contain an object $p$ that it believes is the Gödel code of a proof of $G$. Since no such standard proof exists, this $p$ must be a non-standard number—a "phantom proof" from our perspective, but a perfectly valid object within the bizarre reality of $M$.

The connections become even more tangible when we consider the theory of computation. Our computers run on algorithms, which are formalized as recursive functions. How do these familiar objects behave when their inputs are non-standard numbers?

First, the good news. If we have a function $f$ (like addition or multiplication) and PA is strong enough to prove that for every input $x$ there exists a unique output $y$, then this property of being a well-defined function holds true in every non-standard model as well. If you give a non-standard number $a$ as input to this function inside a non-standard model $M$, it will return a single, unique output $b$ (which will likely also be non-standard). The proofs of PA are robust enough to guarantee that functions behave like functions, even in these strange new domains.

But here is the fascinating flip side. Suppose PA can prove that a function has an output for every input, but it cannot prove the output is always unique. What does this failure of proof imply? It implies that there must exist a non-standard model $M$ and a non-standard input $a$ for which the function yields at least two different outputs, $b_1$ and $b_2$!. The syntactic limitation—the inability to prove a theorem—forces the existence of a semantic counterpart: a strange mathematical world where that theorem is false. Non-standard models are not optional; they are required to exist by the very incompleteness of our axiom system.

We can even peer into what a "computation" might look like in such a world. The formulas that represent computable functions in PA often do so by asserting the existence of a "computation trace"—a coded sequence of steps that starts with the input and ends with the output. When we compute a function for a standard input $n$, the trace is a standard, finite object. But what if we compute the function for a non-standard input $a$? The computation might proceed for a non-standard number of steps! The witness for the existence of the computation—the Gödel number of the trace—can itself be a non-standard number. This gives us a mind-bending but perfectly logical picture: computations that are infinitely long from our perspective but which "complete" inside the non-standard model.

Perhaps the most profound connection non-standard models offer is to the philosophy of truth and self-reference. In a celebrated theorem, Alfred Tarski proved that any language powerful enough to express arithmetic cannot define its own truth predicate. In essence, a system cannot fully comprehend its own notion of truth. It's like trying to see your own eyes without a mirror.

Non-standard models provide the mirror.

While arithmetic cannot define its own truth predicate from within, advanced results in model theory show that it's perfectly consistent to take a non-standard model $M$ of PA and add a new predicate $S$ to it, creating an expanded model $\langle M, S \rangle$. This new predicate $S$ can be made to act as a full "satisfaction class"—a truth predicate for all statements about the model $M$, including statements involving non-standard elements.

How does this not contradict Tarski's theorem? Because the predicate $S$ is not definable using the original language of arithmetic. It is an "external" addition, an expansion of the model's reality. This reveals the precise meaning of Tarski's theorem: it's not that truth is paradoxical, but that its definition requires a richer context, a "meta-language" or a more expansive universe. Non-standard models give us a concrete way to formalize such a universe. We can step into a non-standard world and, from that new vantage point, look back upon the system and see its truths laid bare in a way it could never do for itself.

This leads to a final, subtle point: a kind of "relativity" of truth. The relationship between truth in our standard world $\mathbb{N}$ and truth in a non-standard world $M$ depends on the complexity of the statement.

• Simple "existential" statements (of the class $\Sigma_1$), like "There exists a number $y$ that is a witness for property $P$," are ​​upward absolute​​. If such a statement is true in $\mathbb{N}$, its witness $y$ is a standard number. Since every standard number is also in $M$, the statement must also be true in $M$. Truth of this kind is robust; it travels upward into the more complex worlds.
• Simple "universal" statements (of the class $\Pi_1$), like "For all numbers $y$, property $P$ holds," are ​​downward absolute​​. If such a statement is true in $M$, it must be true for all of $M$'s elements, including all the standard ones. Therefore, it must also be true in $\mathbb{N}$.
• However, this symmetry breaks down. A $\Pi_1$ statement can be true in $\mathbb{N}$ but false in $M$ (like $\text{Con}(PA)$), and a $\Sigma_1$ statement can be true in $M$ (witnessed by a non-standard element) but false in $\mathbb{N}$. For more complex statements, the correspondence becomes even looser. Truth is not an absolute, monolithic property; its persistence across different mathematical realities depends on its logical form.

In the end, non-standard models are far from being mere curiosities. They are an essential part of the story of modern logic. They provide the stage on which the drama of incompleteness unfolds, a laboratory for testing the limits of computation, and a vantage point for contemplating the nature of truth itself. They show us that the familiar world of natural numbers is but one island—our home island, to be sure—in a vast archipelago of possible worlds, all governed by the same deep and beautiful laws of logic.