|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png) Viewing Message
|
|
|
| ``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 ] | |
|
|
|
|
|
|
|
