Structural induction is a proof method that is used in mathematical logic (e.g., the proof of Los s theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction.
In general, the idea is that one wishes to prove some proposition P ( x ), where x is any instance of some sort of recursively-defined structure such as lists or trees. A well-founded partial order is defined on the structures. The structural induction proof then consists of proving that the proposition holds for all the minimal element structures, and that if it holds for the substructures of a certain structure S , then it must hold for S also. For example, if the structures are lists, one usually introduces the partial order
