# 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: ${\ displaystyle P}$${\ displaystyle \ leq}$${\ displaystyle X}$

1. ${\ displaystyle P (x)}$is true for all minimal elements of .${\ displaystyle X}$
2. If an element of and is true for all , then is also true.${\ displaystyle x}$${\ displaystyle X}$${\ displaystyle P (y)}$${\ displaystyle y ${\ displaystyle P (x)}$

Then true for all elements of . ${\ displaystyle P (x)}$${\ displaystyle x}$${\ displaystyle X}$

## 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${\ displaystyle \ mathbb {N} = \ left \ {1,2,3, \ ldots \ right \}}$
${\ displaystyle a \ leq b}$If a divisor of is${\ displaystyle a}$${\ displaystyle b}$
${\ displaystyle M \ leq N}$if ${\ displaystyle N \ subseteq M}$
• the set of all pairs of natural numbers with order${\ displaystyle \ mathbb {N} \ times \ mathbb {N}}$
${\ displaystyle (m, n) \ leq (a, b)}$if and${\ displaystyle m \ leq a}$${\ displaystyle n \ leq b}$
${\ displaystyle s \ leq t}$If a substring of is${\ displaystyle s}$${\ displaystyle t}$
${\ displaystyle s \ leq t}$If a part of expression is${\ displaystyle s}$${\ displaystyle t}$
• loads of sets with the order
${\ displaystyle A \ leq B}$, if is an element of (really element, not subset!)${\ displaystyle A}$${\ displaystyle B}$

## 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 ${\ displaystyle (X, \ leq)}$${\ displaystyle x \ in X}$${\ displaystyle x}$

${\ displaystyle X: = \ left \ {(a, b) \ mid a, b \ in \ mathbb {N} _ {0}, a \ geq b> 0 {\ mbox {or}} a = b = 0 \ right \}}$

(where ) with the order ${\ displaystyle \ mathbb {N} _ {0} = \ left \ {0,1,2,3, \ ldots \ right \}}$

${\ displaystyle (m, n) \ leq (a, b)}$if or${\ displaystyle (a, b) = (0,0)}$${\ displaystyle (m = a {\ mbox {and}} n \ geq b)}$

It is z. B. and . is well-founded, but there are descending chains of arbitrary (finite) length at the beginning. ${\ displaystyle (0.0)> (4.1)> (4.2)> (4.3)> (4.4)}$${\ displaystyle (0,0)> (2,1)> (2,2)}$${\ displaystyle X}$${\ displaystyle (0,0)}$