# well-founded induction

## Primary tabs

Keywords:
well-founded relation, induction
Type of Math Object:
Theorem
Major Section:
Reference
Groups audience:

## Mathematics Subject Classification

### You lost me...

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 }?

### Re: You lost me...

I wil post other definitions. An R-minimal element of a set X is an element a in X that has no "predecessors", so all the elements in your set are R-minimal if R is the division relation.

### Re: You lost me...

There was actually a caveat, in the division relation, it is better not to allow 1 to be related to anything, i.e. you define aRb if and only if a|b and a!=1, otherwise you run into trouble.

### update suggestion

[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.

!(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.

### Re: update suggestion

[Now both of my posts appear in the listing. me stupid should have used the reload button.]

### Re: update suggestion

> _____________________________________________
>
> 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.
> _____________________________________________

Shouldn't "minimal" be "minimum" in (ii)?

### Re: update suggestion

"Minimal" refers to the above described term "E-minimal". But you are right, for a totally ordered set, we can also use the term minimum from other contexts.