# Order Theory: Definition

What is the difference between :

• Quasi Orders
• Partial Orders
• Well Quasi Orders
• Well Founded Orders and
• Complete Partial Orders

What is the benefit of each of them if exist ? why do we need such things in Mathematics ?

-
You can find all definitions on Wikipedia. – Michael Greinecker Mar 8 '12 at 13:19
Definitons in W.P are overlapped with different names. – M.M Mar 8 '12 at 13:22
Terminology is not uniform. Many people call quasi orders preorders and complete partial orders complete lattices. – Michael Greinecker Mar 8 '12 at 13:24
This is why I have this misunderstanding – M.M Mar 8 '12 at 13:26
Why not write down some definitions, and ask others to correct you? People here always seem willing to correct others! – GEdgar Mar 8 '12 at 13:35

There’s nothing here that you can’t find in Wikipedia, but perhaps it’s useful to gather these in one place. A binary relation $\preceq$ on a set $S$ is:

• a quasi-order, also sometimes called a preorder, if $\preceq$ is a reflexive, transitive relation on $S$;

• a partial order if $\preceq$ is a reflexive, transitive, antisymmetric relation on $S$ (so a partial order is an antisymmetric quasi-order);

• well-founded if every non-empty subset $A$ of $S$ has a minimal element with respect to $\preceq$, i.e., an element $m\in A$ such that if $a\in A$, and $a\preceq m$, then $m\preceq a$;

• a well-founded partial order if it is both well-founded and a partial order on $S$; and

• a well-quasi-order if it is a well-founded quasi-order on $S$ with no infinite antichains, where an antichain is a subset $A$ of $S$ such that for all $a,b\in A$ with $a\ne b$, $a\not\preceq b$ and $b\not\preceq a$. Equivalently, $\preceq$ is a well-quasi-order on $S$ if it is a quasi-order on $S$ with the property that for each infinite sequence $s_0,s_1,s_2,\dots$ in $S$ there are indices $m<n$ such that $s_m\preceq s_n$.

Assuming some part of the axiom of choice, $\preceq$ is well-founded if and only if there is no infinite, strictly decreasing sequence with respect to $\preceq$. That is, if we write $x\succ y$ to mean that $y\preceq x$ and $x\ne y$, then $\preceq$ is well-founded if and only if there is no infinite sequence $$s_0\succ s_1\succ s_2\succ\dots$$ in $S$.

The term complete partial order is in my opinion too ambiguous to be used without giving a definition any time you use it. For the notion of directed-complete partial order see Wikipedia.

All of these notions are important in one or another part of mathematics. Partial orders in particular are ubiquitous; I can’t think of a branch of mathematics in which I’ve not encountered them. Quasi-orders are a very natural generalization of partial orders. Imagine ranking a bunch of alternatives, for instance: if no two alternatives get the same rank, you have a partial order $-$ in fact, a linear (or total) order $-$ but if you give two alternatives the same rank, you now have only a quasi-order. In other words, quasi-orders allow you to have distinct elements that occupy the same position in the order.

Well-foundedness is important in part because it allows inductive arguments to be carried out; they may not be quite so noticeable as partial orders, but well-founded relations are also found throughout mathematics.

Well-quasi-orders are much less familiar objects, but the very title of J.B. Kruskal’s The theory of well-quasi-ordering: A frequently discovered concept (Journal of Combinatorial Theory, Series A 13 (3): 297–305) is a pretty clear indication that they are useful. And that, in the end, is the only real answer to ‘Why do we need $X$ in mathematics?’: because it proves useful.

-
With these definitions it would seem that a well-founded quasi-order is automatically a partial order: if one would have both $x\preceq y$ and $y\preceq x$ with $x\neq y$, then the finite set $\{x,y\}$ has no minimal element. Of so, then why the "quasi" in "well-quasi-order"? – Marc van Leeuwen Mar 8 '12 at 14:43
@Marc: Both elements of that set are $\preceq$-minimal; I just tried to be too efficient and need to fix the definition of minimal. – Brian M. Scott Mar 8 '12 at 14:48