Gödel numbering lets math statements talk about themselves

Gödel numbering – Kurt Gödel’s incompleteness theorems hinge on a deceptively concrete idea: assign a unique number—now called a Gödel number—to every mathematical statement. That makes it possible to turn proofs and axioms into arithmetic questions, including a statement that

Last week, the story ended with a promise mathematics couldn’t keep: there would always be questions a formal system could not answer. This week, the mechanism behind that break comes into view—one that starts with numbers you can calculate.

Kurt Gödel. a then 25-year-old logician. showed that even as experts tried to build a seemingly firm foundation for all mathematics. the effort would never settle every question. The result is famous for what it took away—completeness—but even more remarkable for how it was achieved. Gödel found a way to make a mathematical system talk about its own capabilities while staying inside the rules of that same system.

He did that in a way mathematicians had never managed before. Gödel used the computational rules and logical inferences that follow from the foundational axioms of mathematics—Zermelo-Fraenkel set theory with the axiom of choice. commonly written as ZFC—to produce statements about that system itself.

The route ran through encoding. Gödel developed an approach that assigns a unique number to each mathematical statement. The coding idea can sound abstract until you see how it’s constructed. Gödel assigned the numbers 1 through 12 to the 12 basic logical operations. including operations like “plus” and the logical operator “OR.” Variables such as m or n were matched to prime numbers larger than 12.

If you now build a statement from those 12 operations and some variables, the corresponding code number can be calculated. A simple example makes the point. For the statement “0 + 0 = 0. ” the necessary Gödel numbers are 0 for the first “0. ” “+” for the plus sign. and “=” for the equals sign. Those become 6, 11, and 5. The sequence 6, 11, 6, 5, 6 stands in for “0 + 0 = 0.”.

But here’s the part that matters: just lining up the digits and forming “611656” does not work. The coding could fit too neatly to other interpretations, such as 6, 1, 1, 6, 5, 6, which correspond to “0 NOT NOT 0 = 0.”

To prevent that kind of ambiguity, Gödel’s method used prime factorization. Any number can be uniquely broken down into its prime factors—like 12 = 2^2 × 3. To encode a statement built from n Gödel numbers. Gödel multiplied the first n prime numbers together. raising each prime to the power of the corresponding Gödel number.

For the example with Gödel numbers 6, 11, 6, 5, 6, the coding becomes 2^6 × 3^11 × 5^6 × 7^5 × 11^6. In this scheme, each statement maps to a number that can be decoded unambiguously back into the original statement.

A language for arithmetic truths

Once statements can be expressed as numbers, the rest follows with the ordinary tools of mathematics. If Gödel encodes axioms and a statement, then it becomes possible to use arithmetic operations to check whether that statement can be proved using the axioms.

That’s the core stroke of genius: Gödel didn’t just translate mathematics into numbers. He arranged it so the system could make a statement about itself.

He managed to formulate a statement G that reads: “The statement G cannot be proved.” From there the logic turns sharp. Suppose G is false. Then the negation of G holds: “The statement G can be proved.” But if that’s true. then G must be true. That contradiction comes directly from assuming G was false in the first place.

So G has to be true. Yet in this case, G cannot be proved. The consequence for axiomatic systems is stark. If an axiom system is free of contradictions, then there are necessarily true but unprovable statements. In other words, the foundation of mathematics is necessarily incomplete.

And that doesn’t depend on just one particular set of axioms. Gödel’s seminal work also shows this kind of incompleteness holds for all axiom systems—not only for ZFC.

The takeaway is easy to misread. Gödel’s conclusion doesn’t mean there are problems that are neither false nor true. The limitation is about provability: they are not always provable, even when they are true.

This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission. It was translated from the original German version with the assistance of artificial intelligence and reviewed by our editors.

If there’s a human feeling threaded through the math here, it’s the sense that a clean dream has been barred from the start. Gödel’s numbering method doesn’t just break a theorem—it shows how a system can be made to face a mirror, and then watch the mirror refuse to answer everything it reflects.

Science doesn’t always get to keep its promises. Sometimes, as with Gödel, the best it can do is be honest about what can’t be finished.

Gödel numbering incompleteness theorems Kurt Gödel ZFC formal systems mathematical logic prime factorization self-reference