Editing Well-quasi-ordering (section)

==Motivation==

[[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 <math>\le</math> is said to be well-founded if the corresponding strict order <math>x\le y\land y\nleq x</math> 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 <math>\le</math> for a set <math>X</math> one can define a quasiorder <math>\le^{+}</math> on <math>X</math>'s power set <math>P(X)</math> by setting <math>A \le^{+} B</math> if and only if for each element of <math>A</math> one can find some element of <math>B</math> that is larger than it with respect to <math>\le</math>. One can show that this quasiordering on <math>P(X)</math> needn't be well-founded, but if one takes the original quasi-ordering to be a well-quasi-ordering, then it is.