**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Well-founded relation

Summary

In mathematics, a binary relation R is called well-founded (or wellfounded or foundational) on a class X if every non-empty subset S ⊆ X has a minimal element with respect to R, that is, an element m ∈ S not related by s R m (for instance, "s is not smaller than m") for any s ∈ S. In other words, a relation is well founded if
(\forall S \subseteq X); [S \neq \varnothing \implies (\exists m \in S) (\forall s \in S) \lnot(s \mathrel{R} m)].
Some authors include an extra condition that R 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 x0, x1, x2, ... of elements of X such that xn+1 R xn for every natural number n.
In order theory, a partial order

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people

No results

Related publications

No results

Related units

No results

Related concepts

No results

Related lectures

Related courses

No results

No results