Peano Arithmetic

What if you could rebuild the entire universe of numbers from scratch? Peano Arithmetic (PA) represents one of the most significant attempts in modern mathematics to do just that—to establish a rigorous, formal foundation for the natural numbers and their properties. While our intuitive understanding of counting and addition seems simple, creating a logical system that captures this intuition without contradiction or ambiguity is a profound challenge. This article addresses this foundational quest, exploring how a few simple axioms can give rise to a system powerful enough to describe all of computation, yet is ultimately, and fascinatingly, incomplete.

In the following chapters, we will embark on a journey into the heart of mathematical logic. The "Principles and Mechanisms" chapter will lay down the building blocks of Peano Arithmetic, from its basic language to the powerful induction schema, and reveal how it can simulate any computer program. Subsequently, the "Applications and Interdisciplinary Connections" chapter will explore the stunning consequences of this power, delving into Gödel's incompleteness theorems, the limits of computability, and the new fields of logic that arose from discovering the boundaries of mathematical proof.

Imagine you are given a box of LEGOs, but not just any box. This one contains only the most elementary pieces imaginable, and your task is to construct the entire universe of numbers. Not just to build them, but to write down the unshakeable rules that govern their every interaction, from the simplest addition to the most complex theorems. This is the spirit of Peano Arithmetic (PA)—a quest to capture the essence of the natural numbers, $\{0, 1, 2, \dots\}$, in a formal, logical system. But as we shall see, this seemingly straightforward task leads us to some of the most profound and strange discoveries in all of mathematics.

Before we can state any rules, we need a language. The language of Peano Arithmetic is beautifully sparse. We have symbols for just a few fundamental ideas:

• A constant, $0$, to get us started.
• A unary function, $S$, for "successor". Think of it as the "+1" operation.
• Two binary functions, $+$ for addition and $\cdot$ for multiplication.

With these, we can construct the name for any natural number. The number we call '3' is, in this language, the term $S(S(S(0)))$. We call these formal terms ​​numerals​​. This distinction between a number (an abstract idea) and its numeral (its name in the formal system) is crucial. It’s like the difference between the person Richard Feynman and the string of letters "Richard Feynman". One is a living, breathing entity; the other is a symbol that represents him. Arithmetization, the process of making mathematics talk about itself, hinges on this ability to manipulate names within the system.

With our language in hand, we can lay down the first, most basic axioms. These axioms, which form a weak system known as ​​Robinson Arithmetic (Q)​​, are essentially the instruction manual for our symbols. They state obvious truths, such as:

• $0$ is not the successor of any number: $\forall x (S(x) \neq 0)$.
• If two numbers have the same successor, they are the same number: $\forall x \forall y (S(x) = S(y) \rightarrow x = y)$.
• Rules for addition: $\forall x (x + 0 = x)$ and $\forall x \forall y (x + S(y) = S(x+y))$.
• Rules for multiplication: $\forall x (x \cdot 0 = 0)$ and $\forall x \forall y (x \cdot S(y) = (x \cdot y) + x)$.

This system, Q, is sensible. It can prove simple facts like $\overline{2} + \overline{2} = \overline{4}$. But it is surprisingly feeble. It is so weak, in fact, that it cannot prove the general statement that addition is commutative, $\forall x \forall y (x+y = y+x)$. It can verify every specific instance you give it, but it cannot grasp the universal principle. To do that, we need a far more powerful tool.

The true engine of Peano Arithmetic, the ingredient that elevates it from a simple calculator to a powerful deductive system, is the ​​Principle of Mathematical Induction​​. You probably know the intuitive idea: if you have a line of dominoes, and you know that (1) you can knock over the first domino, and (2) knocking over any domino will always knock over the next one, then you can be sure that all the dominoes will fall.

In Peano Arithmetic, this isn't a single axiom but an infinite ​​axiom schema​​. It says that for any property you can possibly state in the language of arithmetic, if you can prove it's true for $0$, and you can prove that if it's true for some number $x$, then it must also be true for its successor $S(x)$, then you can conclude it is true for all numbers.

Formally, for any formula $\varphi(x)$: $(\varphi(0) \land \forall x (\varphi(x) \rightarrow \varphi(S(x)))) \rightarrow \forall x \varphi(x)$

