Structural Induction
Mathematical induction relies on the structure of the 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 the tree of depth m + 1 has P
Arbitrary syntax domains:
D ::= Option1 | Option2 | Option3 | …| Option n
To prove that all members of D have P
- assume occurences of D in option i have P
- prove that option I has P (for each option i)