# 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-