This schema is what gives PA its strength. With induction, we can finally prove that addition is commutative, that multiplication distributes over addition, and countless other foundational properties of arithmetic that are completely beyond the reach of Robinson Arithmetic. It is the mechanism that allows PA to move from checking individual cases to proving universal truths.

Now we have a system, PA, that seems to fully capture our intuitions about numbers. But its true power lies not just in proving facts about numbers, but in its ability to reason about something else entirely: ​​computation​​.

The central concept here is ​​representability​​. We say a function $f(x)$ is representable in PA if we can write a formula $\varphi_f(x,y)$ that acts as a perfect checker for it. That is, for any numbers $n$ and $m$, if $f(n)=m$, then PA can prove the statement $\varphi_f(\bar{n}, \bar{m})$. Moreover, for any input $\bar{n}$, PA can prove that there exists a unique output $y$ that satisfies the formula.

In one of the great triumphs of modern logic, it was shown that every ​​computable function​​—that is, any function for which you could write a computer program—is representable in PA. This is a staggering claim. How can a simple system of arithmetic mimic any possible algorithm?

The key insight, due to Kurt Gödel, is a brilliant trick for encoding information. It turns out that you can encode an entire sequence of computational steps—the full history of a program's execution—as a single, gigantic natural number. Then, you can create a formula in PA that essentially says, "There exists a number that encodes a valid step-by-step computation of function $f$ starting with input $x$ and ending with output $y$." Because all the rules for checking this computation (Is the initial state correct? Does each step legally follow from the previous one?) are simple and mechanical, they can be expressed using just the basic $+$, $\cdot$, and logical quantifiers of PA.

This process, known as ​​arithmetization​​, turns statements about algorithms into statements about numbers. PA, by reasoning about numbers, can now reason about the behavior of any computer program. This is the bridge that leads directly to Gödel's famous incompleteness theorems.

Just as we reach the pinnacle of PA's power, we stumble upon a crack in its foundations. We think we have written down the definitive rules for the natural numbers, $\{0, 1, 2, \dots\}$. But have we?

The axioms of PA are formulated in ​​first-order logic​​, which means its quantifiers ($\forall$ "for all", $\exists$ "there exists") range over individual numbers, not over sets of numbers. This choice gives first-order logic some beautiful and powerful properties, most notably the ​​Compactness Theorem​​. This theorem states that if every finite subset of a (possibly infinite) list of axioms has a model, then the whole list must have a model.

We can use this theorem to play a devilish trick on Peano Arithmetic. Consider the standard axioms of PA. Let's add a new constant symbol, $c$, to our language. Now, let's add an infinite list of new axioms:

• $c > \overline{1}$
• $c > \overline{2}$
• $c > \overline{3}$
• ...and so on, for every natural number.

Does this new, infinitely long list of axioms have a model? According to the Compactness Theorem, we only need to check if every finite subset has a model. Pick any finite collection of these new axioms. It will look something like $\{c > \overline{10}, c > \overline{42}, c > \overline{1000}\}$. We can easily find a model for this finite set: just use the ordinary natural numbers and interpret $c$ to be, say, $1001$. It satisfies all the axioms of PA and the few axioms about $c$ that we picked.

Since every finite subset is satisfiable, the entire infinite set must be satisfiable. This means there exists a mathematical structure—a ​​non-standard model of arithmetic​​—that satisfies all the axioms of PA, but which contains a "number" $c$ that is larger than every standard natural number. This model contains our familiar numbers as an initial segment, but it also contains other "number lines" of strange, infinite elements that stretch out beyond them.

But wait! How can this be? Doesn't the axiom of induction guarantee that everything that is true for 0 and is passed from $n$ to $n+1$ must be true for all numbers? Shouldn't that get rid of these strange, unreachable numbers? The subtle answer is no. The first-order induction schema only applies to properties that can be defined by a formula in the language of PA. The property of "being a standard number" cannot be defined in this way. The dominoes of induction knock over all the numbers in any given "number line" in the model, but they can't jump across the infinite gaps to the non-standard ones.

This reveals a fundamental trade-off. By using first-order logic, we get powerful tools like the Compactness and Completeness theorems, but we lose the ability to uniquely "pin down" the structure of the natural numbers. If we were to use ​​second-order logic​​, where we can quantify over all sets of numbers, we could write an induction axiom so powerful that it would rule out non-standard models. The resulting theory, second-order PA, is ​​categorical​​—it has only one model up to isomorphism. But in doing so, we would lose the very completeness and compactness properties that make first-order logic so well-behaved.

