First-order Peano Arithmetic

The natural numbers—0, 1, 2, and so on—are the bedrock of mathematics, yet their intuitive simplicity masks deep philosophical and logical challenges. How can we capture the infinite world of numbers and their properties within a finite, rigorous formal system? This pursuit is not merely academic; it probes the very limits of what can be formalized, computed, and proven. This article tackles this fundamental question by exploring First-order Peano Arithmetic (PA), the cornerstone axiomatic system designed for this purpose. In the following chapters, we will first construct this system from the ground up, detailing its language, axioms, and the powerful principle of induction. Then, we will uncover the startling consequences of this formalization, from its role as a model of universal computation to the profound limitations revealed by Gödel, Tarski, and the existence of strange 'nonstandard' worlds. We begin our journey by defining the precise principles and mechanisms that constitute Peano Arithmetic.

Alright, we've set the stage. We want to capture the essence of numbers in a formal system. But how do you do that? You can't just write "numbers are things you count with" in a mathematical treatise. We need to be more precise, like a watchmaker assembling a delicate timepiece. We need to build our theory of arithmetic from the ground up, with clearly defined components and rules. This journey will take us from the simple act of counting to the profound limits of reason itself.

First, if we're going to talk about numbers, we need a language. Not English or Chinese, but a language of pure logic, stripped of all ambiguity. Let's call it $L_{PA}$, the language of Peano Arithmetic. What are the words in this language? It’s surprisingly simple. We only need a few special symbols to get started.

First, we need a place to begin. We'll have a symbol for a specific number: $0$. This is our anchor, the first step on the infinite ladder of numbers.

Next, we need a way to get from one number to the next. For this, we have a "successor" machine, a function we'll call $S$. If you give $S$ a number, it spits out the very next one. So, $S(0)$ is our language's way of saying "one". $S(S(0))$ is its way of saying "two", and so on. For any natural number $n$, we can represent it with a term we call a ​​numeral​​, $\overline{n}$, which is just the symbol $S$ applied to $0$ exactly $n$ times.

Finally, we want to do arithmetic! We introduce two more function symbols: $+$ for addition and $\cdot$ for multiplication. These are like little factories. The $+$ factory takes two numbers and gives you their sum. The $\cdot$ factory takes two numbers and gives you their product.

And that's it! Our entire language for arithmetic is built from these four non-logical symbols—$0, S, +, \cdot$—along with variables (like $x, y, z$), the equality sign $=$, and the standard logical connectors ("and", "or", "not", "if...then") and quantifiers ("for all" $\forall$, "there exists" $\exists$). With these simple tools, we can construct terms like $(S(S(0)) \cdot S(0)) + S(S(S(0)))$, which is the formal way of writing $(2 \cdot 1) + 3$.

A language is just a collection of symbols until you give it grammar—rules that tell you which statements are true. These rules are our ​​axioms​​. For Peano Arithmetic (PA), we need a handful of axioms that we believe are self-evidently true about the numbers we use every day.

We start with some basic properties of our successor machine, $S$:

1. ​​Zero is the beginning:​​ Nothing comes before zero. In our formal language, this means $0$ is not the successor of any number: $\forall x (S(x) \neq 0)$.
2. ​​No two numbers lead to the same next number:​​ If the successor of $x$ is the same as the successor of $y$, then $x$ and $y$ must have been the same number to begin with. Formally, $\forall x \forall y (S(x) = S(y) \rightarrow x=y)$.

These two simple rules ensure that our numbers form a clean, infinite line starting at $0$, with no loops or branches.

Next, we must teach our system what addition and multiplication actually do. We can't just assume it knows. We have to define them. The way we do this is wonderfully elegant, using a method called recursion. We define the operations for $0$, and then we show how to extend the definition to the next number using the successor function $S$.

For addition:

1. Adding zero to any number doesn't change it: $\forall x (x + 0 = x)$.
2. Adding the successor of $y$ to $x$ is the same as taking the successor of $(x+y)$: $\forall x \forall y (x + S(y) = S(x+y))$. For example, $7 + (5+1)$ is the same as $(7+5)+1$.

For multiplication:

1. Multiplying any number by zero gives zero: $\forall x (x \cdot 0 = 0)$.
2. Multiplying $x$ by the successor of $y$ is the same as calculating $(x \cdot y)$ and then adding $x$ to the result: $\forall x \forall y (x \cdot S(y) = (x \cdot y) + x)$. For example, $7 \cdot (5+1)$ is the same as $(7 \cdot 5) + 7$.

With these axioms, we have defined the fundamental operations of arithmetic for our formal system. We've given it the basic rules of the game. But to do anything truly interesting, we need one more piece, the most powerful tool in our arsenal.

How do we prove that a property holds for all natural numbers? We can't check them one by one, because there are infinitely many. We need a more clever principle. You've likely seen it before: it's like a line of dominoes. If you can prove that...

