# How does Gödel’s encoding of mathematical statements into natural numbers enable self-referential propositions?

As part of his proof for the first incompleteness theorem, Gödel encoded mathematical expressions into unique numbers. These were used to construct statements exhibiting self-referentiality, such as his famous `'this statement cannot be proven'` one. In order to make self-referential statements using a numerical code, one can choose a number to represent an expression which already contains that number.

When Gödel uses the numbers as coded propositions, he is still fundamentally using the expression which the number represents. I don't see how this contributes anything useful. If one said that '2' represents 3 elephants, '3' represents 4 elephants, and ‘0’ represents 7 elephants, it would follow that 2 + 3 = 0. But this is not significant. The meaning of the numbers has been rearranged. The symbolically-transposed system of Gödel-numbering must work as ordinary logical and mathematical statements already work.

If Gödel numbering is nothing other than superficial symbolic substitution, why would it be indispensable, let alone relevant, towards the purpose of constructing special “self-referential” statements?

• In a nutshell, encoding means to assign number to basic symbols and define rules to compute numbers corresponding to formulas (strings of symbols) and derivations (sequences of formulas). Commented Feb 4 at 10:47
• See here and here for examples of encoding. Commented Feb 5 at 6:40
• But the key-point is not so much encoding, that is quite trivial: electronic computers use it everywhere because programs, i.e. computations, i.e. derivations are encoded with string of 0s and 1s (binary, hexadecimal). The key-point id the representability of relations with formal aritmetic. See also here. Commented Feb 5 at 6:44
• Without encoding how can you express and make use of provability in the self-referential Gödel sentence recursively constructed from the modified diagonal sequence of all provable statements within the formal system? OTOH, though encoding g is formally needed to define its represented Godel sentence G but conceptually encoding has not much to do with self-reference as you also claimed, diagonal lemma is crucial to enable it… Commented Feb 6 at 6:49
• @DoubleKnot Please add that as an answer, seems like you know precisely what the questioner is asking. Thank you. Commented Feb 6 at 17:38

As I have recently learned, the Gödel sentence was not originally "directly" self-referential. But first, then, here's what Gödel says about the matter in his introduction to his famous paper:

So it's like saying, "There is a sentence with seven words," and then noticing that that very sentence satisfies the description, rather than saying, "This is a sentence with seven words." For a "directly" self-referential Gödel coding, though, see Kripke[??]: "Nevertheless we propose a nonstandard Gödel numbering allowing a statement to contain a numeral designating its own Gödel number." See also Cheng[20], where it is asserted (e.g. pg. 22/sec. 3.4) that the Gödel sentence can be taken as a formalization of the liar or other paradoxes and following Gödel's own remark about epistemological antinomies (note that Cheng's essay is a broad, detailed overview of the state-of-the-art when it comes to analysis of the incompleteness theorems).

• Very nice answer but I’d love to see it elaborated on, i.e. more background filled in for someone new to the topic (such as myself). Thank you. Commented Feb 4 at 12:40
• Technically I was requesting the inverse: “did read; want longer” (dr;wl) 🙂. Commented Feb 4 at 19:19
• Very interesting, thank you! Personally the paper was a little dense for me so this is helpful Commented Feb 5 at 7:48

You ask: How does Gödel’s encoding of mathematical statements into natural numbers enable self-referential propositions? The short answer is, it doesn't.

A longer answer is to say, strictly speaking it doesn't, but it does enable a way to construct a sentence within the language of first-order arithmetic that in an indirect way can be thought of as stating something about itself. The emphasis here is on indirect. A sentence of this kind is a legitimate sentence of arithmetic. It is not directly self-referential or self-contradictory or paradoxical in any way.

The way this works is through a fixed-point theorem called the diagonal lemma. Suppose F is a formal system of arithmetic, φ(n) is a formula of arithmetic with n as a natural number parameter, χ is a sentence of arithmetic, and <χ> is the Gödel number of the sentence χ. Then the diagonal lemma assures us that

For every formula φ(n) there is a sentence χ such that φ(<χ>) if and only if F proves χ

This establishes a biconditional link between "φ(<χ>)" which is a sentence in first-order arithmetic, and "F proves χ", which is a metalanguage statement about the sentence χ. The sentence χ is not directly self-referential, but it is possible to understand it as indirectly stating of itself that it has the property φ.

As a corollary we can use this formalism to state some familiar theorems. Tarski's theorem on the undefinability of truth arises when we take φ(<χ>) to represent the property that χ is not true. Provided we accept bivalence, i.e. that sentences are always either true or false, and we accept Tarski's adequacy condition for truth:

'α' is true if and only if α

Then the diagonal lemma proves that any system of arithmetic F that satisfies this is inconsistent. Or stated contrapositively, any consistent theory of arithmetic cannot contain its own truth predicate satisfying this condition.

Gödel’s first incompleteness theorem arises when we understand φ(<χ>) to represent the property χ is not provable in F. In this case, we do not prove that F is inconsistent, but provided we assume that F is consistent, we get the result that there is some sentence of arithmetic that is neither provable nor disprovable in F.

In order to avoid afficionados squirming in their seats, I should add that I am talking here of formal systems of arithmetic that are recursively axiomatisable and sufficiently strong to include a significant amount of arithmetic. If we relax those conditions, then we can avoid the above results. I also assume the underlying logic is classical.

For a more detailed explanation of the above, you can download Peter Smith's free book.

• +1 Highlighting the metalanguage/object language distinction (and for the usual ease of comprehension).
– J D
Commented Feb 6 at 22:13
• "φ(n) is a formula of arithmetic with n as a natural number parameter", would this be a typical algebraic expression like n^2 - 1 = (n + 1)(n - 1)? Commented Feb 6 at 23:46
• "χ is a sentence of arithmetic, and <χ> is the Gödel number of the sentence χ". Why do we need to distinguish between a sentence X with no free variable n (I assume), vs. phi, a formula with a free variable? Are only the "closed formula" assigned Godel numbers? Why? Does Godels incompleteness theorem somehow depend on ordering the sentences of arithmetic? (As I am only used to seeing the diagonal argument as a way to prove that a set is not "closed", in a certain way). Commented Feb 6 at 23:48
• Specifically, φ is a predicate defined over the natural numbers, so it is an algebraic expression that n either satisfies or it doesn't. What you wrote is a theorem of arithmetic, so it wouldn't be useful because it is always true. Commented Feb 7 at 0:41
• The point of the diagonal lemma is that it expresses a relationship between a property of a (closed) sentence, namely that it is provable-in-F, and a property of the Gödel number of that sentence, namely that it satisfies the algebraic formula φ. This relationship effectively bridges the gap between object language and metalanguage. The metalinguistic χ is provable-in-F holds if and only if in the object language <χ> satisfies φ. Commented Feb 7 at 0:41