~hanwen >_

Gödel's β Function

#math

简体中文

Today in the Introduction to Recursion Theory course I was told about Gödel’s β Function, which makes it possible to encode a finite sequence into a single natural number.

The Definition

Before the function it self, there are some auxiliary functions that need to be defined.

First we come up with the quotient and remainder functions. For all 𝑚,𝑛∈𝜔, let quo(𝑚,𝑛) and rem(𝑚,𝑛) be the quotient and remainder of 𝑚 divided by 𝑛, respectively, if 𝑛≠0, and 0 otherwise.

Then follows the (floored) square root and exceedence functions. For all 𝑛∈𝜔, let [√𝑛] be the largest number 𝑘 that 𝑘2≤𝑛, and K(𝑛)=𝑛−[√𝑛]2.

Now comes the J and L functions, named after what Gödel named them. Let J(𝑚,𝑛)=((𝑚+𝑛)2+𝑛)2+𝑚, and L(𝑛)=K([√𝑛]). The definitions may seems weird at first glance, but they would soon show their power. And they have great properties: for all 𝑚,𝑛∈𝜔, K(J(𝑚,𝑛))=𝑚 and L(J(𝑚,𝑛))=𝑛. The proof goes as follows.

For that property of K and J, it suffices to show that [√J(𝑚,𝑛)]=(𝑚+𝑛)2+𝑛, and this can be brought out by the fact that

((𝑚+𝑛)2+𝑛+1)2=((𝑚+𝑛)2+𝑛)2+2((𝑚+𝑛)2+𝑛+1)+12>((𝑚+𝑛)2+𝑛)2+𝑚.

That property of L and J is also easy following similar approach. These two properties means that the arguments of J can be extracted from the result of it, and that means J is an 1-1 function.

Finally, the Gödel’s β function is defined by 𝛽(𝑚,𝑖)=rem(K(𝑚),1+(𝑖+1)·L(𝑚)). (Note that this is not the original definition (3-ary) but a simplified 2-ary one.) The definition is also a bit of complicated, but the following lemma tells us about why it is amazing.

Gödel’s β Function Lemma

For all 𝑚0,…,𝑚𝑛−1∈𝜔, there exists a 𝑚∈𝜔 such that

𝛽(𝑚,𝑖)=𝑚𝑖

for all 𝑖<𝑛.

And the the proof entails an algorithm to calculate such an 𝑚.

Before the proof, we need to prove two preliminary propositions.

Bézout’s Lemma

(Note that this lemma is a weaken version of the original theorem.)

If 𝑚,𝑛∈𝜔 and they are coprime, then 𝑎𝑚+𝑏𝑛=1 for some integers 𝑎 and 𝑏.

Proof: Let 𝑆={𝑎𝑚+𝑏𝑛∣𝑎𝑚+𝑏𝑛∈𝜔}, i.e. the set of all positive (integral) linear composition of 𝑚 and 𝑛. Thus there must be a minimum value 𝑝∈𝑆 for this non-empty set (the non-emptiness is trivial). What this proof wants to show is that 𝑝=1. We prove this by contradiction. Assume that 𝑝≠1. Take 𝑞∈𝑆, let 𝑟=rem(𝑞,𝑝), we have 0≤𝑟<𝑝. And rem(𝑞,𝑝)∈𝑆 since 𝑝 and 𝑞 are both (integral) linear composition of 𝑚 and 𝑛, so rem(𝑞,𝑝) must be 0, otherwise it contradicts with the minimality of 𝑝. Then we have 𝑝∣𝑞 for all 𝑞∈𝑆. Note that 𝑚∈𝑆 and 𝑛∈𝑆, so 𝑝 is a common divisor of 𝑚 and 𝑛, which leads to the contradiction toward the coprimality of 𝑚 and 𝑛 if 𝑝≠1.

Chinese Remainder Theorem

For all 𝑘0,…,𝑘𝑛−1∈𝜔, if 𝑑0,…,𝑑𝑛−1∈𝜔 are pairwise coprime and 𝑘𝑖<𝑑𝑖 for all 𝑖<𝑛, then there exists a 𝑘∈𝜔 such that rem(𝑘,𝑑𝑖)=𝑘𝑖 for all 𝑖<𝑛.

