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 Graph Search.
Concept
Well-quasi-ordering
Summary
In mathematics, specifically order theory, a well-quasi-ordering or wqo on a set is a quasi-ordering of for which every infinite sequence of elements from contains an increasing pair with
Well-founded induction can be used on any set with a well-founded relation, thus one is interested in when a quasi-order is well-founded. (Here, by abuse of terminology, a quasiorder is said to be well-founded if the corresponding strict order is a well-founded relation.) However the class of well-founded quasiorders is not closed under certain operations—that is, when a quasi-order is used to obtain a new quasi-order on a set of structures derived from our original set, this quasiorder is found to be not well-founded. By placing stronger restrictions on the original well-founded quasiordering one can hope to ensure that our derived quasiorderings are still well-founded.
An example of this is the power set operation. Given a quasiordering for a set one can define a quasiorder on 's power set by setting if and only if for each element of one can find some element of that is larger than it with respect to . One can show that this quasiordering on needn't be well-founded, but if one takes the original quasi-ordering to be a well-quasi-ordering, then it is.
A well-quasi-ordering on a set is a quasi-ordering (i.e., a reflexive, transitive binary relation) such that any infinite sequence of elements from contains an increasing pair with . The set is said to be well-quasi-ordered, or shortly wqo.
A well partial order, or a wpo, is a wqo that is a proper ordering relation, i.e., it is antisymmetric.
Among other ways of defining wqo's, one is to say that they are quasi-orderings which do not contain infinite strictly decreasing sequences (of the form ) nor infinite sequences of pairwise incomparable elements. Hence a quasi-order (X, ≤) is wqo if and only if (X,
Official source
About this result
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.