(60 minutes to learn)
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.
-this concept has no prerequisites-
- 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)
→ Coursera: Introduction to Logic (2014)
An introductory logic course geared towards computer scientists.
Location: Lecture sequence "Induction"
- Click on "Preview" to see the videos.
→ 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
-No Additional Notes-
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation