In mathematics, a binary relation  is called well-founded (or wellfounded or foundational) on a class  if every non-empty subset  has a minimal element with respect to , that is, an element  not related by  (for instance, " is not smaller than ") for any . In other words, a relation is well founded if

Some authors include an extra condition that  is set-like, i.e., that the elements less than any given element form a set.

Equivalently, assuming the axiom of dependent choice, a relation is well-founded when it contains no infinite descending chains, which can be proved when there is no infinite sequence  of elements of  such that  for every natural number .

In order theory, a partial order is called well-founded if the corresponding strict order is a well-founded relation. If the order is a total order then it is called a well-order.

In set theory, a set  is called a well-founded set if the set membership relation is well-founded on the transitive closure of . The axiom of regularity, which is one of the axioms of Zermelo–Fraenkel set theory, asserts that all sets are well-founded.

A relation  is converse well-founded, upwards well-founded or Noetherian on , if the converse relation  is well-founded on . In this case  is also said to satisfy the ascending chain condition. In the context of rewriting systems, a Noetherian relation is also called terminating.

Induction and recursion

An important reason that well-founded relations are interesting is because a version of transfinite induction can be used on them: if () is a well-founded relation,  is some property of elements of , and we want to show that

 holds for all elements  of ,

it suffices to show that:

 If  is an element of  and  is true for all  such that , then  must also be true.

That is,

Well-founded induction is sometimes called Noetherian induction, after Emmy Noether.

On par with induction, well-founded relations also support construction of objects by transfinite recursion. Let  be a set-like well-founded relation and  a function that assigns an object  to each pair of an element  and a function  on the initial segment  of . Then there is a unique function  such that for every ,

That is, if we want to construct a function  on , we may define  using the values of  for .

As an example, consider the well-founded relation , where  is the set of all natural numbers, and  is the graph of the successor function . Then induction on  is the usual mathematical induction, and recursion on  gives primitive recursion. If we consider the order relation , we obtain complete induction, and course-of-values recursion. The statement that  is well-founded is also known as the well-ordering principle.

There are other interesting special cases of well-founded induction. When the well-founded relation is the usual ordering on the class of all ordinal numbers, the technique is called transfinite induction. When the well-founded set is a set of recursively-defined data structures, the technique is called structural induction. When the well-founded relation is set membership on the universal class, the technique is known as ∈-induction. See those articles for more details.

Examples

Well-founded relations that are not totally ordered include:
 The positive integers , with the order defined by  if and only if  divides  and .
 The set of all finite strings over a fixed alphabet, with the order defined by  if and only if  is a proper substring of .
 The set  of pairs of natural numbers, ordered by  if and only if  and .
 Every class whose elements are sets, with the relation ∈ ("is an element of"). This is the axiom of regularity.
 The nodes of any finite directed acyclic graph, with the relation  defined such that  if and only if there is an edge from  to .
Examples of relations that are not well-founded include:
 The negative integers , with the usual order, since any unbounded subset has no least element.
 The set of strings over a finite alphabet with more than one element, under the usual (lexicographic) order,  since the sequence  is an infinite descending chain.  This relation fails to be well-founded even though the entire set has a minimum element, namely the empty string.
 The set of non-negative rational numbers (or reals) under the standard ordering, since, for example, the subset of positive rationals (or reals) lacks a minimum.

Other properties

If  is a well-founded relation and  is an element of , then the descending chains starting at  are all finite, but this does not mean that their lengths are necessarily bounded. Consider the following example: 
Let  be the union of the positive integers with a new element ω that is bigger than any integer.  Then  is a well-founded set, but
there are descending chains starting at ω of arbitrary great (finite) length; 
the chain  has length  for any .

The Mostowski collapse lemma implies that set membership is a universal among the extensional well-founded relations: for any set-like well-founded relation  on a class  that is extensional, there exists a class  such that  is isomorphic to .

Reflexivity

A relation  is said to be reflexive if  holds for every  in the domain of the relation. Every reflexive relation on a nonempty domain has infinite descending chains, because any constant sequence is a descending chain.  For example, in the natural numbers with their usual order ≤, we have .  To avoid these trivial descending sequences, when working with a partial order ≤, it is common to apply the definition of well foundedness (perhaps implicitly) to the alternate relation < defined such that  if and only if  and . More generally, when working with a preorder ≤, it is common to use the relation < defined such that  if and only if  and . In the context of the natural numbers, this means that the relation <, which is well-founded, is used instead of the relation ≤, which is not.  In some texts, the definition of a well-founded relation is changed from the definition above to include these conventions.

References

 Just, Winfried and Weese, Martin (1998) Discovering Modern Set Theory. I, American Mathematical Society .
 Karel Hrbáček & Thomas Jech (1999) Introduction to Set Theory, 3rd edition, "Well-founded relations", pages 251–5, Marcel Dekker 

