@JadeVanadium Why is godel numbering useful?

I mean, there are other more intuitive ways to encode syntax, but then why use prime numbers?

Maybe there is a deep reason behind it I am not aware of...

@KripkePlatek I think the encoding Godel used, using prime numbers, is actually one of the simplest way to get Peano Arithmetic to encode arbitrary strings from an infinite alphabet. Using something like base-10, we can easily encode arbitrary finite strings where our alphabet has only 10 symbols, and of course other bases let us have larger alphabets...

But I think using Primes is one of the most intuitive ways to get arithmetic to encode arbitrary finite sequences from an infinite alphabet

I mean, there is also Godel's beta function, which can be used to encode arbitrary sequences, but I think everyone who's ever seen Godel's beta function has agreed that it's not very intuitive hahah

What other kind of encoding were you thinking of?

@JadeVanadium I was thinking about assigning to each symbol a positive number and use 0 as separator.

But reading your response, there is more to this encoding thing than I first initially thought.

I have to read more about this to make an informed judgement...

Oh I see, you mean an encoding using binary strings? It's true that that would work; binary strings can be easily encoded using base 2, and that would also give you an infinite alphabet. Which of the two qualifies as "more intuitive" is entirely subjective, I think. I personally have a lot of familiarity with the encoding using primes, since it's something I've dealt with often for several distinct purposes, so I guess that explains why I have that sort of bias.

The fact that the prime encoding gives a bijection is also an interesting feature; that's the sort of thing I'd be drawn to even if I didn't have those other biases. Perhaps Godel was drawn to it for the same reasons.

It's also worth noting that there are probably several historical reasons that made that choice more likely. The extent to which strings are considered intuitive is probably influenced by how the field of mathematics has progressed, especially with its relation to computation. If I recall, computation was a largely underdeveloped subject, at the time of Godel's work, whereas the Fundamental Theorem of Arithmetic has been around for ages.

Regardless, I do think it was a largely subjective decision. The prime encoding is interesting in its own right, but in the end there are many different encodings he could have used. It was probably just the first one he thought of.

Ah, just to throw another possibility in: as a set theorist, if I were going to use binary anyway, It would be easier to simply use the BIT predicate to interpret the hereditarily finite sets, and then we can encode strings as functions using sets of ordered pairs

Actually, as someone who has more experience with sets than almost any other structure, that feels like the most obvious course of action... despite the fact that it would almost obviously require more work :)