Go backward to Mathematical Induction Go up to Top Go forward to Example

Structural Induction

Mathematical induction relies on structure of natural numbers:

N ::= 0 | N + 1

• Show that all trees of zero depth has P.
• Assume trees of depth m or less have P.
• Prove that tree of depth m+1 has P.

Arbitrary syntax domains:

• D ::= Option₁ | Option₂ | ... | Option_n
• To prove that all members of D have P
  1. Assume occurences of D in Option_i have P,
  2. Prove that Option_i has P.
  (for each Option_i).