# Well-founded crowd

In mathematics a **well-founded set** (also **well-founded set** , **well-founded order** , **terminating order** , **Noetherian order** ) is a semi-ordered set that does not contain any infinite, genuinely descending chains. Equivalently, a semi-ordered set is called well-founded if every non-empty subset contains at least one minimal element .

All well-ordered sets are well-founded because in a well-ordered set every non-empty subset must have a smallest element and the smallest element of a set is always minimal. Unlike well-ordered sets, well-founded sets do not need to be totally ordered . All totally ordered well-founded sets are well ordered.

## Noetherian induction

Profound amounts allow the application of noetherian induction, a version of transfinite induction : Is a property of elements of a under an order relation depth amount , and the following statements are true:

- is true for all minimal elements of .
- If an element of and is true for all , then is also true.

Then true for all elements of .

## Examples

The whole numbers , the rational numbers, and the real numbers in their natural order each contain infinite descending chains and are therefore not well founded.

The power set of a set with the subset relation as order is well founded if and only if the set is finite . All finite semi-ordered sets are well-founded because finite sets can only have finite chains.

The following sets are well-founded but not totally ordered:

- the natural numbers with the order

- If a divisor of is

- the set of sub-modules of a noetheric module with the order

- if

- the set of all pairs of natural numbers with order

- if and

- If a substring of is

- the set of regular expressions over a given alphabet with the order

- If a part of expression is

- loads of sets with the order

- , if is an element of (really element, not subset!)

## Length of descending chains

If and is a well-founded set , then the descending chains at the beginning are all finite, but their length does not have to be restricted. Consider e.g. B. the amount

(where ) with the order

- if or

It is z. B. and . is well-founded, but there are descending chains of arbitrary (finite) length at the beginning.