Is Gödel numbering necessary for logic?

Question

I have go through the book "Gödelian Puzzle Book" written by Raymond M.Smullyan.In my opinion,since all the questions related to construct or prove (the existence of at least) a sentence which is undecidable,not provable,not solvable and not representable etc. all can be solved by basic set and the miracle fixed point properties(and this is the core idea).So this lead me to think whether or not Gödel numbering is inevitable for some problems or it is just a great trick that to deal with some question related to the incompleteness of arithematic more easily?

Answer 1

If all we're interested in is set theory, then we can perfectly well build a theory of symbol strings and/or abstract syntax trees for logical formulas and inference trees out of basic set theory, and develop the entirety of the incompleteness theorem in that setting.

The reason why it's usually not done that way is twofold:

First, when Gödel originally did his work, the adequacy and safety of using formal set theory as a basis for mathematics was still much more contentious than it is today -- so showing that set theory is undecidable would have been a much less striking result than showing a "flaw" in good old integer arithmetic which everyone believed in implicitly! Therefore Gödel worked with theories of arithmetic, and there's still a tendency to defer to the way things were done first.

Second, as mathematicians we want our results to be as strong and general as we can make them. Between

(a) Every reasonable theory that is strong enough to express set theory is necessarily incomplete.

(b) Every reasonable theory that is strong enough to express integer arithmetic and quantification over integers is necessarily incomplete.

claim (b) is quite a bit stronger -- there are more theories that can be made to model integer arithmetic than there are set theories, and everything that can speak interestingly about sets can also speak about integers.

So working with integers allows us to prove a strictly stronger result. This requires doing some kind of arithmetization, though not necessarily using Gödel's particular numbering scheme.

---

Of course we could also prove (the computer scientist's dream formulation):

(c) Every reasonable theory that is strong enough to express lisp-like data and primitive recursive programs that operate on them is necessarily incomplete.

which has the same strength as (b) -- we could then relegate the Gödel-style arithmetization to a proof that integer arithmetic is enough to express lisp-like data and primitive recursion, and then get incompeteness of, for example, PA as a corollary.

But, for better or worse, there are a lot more people who find integer-arithmetic natural and familiar than there are people who find lisp-like data natural and familiar, so doing (c) would still be a detour for most of the audience.