1. The first domino falls (the property holds for $0$), and
2. If any given domino falls, it will knock over the next one (if the property holds for a number $x$, it must also hold for its successor $S(x)$), ...then you can be certain that all the dominoes will fall.

This is the principle of mathematical induction. How do we put this powerful idea into our first-order language? Here we encounter a subtle but profound point. In an ideal world, we would have a single axiom that says: "For any property $P$, if $P(0)$ is true and $\forall x (P(x) \rightarrow P(S(x)))$ is true, then $\forall x P(x)$ is true."

But in our first-order language, we don't have a way to say "for any property". Variables like $x$ and $y$ stand for numbers, not for abstract properties. This is the crucial limitation of being "first-order". So, we have to cheat a little. We introduce an ​​axiom schema​​. It's not one axiom, but an infinite recipe for generating axioms. The schema says: for any formula $\varphi(x)$ that you can possibly write down in our language $L_{PA}$, the following is an axiom: $(\varphi(0) \land \forall x(\varphi(x) \rightarrow \varphi(S(x)))) \rightarrow \forall x \varphi(x)$ This means that our domino principle applies to any property we can express as a formula. This schema is the engine of PA, allowing us to prove infinitely many facts from our finite set of basic axioms.

You might wonder, is this domino principle just an arbitrary rule we decided to add? Or is there a deeper reason it's true for the numbers we know and love? The reason is beautiful. In the language of set theory, the natural numbers $\mathbb{N}$ can be constructed as the smallest set that contains $0$ and is "closed" under the successor operation. Now, think about a property $\varphi(x)$ that satisfies the conditions for induction. The set of numbers for which $\varphi(x)$ is true must contain $0$ and be closed under the successor operation. But since $\mathbb{N}$ is the smallest such set, this set of numbers must be all of $\mathbb{N}$!. So, the induction schema isn't just a convenient rule; it's a reflection of the very nature of what the natural numbers are.

With our language and axioms in place, we have created Peano Arithmetic. The structure we were trying to describe is the one we all learned about in school: the set of natural numbers $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$ with the familiar operations of successor, addition, and multiplication. We call this the ​​standard model​​ of arithmetic.

Now for the million-dollar question: Did we succeed? Do our axioms perfectly pin down the standard model, and nothing else? It seems like they should. They are all obviously true statements about $\mathbb{N}$. But here, logic has a spectacular surprise in store for us. The answer is no.

The axioms of PA, as powerful as they are, admit other, bizarre models that are not at all like the natural numbers we know. These are called ​​nonstandard models​​. The proof of their existence is one of the most elegant applications of a tool called the ​​Compactness Theorem​​. Imagine we add a new constant symbol, let's call it $c$, to our language. And we add a new, infinite list of axioms:

• $c \neq \overline{0}$
• $c \neq \overline{1}$
• $c \neq \overline{2}$
• ... and so on, for every numeral $\overline{n}$.

We are demanding that $c$ be a number that is not any of the standard natural numbers. Does this create a contradiction? The Compactness Theorem tells us that a theory has a model as long as every finite part of it has a model. So, let's take any finite list of these new axioms, say up to $c \neq \overline{N}$. Can we find a model for PA plus this finite list? Sure! We can just use the standard model $\mathbb{N}$ and decide that our new symbol $c$ will just mean the number $N+1$. In this interpretation, all the axioms of PA are true, and all our finitely many demands like "$c$ isn't 5" or "$c$ isn't 100" are also true.

Since every finite piece of our new theory is consistent, the Compactness Theorem guarantees that the whole infinite theory must have a model! This model is a model of PA, but it contains an element $c$ that is, by definition, not equal to any standard natural number. This $c$ is a "nonstandard" number. This model contains a copy of the standard natural numbers, but it also contains other elements "beyond infinity." The existence of these strange worlds is a direct consequence of the fact that our induction principle is a first-order schema, not a single, all-powerful second-order axiom. The schema leaves loopholes, and these nonstandard numbers are what slip through the cracks. PA is not ​​categorical​​; it does not uniquely describe one structure.

At first, these nonstandard models might seem like a bizarre flaw, a failure of our logical system. But in science, failures are often the most interesting part—they teach us something new. The existence of these strange mathematical universes has profound implications for what we can know and what we can prove.

Remember, a statement is provable from the axioms of PA only if it is true in every model of PA. This is guaranteed by the Soundness and Completeness theorems of first-order logic. Now, imagine a statement that happens to be true for our standard numbers $\mathbb{N}$, but is false in one of those weird nonstandard models. What can we say about it? Since it's not true in all models of PA, it cannot be provable from the axioms of PA!. These nonstandard models give us a powerful tool to show that certain truths are, in fact, unprovable.

