4
$\begingroup$

Please consider the following set:

$S = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{4\}, \{1,2\}, \{3,4\}, \{1,2,3\}, \{2,3,4\}, \{1,2,3,4\} \}$

Consider the Poset $(S,\leq)$ where $\leq$ is the relation $a \leq b$: "a is subset of b".

Is this a Lattice? I have a doubt about trying to find the meet of $\{1,2,3\}$ and $\{2,3,4\}$. It seems that there are $\{2\}$ and $\{3\}$ as possible meets. But the meet must be unique...

I mean, I know that the meet is the greatest lower bound. However in this case i find two different greatest lower bounds. I know that the meet is unique. However cannot really understand the situation here.

Thanks

$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

You are quite right: the meet of two elements in a lattice must be unique. It must be the greatest lower bound, not just a lower bound. Here, as you say, both $\{2\}$ and $\{3\}$ are lower bounds for the pair $$\Big\{\{1,2,3\},\{2,3,4\}\Big\}\;,$$ but since neither of them is a subset of the other, neither of them is the greatest lower bound of the pair. If their intersection, $\{2,3\}$, belonged to $S$, it would be their meet, but it doesn’t. If $\{3\}$ did not belong to $S$, $\{2\}$ would be their meet, and if $\{2\}$ did not belong to $S$, $\{3\}$ would be their meet. As it is, however, they have no meet, and therefore $\langle S,\le\rangle$ is not a lattice.

Note that $\langle S,\le\rangle$ fails to be a lattice for other reasons as well. For example, $\{2\}$ and $\{3\}$ have no join: $\{1,2,3\}$ and $\{2,3,4\}$ are both upper bounds but neither is a least upper bound.

By the way, I suspect that the first element of $S$ is supposed to be $\varnothing$, not $\{\varnothing\}$.

$\endgroup$
1
  • $\begingroup$ Yeah, sorry my mistake in typing the emptyset. Thankyou a lot $\endgroup$
    – Andry
    Feb 23, 2012 at 8:20
3
$\begingroup$

You are correct to be skeptical, and you are right that the two sets $\{1,2,3\}$ and $\{2,3,4\}$ have no greatest lower bound in $S$. Matt's answer would be correct if $S$ were the power set (the set of all subsets) of $\{1,2,3,4\}$, so that the meet would be intersection and the join would be union. Unfortunately, when $S$ does not contain all subsets, you have to be more careful. The join must be the unique smallest set in $S$ above or equal to the union, and the meet must be the unique largest set in $S$ below or equal to the intersection. In this case, as you note, $\{1,2,3\}$ and $\{2,3,4\}$ have no such meet in $S$.

$\endgroup$

You must log in to answer this question.

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