A Bound in Gödel 1931

When teaching Gödel's famous 1931 paper on the incompleteness theorems this semester, I got hung up on one of the bounds he gives in the course of the 45 definitions of primitive recursive notions. This is the case of concatenation. Recall that Gödel here codes finite sequences via prime factorization, so the sequence <a₁, ..., a_n> is coded as: 2^a₁ × ... ×p_n^a_n, where p_n is the n^th prime. The 'star function' is then defined as follows:

x * y = μz≤Pr[l(x) + l(y)]^x+y {∀n≤l(x)(n Gl z = n Gl x) &

     ∀n≤l(y)(0<n → (n + l(x)) Gl z = n Gl y)}

Here, l(x) is the length of the sequence x; n Gl x is the n^th element of that sequence. So the definition says that x * y is the least number coding a sequence that agrees with x on its first l(x) elements and agrees with y on the next l(y) elements. Of course, there is such a number (and, actually, given how "Gl" works, there are infinitely many). The bound is needed to guarantee that * is primitive recursive.

The question, though, is how the bound is supposed to work. Gödel does not often discuss his bounds, which tend to be pretty loose, but he does explain one of them in footnote 35. And if one follows the sort of reasoning Gödel uses there, then it is difficult to see how to get the bound in the above.

I asked a question about this on the Foundations of Mathematics mailing list, and Alasdair Urquhart took the bait and replied with an elegant proof showing why Gödel's bound works. I thought I'd record a version of it here, in case anyone else has a similar question.

First, we show, by a straightforward induction on n, that 2^a₁ × ... ×p_n^a_n ≤ p_n^{a₁ + ... + a_n}.

Now let <a₁, ..., a_n> and <b₁, ..., b_m> be two sequences. The code of their concatenation is:

2^a₁ × ... ×p_n^a_n × p_n+1^b₁ × ... × p_n+m^b_m ≤ p_n+m^{a₁ + ... + a_n + b₁ + ... + b_m}

Moreover,

a₁ + ... + a_n ≤ 2^a₁ + ... + p_n^a_n ≤ 2^a₁ × ... × p_n^a_n = x

and similarly for the other sequence. (Note that the last inequality depends upon the fact that none of the a_i = 0, but Gödel's coding of sequences only works for positive integers.) So

a₁ + ... + a_n + a_n+1 + ... + a_n+m ≤ x + y

which gives Gödel's bound.