The strange existence of non-standard models and the limits of first-order induction are not just mathematical curiosities. They are symptoms of a deeper limitation, one that mirrors a famous problem in the theory of computation: the ​​Halting Problem​​.

The Halting Problem asks: can you write a single computer program that, given any other program and its input, can decide whether that program will eventually halt or run forever? Alan Turing proved that such a universal verifier is impossible. There is no algorithm that can solve this for all cases. This isn't a limitation of our current technology or programming skill; it's a fundamental logical barrier. Rice's Theorem generalizes this even further, stating that any non-trivial property about what a program does (e.g., "Does this program ever output 42?") is undecidable.

The connection is this: Peano Arithmetic, through arithmetization, can talk about the behavior of programs. When a program halts, it does so in a finite number of steps, and PA is powerful enough to verify the existence of this finite computation history and prove that the program halts. But when a program runs forever, PA may not be able to prove it. Just as there are total computable functions whose totality PA cannot prove [@problem_id:2986074, Solution C], there are programs that never halt, but PA cannot prove they never halt.

The system we built is powerful enough to simulate any computation. It is so powerful, in fact, that it inherits the same fundamental limits of knowability that plague computation itself. The journey to formalize arithmetic did not lead to a complete and final foundation for all of mathematics. Instead, it led us to the edge of an unknowable horizon, a place where truth outruns proof. And that is the story we will explore next.

We have explored the beautiful, austere axioms of Peano Arithmetic ($PA$), a system designed to capture the essence of something as elementary as counting. It seems so simple, so self-contained. And yet, when we look closely, we find that this system is not just a description of numbers. It is a universe unto itself, with profound and often shocking connections to the deepest questions of logic, computation, and the very nature of truth. The applications of Peano Arithmetic are less about building bridges or circuits, and more about building—and discovering the limits of—the edifices of reason itself.

The first great leap is to realize that a theory of numbers can be made to talk about itself. How is this possible? The trick is ingenious, a bit of mathematical magic known as Gödel numbering. We can create a systematic code, a dictionary, that translates every symbol, every formula, and every chain of reasoning—every proof—into a unique natural number.

Imagine assigning a number to each letter of the alphabet: A=1, B=2, and so on. A word like "CAB" could become a number, perhaps through a scheme like $2^3 \cdot 3^1 \cdot 5^2$. This is a vast oversimplification, but the core idea is the same. Using the properties of prime numbers, we can encode any sequence of symbols into one number, and—crucially—we can decode it. A formula like "$\exists x (S(x) = 0)$" isn't just a string of ink on a page; it becomes a specific, gigantic integer. A proof, which is just a sequence of formulas, also becomes a single, even more gigantic, integer.

This is more than just labeling. Because Peano Arithmetic is a powerful theory about numbers, it can now, indirectly, reason about its own formulas and proofs. A syntactic question like "Is this sequence of formulas a valid proof?" transforms into a complex numerical question, something like "Does this number have a specific set of prime factors with specific exponents?" And because the rules of syntax and proof-checking are systematic and algorithmic, these numerical questions can be answered by functions that are themselves definable within Peano Arithmetic. Arithmetic has built a mirror. Now, what does it see?

What arithmetic sees in its mirror is both astonishing and humbling. It sees the very limits of what can be proven, what can be defined, and what can be computed.

First, it sees ​​Gödel's Incompleteness​​. By using Gödel numbering, we can construct a sentence, let's call it $G$, which asserts its own unprovability. It is a perfectly valid statement within the language of arithmetic that effectively says, "The formula with Gödel number $\ulcorner G \urcorner$ is not provable in Peano Arithmetic." We are then faced with a dizzying paradox. If we could prove $G$, then what $G$ says would be false (since it claims to be unprovable), meaning we've just proven a false statement! This would make PA inconsistent. On the other hand, if we cannot prove $G$, then what $G$ says is true. So, if PA is consistent, there must exist statements that are true but forever beyond the reach of proof within the system. This is not a failure of PA; it's a fundamental feature of any formal system powerful enough to look in the mirror. There will always be more truths than proofs.

