Thomas A. Alspaugh
Structural Induction

A proof of P(x) by structural induction over the elements of a recursively defined set X is analogous to those by mathematical and strong induction, except:

  1. its basis step proves P(x0) for every element x0 in the basis set of X, and
  2. its inductive step proves that for every recursive rule from x1, x2, … , xn to x, if P(x1), P(x2), … , P(xn) then P(x).

Every well-formed propositional logic formula contains an equal number of left and right parentheses.

Basis steps:

  1. T has an equal number (0) of left and right parentheses.
  2. F has an equal number (0) of left and right parentheses.
  3. a has an equal number (0) of left and right parentheses.
  4. …
  5. z has an equal number (0) of left and right parentheses.

Inductive steps:

  1. If φ has equal numbers of left and right parentheses, then ¬φ has the same equal numbers of left and right parentheses.
  2. If φ1 has equal numbers m of left and right parentheses, and φ2 has equal numbers n of left and right parentheses, then φ1∧φ2 has equal numbers m+n of left and right parentheses.
  3. If φ1 has equal numbers m of left and right parentheses, and φ2 has equal numbers n of left and right parentheses, then φ1∨φ2 has equal numbers m+n of left and right parentheses.
  4. If φ has equal numbers n of left and right parentheses, then (φ) has n+1 left and n+1 right parentheses, an equal number of both.

As with mathematical and strong induction proofs, a structural inductive proof of P(x) can be thought of as a recipe for constructing a proof for any specific element y of the set. If y is an element of the set, there is a sequence of rule applications that begins from one or more elements of the basis set and ends with y, and the specific proof of P(y) begins with the basis step(s) for the basis elements that were used, continues with the inductive steps for the rules that were used, and concludes with P(y).

Another way of thinking of a structural inductive proof is that it shows that the proposition is true for the basis elements, and then shows that all of the rules preserve the proposition for all derived elements.

flip bgunflip