Structural Induction: Definition
To prove \(P(x)\) holds for all Q#1 in recursively defined set \(R\), prove:
-
\(P(\)Q#2\()\) for each base case \(b\) in Q#3
-
\(P(\)Q#4\()\) for each constructor, \(c\), assuming induction hypothesis \(P(\)Q#5\()\)
-
Which variable should replace the placeholder Q#1?
-
Which variable should replace the placeholder Q#2?
-
Which variable should replace the placeholder Q#3?
-
Which variable should replace the placeholder Q#4?
-
Which variable should replace the placeholder Q#5?