Gödel numbering question

Factual Questions
1

Despite being led through the incompleteness proof multiple times, I only have a rough grasp of how it works so forgive me if I say something incomprehensible. As I understand it, the basic idea is that any logical system (e.g., first order logic with the Peano axioms) powerful enough to entail arithmetic is either inconsistent or incomplete. This is because, using Gödel numbering, which is a mapping between logical symbols and numbers, we can construct a sentence that says “I am not provable in this system.” If it’s provable its false (making the system inconsistent) and if it’s not provable it’s true (making the system incomplete). Since the system is consistent by stipulation, it is incomplete.

My question is this. Gödel numbering is an essential part of the proof - without it you could not get formulas to talk about themselves. However, it seems to me like it is external to the logical system itself. The mapping from numbers to logical symbols seems non-trivial. So on my understanding we should say the the logical system + Gödel numbering is inconsistent. Obviously this is wrong. What gives?

2

I don’t really follow your question. My recollection is that Goedel numbering as done originally is (obviously) good enough for the proof, but somewhat needlessly complex.

There are other ways of devising numbering systems. When I learned Goedel, the main text we used was by Boolos, Burgess, and Jeffrey, called Computability and Logic – they used a system based on unique prime number factorization, which was a lot more clear to understand and helped me grok Goedel when working through his paper.

If you don’t have Nagel and Newman’s little book, I recommend it – it’s short, but a classic, and not really dumbed down much, especially if, as it sounds, you have a solid background in metamathematics.

Am I just being dense, or is there some aspect of your question that’s not clearly stated?

3

The essential idea behind Gödel’s argument is that if you have a system for making statements about numbers that’s sufficiently strong, then you can take statements about that system and encode them as statements about numbers that can be expressed in that system. The reason this is interesting is because there was a lot of work done in the early part of the twentieth century to create logical systems of arithmetic that could talk about numbers but not themselves. What Gödel showed is that you just can’t do that–if you have a system that can do arithmetic, it can do logic as well and break itself.

4

(Started typing this before other posts showed up; it’s just in response to the OP)

I’m not sure I understand your objection.

However, let me say this:
A) The way Goedel coding is used in the incompleteness proof works is like this:

One has an operator Combine and a predicate Provable in the language of interest, and also a way of associating to every symbol-string s in the language a corresponding term [s] in the language, in such a way that:

  1. Combine([phi], [t]) is always provably equal to [phi(t)]
  2. p is provable in the system of interest if and only if Provable([p]) is provable in the system of interest.

From 1), you can show that there is a particular proposition g such that g is provably equivalent to ~Provable([g]). [All that goes into doing this is following out what’s involved in interpreting recursive statements; if I were to give you the instructions “Read this sentence out loud twice”, you’d have no difficulty following them. You would know to simply find every instance of the phrase “this sentence”, replace it with the entire sentence, and then proceed. That’s all that “diagonalization”/the Y combinator/etc. is.]. Thus, by 2), Provable([g]) is provable iff g is provable iff ~Provable([g]) is provable. Since there is a proposition which is provable iff its negation is, we cannot have both consistency and completeness.

You might object: How do we know we can find a correspondence sending symbol-strings s to terms [s] and so on such that 1) and 2) are true? Well, it depends on what you take terms to represent. If terms are supposed to represent strings of bits, you just imagine some way of coding symbol-strings as strings of bits, and then send every symbol-string to the term directly representing the corresponding string of bits. You do this in such a way that all the things you might like to say about symbol-strings are easy enough to say in terms of their representing numbers instead, and then you’re golden.

We live in the computer age; the idea that any data can be represented as a string of bits you ought to be familiar and old hat to us now.

If terms are supposed to represent something other than strings of bits (e.g., natural numbers, or integers, or what have you), you just do the same thing, mutatis mutandis. Speaking of which…

