# Are two elements always in a relation within a partially ordered set?

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

• 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. :) Mar 25 '12 at 15:48
• The question is okay here. Partial orders are used a lot in CS. Mar 25 '12 at 16:39
• Abusing a comment by Jeffe: Sometimes a red herring is literally a herring.
– Raphael
Mar 25 '12 at 17:09
• In particular, every set has a trivial partial order in which no pair of distinct elements is comparable. It's usually denoted =. Mar 26 '12 at 0:16

We say $a$ and $b$ are comparable when at least one of the following holds:
• $a\leq b$,
• $b \leq a$.
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.