This is a very convenient diagrammatic form in which to present recursive programs, as we illustrate in Example 6.4.7 and Exercises 6.27 ff. Expand and rearrange the diagram of partial functions. Z Q satisfying the recursion equation. Then the two parallel rectangles on the right commute since p and q are total attempts. V be the equaliser of p and q , and form the pullback H .
T Q are equal by construction, and j is mono by hypothesis.
See also Exercise 6.14 . The general recursion theorem It remains to show that well-foundedness is sufficient for recursion. There is a zero attempt, with as support, and we now describe the successor. Remark 6.3.1 says that T acts on such diagrams. Then Y and Z are well founded by Corollary 6.3.6 .