This leads us directly to the doorstep of Kurt Gödel and his famous ​​Incompleteness Theorems​​. What Gödel showed is that for any consistent, formal system like PA that is strong enough to do basic arithmetic, there will always be statements that are true in the standard model but are unprovable within the system. PA is incomplete. It cannot capture all the truths about the natural numbers.

The final, humbling conclusion is perhaps the most famous. Consider the statement "Peano Arithmetic is consistent" (which we can write as a complex formula, $\operatorname{Con}(PA)$). We certainly believe this is true. Indeed, from within a more powerful theory like Zermelo-Fraenkel set theory (ZFC), we can construct the standard model $\mathbb{N}$ and verify that it satisfies all the axioms of PA. Since PA has a model, it must be consistent, and ZFC can formally prove this: $\mathrm{ZFC} \vdash \operatorname{Con}(PA)$. But Gödel's Second Incompleteness Theorem shows that PA itself, if it is consistent, cannot prove its own consistency. A system cannot use its own rules to provide an absolute guarantee of its own reliability.

Our attempt to build a perfect, complete, and self-verifying system for arithmetic has led us to a fundamental discovery about the limits of formal reasoning itself. We set out to capture the simple truths of numbers and ended up staring into the abyss of the unprovable. And that, in a nutshell, is the enduring beauty and power of mathematical logic.

We have spent some time laying down the axioms of Peano Arithmetic, like a child carefully setting up a line of dominoes. We defined the language, the rules of the game, and the principle of induction. At first glance, it seems a rather sterile exercise—a formal description of what we learned in elementary school: counting, adding, and multiplying. But now, we are ready to tip the first domino and watch. What we will see is not a simple, linear cascade, but an explosive, branching chain reaction that tears through the foundations of mathematics, computer science, and philosophy. The study of these simple axioms, it turns out, is the study of the very limits of thought itself.

One of the first startling discoveries is that Peano Arithmetic (PA) is not just about numbers; it’s about computation. Any process that you can describe as a clear, step-by-step mechanical procedure—what we call an algorithm—can be mirrored and simulated within the language of PA.

