Gödel’s beta function

Gödel’s $\beta$ function is the tool needed to express in a formal theory Z assertions about finite sequences of natural numbers. (For a description of Z see the PM entry "beyond formalism: Gödel’s incompleteness" (http://planetmath.org/BeyondFormalism)).

Let

$$1,\mathrm{\dots },n.$$

be a sequence of natural numbers. Then there is the factorial $n!$ such that

$$n\cdot (n-1)\cdot \mathrm{\dots }\cdot 1=n!.$$

This means that the factorial $n!$ is divided by each of the elements of

$$1,\mathrm{\dots },n$$

so that we can build the derived sequence

$$1\mid n!,2\mid n!,\mathrm{\dots },n\mid n!.$$

Definition 1  [Gödel’s $\mathrm{\Gamma }$ sequence]

If we denote $n\mathrm{!}$ by $l$ then the elements of Gödel’s $\mathrm{\Gamma }$ sequence are the numbers of the form

$(k+1)\cdot l+1.$

Its general representation is

$$\mathrm{\Gamma }=1\cdot l+1,2\cdot l+1,\mathrm{\dots },n\cdot l+1,(n+1)\cdot l+1.$$

Theorem 1:

The elements of $\mathrm{\Gamma }$ are pairwise relatively prime.

Proof: (Reductio)

1. We assume the existence of a prime number $p$ such that $p$ divides

   $$(j+1)\cdot l+1$$

   and $p$ divides also

   $$(j+k+1)\cdot l+1.$$

2. This gives by definition the congruence

   $$[(j+k+1)\cdot l+1]\equiv [(j+1)\cdot l+1]\mathit{\hspace{1em}}(modp)$$

3. Therefore $p$ divides

   $$[(j+k+1)\cdot l+1]-[(j+1)\cdot l+1].$$

4. Then $p$ divides

   $$j\cdot l+k\cdot l+l+1-j\cdot l-l-1,$$

   that is, $p$ divides $k\cdot l$.

5. But

   $$p\mid k\cdot l\to p\mid k\vee p\mid l.$$

Case I: Assume $p\mathrm{\mid }l$

1. $p\mid l\to p\mid l\cdot (j+1).$

2. But by hypothesis: $p\mid (j+1)\cdot l+1.$

3. Therefore: $(p\nmid l).$

Case II: Assume $p\mathrm{\mid }k$

1. $k\le n\le \text{max}(1,\mathrm{\dots },n).$

2. But $(\forall k)k\mid l.$

3. $p\mid k\wedge k\mid l\to p\mid l$

Case I.3. and Case II.3. are the desired contradiction.

Definition 2:  [Gödel’s $\beta$ function]

If $m\mathrm{,}l\mathrm{,}$ and $k$ are natural numbers then the function

$\beta (m,l,k)$

computes the rest of the division of $m$ by a term $(k+1)\cdot l+1$

of the $\mathrm{\Gamma }$-sequence.

Therefore: $\beta (m,l,k)=R[m,(k+1)\cdot l+1].$

Theorem 2:  [Sequences of natural numbers are representable by the $\beta$ function.]

Proof:

1. Let

   $$a_o,\mathrm{\dots },a_n$$

   be a sequence of natural numbers.

2. Then there is a number $l$ such that

   $$\mathrm{\Gamma }=1\cdot l+1,2\cdot l+1,\mathrm{\dots },n\cdot l+1,(n+1)\cdot l+1.$$

3. If $l\ge \text{max}(a_o,\mathrm{\dots },a_n).$

4. Then

5. But by the previous proposition the numbers

   $$(k+1)\mathrm{\dots }l+1$$

   are pairwise relatively prime.

6. This implies that the simultaneous congruences

   $$x\equiv a_o[(mod1\cdot l+1)]$$

   $$\mathrm{⋮}$$

   $$x\equiv a_n[(mod(n+1)\cdot l+1)]$$

   have a common solution $m$, by the chinese remainder theorem.

7. Therefore

   $$m\equiv a_k[(mod(k+1)\cdot l+1)].$$

8. This means that

   $$a_k=R[m,(k+1)\cdot l+1].$$

9. But that is

   $$a_k=\beta (m,l,k).$$

It is easily seen that the $\beta$ function is primitive recursive.

For that we only have to redenominated $m,l$ and $k$ as:

Then $\beta (x_1,x_2,x_3)=R[x_1,(x_3+1)\cdot x_2+1]$.

But the functions "+", "$\cdot$" e "$R$" are primitive recursive.

Therefore $\beta$ is primitive recursive.