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 ?

  • 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 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.

  • 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