When is a line diagram not lattice?

264 Views Asked by At

A line Diagram

Can anyone please explain why the line diagram above is not a lattice as per the definition of lattice? The relation is $\leq$ and the element above is less or equal to the element below. The explanation given was that s,t has no supremum and p,t does not have a smallest element in the set of all its upper bounds. Only problem is I have not studied any set theory or relations beyond high school. Can somebody explain it to intuitively while sticking to the standard mathematical definitions, it would help me a lot?

1

There are 1 best solutions below

0
On BEST ANSWER

In a lattice, every pair of elements has a supremum and an infimum. Let's show that $t$ and $s$ have no supremum, so that this is not a lattice.

Another perhaps more suggestive term for supremum is least upper bound. An upper bound for a pair of elements is any element that is greater than or equal to both of them. From the diagram, we see that $p\ge t,$ and $p\ge s,$ so $p$ is an upper bound for $s$ and $t.$ Similarly, $q$ and $1$ are also upper bounds for $s$ and $t$ because they are both greater than $s$ and greater than $t.$

(On the other hand, $s$ is not an upper bound for $\{s,t\}$ because, while we have $s\ge s,$ it is not the case that $s\ge t$. Similarly, $t$ and $0$ are not upper bounds.)

So we have the upper bounds $p,q,$ and $1.$ A supremum (if it exists) is the least upper bound. Least means it is less than or equal to all of the others. So we need to check $p,q,$ and $1$ and see if any of them is less than or equal to all the others.

Clearly $1$ is not... it is greater than both $p$ and $q,$ so $1$ is not the supremum of $\{s,t\}.$ How about $p$? We have $p\le 1$ and $p\le p,$ but we don't have $p\le q.$ So $p$ is not the least. The situation with $q$ is completely symmetrical, so it is not the least either.

And that's it, we've checked all possibilities and did not find any least upper bound. Thus $\{s,t\}$ has no least upper bound and this poset is not a lattice.