structural induction

(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.
Author: Michael Genesereth
Other notes:
  • Click on "Preview" to see the videos.


See also

-No Additional Notes-