PlanetMath: well-founded induction

Math for the people, by the people.

bshanks

your stuff your info (view)
preferences
permissions
your objects
your groups
watches
corrections (1)
mailbox
notices (2)

members only user activity
user list
sys stats

add to Encyclopædia
Papers
Books
Expositions

Main Menu

the math Encyclopædia
Papers
Books
Expositions

meta Requests (55)
Orphanage (10)
Unclass'd (217)
Unproven (164)
Corrections (112)

talkback Polls
Forums
Feedback
Bug Reports

information Docs
Classification
News
Legalese
History
ChangeLog
TODO List

well-founded induction

(Theorem)

The principle of well-founded induction is a generalization of the principle of transfinite induction.

Definition. Let be a non-empty set, and be a partial order relation on . Then is said to be a well-founded relation if and only if every subset $X\subseteq S$ has an -minimal element. In the special case where is a total order, we say is well-ordered by . The structure is called a well-founded set.

Note that is by no means required to be a total order. A classical example of a well-founded set that is not totally ordered is the set $\mathbb{N}$ of natural numbers ordered by division, i.e. if and only if divides , and $a\not=1$ . The -minimal elements of this order are the prime numbers.

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

$\Phi$ is true for all the -minimal elements of
for every , if for every such that , we have $\Phi(x)$ , then we have $\Phi(a)$

then $\Phi$ is true for every $a\in S$ .

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

"well-founded induction" is owned by jihemme.

(view preamble)

Also defines:

Well-founded induction

Keywords:

Well-founded relation, induction

Attachments:: proof of the well-founded induction principle (Proof) by jihemme
example of well-founded induction (Example) by jihemme

Cross-references: fundamental theorem of arithmetic, prime numbers, order, divides, natural numbers, totally ordered, structure, well-ordered, total order, subset, relation, partial order, principle of transfinite induction
There are 2 references to this object.

This is version 10 of well-founded induction, born on 2002-06-01, modified 2002-06-08.
Object id is 2988, canonical name is WellFoundedInduction.
Accessed 695 times total.

Classification:

AMS MSC:

03B10 (Mathematical logic and foundations :: General logic :: Classical first-order logic)

Pending Errata and Addenda

None.[ View all 3 ]

Discussion

Interact