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.

  • 1
    Yeah. I see where am I wrong. That $a$ and $b$ may not be comparable because preorder is not total.2012-12-10
  • 0
    Precisely so. ${}$2012-12-10
  • 1
    Just take the disjoint union of two copies of $\Bbb Z$, with no order relations between the two copies. It looks the same upside down.2012-12-10
  • 0
    There we go. I figured there was an easy counterexample. Thanks, @Brian.2012-12-10
  • 0
    @Cameron: My pleasure.2012-12-10