Induction

This chapter is about two of the most important topics in a course on discrete mathematics —induction and inductive definitions. Nowadays most authors prefer to call “inductive” definitions “recursive”. These topics are called upon in numerous sequel courses such as logic, data structures, theory of computation, design and analysis of algorithms. In this chapter we introduce the induction (proof) principle on \({\mathbb {N}}\) as an equivalent principle to the least (integer) principle on \({\mathbb {N}}\) . But we also generalise induction in two important directions making this tool sophisticated enough to be applicable to advanced readings, for example (axiomatic) set theory, which is relevant to mathematics students: One direction is to recognise that the induction principle (equivalently, the minimal conditionMinimal condition or principle, MC, which is a generalisation of the least principle on \({\mathbb {N}}\) ) which on \({\mathbb {N}}\) is an attribute of the “natural” order <, can be extended to arbitrary orders on arbitrary classes. This opens applicability of induction to any classes that are equipped with an order that has MC.