PlanetMath: definition too restrictive ?

(more info)

Math for the people, by the people.

donor list - find out how

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (237)
Orphanage
Unclass'd
Unproven (550)
Corrections (54)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Copyright
About

Viewing Correction to 'well-founded induction'

definition too restrictive ? by smw
Correction id: 7571
Filed on: 2006-02-19 23:30:20
Status: Accepted on 2006-03-24 23:24:25
Type: Meta/Minor

Correction text:

It appears that you restrict the definition of well-foundedness to posets, but the proof of well-founded induction only uses the property that "every nonempty subset has a minimal element." Therefore, it would seem that the definition of "well-foundedness" should simply be a (binary) relation R such that "every nonempty subset has an R-minimal element," and should not require that R be a partial order. (Query: In *practice,* is R usually/always a partial order?)

This Wiki is the only thing I could find that agrees with the definition as I am proposing http://en.wikipedia.org/wiki/Well-founded_relation (By the way, I can find anything, one way or the other, about this in the books that I have with me at the moment.)

No comment from object owner ratboy.

Discussion

forum policy

update by Schneemann on 2006-02-27 10:42:54

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 ]

Interact

new correction | post message