Appendix B: Induction
- Last updated
- Sep 12, 2021
- Save as PDF
( \newcommand{\kernel}{\mathrm{null}\,}\)
- 1.1: B.1- Introduction
- Induction is an important proof technique which is used, in different forms, in almost all areas of logic, theoretical computer science, and mathematics. It is often contrasted with deduction, and characterized as the inference from the particular to the general.
- 1.2: B.2- Induction on ℕ
- In its simplest form, induction is a technique used to prove results for all natural numbers. We establish that something is true for 0 and show that whenever it is true for a number n, it is also true for the next number n+1.
- 1.3: B.3- Strong Induction
- There is a variant of the principle of induction in which we don’t just assume that the claim holds for the predecessor k−1 of k, but for all numbers smaller than k, and use this assumption to establish the claim for k.
- 1.4: B.4- Inductive Definitions
- In logic we very often define kinds of objects inductively, i.e., by specifying rules for what counts as an object of the kind to be defined which explain how to get new objects of that kind from old objects of that kind.
- 1.5: B.5- Structural Induction
- So far we have used induction to establish results about all natural numbers. But a corresponding principle can be used directly to prove results about all elements of an inductively defined set. This often called structural induction, because it depends on the structure of the inductively defined objects.
- 1.6: B.6- Relations and Functions
- When we have defined a set of objects inductively, we can also define relations on these objects by induction, and give inductive definitions of functions.
