7
$\begingroup$

In a partially ordered set, am I always able to order two arbitrary elements out of the set? Or is it possible that two elements within the set have no order relation to each other?

For example if there are three elements $\{a, b, c\}$ and $a \leq b$ and $a \leq c$, does either $b \leq c$ or $c \leq b$ have to hold?

I need this to understand the fixed point theory for semantics of programming languages (denotation of while loops).

$\endgroup$
4
  • $\begingroup$ I know the tag is probably wrong, but I have no clue what tag to chose. Could anyone more knowledgable retag the question please? I'm also not sure if this does even fit here or should rather be moved to math.SE. If yes, please move. :) $\endgroup$
    – magnattic
    Mar 25 '12 at 15:48
  • 2
    $\begingroup$ The question is okay here. Partial orders are used a lot in CS. $\endgroup$ Mar 25 '12 at 16:39
  • $\begingroup$ Abusing a comment by Jeffe: Sometimes a red herring is literally a herring. $\endgroup$
    – Raphael
    Mar 25 '12 at 17:09
  • 4
    $\begingroup$ In particular, every set has a trivial partial order in which no pair of distinct elements is comparable. It's usually denoted =. $\endgroup$
    – JeffE
    Mar 26 '12 at 0:16
8
$\begingroup$

In a partially ordered set, there may be members which are not comparable. A partial order where all elements are comparable is called a total order.

We say $a$ and $b$ are comparable when at least one of the following holds:

  • $a\leq b$,
  • $b \leq a$.
$\endgroup$
0
7
$\begingroup$

In a partially ordered set (poset for short), you can have $a \le b$ and $a \le c$ without $b$ and $c$ being comparable (i.e. neither $b \le c$ nor $c \le b$ holds). That's what makes it a partial order and not a total order. Mathematicians often mean a total order when say “order”, because the primary example of an ordered set is the real numbers (or subsets such as the natural integers); computer scientists use more partial orders at an elementary level, so in CS, assume partial unless told total.

A typical example of poset is set inclusion: $\{x\} \subset \{x,y\}$ and $\{x\} \subset \{x,z\}$, but neither of $\{x,y\}$ and $\{x,z\}$ is a subset of the other.

Posets often arise in denotational semantics to represent an amount of knowledge about a program. $a \le b$ means that $b$ is a better approximation of the behavior of the program than $a$. For example, if $a$ is “the program is a function from the integers that terminates for all inputs”, $b$ is “the program calculates the successor function” and $c$ is “the program calculates the double function”, then $a \le b$ and $a \le c$ but $b$ and $c$ are not comparable.

$\endgroup$

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.