2
$\begingroup$

In the definition of directed set, they emphasized that aside from it having a preorder, "every pair of elements has an upper bound."

My question is that isn't the latter property implied by the definition of preorder? If $a\ge b$, then of course they have an upper bound: $a$! Isn't it true that $a\ge a$ and $a\ge b$?

1 Answers 1

4

Not at all. Consider any binary tree that isn't totally ordered. It's a partial order (so a preorder), but has incomparable elements that will thus have no common upper bound.

Of course, in this particular counterexample, the inverse relation will direct the set, but for a general preorder, neither the given relation nor its inverse need direct the set. For example (thanks, Brian!), consider the set $X=\bigl(\Bbb Z\times\{0\}\bigr)\cup\bigl(\Bbb Z\times\{1\}\bigr)$, with the relation $\precsim$ given by $\langle m,j\rangle\precsim\langle n,k\rangle$ iff $j=k$ and $m\leq n$ (where $\leq$ is the standard non-strict order on $\Bbb Z$). Both $\precsim$ and $\precsim^{-1}$ preorder $X$ (isomorphically), but do not direct the set.

  • 0
    @Cameron: My pleasure.2012-12-10