Analysis and impact
哥德尔证明的核心技巧是"哥德尔编码"——为每一个数学符号、公式和证明序列分配一个唯一的自然数。这样一来，关于数学命题的元数学陈述（比如"某个公式可以被证明"）本身也能被翻译成算术命题。哥德尔随后构造了一个命题 G，其含义大致是"G 在系统内不可证"。如果 G 可证，则系统证明了假命题，说明系统不一致；如果 G 不可证，则 G 为真但系统无法证明它，说明系统不完备。无论哪种情况，系统都无法同时满足一致性与完备性。来源
这一结果对数学基础产生了深远影响。它终结了希尔伯特纲领中"用有限方法证明数学系统一致且完备"的雄心，也意味着任何包含基本算术的形式系统都存在"真但不可证"的命题。文章强调，哥德尔的证明并非否定数学的可靠性，而是划定了形式化方法的边界：数学真理的集合严格大于任何给定公理系统所能证明的命题集合。来源
值得注意的是，哥德尔不完备定理的影响早已超出纯数学范畴。在当代人工智能研究中，形式系统的局限性问题以新的面貌出现。例如，近期有研究探讨大语言模型的安全对齐在非英语语境下是否依然有效，发现同一模型面对日语提问时可能给出与英语完全不同的风险建议。来源 另一项立场论文则主张，AI 对齐方法需要更贴近人类推理的实际过程，而非依赖单一形式化框架。来源 这些工作虽与哥德尔定理相隔近一个世纪，但共享同一个深层关切：任何封闭的形式系统——无论是公理化数学还是基于统计的语言模型——都存在其内在的表达与验证边界。原文未提供哥德尔定理与这些 AI 研究之间的直接关联论证，上述联系仅为背景延伸。
References
Original source text
Home
How Gödel’s Proof Works
Comment
Save Article
Read Later
Share
Copied!
Copy link
Ycombinator
-
Comment
Comments
-
Save Article Read Later
Read Later
How Gödel’s Proof Works
By *
Natalie Wolchover
July 14, 2020
His incompleteness theorems destroyed the search for a mathematical theory of everything. Nearly a century later, we’re still coming to grips with the consequences.
Comment
Save Article
Read Later
Every mathematical system will have some statements that can never be proved.
Olena Shmahalo/Quanta Magazine
Introduction
In 1931, the Austrian logician Kurt Gödel pulled off arguably one of the most stunning intellectual achievements in history.
Mathematicians of the era sought a solid foundation for mathematics: a set of basic mathematical facts, or axioms, that was both consistent — never leading to contradictions — and complete, serving as the building blocks of all mathematical truths.
But Gödel’s shocking incompleteness theorems, published when he was just 25, crushed that dream. He proved that any set of axioms you could posit as a possible foundation for math will inevitably be incomplete; there will always be true facts about numbers that cannot be proved by those axioms. He also showed that no candidate set of axioms can ever prove its own consistency.
His incompleteness theorems meant there can be no mathematical theory of everything, no unification of what’s provable and what’s true. What mathematicians can prove depends on their starting assumptions, not on any fundamental ground truth from which all answers spring.
In the 89 years since Gödel’s discovery, mathematicians have stumbled upon just the kinds of unanswerable questions his theorems foretold. For example, Gödel himself helped establish that the continuum hypothesis, which concerns the sizes of infinity, is undecidable, as is the halting problem, which asks whether a computer program fed with a random input will run forever or eventually halt. Undecidable questions have even arisen in physics, suggesting that Gödelian incompleteness afflicts not just math, but — in some ill-understood way — reality.
Here’s a simplified, informal rundown of how Gödel proved his theorems.
Gödel Numbering
Gödel’s main maneuver was to map statements about a system of axioms onto statements within the system — that is, onto statements about numbers. This mapping allows a system of axioms to talk cogently about itself.
The first step in this process is to map any possible mathematical statement, or series of statements, to a unique number called a Gödel number.
The slightly modified version of Gödel’s scheme presented by Ernest Nagel and James Newman in their 1958 book, Gödel’s Proof, begins with 12 elementary symbols that serve as the vocabulary for expressing a set of basic axioms. For example, the statement that something exists can be expressed by the symbol ∃, while addition is expressed by +. Importantly, the symbol s, denoting “successor of,” gives a way of specifying numbers; ss0, for example, refers to 2.
These twelve symbols then get assigned the Gödel numbers 1 through 12.
Constant sign Gödel number Usual Meaning
~ 1 not
∨ 2 or
⊃ 3 if…then…
∃ 4 there is an…
= 5 equals
0 6 zero
s 7 the successor of
( 8 punctuation mark
) 9 punctuation mark
, 10 punctuation mark
-
11 plus
× 12 times
Next, letters representing variables, starting with x, y and z, map onto prime numbers greater than 12 (that is, 13, 17, 19, …).
Then any combination of these symbols and variables — that is, any arithmetical formula or sequence of formulas that can be constructed — gets its own Gödel number.
For example, consider 0 = 0. The formula’s three symbols correspond to Gödel numbers 6, 5 and 6. Gödel needs to change this three-number sequence into a single, unique number — a number that no other sequence of symbols will generate. To do this, he takes the first three primes (2, 3 and 5), raises each to the Gödel number of the symbol in the same position in the sequence, and multiplies them together. Thus 0 = 0 becomes 2 6 × 3 5 × 5 6 , or 243,000,000.
The mapping works because no two formulas will ever end up with the same Gödel number. Gödel numbers are integers, and integers only factor into primes in a single way. So the only prime factorization of 243,000,000 is 2 6 × 3 5 × 5 6 , meaning there’s only one possible way to decode the Gödel number: the formula 0 = 0.
Gödel then went one step further. A mathematical proof consists of a sequence of formulas. So Gödel gave every sequence of formulas a unique Gödel number too. In this case, he starts with the list of prime numbers as before — 2, 3, 5 and so on. He then raises each prime to the Gödel number of the formula at the same position in the sequence (2 243,000,000 × …, if 0 = 0 comes first, for example) and multiplies everything together.
Arithmetizing Metamathematics
The real boon is that even statements about arithmetic formulas, called metamathematical statements, can themselves be translated into formulas with Gödel numbers of their own.
First consider the formula ~(0 = 0), meaning “zero does not equal zero.” This formula is clearly false. Nevertheless, it has a Gödel number: 2 raised to the power of 1 (the Gödel number of the symbol ~), multiplied by 3 raised to the power of 8 (the Gödel number of the “open parenthesis” symbol), and so on, yielding 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 .
Because we can generate Gödel numbers for all formulas, even false ones, we can talk sensibly about these formulas by talking about their Gödel numbers.
Consider the statement, “The first symbol of the formula ~(0 = 0) is a tilde.” This (true) metamathematical statement about ~(0 = 0) translates into a statement about the formula’s Gödel number — namely, that its first exponent is 1, the Gödel number for a tilde. In other words, our statement says that 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 has only a single factor of 2. Had ~(0 = 0) begun with any symbol other than a tilde, its Gödel number would have at least two factors of 2. So, more precisely, 2 is a factor of 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 , but 2 2 is not a factor.
We can convert the last sentence into a precise arithmetical formula that we can write down * using elementary symbols. This formula of course has a Gödel number, which we could calculate by mapping its symbols onto powers of primes.
This example, Nagel and Newman wrote, “exemplifies a very general and deep insight that lies at the heart of Gödel’s discovery: typographical properties of long chains of symbols can be talked about in an indirect but perfectly accurate manner by instead talking about the properties of prime factorizations of large integers.”
Conversion into symbols is also possible for the metamathematical statement, “There exists some sequence of formulas with Gödel number x that proves the formula with Gödel number k” — or, in short, “The formula with Gödel number k can be proved.” The ability to “arithmetize” this kind of statement set the stage for the coup.
G Itself
Gödel’s extra insight was that he could substitute a formula’s own Gödel number in the formula itself, leading to no end of trouble.
To see how substitution works, consider the formula (∃x)(x = sy). (It reads, “There exists some variable x that is the successor of y,” or, in short, “y has a successor.”) Like all formulas, it has a Gödel number — some large integer we’ll just call m.
Now let’s introduce m into the formula in place of the symbol y. This forms a new formula, (∃x)(x = sm), meaning, “m has a successor.” What shall we call this formula’s Gödel number? There are three pieces of information to convey: We started with the formula that has Gödel number m. In it, we substituted m for the symbol y. And according to the mapping scheme introduced earlier, the symbol y has the Gödel number 17. So let’s designate the new formula’s Gödel number sub(m, m, 17).
Substitution forms the crux of Gödel’s proof.
He considered a metamathematical statement along the lines of “The formula with Gödel number sub(y, y, 17) cannot be proved.” Recalling the notation we just learned, the formula with Gödel number sub(y, y, 17) is the one obtained by taking the formula with Gödel number y (some unknown variable) and substituting this variable y anywhere there’s a symbol whose Gödel number is 17 (that is, anywhere there’s a y).
Things are getting trippy, but nevertheless, our metamathematical statement — “The formula with Gödel number sub(y, y, 17) cannot be proved” — is sure to translate into a formula with a unique Gödel number. Let’s call it n.
Now, one last round of substitution: Gödel creates a new formula by substituting the number n anywhere there’s a y in the previous formula. His new formula reads, “The formula with Gödel number sub(n, n, 17) cannot be proved.” Let’s call this new formula G.
Naturally, G has a Gödel number. What’s its value? Lo and behold, it must be sub(n, n, 17). By definition, sub(n, n, 17) is the Gödel number of the formula that results from taking the formula with Gödel number n and substituting n anywhere there’s a symbol with Gödel number 17. And G is exactly this formula! Because of the uniqueness of prime factorization, we now see that the formula G is talking about is none other than G itself.
G asserts of itself that it can’t be proved.
But can G be proved? If so, this would mean there’s some sequence of formulas that proves the formula with Gödel number sub(n, n, 17). But that’s the opposite of G, which says no such proof exists. Opposite statements, G and ~G, can’t both be true in a consistent axiomatic system. So the truth of G must be undecidable.
However, although G is undecidable, it’s clearly true. G says, “The formula with Gödel number sub(n, n, 17) cannot be proved,” and that’s exactly what we’ve found to be the case! Since G is true yet undecidable within the axiomatic system used to construct it, that system is incomplete.
You might think you could just posit some extra axiom, use it to prove G, and resolve the paradox. But you can’t. Gödel showed that the augmented axiomatic system will allow the construction of a new, true formula Gʹ (according to a similar blueprint as before) that can’t be proved within the new, augmented system. In striving for a complete mathematical system, you can never catch your own tail.
No Proof of Consistency
We’ve learned that if a set of axioms is consistent, then it is incomplete. That’s Gödel’s first incompleteness theorem. The second — that no set of axioms can prove its own consistency — easily follows.
What would it mean if a set of axioms could prove it will never yield a contradiction? It would mean that there exists a sequence of formulas built from these axioms that proves the formula that means, metamathematically, “This set of axioms is consistent.” By the first theorem, this set of axioms would then necessarily be incomplete.
But “The set of axioms is incomplete” is the same as saying, “There is a true formula that cannot be proved.” This statement is equivalent to our formula G. And we know the axioms can’t prove G.
So Gödel has created a proof by contradiction: If a set of axioms could prove its own consistency, then we would be able to prove G. But we can’t. Therefore, no set of axioms can prove its own consistency.
Gödel’s proof killed the search for a consistent, complete mathematical system. The meaning of incompleteness “has not been fully fathomed,” Nagel and Newman wrote in 1958. It remains true today.
For the curious, the statement reads: “There exists some integer x such that x multiplied by 2 is equal to 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 , and there does not exist any integer x such that x multiplied by 4 is equal to 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 .” The corresponding formula is:
(∃x)(x × ss0 = sss … sss0) ⋅ ~(∃x)(x × ssss0 = sss … sss0)
where sss … sss0 stands for 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 copies of the successor symbol s. The symbol ⋅ means “and,” and is shorthand for a longer expression in the fundamental vocabulary: p ⋅ q stands for ~(~p ∨ ~q). [Back to article.]
This article was reprinted on Wired.com.
The Quanta Newsletter
Get highlights of the most important news delivered to your email inbox
Also in Abstractions blog
Scientists Find a Fast Way to Describe Quantum Systems
Scientists Find a Fast Way to Describe Quantum Systems
By *
Lakshmi Chandrasekaran
May 1, 2024
Comment
Save Article
Read Later
Mathematicians Marvel at ‘Crazy’ Cuts Through Four Dimensions
Mathematicians Marvel at ‘Crazy’ Cuts Through Four Dimensions
By *
Jordana Cepelewicz
April 22, 2024
Comment
Save Article
Read Later
Insects and Other Animals Have Consciousness, Experts Declare
Insects and Other Animals Have Consciousness, Experts Declare
By *
Dan Falk
April 19, 2024
Comment
Save Article
Read Later
Comment on this article
Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English.
Show comments
Next article
The Math of Social Distancing Is a Lesson in Geometry