Think of a simple computer program. It takes inputs, follows a sequence of operations, and produces an output. We can do the same in PA. For a vast class of computable functions known as "primitive recursive functions" (which covers most algorithms you'd ever think of writing), we can construct a formula in the language of arithmetic that perfectly represents the function's graph. This formula, let’s call it $\varphi_f(\vec{x}, y)$, acts as a logical stand-in for the statement "$y$ is the result of computing the function $f$ on inputs $\vec{x}$". This is not just a loose analogy. PA is powerful enough to prove that for any input $\vec{x}$, there exists a unique output $y$ that satisfies the formula.

This extends beyond functions to properties, or relations. Consider the relation "$x$ divides $y$". We can define its characteristic function, which outputs $1$ if the relation holds and $0$ if it doesn't. This function is primitive recursive, and therefore, the property of divisibility can be captured perfectly by a formula in PA. The formula that does this, $\exists z \le y (x \cdot z = y)$, is remarkably simple. It states that "$x$ divides $y$" is true if you can find a number $z$ (no bigger than $y$) such that $x$ times $z$ equals $y$. The fact that we only need to search up to $y$ (a bounded quantifier) is a key reason why this property is so straightforward for PA to handle.

What gives PA this extraordinary power? The secret ingredient is its full-blown axiom schema of induction. Weaker systems of arithmetic exist, but PA's induction applies to any property definable by a formula in its language, no matter how complex. This allows PA to prove the totality of functions whose very definition involves searching for things, or asserting that "there exists" some object, like a code for a computation.

The ultimate testament to this power is the famous Ackermann function. It is a total computable function, but it grows so mind-bogglingly fast that it is not primitive recursive—it outpaces any function definable by simple nested loops. You can't write a "for" loop to compute it without using a stack that can grow. Yet, using a clever nested induction—an induction inside an induction—PA can prove that the Ackermann function is total, that it always halts and gives a value for any pair of natural numbers. PA is, in a sense, a powerful "universal computer" expressed in the austere language of logic.

Having been amazed by PA's power to contain the world of computation, we naturally ask: what are its limits? Can it capture everything? And here, the story takes a dramatic turn. The exploration of PA's boundaries leads to some of the deepest results in modern logic.

​​The Problem of Truth​​

Let's start with a simple-sounding question: Can PA define its own notion of truth? That is, can we write a formula, let's call it $T(x)$, which is true if and only if $x$ is the Gödel number (a code) of a true sentence of arithmetic?

For a moment, it seems possible. If we restrict ourselves to a very simple part of the language—the so-called $\Delta_0$ formulas, where all quantifiers are bounded (e.g., "for all $x \lt 100$...")—then the answer is yes! We can write a formula $T_{\Delta_0}(x)$ that perfectly checks the truth of any $\Delta_0$ sentence. It works because checking such a sentence never requires an infinite search; we only ever have to check a finite number of cases.

But this is a false dawn. The moment we allow unbounded quantifiers ("for all $x$...") in our language, the whole project collapses. Alfred Tarski proved that for any language rich enough to talk about its own syntax (like the language of PA), a truth predicate for that language is undefinable within the language itself. The proof is a brilliant formalization of the ancient Liar's Paradox. Using a beautiful device called the Diagonal Lemma, one can construct a sentence $\lambda$ which effectively says, "This sentence is not true" or, more formally, $\lambda \leftrightarrow \neg T(\ulcorner \lambda \urcorner)$. If such a truth predicate $T(x)$ existed, this sentence would be true if and only if it were false—a logical impossibility. The conclusion is inescapable: the semantic notion of truth in arithmetic is a richer, higher-level concept that cannot be fully captured within arithmetic. We must always step outside the system to talk about its truth.

​​The Problem of Proof​​

So we can't define truth. But perhaps we can still prove all true statements? This was a central plank of Hilbert's program: to find a complete and consistent set of axioms for all of mathematics. Gödel's First Incompleteness Theorem shattered this dream.

It is crucial here to distinguish two kinds of "completeness". The underlying logical system we use, first-order logic, is indeed complete in its own way: Gödel's Completeness Theorem says that any sentence that is logically valid (true in every possible universe) is provable. But any specific, sufficiently powerful axiomatic theory written in that logic, like PA, is doomed to be incomplete. Gödel showed that as long as PA is consistent, there will be sentences that are true in the standard model of the natural numbers but which PA can never prove.

For a long time, these "undecidable" sentences seemed like artificial, self-referential paradoxes. But in 1977, Jeff Paris and Leo Harrington discovered a "natural" undecidable statement. The Paris–Harrington principle is a small variation on a well-known result in combinatorics called the finite Ramsey theorem. It's a statement about coloring sets of numbers, and it is demonstrably true. Yet, PA cannot prove it. Why? The reason is even more profound. It turns out that the Paris–Harrington principle is strong enough to imply the consistency of PA itself. And by Gödel's Second Incompleteness Theorem, no sufficiently strong, consistent theory can prove its own consistency. The system cannot, from within its own resources, vouch for its own sanity.

The incompleteness of PA has another bizarre and wonderful consequence. If the axioms don't pin down all the truths about the natural numbers, do they at least pin down the world of the natural numbers? Do the axioms force a unique structure? The answer is a resounding no.

Because PA is a first-order theory, it is subject to the powerful Löwenheim–Skolem and Compactness theorems of model theory. These theorems imply that if PA has its intended model ($\mathbb{N}$), it must also have other, "nonstandard" models that are not isomorphic to it. There are strange universes that satisfy every single axiom of PA, but which contain "infinite" numbers—numbers larger than any standard integer $0, 1, 2, \dots$.

In these nonstandard models, the standard numbers we know and love form a perfect initial copy of $\mathbb{N}$. But this copy does not exhaust the model. There are other numbers "beyond infinity." How can this be, if we have the axiom of induction? Induction tells us that any property that holds for $0$ and is passed from any number to its successor must hold for all numbers. But here is the catch: the induction schema of first-order PA only applies to properties that are definable by a formula in the language of PA. The set of standard numbers, while a perfectly good set from our external perspective, is not definable within the model. It is an "external" property. Therefore, induction simply flies over it, unable to "see" it and conclude that it is the whole model.

This phenomenon represents a deep limitation of first-order logic and a failure of Hilbert's dream of a categorical formalization—a system that describes one, and only one, mathematical structure. We can, in fact, achieve categoricity for arithmetic by moving to a more powerful framework called second-order logic. But this move comes at a terrible price. In second-order logic, we lose the completeness of the deductive system itself. We sacrifice a universal, mechanical proof-checking procedure, which was another of Hilbert's most cherished goals. We are faced with a fundamental trade-off: we can either have a unique intended model, or we can have a complete proof system, but we cannot have both.

The journey through Peano Arithmetic is a perfect parable for the scientific enterprise. We start with simple, self-evident rules for a familiar world. We discover they have unexpected power, allowing us to model vast domains of computation. But as we push against the boundaries, we find that our system is not the master key we had hoped for. It is incomplete, unable to capture all truths or even to prove its own consistency. It is not even capable of describing a single, unambiguous reality.

But these are not failures. They are the most profound discoveries. They teach us that truth is a more elusive concept than proof, that semantics will always transcend syntax, and that our formal systems, no matter how powerful, are imperfect mirrors of the mathematical reality they seek to describe. The fact that a system designed to formalize the simple act of counting could lead us to the very heart of these deep philosophical questions is a testament to the incredible, interconnected beauty of mathematics.