4.II.16G

Set Theory and Logic
Part II, 2007

Explain what is meant by a well-founded binary relation on a set.

Given a set aa, we say that a mapping f:aPaf: a \rightarrow \mathcal{P} a is recursive if, given any set bb equipped with a mapping g:Pbbg: \mathcal{P} b \rightarrow b, there exists a unique h:abh: a \rightarrow b such that h=ghfh=g \circ h_{*} \circ f, where h:PaPbh_{*}: \mathcal{P} a \rightarrow \mathcal{P} b denotes the mapping a{h(x)xa}a^{\prime} \mapsto\left\{h(x) \mid x \in a^{\prime}\right\}. Show that ff is recursive if and only if the relation {x,yxf(y)}\{\langle x, y\rangle \mid x \in f(y)\} is well-founded.

[If you need to use any form of the recursion theorem, you should prove it.]