Structural induction

The structural induction is a proof method that is used, among other things, in logic, theoretical computer science and graph theory. It is a more general form of mathematical induction. With the method statements about the elements of recursively constructed quantities can prove ( for example, amounts of lists, formulas, graphs).

For the complete induction properties of natural numbers be proved; wherein the structural characteristics for induction amounts shown, the elements of base elements of a finite number of construction steps ( already constructed using elements ) or by means of a generating system arise. So there is minimal (also: simple or basic) elements and recursively defined (or recursively formed ) elements of the set. In the natural numbers is the basic element (or, depending on the definition of the natural numbers ) and the design step is the transition from one number to the number.

To prove a statement for the elements of a set, it is in an induction beginning the validity of the statement to the simplest members and induction circuit, the validity of the statement to the recursive elements formed under the condition that the message for the elements used in the construction applies. If both are satisfied, the statement holds for all elements. Transfer the induction so over the structural design of the elements.

Structural induction is a special case of induction for sets with a well-founded ( partial) order.

Example of a definition by structural induction

The set of propositional formulas can be by structural induction as follows define:

By this definition, for example, the following terms propositional formulas:

Many brackets can be omitted if one takes advantage of the associativity and and agreed to operator precedence.

Other examples of definitions by structural induction can be found in Articles Elementary language and word (theoretical computer science ) (definition of mirroring).

Example of a proof by structural induction

Is proved the sentence:

The proof:

The equal sign stands for syntactic equality, ie Equal sign character. In each induction step, assume that for each and the equivalent formulas exist, the only and use ( induction hypothesis ).

In a concrete structure can be the proof steps in the reverse order, ie "from the outside to the inside ", apply. For example, apply to the average of the above propositional formulas the following equivalences:

The applications of the induction step 1 and the induction start here empty, ie they do not change the expression. ( In the first formula above all induction steps and the induction base would be empty. ) The fact that the last formula can simplify yet, incidentally, is irrelevant here.

  • Theoretical computer science
  • Mathematical Logic
  • Graph Theory
752029
de