Second, an even deeper chasm is revealed: ​​Tarski's Undefinability of Truth​​. We might be tempted to patch Gödel's problem by adding a "truth predicate," a formula $Tr(x)$ that is true if and only if $x$ is the Gödel number of a true sentence. Alfred Tarski showed this is impossible. If such a formula existed within the language of arithmetic, one could construct a new sentence—the Liar sentence, $L$—that asserts "The sentence with Gödel number $\ulcorner L \urcorner$ is not true." This leads to an inescapable contradiction: $L$ is true if and only if it is not true. The conclusion is stunning: while we can stand outside arithmetic (in what we call a metalanguage) and speak about which of its sentences are true, the language of arithmetic itself cannot contain its own concept of truth. Truth transcends provability, and it even transcends the language in which it is expressed.

These logical limits have a stark reflection in the world of ​​Theoretical Computer Science​​. Consider the question: "Can we write a computer program that can take any formal system, like PA, and determine if it's inconsistent (i.e., if it will ever prove a contradiction like $0=1$)?" This problem is deeply connected to Gödel's work. The set of all theorems of PA is "recursively enumerable," meaning a Turing machine could, in theory, list them all out one by one. Asking if $0=1$ will ever appear on this list is a decision problem. It turns out that this problem is equivalent to the famous Halting Problem—the problem of determining whether an arbitrary computer program will finish running or continue forever. And as Alan Turing proved, the Halting Problem is undecidable. There is no general algorithm that can solve it. Therefore, there can be no general algorithm to determine the consistency of a sufficiently strong formal system. The limits of proof are the limits of computation.

One might think this is a rather grim conclusion—that the house of mathematics is built on foundations we can't prove are sound, with truths we can't reach. But in science, a limitation is often the doorway to a new field of study. So it is with Peano Arithmetic.

​​Provability Logic:​​ If we can't have a theory of truth, perhaps we can have a theory of provability. This is the idea behind Provability Logic. We can use the language of modal logic, where a special symbol $\Box$ is placed before a statement $p$ to mean "p is provable." The astonishing discovery, made by Robert Solovay, is that all the universal principles of provability within PA can be perfectly and completely captured by a simple, elegant modal logic called GL. This logic includes axioms like $\Box(p \rightarrow q) \rightarrow (\Box p \rightarrow \Box q)$, which says that if you can prove an implication, and you can prove its premise, you can prove its conclusion. It also includes the strange and wonderful Löb's Axiom: $\Box(\Box p \rightarrow p) \rightarrow \Box p$. This logic, GL, provides a complete map, not of the entire landscape of arithmetic truth, but of the structure of its proofs. It's a beautiful example of finding order and completeness within a system known for its incompleteness.

​​Reverse Mathematics:​​ The discovery of PA's incompleteness and the existence of many different models led to a new kind of question. Instead of asking, "What can we prove from these axioms?", mathematicians began to ask, "Given this famous theorem of mathematics, what is the weakest set of axioms needed to prove it?" This is the program of Reverse Mathematics. It takes the "zoo" of possible axiom systems—many of which are subsystems of a more general second-order arithmetic—and uses them to classify the logical strength of theorems from calculus, algebra, and combinatorics. The base system for this study, called $RCA_0$, is deeply connected to Peano Arithmetic and formalizes what might be called "computable mathematics." This field has transformed the study of foundations from a search for a single "true" foundation into a powerful tool for understanding the intricate connections between different areas of mathematics.

​​Models and Descriptive Set Theory:​​ Peano Arithmetic does not have just one interpretation—the familiar natural numbers $0, 1, 2, \dots$. It has a vast, uncountable infinity of "non-standard models." These are bizarre mathematical structures that satisfy all of PA's axioms but contain "infinite" numbers and can even have properties that defy our intuition, such as infinite descending sequences of numbers. Understanding the structure of this collection of all possible models of PA is a profound challenge. Here, logic connects with another advanced field: descriptive set theory, a branch of mathematical analysis that studies the complexity of sets of real numbers. By encoding each possible countable model of PA as a real number, mathematicians can use the powerful tools of analysis to classify the complexity of sets like "the set of all non-standard models." This work reveals a deep and unexpected unity, where questions about the foundations of arithmetic become high-level questions about the structure of the real number line.

From the simple act of counting, Peano Arithmetic takes us on an extraordinary journey. It shows us how a formal system can become self-aware, and in doing so, reveals its own limitations. But these limits are not walls; they are horizons. They have opened up new ways of thinking about proof, computation, truth, and the very structure of mathematical reality, showing that the most fundamental questions often lead to the most surprising and beautiful connections.