B) Goedel numbering is a bit of a red herring; it’s only necessary to talk about Goedel numbering if your goal is to show incompleteness for specifically arithmetic systems. If the systems you are studying axiomatize the notion of a finite list of objects more directly (or recursive data structures and functions or such things), then there’s no need to bother trying to encode everything as a number. It just so happens that there is a hack (of vanishingly little significance, IMHO) by which one can interpret Finite List Theory (or Finite Set Theory or such things) within the first-order theory of natural numbers, successor, addition, and multiplication, by use of the Chinese Remainder Theorem. It is only a quirk of history that so much focus has been given on this particular presentation of the Goedelian phenomena.

5

one second

6

Eh, let me just put it this way:

Here is a sentence which demonstrates Xenocrates’ cannot correctly assert:

“Xenocrates will never assert this sentence”

If you assert that sentence, well, you will be manifestly wrong. On the other hand, if you refrain from ever asserting that sentence, it will be a true sentence you never assert. This is incompleteness in a nutshell.

“But”, you might object, “That’s not a proper sentence. It refers to itself.”

Sure it’s a proper sentence. So what if it’s self-referential? We have no difficulty interpreting self-reference. Here, I’ll help you out: let’s say the unrolling of a recursive sentence like this is what you get when you take every instance of “this sentence” within it, and replace it with the sentence itself. (That, after all, is what “this sentence” means, right?)

So, unrolling our previous recursive sentence gives us:
“Xenocrates will never assert ‘Xenocrates will never assert this sentence’”.

You might still object: “Well, that’s still gibberish; it may not be directly recursive, but it makes reference to the possibility of Xenocrates asserting a recursive sentence. This is nonsense! Self-reference frightens and confuses me. No one should ever be considered capable of asserting anything recursive.”

Fine, we’ll pacify you yet. Everywhere where we would want to speak directly of asserting a self-referential sentence, we’ll merely replace it with talk of asserting the unrolling of that sentence instead.

So, let’s say the cleaning-up of a self-referential sentence is what you get when you replace every instance of “this sentence” with “the unrolling of this sentence” instead. And the full-unrolling of a recursive sentence will be what you get when you clean it up and then unroll it.

Then the full-unrolling of our original recursive sentence will be this:
“Xenocrates will never assert the unrolling of ‘Xenocrates will never assert the unrolling of this sentence’”

Now there’s no room left for objection. Here’s our original sentence translated into a world with no direct support for self-reference, yet retaining that behavior all the same. By making the interpretation of recursive sentences entirely explicit, we’ve shown that you can’t get away from them; even if you refuse to directly incorporate the mechanisms for interpreting recursion into your hardware, we’ll just build them up in software again.

The above is Goedel’s incompleteness theorem. You could take the above and encode it quite directly into any framework in which concepts like “sentence”, “assert”, etc., could be described quite directly. E.g., systems of set theory or list theory or the theory of computer programs acting on symbol-strings or the theory of axiomatic systems and proofs within them or…

You could also take the above and encode it quite indirectly into any framework in which any of those could be encoded quite indirectly. This is what happens with Peano Arithmetic; it turns out to be possible to interpret the theory of finite lists of natural numbers within the theory of natural numbers, successor, addition, and multiplication. Which is a fine piece of trivia, but nothing particularly interesting in the end (for example, it is markedly easier to interpret all this within the theory of natural numbers, successor, addition, multiplication, and exponentiation. Is that of philosophical importance? And easier still to define all this within the theory of natural numbers, successor, and recursively defined functions, if one is committed to natural numbers (which is, after all, where addition, multiplication, exponentiation, etc., all come from, all the same)).

All the stuff about natural numbers and addition and multiplication is just some fluff of the essence of the Goedelian phenomena. The structure above is what really matters, and not just as some detail-shorn, arigorous approximation; it’s the real deal.

7

All that editing and still a typo (“edito”?). Either strike the word “demonstrates” or replace everything after it with “the Goedelian phenomena as applied to Xenocrates”.

