请输入您要查询的字词:

 

单词 WellfoundedInduction
释义

well-founded induction


Definition. Let S be a non-empty set, and R be a binary relationMathworldPlanetmath on S. Then R is said to be a well-founded relation if and only if every nonempty subset XS has an R-minimal element (http://planetmath.org/RMinimalElement). When R is well-founded, we also call the underlying set S well-founded.

Note that R is by no means required to be a total orderMathworldPlanetmath, or even a partial orderMathworldPlanetmath. When R is a partial order, then R-minimality is the same as minimality (of the partial order). A classical example of a well-founded set that is not totally ordered is the set of natural numbersMathworldPlanetmath ordered by division, i.e. aRb if and only if a divides b, and a1. The R-minimal elements of are the prime numbersMathworldPlanetmath.

Let Φ be a property defined on a well-founded set S. The principle of well-founded induction states that if the following is true :

  1. 1.

    Φ is true for all the R-minimal elements of S

  2. 2.

    for every a, if for every x such that xRa, we have Φ(x), then we have Φ(a)

then Φ is true for every aS.

As an example of application of this principle, we mention the proof of the fundamental theorem of arithmeticMathworldPlanetmath : every natural number has a unique factorization into prime numbers. The proof goes by well-founded induction in the set ordered by division.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 5:06:39