Confusion in Godel's numbering for subscripts

461 Views Asked by At

I don't understand how to represent subscripts in Godel's numbering.
Suppose I have a formula:
$$x_1 + sx_{11} = s(x_1 + x_{11})$$
and an encoding:
enter image description here
then what should be the Godel Numbering?

Should I just treat the above formula as:
$$x1 + sx11 = s(x1 + x11)$$
and encode it?

[This is a homework question and the only statement that's supposed to be helpful is cryptic and unfathomable: "Additional variables are obtained with unary subscripts on the variable x. Thus $x_1$ is a variable, $x_{11}$ a second, $x_{111}$ a third and so on."]

2

There are 2 best solutions below

0
On BEST ANSWER

"Should I just treat...?" - yes.

A valid formula cannot contain two variables or constants consecutively, so there is no danger of $x11$ being misinterpreted as $x$ plus $1$ plus $1$ or $x$ times $11$ or . . . .

0
On

In this case, it does seem that you will encode the subscript in unary notation. It is worth pointing out that the more common way of doing this (and the way that Gödel originally did it) was to use a different number for each variable. So, for example, you might have $x_1 = 21$, $x_2 = 22$, and so on.

In this more common method, the subscripts are not viewed as part of the formula. They are viewed as just a way for us to write an infinite number of variables on paper with a finite alphabet. In other words, the entire symbol "$x_{122}$" is viewed as being one character long, and that character is the symbol for the 122nd variable, which might have Gödel number $142$.

Of course, in either your method or the common method the entire Gödel number of the expression can be written in binary, and thus reduced to a finite string of 0s and 1s. So there is no real benefit to encoding the subscripts of the variables at the beginning rather than just using a different number for each variable.