Gödel's beta function, without the Chinese remainder theorem

Question

As we all know, Gödel's beta function exploits the Chinese remainder theorem to encode a finite sequence of naturals into a single natural. This does not require a strong theory; it can be carried out in, e.g., the theory of discretely ordered semiring plus the $\Sigma_1$ induction.

While the CTR is by no means hard, it would be helpful to base your encoding of strings on a even more trivial number-theoretic facts, since there would be less chances you screw things up when you take an oral exam or you teach a class.

Question: Can one use even easier number-theoretic facts to encode finite sequence of naturals in a single natural? The encoding and decoding has to be able to be done in the theory of discretely ordered semiring plus the $\Sigma_1$ induction.

Answer 1

See :

• Raymond Smullyan, Theory of formal systems (1961), page 78:

our proof follows novel lines in that all appeal to the traditional number theory devices accorded this in the past — e.g., prime factorization, congruences and the Chinese remainder theorem — are avoided. Thus Gödel's program of establishing incompleteness, even of first order theories involving plus and times as their sole arithmetical primitives, can, by the methods of this section, be carried out without appeal to number theory.

Answer 2

What about replacing the string $a_n \dots a_0$ with the number $f(a_n \dots a_0)$ whose binary representation is obtained by replacing each $a_i$ in $a_n \dots a_0$ with $1$ followed by $a_i$ zeroes? This gives bijection I believe, with the empty string being sent to $0$. Defining $b_0$ as $0$ and $b_i$ as $\sum_{j = 0}^{i - 1} (a_j + 1)$ else, I think gives that $f(a_n \dots a_0) = \sum_{i = 0}^n 2^{a_i + b_i}$. Don't know whether the encoding and decoding is simple enough for your needs.