How Gödel numbers turn mathematical laws against themselves
How Gödel numbers let you do math with math itself By encoding mathematical statements into numbers, mathematician Kurt Gödel used ordinary arithmetic to check whether a statement can be proved This article is from Proof Positive , our friendly math newsletter that's delivered
By encoding mathematical statements into numbers, mathematician Kurt Gödel used ordinary arithmetic to check whether a statement can be proved
This article is from Proof Positive , our friendly math newsletter that's delivered to your inbox every Tuesday afternoon. Sign up today and read it first.
Last week I explained how a then 25-year-old logician, Kurt Gödel, overturned a basic assumption of many mathematicians in the early 20th century. Even as experts were building a seemingly firm foundation for all mathematics, Gödel demonstrated that this effort would never answer every question.
If you're enjoying this article, consider supporting our award-winning journalism by subscribing . By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
Gödel’s incompleteness theorems are among the most fascinating results in mathematics. They have revolutionized the subject—and disillusioned scientists. But in addition to their far-reaching consequences, his ideas fascinated his colleagues by being able to say something about the capabilities of a mathematical system while operating within that system.
That is, Gödel used the computational rules and logical inferences that follow from the foundational axioms of mathematics (the Zermelo-Fraenkel set theory with the axiom of choice, or ZFC) to make statements about that system itself. This was a brilliant feat that no one had ever accomplished before.
To do this, he developed an approach that involved assigning a unique number to each mathematical statement. Instead of writing, for example, “for every number m , there is another number n greater than m ,” he defined a corresponding natural number (which is very large) from which the statement could be derived. The coding is not even that complicated: Gödel assigned the so-called Gödel numbers 1 to 12 to the 12 basic logical operations such as “plus” or the logical operator “OR.” Variables such as m or n corresponded to prime numbers larger than 12.
If you now form a statement from the 12 operations and some variables, the corresponding code number can be calculated quickly. For example: For the statement 0 + 0 = 0, you need the Gödel numbers 0, + and =. These are 6, 11 and 5. Now this must succeed in transforming the series 6, 11, 6, 5, 6 (which stands for 0 + 0 = 0) into a number, from which one can unambiguously decode the original statement. Simply lining up the digits and forming “611656” does not work because the coding could fit also to the Gödel numbers 6, 1, 1, 6, 5, 6, which correspond to the statement 0 NOT NOT 0 = 0.
