## You are here

Homewell-founded induction

## Primary tabs

# 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 $\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.

## Mathematics Subject Classification

03B10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Lorenz system by David Bankom

Oct 19

new correction: examples and OEIS sequences by fizzie

Oct 13

new correction: Define Galois correspondence by porton

Oct 7

new correction: Closure properties on languages: DCFL not closed under reversal by babou

new correction: DCFLs are not closed under reversal by petey

Oct 2

new correction: Many corrections by Smarandache

Sep 28

new question: how to contest an entry? by zorba

new question: simple question by parag

Sep 26

new question: Latent variable by adam_reith

## Comments

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

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

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

What about this?

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 an E-minimal element y \in S, that means, [*, y) \cap S = \emptyset.

(iii) Every totally ordered, nonempty S \subseteq M has a unique minimum y \in S, that means, S \subseteq [y, *].

where [y, *] is the set of those z \in M with y=z or y<z.