Metraipolis › archive › dc_cbbf89863c0b
Structural induction — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Structural_induction
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T11:25:28.440Z
- SHA-256 of the archived text
89771ac83bf04a8381477cfcc44fe7854ebf90790fcb222e20fb75f4993ce245- Stable URL of this page
https://metraipolis.com/documento/dc_cbbf89863c0b
How to cite
Structural induction — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Structural_induction (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_cbbf89863c0b (Metraipolis archive dc_cbbf89863c0b, sha256 89771ac83bf04a8381477cfcc44fe7854ebf90790fcb222e20fb75f4993ce245)
BibTeX
@misc{dccbbf89863c0b,
title = {Structural induction — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Structural_induction},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_cbbf89863c0b; sha256 89771ac83bf04a8381477cfcc44fe7854ebf90790fcb222e20fb75f4993ce245},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Structural_induction. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 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 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 "<", in which L < M whenever list L is the tail of list M. Under this ordering, the empty list [] is the unique minimal element. A structural induction proof of some proposition P(L) then consists of two parts: A proof that P([]) is true and a proof that if P(L) is true for some list L, and if L is the tail of list M, then P(M) 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 P(L) then consists of:
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Graph theory»).
Fonte: Wikipedia in inglese, voce «Structural induction» — https://en.wikipedia.org/wiki/Structural_induction
Wikidata Q1932759 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1932759
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Structural_induction?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1375758618, consultata il 2026-10-07T11:16:08.669Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 1d4fb7c6bd38f68c49951646e4985fe0c1d6dfb453a0c70319679d6d44cad597