3
$\begingroup$

Say that a set is tree ordered if the downset $\downarrow a =\{b:b\leq a\}$ is linearly ordered for each $a$. In a comment, Keinstein says that such sets are also semi-lattices, provided they are connected. This doesn't seem true to me.

Consider e.x. this tree:

   a    c    e
    \  / \  /
      b    d

$b\wedge d$ does not exist, so it is not a lattice.

Am I missing something?

$\endgroup$
5
  • $\begingroup$ I think you are right. (But I'm not sure, so this is going as a comment.) Semi lattices are either join or meet semi-lattices. A meet semi lattice is one in which every finite set has a greatest lower bound. Similarly for a join semi-lattice. A tree with a single root is a "meet" semi-lattice, but your tree is neither. $\endgroup$
    – Areaperson
    May 21, 2014 at 20:09
  • 3
    $\begingroup$ Your example is not tree-ordered since ${\downarrow}c$ is not linearly ordered. $\endgroup$
    – user642796
    May 21, 2014 at 20:15
  • 2
    $\begingroup$ What does connected mean in this context? For finite sets, one can interpret it quite easily (form a graph out of the set, with edges given by relations $a<b$ with no $c$ such that $a<c<b$, and we say the graph is connected), but I am not sure how to interpret it for infinite sets. $\endgroup$
    – anon
    May 22, 2014 at 2:56
  • $\begingroup$ Every binary relation can be considered as a directed graph, when we interpret all the pairs of the relation as edges. This allows us to use the definition of a connected graph (in the sense of undirected graphs), here. The Neigbourhood relation @seaturtles mentions is something different. Not every order relation has such a neighbourhood relation. For example $\mathbb Q$ has no Hasse diagram. $\endgroup$
    – Keinstein
    May 24, 2014 at 13:51
  • $\begingroup$ @Keinstein Thanks, I should have thought of that. $\endgroup$
    – anon
    May 24, 2014 at 15:34

2 Answers 2

Reset to default
4
$\begingroup$

Your example is not tree-ordered since ${\downarrow}c$ is not linearly ordered.

$\endgroup$
0
$\begingroup$

Suppose $L$ is tree-ordered - downward sets are linear - and connected. Let $a,b\in L$. Connectedness tells us there is a path betweeen $a$ and $b$: by using transitivity such a path can be simplified into a "zig-zag" path just as you have in your example (since $u< v< w\Rightarrow u< w$), and so in particular we can take a zig-zag path of minimal length between $a$ and $b$. This minimal path cannot contain an upright triangle $x< y> z$: taking the downward set of $y$ we see $x$ and $z$ are comparable and hence this triangle can be simplified to either $x< z$ or $x>z$ contradicting minimality. This leaves only two possibilities: $a$ and $b$ are directly comparable, or $a>c<b$ is the entire path, so the set of common lower bounds for $a$ and $b$ is nonempty. Since this is the intersection of two linearly ordered sets it is itself linearly ordered and has a maximum, so there is a maximum lower bound on $a,b$.

$\endgroup$
3
  • $\begingroup$ Thanks for providing the proof. Just one remark: The intersection of linearly ordered sets is not necessarily linear (for a counterexample see the Szpilrajn's lemma). But the intersection of linearly ordered downsets is linearly ordered. $\endgroup$
    – Keinstein
    May 24, 2014 at 18:22
  • $\begingroup$ @Keinstein Apparently there is a difference between intersecting orders and intersecting ordered sets. The first means we take two orders on $X$ and intersect them as subsets of $X\times X$. The second means we have two subsets $A,B\subseteq X$ and restrict the order to the intersection $A\cap B$. It's true that the intersection of linear orders needn't be linear, but intersecting linearly ordered sets (as subposets of some ambient ordered set, which is what I am doing here) does yield a linearly ordered set. (Indeed, any subset of a linearly ordered set is also linearly ordered.) $\endgroup$
    – anon
    May 25, 2014 at 7:00
  • 1
    $\begingroup$ With the restriction that both order relations are suborders of the same order you are right, but this restriction is necessary. Otherwise you end up with the general case of the intersection of linear orders. An example: $\bigl(\{a,b\},\{(a,a), (a,b), (b,b)\}\bigr)∩\bigl(\{a,b\},\{(a,a),(b,a),(b,b)\}\bigr)=\bigl(\{a,b\},\{(a,a),(b,b)\}\bigr)$. There is another point that shows that this property depends mainly on the relation: You can extend each suborder to the whole set by the discrete order on the complementary set and get the same result. $\endgroup$
    – Keinstein
    May 25, 2014 at 9:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .