This is a place holder for potential sponsor logos.

well-founded induction

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 $\Nat$ 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 $\Nat$ 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 :

$\Phi$ is true for all the $R$ -minimal elements of $S$
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 $\Nat$ ordered by division.

well-founded induction is owned by ratboy, Jean-Martin Albert, yark, Chi Woo.

How to Cite This Entry

ratboy, Jean-Martin Albert, yark, Chi Woo. "well-founded induction" (version 19). PlanetMath.org. Freely available at http://planetmath.org/WellFoundedInduction.html.

Classification

AMS MSC:

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

Pending Errata and Addenda

None. [ View all 5 ]

Interact

Discussion

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 ]

Re: update suggestion by Schneemann on 2006-02-27 12:32:32
Re: update suggestion by ratboy on 2006-02-27 13:47:37
- Re: update suggestion by Schneemann on 2006-02-27 14:21:49

You lost me... by Patrick Stein 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 }?