Definition of Gödel's $\beta$-function in Shoenfield's book "Mathematical Logic"

53 Views Asked by At

In Section 6.4, page 116, Shoenfield defines

$$ \beta(a,i)=\mu x_{x<a\stackrel{\cdot}{-}1}\exists y_{y<a}\exists z_{z<a} (a=\text{OP}(y,z)\wedge\text{Div}(y,1+(\text{OP}(x,i)+1)\cdot z)) $$

with $\text{OP}(u,v):=(u+v)\cdot (u+v)+u+1$ and $\text{Div}(u,v):\longleftrightarrow \exists t(tv=u)$.

Furthermore, $\mu x P(x,\overrightarrow{a})$ is defined as the least $x$ such that $P(x,\overrightarrow{a})$ holds assuming the existence of an $x$ with $P(x,\overrightarrow{a})$.

My question is the following: Is the definition of $\beta$ correct since there is not for every natural number $a$ a pair $(y,z)$ of natural numbers satisfying $\text{OP}(y,z)=a$?

Also if $\beta$ is not total it fulfills its purpose of coding finite sequences of natural numbers.

I am aware that questioning the correctness of this definition is daunting as Shoenfield's book is a classic.

1

There are 1 best solutions below

1
On

Check out p. 112, where Shoenfield defines his bounded $\mu$ operator, which is the one in use here.

The definition ensures that $\mu x_{x < a}\varphi(x)$ is always defined -- even if there is no $n < a$ such that $\varphi(n)$ is true.