PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (198)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
well-founded induction (Theorem)

Definition. Let $ S$ be a non-empty set, and $ R$ be a binary relation on $ S$. Then $ R$ is said to be a well-founded relation if and only if every nonempty subset $ X\subseteq S$ has an $ R$-minimal element. 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 order, or even a partial order. 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 $ \mathbb{N}$ of natural numbers ordered by division, i.e. $ aRb$ if and only if $ a$ divides $ b$, and $ a\not=1$. The $ R$-minimal elements of $ \mathbb{N}$ are the prime numbers.

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

  1. $ \Phi$ is true for all the $ R$-minimal elements of $ S$
  2. for every $ a$, if for every $ x$ such that $ xRa$, 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.



Anyone with an account can edit this entry. Please help improve it!

"well-founded induction" is owned by ratboy. [ full author list (4) | owner history (1) ]
(view preamble)

View style:

See Also: principle of finite induction

Keywords:  well-founded relation, induction

Attachments:
proof of the well-founded induction principle (Proof) by jihemme
example of well-founded induction (Example) by CWoo
well-founded recursion (Theorem) by CWoo
Log in to rate this entry.
(view current ratings)

Cross-references: fundamental theorem of arithmetic, property, prime numbers, divides, division, natural numbers, totally ordered, partial order, even, total order, subset, relation, well-founded, binary relation
There are 4 references to this entry.

This is version 19 of well-founded induction, born on 2002-06-01, modified 2007-07-03.
Object id is 2988, canonical name is WellFoundedInduction.
Accessed 15723 times total.

Classification:
AMS MSC: 03B10 (Mathematical logic and foundations :: General logic :: Classical first-order logic)
Pending Errata and Addenda
None.
[ View all 5 ]
Discussion
Style: Expand: Order:
forum policy
update suggestion by Schneemann on 2006-02-27 12:28:58
[I posted the same in the discussion on an update by smw, but it doesn't appear in the general discussions listing on the PlanetMath starting page. So I decided to post it here instead.]

I suggest the following wording. (it's a matter of taste to replace (V, E) by (S, R) or similar, and drop the term "graph")

Def (notations). In a directed graph (V, E) with y \in V, the set [*, y) contains all x \in V with (x, y) \in E.
_____________________________________________

Thm. Let (V, E) be a directed graph. The following are equivalent.

(i) Every nonempty subset S \subseteq V has an E-minimal element y \in S, that means [*, x) \cap S = \emptyset.

(ii) If A \subseteq V, such that
 . . . for any y \in V,
 . . . . if [*, y) \subseteq A, then y in A,
 . . then A = L.

Def. A directed graph (V, E) or the binary relation E with the above property (i) is called well-founded.
_____________________________________________

Proof.

![(i) and !(ii)]: Assume A != V, but [*, x) \subseteq A always implies that x in A. Have a look at B = L-A, with a minimal element b \in B.
[*, b) \cap B = \emptyset => [*, b) \subseteq A.
=> contradiction.

!(i) => !(ii): Assume there's a nonempty B \subseteq V with no minimum. Set A = V-B \neq \emptyset. Then for every y \in S with [*, y) \subseteq A, y \in A. (otherwise, y would be a minimal element of B.) However, A != V.
_____________________________________________

Thm. Let (M, <) be a (anti-reflexive) poset. The following are equivalent.

(i) (M, <) is well-founded.

(ii) Every totally ordered, nonempty S \subseteq M has a minimal element.
_____________________________________________

Proof. one proof was posted by smw in the discussion on "transfinite induction".
Another (or the same?) idea is that every nonempty subset has a maximal chain (that can't be further extended by adding smaller and larger elements), and the minimum of this chain is also a minimum of the subset.
_____________________________________________

Thm. Let (M, <) be a totally ordered (anti-reflexive) set (a chain). The following are equivalent.

(i) (M, <) is well-founded.

(ii) (M, <) is well-ordered.
[ reply | up ]
You lost me... by patrickwonders on 2002-06-02 10:28:15
You say it's well-founded only if every subset
has an R-minimal element.

Then, you say the natural numbers are
well-founded under order by division but not
well-ordered. You say that the primes
are the R-minimal elements of that ordering.
Well, then... what R-minimal element is
there in the subset { 6, 8, 9, 10, 15, 25 }?
[ reply | up ]
Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)