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<x}$ ${\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}$

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

${\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}$

• the set of finite words over a given alphabet with the order

${\displaystyle s\leq t}$If a substring of is ${\displaystyle s}$ ${\displaystyle t}$

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

${\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{ oder }}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{ und }}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)}$

See also

• Structural induction