8

That’s a well-said summary. I think, if I can make a leap of faith and semantics, the OP is asking what the relation to Goedel numbering is to … something.

If I can take a stab – if you have a way of encoding any given operation or combinations of operations and logical statements in numerical form, and a way of decrypting that particular Goedel number back into its components, it’s a very convenient way of making a generalization about arithmetic, and anything “higher,” like first- or second-order predicate logic, and so forth.

It’s a tool that makes things plain.

There are plenty of natural language proofs of Goedel’s two incompleteness theorems; if you do a search for “shortest Goedel proof” “natural language” you’ll find probably one I remember but at the same time can’t remember enough to state it. Goedel numbers aren’t necessary to prove the results, in other words, but they are elegant and pretty convenient.

Plus, given Goedel’s eccentricities in life, he probably felt a little more comfortable using his (IMO needlessly complicated numbering scheme) than a simpler prime-number factorization scheme or, god forbid, some natural language sentence involving non-frozen foods.

ETA I missed all of the above due to a weird interruption – good stuff on first glance that I shall look forward to reading and, if I can, add in a few little words. I did learn this stuff in grad school from a prominent logician, so I’m not totally as dumb as I sound, but it’s been a while for me.

9

The point isn’t about “natural language”, per se; the point is that, if what you want to talk about are formulas and proofs in first-order logic, then you might as well directly or at least cleanly axiomatize the notion of a formula in that language, a proof in that language, etc… If what you want to talk about are computer programs, then you might as well directly axiomatize computer programs. Etc. Even Goedel didn’t think reducing everything to the first-order theory of the semiring of natural numbers was particularly important; he only tossed off a couple sentences about it in the midst of an argument which was almost entirely about a higher-order logic instead (in which everything can be coded much more easily).

The point is that, while number addition and multiplication happens to be one particular instance where GIT applies, there is nothing profound in that. Everything significant is already apparent in any of the presentations in which GIT lives more cleanly and naturally.

(Can you imagine if we still started every discussion of computer programming off with an extensive digression into the implications of the Chinese Remainder Theorem for encoding of computable functions into the first-order theory of <N, +, *>? But that’s just the sort of thing we still do whenever we talk about GIT, for no good reason but historical cruft)

10

(Though even first-order logic is a red herring; if what you want to talk about is just the abstract notion of provability, with the Hilbert-Bernays conditions or what have you, then that’s the thing to talk about directly.)

ETA: Oh, I missed that Jaledin missed what I had said. And thus I thought they were replying to me, when they weren’t. So, my previous post (which was meant to be a reply to them replying to me) is perhaps all misdirected.

11

I appreciate all the responses, especially those of Indistinguishable! Unfortunately, I’m still not exactly clear on the answer to my question - this may be too complex a topic for me to understand via forums but no hurt in trying. So I would like to clarify my question - note that I don’t expect to get a “straight” answer to my question… more likely the fact that I’m asking this will reveal some kind of fundamental misunderstanding of what is going on.

I see how once you’ve got self-reference in a consistent system you have incompleteness. Furthermore, I have no problem with self-reference itself (though I do have one question about something Indistinguishable said which I will ask below). What I don’t get is how any system capable of talking about numbers is capable of talking about itself. It seems like the Gödel numbering scheme (or any other similar sort of assignment) is artificially injecting self-reference into a logical system where it wasn’t present before by giving symbols (in this case numbers) a second meaning. I think where I’m going wrong might have something to with Indistinguishable’s claim that even if you don’t build self-reference into the hardware (which is supposed to be, I take it, analogous to the axioms and transformation rules?) you can get it from software. But I still don’t really understand that claim. I get the feeling that you know what I am asking and answered it exactly but somehow I am just not getting it. Sorry! Don’t feel obligated to continue re-explaining it.

