Modern Mathematical Logic

Proofs by induction and definitions by recursion are fundamental tools when working with the natural numbers. However, there are many other places where variants of these ideas apply. In fact, more delicate and exotic proofs by induction and definitions by recursion are two central tools in mathematical logic. We will eventually develop transfinite versions of these ideas in Chapter 9 to give us ways to continue into exotic, infinite realms, and these techniques are essential in both set theory and model theory. In this chapter, we develop the more modest tools of induction and recursion along structures that are generated by one-step processes, like the natural numbers. Occasionally, these types of induction and recursion are called structural.