The composition of $\Delta_0$ fn's $f, g: HF\to HF$ is not necessarily $\Delta_0$?

Question

I am trying to solve the following exercise in Ken Kunen's book The Foundations of Mathematics

The hint vaguely makes sense at the high level but I am unable to follow the proof skeleton. (I am interested in particular in a proof following the given proof skeleton hint, because I am the TA for a class using this text and I want to know if the students will be able to produce a correct proof following the hint; I'm not just interested in a correct proof of the theorem.)

I first established that the basic operators involving pairing and projection of ordered pairs can all be added harmlessly to a $\Delta_0$ formula without affecting it.

Let $f : HF\to HF$ be a function whose graph is $\Delta_1$. Then by definition there is a $\Delta_0$ formula $\varphi$ such that \begin{equation} f(x)=y\iff \exists z. \varphi(x,y,z) \end{equation} Let $x$ be any $HF$ set. Denote by $n_x$ the least natural number $n$ such that $\exists y,z\in R(n),\varphi(x,y,z)$. Denote by $R_x$ the disjoint sum of all $R(n)$ for $n\leq n_x$, i.e. \begin{equation} R_x = \coprod_{n\leq n_x}R(n) = \left\{ \left\langle n,R(n) \right\rangle \mid n\leq n_x\right\} \end{equation} Denote by $h: HF\to HF$ the function which sends $x$ to $\left\langle x,R_x \right\rangle$. We will prove $h$ is $\Delta_0$.

First, by (6.) of Example II.17.5, $\left\langle x,y \right\rangle=z$ is logically equivalent to a $\Delta_0$ sentence, which Kunen calls $\operatorname{op}(x,y,z)$. Note also that ``$z$ is an ordered pair'', $\exists b\in z,\exists x,y\in p.p=\left\langle x,y \right\rangle$ is then $\Delta_0$ in $z$. This is pointed out in (14.) of Lemma II.17.9. I call this $\operatorname{op}(z)$ and use the number of arguments to distinguish them. Note that if $\pi_1, \pi_2$ are the projection operators onto the first and second argument of an ordered pair (and return the empty set if the argument is not an ordered pair) then $\operatorname{op}(z)\land P(x_{1},\dots, x_k,\pi_1(z))$ is logically equivalent to $\exists b\in z,\exists x,y\in b, \operatorname{op}(x,y,z)\land P(x_1,\dots,x_k,x)$ which is $\Delta_0$ in the free variable $z$, so I can use the projection operators freely in a $\Delta_0$ sentence.

By (10.) of Lemma II.17.9, the sentence ``$n$ is a natural number'' is $\Delta_0$. By abuse of notation, I write $n\in \omega$; but be careful to recall that $\omega$ does not denote a term in $HF$. Lastly observe that $\exists ! a\in b. P(x_1,\dots, x_k,a)$ is logically equivalent to the $\Delta_0$ sentence $\exists a\in b.P(x_1,\dots, x_k,a) \land \forall a,a'\in b. P(x_1,\dots,x_k,a')\land P(x_1,\dots, x_k,a)\implies a=a'$.

So define $h$ by $\psi(x,t) = \operatorname{op}(t)\land \pi_1(t)=x \land \pi_2(t)=R_x$. We will show that the relation $s=R_x$ is $\Delta_0$ in $s$ and $x$; from here it is clear that $\psi$ is a $\Delta_0$ definition of $h$.

Define \begin{align} \gamma(x,s):= & \forall p\in s. \operatorname{op}(p)\land \pi_1(p)\in \omega \land \pi_2(p)=R(\pi_1(p))\\ &\textrm{"s is a set of ordered pairs} \\ &\textrm{of the form } (n,R(n)) \textrm{ where } n\in \omega"\\ & \forall p\in s. \forall n'\in \pi_1(p)\exists p'\in s.\pi_1(p')=n'\\ &\textrm{"if }(n,R(n))\in s,\textrm{ so is }(n',R(n'))\textrm{ for }n'<n" \\ & \exists ! q\in s.\exists y,z\in \pi_2(q).\varphi(x,y,z)\\ &\textrm{"in a unique pair }(n,R(n))\textrm{ witnesses }y,z\textrm{ to }\varphi \textrm{ exist in }R(n)"\\ \end{align} However this is not quite right. For this to be correct I would have to establish that the relation $a=R(n)$ is $\Delta_0$, which is equivalent to saying that the graph of the function $n\mapsto R(n)$ is $\Delta_0$. But we don't have that, per se. What we have, given in a previous lemma, is that the graph of $n\mapsto \coprod_{m<n}R(m)$ is $\Delta_0$. This means somehow I need to get hold of the quantity $n_x+1$; but I don't know how to "construct" it in a $\Delta_0$ way from $n_x$ or from $R_x$. I am a bit lost in the face of the unique handicap that I am unable to freely introduce function symbols representing functional relations in virtue of the fact stated in the problem.

Answer 1

The key ideas are

1. Even if we do not know $R(n)=x$ is $\Delta_0$, $R_x$ contains sufficient information to define itself.
2. $V_\omega$ is the closure of $\{\varnothing\}$ under the operation $x,y\mapsto x\cup\{y\}$.

---

Let us consider the conjunction of the following formulas:

• $s$ is a function such that $\operatorname{dom} s$ is an ordinal (so $V$ thinks $\operatorname{dom} s\in\omega$) ,
• $s(0)=0$,
• For $n\in\operatorname{dom}s$ such that $n+1\in\operatorname{dom}s$, if $x,y\in s(n)$ then $x\cup\{y\}\in s(n+1)$.
• For $m=\bigcup\operatorname{dom}s$, there are $y,z\in s(m)$ such that $\phi(x,y,z)$, and
• If $k<m$, then no $y,z\in s(k)$ satisfy $\phi(x,y,z)$.

It is easy to see that the listed formulas are all $\Delta_0$

To prove $s=R_x$, it suffices to prove that $s(n)=R(n)$ for each $n\in\operatorname{dom}s$. By induction, assume that $s(n)=R(n)$. For each $a\in R(n+1)$, we have $a = \bigcup\{\{b\}\mid b\in a\}$, and each $b\in a$ is an element of $R(n)$. Hence we can prove $a\in s(n+1)$ by induction on the size of $a$.