And here is the aforementioned (and as far as I know, separate) question regarding the earlier post. See the quote below:

The full-unrolling still features “this sentence” so how is it that “Everywhere where we would want to speak directly of asserting a self-referential sentence, we’ll merely replace it with talk of asserting the unrolling of that sentence instead.”?

12

I’m still not done reading Indistinguishable’s posts, but all I can say to this last by OP is – how do you formally describe this “unrolling” if not by something tight like a numbering system?

I still am missing something, and it’s probably my fault – I’m better (like most people, probably) at dealing with formalized language than “word problems” (says the guy with 7/8 of a PhD in Comparative Literature!), when it comes to discussing proofs.

More! Best topic I’ve seen in months here, not including the one re geometry of chicks’ nipples and aureolae.

13

In “Xenocrates will never assert the unrolling of ‘Xenocrates will never assert the unrolling of this sentence’”, there’s no use of the term “this sentence”. There’s a mention of it, but no use of it. The ostensible meaninglessness of self-referential sentences no more affects the ability to interpret “Xenocrates will never assert the unrolling of ‘Xenocrates will never assert the unrolling of this sentence’” than the meaninglessness of “Urgbones” affects the meaningfulness of the sentence “There are 7 letters in the string ‘Urgbones’ which are not capitalized”.

For that matter, it never speaks of anyone asserting a sentence which uses the term “this sentence”, either. It only ever speaks of asserting sentences which do not contain the term “this sentence”.

Since it never uses the term “this sentence”, or talks of people asserting sentences which use the term “this sentence”, there is no need to have any account of direct self-reference to interpret it as meaningful; “this sentence” might as well be considered pure gibberish, but the assertion “Xenocrates will never assert the unrolling of ‘Xenocrates will never assert the unrolling of this sentence’” will still be considered meaningful.

If you like, we can spell “this sentence” a little differently, which may make what’s going on a little clearer, by wiping away connotations one might otherwise get confused by.

Let us treat unrolling as an operation that acts on “sentences with holes” (aka, predicates; aka, properties). E.g., “Xenocrates will never assert ____” is a sentence with a hole. (It’s just a particular convenient syntax for talking about the property of being a sentence which Xenocrates will never assert.)

To unroll a sentence with a hole, you replace the hole with the full sentence with a hole. To clean up a sentence with a hole, you replace the hole with “the unrolling of ____”. To fully-unroll a sentence, you clean it up and then unroll it.

Then the full unrolling of “Xenocrates will never assert ____” is “Xenocrates will never assert the unrolling of ‘Xenocrates’ will never assert the unrolling of ____'”.

This is in fact not a sentence with a hole anymore; it’s a hole-less sentence with happens to talk about a sentence with a hole. It’s a complete assertion; it’s not merely a predicate or property waiting for an argument. (Just like “The letters ‘ioawhta’ do not comprise a word in English” is not a gibberish sentence which tries to use a gibberish word “ioawhta”; it’s a meaningful sentence which happens to mention a gibberish word “ioawhta”. Or, “The word ‘nigger’ contains six letters” is not an awful, racist sentence; it is a perfectly dry, true sentence which happens to mention, but not use, a racial slur).

14

In the second to last paragraph above, there was a stray, misplaced apostrophe. It should have been punctuated as follows:

Apologies for the typo.

15

One might just as well achieve the same effect by considering the proposition “Xenocrates will never assert the sentence in temp.txt”, while placing “Xenocrates will never assert the sentence in temp.txt” in temp.txt. Of course, sentences which refer to temp.txt have truth values which are dependent on the contents of the filesystem, which may change over time; one might then easily imagine a way to take a sentence whose truth value had such a dependency, and remove the dependency, by suitably bundling the sentence with a snapshot of the desired filesystem contents, to be loaded before interpreting the sentence. This all amounts to the exact same thing at the end as what was done above; I’m just stumbling around for the metaphor which will connect.