# 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,\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]

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

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

Its general representation is

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

:

The elements of $\Gamma$ are pairwise relatively prime.

Proof: (Reductio)

1. 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. 2.

This gives by definition the congruence

 $[(j+k+1)\cdot l+1]\equiv[(j+1)\cdot l+1]\quad\pmod{p}$
3. 3.

Therefore $p$ divides

 $[(j+k+1)\cdot l+1]-[(j+1)\cdot l+1].$
4. 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. 5.

But

 ${p}\mid{k\cdot l}\rightarrow{p}\mid{k}\vee{p}\mid{l}.$

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

1. 1.

${p}\mid{l}\rightarrow{p}\mid{l}\cdot(j+1).$

2. 2.

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

3. 3.

Therefore: $({p}\nmid{l}).$

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

1. 1.

$k\leq n\leq\text{max}(1,\ldots,n).$

2. 2.

But $(\forall k){k}\mid{l}.$

3. 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]

If $m,l,$ 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 $\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.]

 $\in\mathbb{N}\rightarrow(\exists m)(\exists l)[a_{k}=\beta% (m,k,l)].$

Proof:

1. 1.

Let

 $a_{o},\ldots,a_{n}$

be a sequence of natural numbers.

2. 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. 3.

If $l\geq\text{max}(a_{o},\ldots,a_{n}).$

4. 4.

Then $a_{k}<(k+1)\cdot l+1.$

5. 5.

But by the previous proposition the numbers

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

are pairwise relatively prime.

6. 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. 7.

Therefore

 $m\equiv a_{k}[\pmod{(k+1)\cdot l+1}].$
8. 8.

This means that

 $a_{k}=R[m,(k+1)\cdot l+1].$
9. 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:

 $\begin{array}[]{ccc}m&=&x_{1}\\ l&=&x_{2}\\ k&=&x_{3}.\\ \end{array}$

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.

## References

• 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.
 Title Gödel’s beta function Canonical name GodelsBetaFunction Date of creation 2013-03-22 18:34:57 Last modified on 2013-03-22 18:34:57 Owner gribskoff (21395) Last modified by gribskoff (21395) Numerical id 18 Author gribskoff (21395) Entry type Definition Classification msc 03A05 Classification msc 03-01 Classification msc 11A07 Synonym representation of sequences in formal systems Related topic ChineseRemainderTheorem Related topic BeyondFormalism Related topic FromHilbertsTenthProblemToGodelsTrichotomy Related topic LinearCongruence Defines gamma sequence