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").

Let

$$1, \ldots, n.$$

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

$$n \cdot (n - 1) \cdot \ldots \cdot 1 = n!.$$

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

$$1, \ldots, n$$

so that we can build the derived sequence

$$ {1}\mid{n!}, {2}\mid{n!}, \ldots, {n}\mid{n!}.$$

Definition 1     [Gödel's $\Gamma$ sequence]

Its general representation is

$$\Gamma = 1 \cdot l + 1, 2 \cdot l + 1, \ldots, n \cdot l + 1, (n + 1) \cdot l + 1.$$

Theorem 1:

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] \quad \pmod{p}$$

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} \rightarrow {p}\mid{k} \vee {p}\mid{l}.$$

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

1. ${p}\mid{l} \rightarrow {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}\mid{k}$

1. $k \le n \le {max} (1, \ldots, n).$
2. But $(\forall k) {k}\mid{l}.$
3. $ {p}\mid{k} \wedge {k}\mid{l} \rightarrow {p}\mid{l}$

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

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

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

$$<a_o, \ldots, a_n> \in \mathbb{N} \rightarrow (\exists m) (\exists l) [a_k = \beta (m, k, l)].$$

Proof:

1. Let

   $$a_o, \ldots, a_n$$

   be a sequence of natural numbers.

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

   $$\Gamma = 1 \cdot l + 1, 2 \cdot l + 1, \ldots, n \cdot l + 1, (n + 1) \cdot l + 1.$$

3. If $l \ge {max} (a_o, \ldots, a_n).$
4. Then $a_k < (k + 1) \cdot l + 1.$
5. But by the previous proposition the numbers

   $$(k + 1) \ldots l + 1$$

   are pairwise relatively prime.

6. This implies that the simultaneous congruences

   $$x \equiv a_o [\pmod{1 \cdot l + 1}]$$

   $$\vdots$$

   $$x \equiv a_n [\pmod{(n + 1) \cdot l + 1}]$$

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

7. Therefore

   $$m \equiv a_k [\pmod{(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.

Bibliography

1

Bernays, P., Hilbert, D., Grundlagen der Mathematik, 2.Auflage, Berlin, 1968.

2

Gödel, K., Collected works, ed. S. Feferman, Oxford, 1987-2003.

3

Kleene, S., Introduction to metamathematics, North-Holland, Amsterdam, 1964.