Concept

Well-quasi-ordering

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,

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.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.