Well-founded relation

In mathematics, a well-founded set ( also well-founded amount, founded ordering, order terminating, noetherian order ) is a partially ordered set that contains no infinite descending chains genuine. Equivalently, ie, a partially ordered set 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 least element and the smallest element of a set is always minimal. Unlike well-ordered sets need authoritative quantities not to be totally ordered. All sound totally ordered sets are well-ordered.

Noetherian induction

Sound levels allow the application of Noetherian induction, a version of transfinite induction: If P is a property of elements of an order relation ≤ among a well-founded set X, and the following statements are true:

Then P ( x ) is true for all elements x of X.

Examples

The integers, rational numbers and the real numbers contain infinite strictly decreasing chains in their natural order and are therefore not regarded.

The power set of a set with the subset relation as the order is then grounded precisely when the set is finite. All finite partially ordered sets are well-founded, because finite sets can have only finite chains.

The following quantities are well-founded, but not totally ordered:

  • The natural numbers N = {1, 2, 3, ...} with the order
  • The amount of N × N of all pairs of natural numbers with the order
  • The set of finite words over a given alphabet with the order
  • The set of regular expressions over a given alphabet with the order
  • Each set of sets of atomic

Length Descending chains

If (X, ≤ ) is a well-founded set and x from X, then the beginning at x descending chains are all finite, but its length must not be limited. Consider, for example, the amount

( wherein N0 = {0, 1, 2, 3, ...} ) having the order

It is, for example, (0,0) > (4,1) > (4,2) > (4,3) > (4,4) and (0,0) > (2,1) > (2, 2). X is well-founded, but there is at (0,0 ) starting Descending chains of arbitrary ( finite ) length.

Alphabet (computer science) Structural induction
355700
de