Binary relations
집합론에서 정초 관계(整礎關係, )는 (무한히 재귀적이지 않은) 집합의 원소 관계로서 나타낼 수 있는 이항 관계이다. 정초 관계가 주어진 집합 위에서는 초한 귀납법(超限歸納法, )과 초한 재귀(超限再歸, )를 사용할 수 있다. 초한 귀납법은 모든 원소가 어떤 성질을 만족시킴을 증명할 때 사용한다. 초한 귀납법에 따르면, 어떤 술어가 모든 원소에 대하여 참임을 보이려면, 주어진 원소 ‘이전’의 모든 원소들에 대하여 참임을 가정한 채로, 그 주어진 원소에 대하여 참임을 보이면 충분하다. 이는 자연수에 대한 수학적 귀납법을 일반화한다. 초한 재귀는 정초 관계가 주어진 집합을 정의역으로 하는 함수를 정의하는 방법이다. 초한 재귀에 따르면, 주어진 원소의 함숫값을 그 ‘이전’의 원소들의 함숫값들로부터 결정하는 방법(#초한 귀납법에서의 함수 )이 정해졌을 때, 모든 원소에 대한 함숫값은 유일하게 결정된다.

정의 
집합  위의 이항 관계 에 대하여 다음 다섯 조건이 서로 동치이며, 이를 만족시키는 이항 관계를 정초 관계라고 한다.
 임의의 부분 집합 에 대하여, 인 가 존재한다.
 다음 조건을 만족시키는 열 이 존재하지 않는다.
 임의의 에 대하여, 
 다음 조건을 만족시키는 정렬 전순서 집합 과 단사 함수 가 존재한다.
 임의의 에 대하여, 
 (모스토프스키 붕괴 정리) 다음 조건을 만족시키는 집합 과 단사 함수 가 존재한다.
 임의의 에 대하여, 
 (모스토프스키 붕괴 정리) 다음 조건을 만족시키는 추이적 집합 과 전단사 함수 가 유일하게 존재한다.
 임의의 에 대하여, 
마지막 두 조건은 체르멜로-프렝켈 집합론의 정칙성 공리를 필요로 한다.

성질 
집합 에 대하여, 다음 두 조건이 서로 동치이다.
 공집합이다.
  위에 반사 관계인 정초 관계 가 존재한다.
이는 에 대한 상수열은 이므로 정초 관계의 정의를 위반하기 때문이다.

집합  위의 정초 관계  및 부분 집합 에 대하여, 의 제한  역시  위의 정초 관계이다.

초한 귀납법 
집합  위의 정초 관계 가 주어졌을 때, 다음과 같은 초한 귀납법을 사용할 수 있다. 임의의 술어 에 대하여, 다음 조건이 성립한다고 하자.
 임의의 에 대하여, 만약 라면, 이다.
그렇다면, 가 성립한다.

귀류법을 사용하여, 가 공집합이 아니라고 가정하자. 그렇다면, 의 정초성에 따라 다음 두 조건을 만족시키는 가 존재한다.
 은 거짓이다.
 
두 번째 조건에 대우를 취하면 다음과 같다.
 
따라서, 가 만족시켜야 한다고 가정한 조건에 의하여 은 참이 되는데, 이는 모순이다. 

집합  위의 정초 관계 가 주어졌을 때, 를 정의역으로 하는 함수를 초한 재귀를 통해 정의할 수 있다. 이는 다음과 같다. 임의의 집합  및 함수

에 대하여, 다음 조건을 만족시키는 유일한 함수 가 존재한다.

여기서 은 함수의 제한이다.

다음 세 조건을 만족시키는 함수 들의 집합 를 생각하자.
 
 임의의  및 에 대하여, 라면, 
 임의의 에 대하여, 
그렇다면, 다음 사실들을 보일 수 있다.
 임의의 에 대하여, 
 증명: 초한 귀납법을 사용하여, 이며, 라고 가정하자. 그렇다면 이다.
 
 증명: 초한 귀납법을 사용하여, 이며 라고 가정하자. 이며, 이며, 라고 정의하자. 그렇다면, 이며, 따라서 이다.
이제,

라고 하자. 그렇다면 는 원하는 조건을 만족시킨다. 또한, 첫 번째 사실에 따라 이러한 는 유일하다.

예

정초 집합 
집합 에서, 원소 관계 가  위의 정초 관계라면, 를 정초 집합(整礎集合, )이라고 한다. 체르멜로-프렝켈 집합론의 정칙성 공리(正則性公理, )에 따르면 모든 집합은 정초 집합이다.

정렬 원순서 집합 

원순서 집합 에 대하여 다음 두 조건이 서로 동치이다.
 는 정렬 원순서 집합이다.
  위의 원순서 를 정의하였을 때, 이항 관계 는 정초 관계이다. (여기서 는 하폐포를 뜻한다.)

순서수 
순서수의 정렬 전순서 모임  위에서는 흔히 다음과 같은 (조금 더 약한) 초한 귀납법이 사용된다. 임의의 술어 가 다음 두 조건을 만족시킨다고 하자.
 만약 라면, 이다.
 극한 순서수 에 대하여, 만약 라면, 이다.
 특히, 이다.
그렇다면, 이다.

순서수의 정렬 전순서 모임  위에서는 흔히 다음과 같은 특수한 꼴의 초한 재귀가 사용된다. 임의의 집합  및 함수

및 모임 함수

에 대하여, 다음 두 조건을 만족시키는 모임 함수 가 존재한다.
 임의의 순서수 에 대하여, 
 임의의 극한 순서수 에 대하여, 
 특히, 

(순서수의 모임은 고유 모임이지만, 초한 귀납법과 초한 재귀는 모임 정초 관계가 주어진 모임 위에서도 성립한다.)

참고 문헌

외부 링크 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

집합론