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

-Paid-

See also

-No Additional Notes-