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:a→Paf: a \rightarrow \mathcal{P} a is recursive if, given any set bb equipped with a mapping g:Pb→bg: \mathcal{P} b \rightarrow b, there exists a unique h:a→bh: a \rightarrow b such that h=g∘h∗∘fh=g \circ h_{*} \circ f, where h∗:Pa→Pbh_{*}: \mathcal{P} a \rightarrow \mathcal{P} b denotes the mapping a′↦{h(x)∣x∈a′}a^{\prime} \mapsto\left\{h(x) \mid x \in a^{\prime}\right\}. Show that ff is recursive if and only if the relation {⟨x,y⟩∣x∈f(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.]

Typos? Please submit corrections to this page on GitHub.