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 ?
What is the difference between :
What is the benefit of each of them if exist ? why do we need such things in Mathematics ?
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.