# GetWiki

*Structural induction*

ARTICLE SUBJECTS

being →

database →

ethics →

fiction →

history →

internet →

language →

linux →

logic →

method →

news →

policy →

purpose →

religion →

science →

software →

truth →

unix →

wiki →

ARTICLE TYPES

essay →

feed →

help →

system →

wiki →

ARTICLE ORIGINS

critical →

forked →

imported →

original →

Structural induction

[ temporary import ]

**please note:**

- the content below is remote from Wikipedia

- it has been imported raw for GetWiki

**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

*P*(

*x*) holds for all

*x*of some sort of recursively defined structure, such asformulas, 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

*S*, then it must hold for

*S*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

*x*.)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 '

**- content above as imported from Wikipedia**

- "

- time: 12:10am EST - Tue, Dec 11 2018

- "

__Structural induction__" does not exist on GetWiki (yet)- time: 12:10am EST - Tue, Dec 11 2018

[ this remote article is provided by Wikipedia ]

LATEST EDITS [ see all ]

GETWIKI 09 MAY 2016

GETWIKI 18 OCT 2015

GETWIKI 20 AUG 2014

GETWIKI 19 AUG 2014

GETWIKI 18 AUG 2014

© 2018 M.R.M. PARROTT | ALL RIGHTS RESERVED