structural induction
(60 minutes to learn)
Summary
Many mathematical objects, such as natural numbers, lists, and trees, are defined recursively in terms of basic components and composition rules. Structural induction is a technique for proving statements inductively about recursively defined structures. One proves base cases corresponding to the base objects, as well as inductive steps corresponding to each of the composition rules.
Context
-this concept has no prerequisites-
Goals
- be able to define a mathematical structure (e.g. the natural numbers) in terms of initial elements and operators
- know the Induction Principle, which lets us perform mathematical induction on such structures
- prove the correctness of the Induction Principle
Core resources (read/watch one of the following)
-Free-
→ Coursera: Introduction to Logic (2014)
An introductory logic course geared towards computer scientists.
Location:
Lecture sequence "Induction"
Other notes:
- Click on "Preview" to see the videos.
-Paid-
→ A Mathematical Introduction to Logic
An undergraduate textbook in mathematical logic, with proofs.
Location:
Section 1.4, "Induction and recursion," subsection "Induction," pages 34-38
See also
-No Additional Notes-