Exercise 6.4.2

Proof. Note that there is no such operation that can exactly satisfy both conditions as they actually contradict each other. To see this suppose there is such an operation $𝐅$. Then define the set $x=\varnothing$ and $n=0$ Then by (a) we have that $𝐅(x,n+1)=𝐅(x,1)=0$. It then follows from (b) that there are a $y$ and $z$ such that $x=(y,z)$, but clearly this is not the case for $x=\varnothing$. Hence a contradiction.

To remedy this we simply add a condition to (b), which when restated becomes

(b) $n>0$ and $𝐅(x,n+1)=0$ if and only if there exists $y$ and $z$ such that $x=(y,z)$ and $𝐅(y,n)=0$.

Now, define an operation $𝐆$ by $z=𝐆(x,y_u)$ if and only if either

1.

$y_u$ is a function with parameter $u$, $\mathrm{dom}(y_u)=1$, and $z=0$, or

2.

$y_u$ is a function with parameter $u$, $\mathrm{dom}(y_u)=\alpha +1$ for some ordinal $\alpha$, there are $p$ and $q$ where $x=(p,q)$, $y_p(\alpha )=0$, and $z=0$ or

3.

None of the above hold and $z=1$.

Then by Theorem 6.4.9 there is an operation $𝐅$ such that $𝐅(x,\alpha )=𝐆(x,{𝐅}_x\upharpoonright \alpha )$ for all ordinals $\alpha$ and sets $x$.

Then for any set $x$ we have that clearly $𝐅\upharpoonright 1$ is a function with domain $1$ (and parameter $x$) so that by definition

This shows (a).

To show (b) consider any ordinal $n$ and set $x$.

( $\to$) Suppose that $n>0$ and $𝐅(x,n+1)=0$ so that clearly $(3)$ above cannot be the case. Also $(1)$ cannot be the case since $𝐅(x,n+1)=𝐆(x,{𝐅}_x\upharpoonright n+1)$ and $\mathrm{dom}({𝐅}_x\upharpoonright n+1)=n+1>1$. Hence (2) is the case so that there are $y$ and $z$ such that $x=(y,z)$ and $({𝐅}_y\upharpoonright n+1)(n)=0$. Hence it follows that $F(y,n)=0$.

( $\leftarrow$) Now suppose that there are $y$ and $z$ such that $x=(y,z)$ and $F(y,n)=0$. Then $F(y,n)=G(y,{𝐅}_y\upharpoonright n)=0$.

So if $n=0$ then $\mathrm{dom}({𝐅}_y\upharpoonright n)=\mathrm{dom}({𝐅}_y\upharpoonright 0)=0\ne 1$ so (1) cannot be the case. Also since $0$ is not a successor ordinal (2) cannot be the case either (since $\mathrm{dom}({𝐅}_y\upharpoonright 0)\ne \alpha +1$ for any ordinal $\alpha$). Hence (3) must be the case, but this implies that $F(y,n)=1$, which is a contradiction. So we must have that $n\ne 0$ so $n>0$.

Since $𝐅(y,n)=0$ clearly we have that $({𝐅}_y\upharpoonright n+1)(n)=0$. Since also $\mathrm{dom}({𝐅}_x\upharpoonright n+1)=n+1$ we find that (2) holds for $𝐆(x,{𝐅}_x\upharpoonright n+1)$. From this it follows that $𝐅(x,n+1)=𝐆(x,{𝐅}_x\upharpoonright n+1)=0$.

This completes the proof. □