Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.