sorry for the dumbest question ever, but i want to understand total order in an intuitive way, this is the defition of total order:

i) If $a ≤ b$ and $b ≤ a$ then $a = b$ (antisymmetry);
ii) If $a ≤ b$ and $b ≤ c$ then $a ≤ c$ (transitivity);
iii) $a ≤ b$ or $b ≤ a$ (totality).

totality means that any pair of the total ordered pair is mutually comparable. i dont understand what they mean under comparable, what is the defition of comparability? i can also compare the elements of partial order, where is problem? why is partial order not not mutually comparable?

can someone explain me please in simple words :(

  • $\begingroup$ in a partial order you can't necessarily compare any two elements. For instance, suppose you only have two elements in your partially ordered set, say a and b, and that neither a<=b nor b<=a. How then can you compare a and b? $\endgroup$ – Ittay Weiss Nov 17 '12 at 9:18
  • $\begingroup$ i understand under compare this: i cannot compare elephant with laptop, because they are total different things, but i can compare numbers always, but the result is not always defined. $\endgroup$ – doniyor Nov 17 '12 at 9:21
  • 7
    $\begingroup$ OK, suppose you can compare elephants with each other to see which one is bigger, and you can compare laptops with each other to see which one is more powerful. So the set $E$ of elephants is totally ordered and the set $L$ of laptops is also totally ordered. You can look at the set $L\cup E$ of all elephants and all laptops. Then it is only partially ordered. $\endgroup$ – Dan Shved Nov 17 '12 at 9:27
  • $\begingroup$ @DanShved thanks, now i got the clue. $\endgroup$ – doniyor Nov 17 '12 at 9:28

Two distinct elements are called "comparable" when one of them is greater than the other. This is the definition of "comparable". When you have a partially ordered set, some pairs of elements can be not comparable. i.e. you can have two elements $x$ and $y$ such that $x\leqslant y$ is false and $y \leqslant x$ is also false.

For example, consider the set $\mathbb{R}^2$ and a partial order defined like this: $$ (x_1,x_2) \leqslant (y_1,y_2) \quad\textrm{iff}\quad x_1\leqslant y_1 \,\textrm{and}\,x_2 \leqslant y_2. $$ With this partial order, elements $(0,0)$ and $(1,2)$ of $\mathbb{R^2}$ are comparable, because $(0,0)\leqslant(1,2)$. But elements $(0,1)$ and $(1,0)$ are not comparable, because both statements "$(0,1)\leqslant(1,0)$" and "$(1,0)\leqslant(0,1)$" are false.

  • $\begingroup$ great Dan, this is the right explanation. Thanks! $\endgroup$ – doniyor Nov 17 '12 at 9:26
  • $\begingroup$ I don't understand how you would define "greater than." Suppose a relation is defined on the power set of some finite set. Then how would one element be "greater than" another? $\endgroup$ – user3932000 Mar 27 at 4:07

If $\le$ is a partial order on a set $A$, two elements $a,b$ of $A$ are comparable if either $a\le b$ or $b\le a$; otherwise they are not. For instance, in the partial order $\subseteq$ on $\wp(\Bbb N)$ the sets $\{0,2\}$ and $\{0,1\}$ are not comparable: neither is a subset of the other. On the other hand, the sets $\{0,2\}$ and $\{0,1,2\}$ are comparable: $\{0,2\}\subseteq\{0,1,2\}$.

Another name for a total order is linear order. It expresses the intuitive idea very well: you can picture a linear order $\le$ on a set $A$ as arranging the elements of $A$ in a line. The usual order $\le$ on $\Bbb R$ is a linear (or total) order: if $x,y\in\Bbb R$ are any real numbers, either $x\le y$, or $y\le x$. To put it another way, if $x$ and $y$ are any real numbers, at least one of the statements $x\le y$ and $x\ge y$ must be true. Contrast that with subsets of $\Bbb N$. If $A$ and $B$ are subsets of $\Bbb N$, it’s not the case that at least one of $A\subseteq B$ and $A\supseteq B$ must be true: we just saw that $A=\{0,2\}$ and $B=\{0,1\}$ are a counterexample. The linear order $\le$ lines up the real numbers as a single linear arrangement; the partial order $\subseteq$ does not line of the subsets of $\Bbb N$ in a linear arrangement.

  • $\begingroup$ Great, Brian, thanks a lot. very nicely explained! $\endgroup$ – doniyor Nov 17 '12 at 9:30
  • $\begingroup$ @doniyor: You’re welcome. $\endgroup$ – Brian M. Scott Nov 17 '12 at 9:33

Suppose we have a set that is the union of members of EvilCorp and Skynet. An order on this set is " $a\leq b$ if a has equal or lower rank than b in their company ". This satisfies i) and ii) but not iii) - we can not compare a and b if they are from different companies. So this is not a total order, even though it is quite a natural order.

  • $\begingroup$ Yeaah, you are right. thanks, very good explanation! $\endgroup$ – doniyor Nov 17 '12 at 9:31

As you know that $(D, \leq )$ is a POSET (partially ordered set) if it fulfills three properties of,

  • *R*eflexivity $a\leq a$
  • *A*ntisymmetry $a\leq b$ and $b\leq a$ implies $a=b$
  • *T*ransitivity $a\leq b$ and $b\leq c$ implies $a\leq c$

In addition to these, if all elements in your set $D$ also are comparable with each other, for instance $D$ has $\{a,b,c,d\}$ and you can compare $a\leq b$, $a\leq c$, $a\leq d$, $b\leq c$, $c\leq d$ and so on, then it can be called as a total order. i.e. when you can have the relation $\leq$ totally on all elements.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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