The Definition of Definition by Recursion

120 Views Asked by At

The following is presented as the Transfinite Recursion on well-founded relations in Kenneth Kunen's book.

Assume that $R$ is set like and well founded on $A$ and $\forall{x,s}\exists{!y}\varphi{(x,s,y)}$. Define $G(x,s)$ to be the unique $y$ such that $\varphi{(x,s,z)}$. Then we can write a formula $\psi(x,y)$ for which the following is provable.

1) $\forall{x}\exists{!y}\psi{(x,y)}$, so $\psi$ defines a function $F$ where $F(x)$ is the $y$ such that $\psi(x,y)$.

2) $\forall{a}\in{A} [F(a)=G(a, F\upharpoonright(a\downarrow))]$.

When condition 2) is expressed as a formula, does it become:

$\forall{x\in{A}}\forall{y,z}(\psi(x,y)\iff\varphi(x,z,y)\wedge\psi{(x\downarrow,z)})$

or is it something else?

EDIT 1) Fixed typo.

1

There are 1 best solutions below

0
On

If I’m reading it correctly, (2) appears to expand to this:

$$\forall x\in A\,\exists!y\,\exists!z\Big(\psi(x,y)\land\psi(x\!\!\downarrow,z)\land\varphi(x,z,y)\Big)$$

I think that you have a typo in (1): your $\psi(x,s,y)$ should be $\psi(x,y)$.