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$?

| cite | improve this question | | | | |

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.

| cite | improve this answer | | | | |
  • 1
    $\begingroup$ Yeah. I see where am I wrong. That $a$ and $b$ may not be comparable because preorder is not total. $\endgroup$ – xzhu Dec 10 '12 at 4:00
  • $\begingroup$ Precisely so. ${}$ $\endgroup$ – Cameron Buie Dec 10 '12 at 4:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Dec 10 '12 at 4:13
  • $\begingroup$ There we go. I figured there was an easy counterexample. Thanks, @Brian. $\endgroup$ – Cameron Buie Dec 10 '12 at 4:34
  • $\begingroup$ @Cameron: My pleasure. $\endgroup$ – Brian M. Scott Dec 10 '12 at 4:36

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.