Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
7  
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.A 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.A Mar 8 '12 at 13:26
5  
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
show 4 more comments

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.