Wellfounded relation

In mathematics, a wellfounded relation is an order relation R on a set X where every nonempty subset of X has an Rminimal element; that is, where for every nonempty subset S of X, there is an element m of S such that for every element s of S, s R m implies s = m.
Note that this differs from the definition of the wellorder relation, where the relation is required to be totally ordered and thus requires Rleast elements instead of merely Rminimal ones.
A set equipped with a wellfounded relation is sometimes said to be a wellfounded set. A wellfounded set is a partially ordered set in which every nonempty subset has a minimal element. Equivalently, assuming some choice, it is a partially ordered set which contains no infinite descending chains. If the order is a total order then the set is called a wellordered set.
One reason that wellfounded sets are interesting is because a version of transfinite induction can be used on them: if (X, <=) is a wellfounded set and P(x) is some property of elements of X and you want to show that P(x) holds for all elements of X, you can proceed as follows:
 show that P(x) is true for all minimal elements of X
 show that, if x is an element of X and P(y) is true for all y <= x with y ≠ x, then P(x) must also be true.
Examples of wellfounded sets which are not totally ordered are:
 the positive integers {1, 2, 3, ...}, with the order defined by a <= b iff a divides b.
 the set of all finite strings over a fixed alphabet, with the order defined by s <= t iff s is a substring of t
 the set N × N of pairs of natural numbers, ordered by (n_{1}, n_{2}) <= (m_{1}, m_{2}) iff n_{1} ≤ m_{1} and n_{2} ≤ m_{2}.
 the set of all regular expressions over a fixed alphabet, with the order defined by s <= t iff s is a subexpression of t
 any set whose elements are sets, with the order defined by A <= B iff A is an element of B.
If (X, ≤) is a wellfounded set and x is an element of X, then the descending chains starting at x are all finite, but this does not mean that their lengths are necessarily bounded. Consider the following example: Let X be the union of the positive integers and a new element ω, which is bigger than any integer. Then X is a wellfounded set, but there are descending chains starting at ω of arbitrary great (finite) length; the chain ω, n1, n2, ..., 2, 1 has length n for any n.
A familiar example of a wellfounded relation is the ordinary < relation on the set of natural numbers N. Every nonempty subset of the natural numbers contains a smallest element. This is known as the wellordering principle.
Wellfoundedness is interesting because the powerful technique of induction can be used to prove things about members of wellfounded sets. For the example of the natural numbers above, this technique is called mathematical induction. When the wellfounded set is the set of all ordinal numbers, and the wellfounded relation is set membership, the technique is called transfinite induction. When the wellfounded set is a set of recursivelydefined data structures, the technique is called structural induction. See the articles under those heads for more details.
The axiom of regularity, which is one of the axioms of ZermeloFraenkel set theory, asserts that all sets are wellfounded. The impact of this axiom is that there are no sets in ZFC which contain themselves.de:Fundierte Menge fa:اصل خوشترتیبی