Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural numbers and can be further generalized to arbitrary Noetherian induction. Structural recursion is a recursion method bearing the same relationship to structural induction as ordinary recursion bears to ordinary mathematical induction.
Structural induction is used to prove that some proposition holds for all of some sort of recursively defined structure, such as formulas, lists, or trees. A well-founded partial order is defined on the structures ("subformula" for formulas, "sublist" for lists, and "subtree" for trees). The structural induction proof is a proof that the proposition holds for all the minimal structures and that if it holds for the immediate substructures of a certain structure , then it must hold for also. (Formally speaking, this then satisfies the premises of an axiom of well-founded induction, which asserts that these two conditions are sufficient for the proposition to hold for all .)
A structurally recursive function uses the same idea to define a recursive function: "base cases" handle each minimal structure and a rule for recursion. Structural recursion is usually proved correct by structural induction; in particularly easy cases, the inductive step is often left out. The length and ++ functions in the example below are structurally recursive.
For example, if the structures are lists, one usually introduces the partial order "<", in which whenever list is the tail of list . Under this ordering, the empty list is the unique minimal element. A structural induction proof of some proposition then consists of two parts: A proof that is true and a proof that if is true for some list , and if is the tail of list , then must also be true.
Eventually, there may exist more than one base case and/or more than one inductive case, depending on how the function or structure was constructed. In those cases, a structural induction proof of some proposition then consists of:
Examples
An ancestor tree is a commonly known data structure, showing the parents, grandparents, etc. of a person as far as known (see picture for an example). It is recursively defined: in the simplest case, an ancestor tree shows just one person (if nothing is known about their parents); alternatively, an ancestor tree shows one person and, connected by branches, the two ancestor subtrees of their parents (using for brevity of proof the simplifying assumption that if one of them is known, both are).
As an example, the property "An ancestor tree extending over generations shows at most persons" can be proven by structural induction as follows: In the simplest case, the tree shows just one person and hence one generation; the property is true for such a tree, since . Alternatively, the tree shows one person and their parents' trees. Since each of the latter is a substructure of the whole tree, it can be assumed to satisfy the property to be proven (a.k.a. the induction hypothesis). That is, and can be assumed, where and denotes the number of generations the father's and the mother's subtree extends over, respectively, and and denote the numbers of persons they show. In case , the whole tree extends over generations and shows persons, andi.e. the whole tree satisfies the property. In case , the whole tree extends over generations and shows persons by similar reasoning, i.e. the whole tree satisfies the property in this case also. Hence, by structural induction, each ancestor tree satisfies the property.
As another, more formal example, consider the following property of lists :
Here denotes the list concatenation operation, the list length, and and are lists.
In order to prove this, we need definitions for length and for the concatenation operation. Let denote a list whose head (first element) is and whose tail (list of remaining elements) is , and let denote the empty list. The definitions for length and the concatenation operation are:
Our proposition is that is true for all lists when is . We want to show that is true for all lists . We will prove this by structural induction on lists.
First we will prove that is true; that is, is true for all lists when happens to be the empty list . Consider :
So this part of the theorem is proved; is true for all , when is , because the left-hand side and the right-hand side are equal.