Proof: For each 𝑖<𝑛, let 𝑚𝑖=𝑑0⋯𝑑𝑛−1𝑑𝑖. Since 𝑑0,…,𝑑𝑛−1 are pairwise coprime, 𝑚𝑖 and 𝑑𝑖 are coprime. By Bézout’s Lemma, there are integers 𝑎𝑖 and 𝑏𝑖 such that 𝑎𝑖𝑚𝑖+𝑏𝑖𝑑𝑖=1. The insight here is that for each 𝑑𝑖, we construct the number that its remainder divided by 𝑑𝑖 is 𝑘𝑖, and compose these constructed numbers in a way that they won’t affect each other. Note that 𝑚𝑖 cannot be divided by 𝑑𝑖, can be divided by 𝑑𝑗 for any 𝑗<𝑛 where 𝑗≠𝑖, and there is an 1 on the right hand side of the equation we got from the Bézout’s Lemma. It is easy to see that, now it suffices to take

𝑘=∑𝑖<𝑛𝑘𝑖𝑎𝑖𝑚𝑖+𝑙𝑑0⋯𝑑𝑛−1,

where 𝑙 is any natural number such that 𝑘≥0.

The Proof fo Gödel’s β Function Lemma

Finally we come to the proof of the lemma. From the definition of J and 𝛽, we can see that we only need to find a proper value of L(𝑚) such that the numbers 1+(𝑖+1)·L(𝑚) for each 𝑖<𝑛 coprime, then construct the value of K(𝑚) by Chinese Remainder Theorem, and calculate the 𝑚=J(K(𝑚),L(𝑚)). For convenience, denote 1+(𝑖+1)·L(𝑚) by 𝑑𝑖 for each 𝑖<𝑛.

What conditions should the value of L(𝑚) satisfy? First, it must make 𝑑𝑖=1+(𝑖+1)·L(𝑚)>𝑚𝑖, which is one of the conditions asked by Chinese Remainder Theorem. Second, it makes those 𝑑𝑖‘s pairwise coprime. To prove propositions like ‘there is no prime 𝑝 such that 𝑝∣𝑑𝑖 and 𝑝∣𝑑𝑗 for different 𝑖,𝑗<𝑛’, consider proof by contradiction. Think about what if there is some prime 𝑝 such that 𝑝∣𝑑𝑖 and 𝑝∣𝑑𝑗 for different 𝑖,𝑗<𝑛, i.e. 𝑝∣1+(𝑖+1)·L(𝑚) and 𝑝∣1+(𝑗+1)·L(𝑚). Assume 𝑖<𝑗 without loss of generality, we have 𝑝∣(𝑗−𝑖)·L(𝑚). It will be good if we have 𝑝∣L(𝑚), which would lead to the contradiction that 𝑝∣1. So things become evident: find a construction of L(𝑚) such that (𝑗−𝑖)∣L(𝑚). This can be achived by making L(𝑚) divisible by the product of all the possible values of 𝑗−𝑖, which ranges from 1 to 𝑛−1. This is to say, making (𝑛−1)!∣L(𝑚) would be a good idea. With the first condition that L(𝑚) should satisfy, it suffices to take L(𝑚)=𝑙!, where 𝑙=max{𝑛,𝑚0,…,𝑚𝑛−1}. I take 𝑛 instead of 𝑛−1 there for better elegance with the same effect.

The above is not a strictly stated proof, however it is easy to rewrite it into one.

Mumbles (Again)

The reason I write this post is not that the ability of Gödel’s β Function to encode a finite sequence into a number is amazing (there are many other techniques to achive this, e.g. encode the sequence into the exponents of an initial segment of primes), nor that the proof is elegant (though it is). It is just because I recalled the confusion that those two preliminary propositions caused to me, and realized that they seems easy for me now, and can be used to prove such lemmas. This feels strange, so I decided to write it down.