0
$\begingroup$

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 ?

  • 7
    You can find all definitions on Wikipedia.2012-03-08
  • 0
    Definitons in W.P are overlapped with different names.2012-03-08
  • 0
    Terminology is not uniform. Many people call quasi orders preorders and complete partial orders complete lattices.2012-03-08
  • 0
    This is why I have this misunderstanding2012-03-08
  • 6
    Why not write down some definitions, and ask others to correct you? People here always seem willing to correct others!2012-03-08
  • 0
    I want the most famous and clear definitions for these terms. I can not judge the correctness of the definitions2012-03-08
  • 0
    A start. A binary relation $\le$ on a set $E$ is a **partial order** iff it is transitive, reflexive, and anti-symmetric. **transitive**: if $a\le b$, $b \le c$, then $a \le c$. **reflexive**: for all $a \in E$, $a \le a$. **anti-symmetric**: if $a\le b$ and $b \le a$, then $a = b$.2012-03-08
  • 0
    is it the same thing as quasi orders ?2012-03-08
  • 0
    @GEdgar: And how...2012-03-08

1 Answers 1

6

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

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.

  • 0
    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"?2012-03-08
  • 0
    @Marc: Both elements of that set are $\preceq$-minimal; I just tried to be too efficient and need to fix the definition of *minimal*.2012-03-08