Paper 1, Section II, I

Logic and Set Theory
Part II, 2014

Explain what is meant by saying that a binary relation ra×ar \subseteq a \times a is well-founded. Show that rr is well-founded if and only if, for any set bb and any function f:Pbbf: \mathcal{P} b \rightarrow b, there exists a unique function g:abg: a \rightarrow b satisfying

g(x)=f({g(y)y,xr})g(x)=f(\{g(y) \mid\langle y, x\rangle \in r\})

for all xax \in a. [Hint: For 'if', it suffices to take b={0,1}b=\{0,1\}, with f:Pbbf: \mathcal{P} b \rightarrow b defined by f(b)=11b.]\left.f\left(b^{\prime}\right)=1 \Leftrightarrow 1 \in b^{\prime} .\right]