1
$\begingroup$

I am asked to prove that every chain is a distributive lattice.

Is it true that every chain is a lattice?

I am told that a chain is a poset where we can compare any two elements. A lattice is a poset where every subset has a lub and a gld. I don't understand how then every chain is a lattice.

what if we take two elements in a chain that do not have a lub, then how can we even talk about distributive of meets over joins?

$\endgroup$
6
  • 1
    $\begingroup$ According to the definition I know, only finite subsets of a lattice are assumed to have least upper bounds or greatest lower bounds. $\endgroup$ Oct 15, 2014 at 7:29
  • $\begingroup$ But even still, how can we talk about the lub of two elements of a chain when we don't even know that such a lub exists? $\endgroup$
    – tmpys
    Oct 15, 2014 at 7:33
  • 2
    $\begingroup$ Assume that $a \leq b$. It is also true that $a \leq a$, hence $a$ is a lower bound of the set $\{a, b\}$. To prove that it is the greatest lower bound note that if some $c$ is another lower bound of $\{a, b\}$ then by definition $c \leqslant a$. It means that $a$ is the greatest lower bound of $\{a, b\}$. Same reasoning shows that $b$ is the least upper bound of $\{a, b\}$. $\endgroup$ Oct 15, 2014 at 7:34
  • 1
    $\begingroup$ @HaraldHanche-Olsen Yes, if additionally every (including infinite) subset has glb and lub then it is a complete lattice $\endgroup$ Oct 15, 2014 at 8:20
  • $\begingroup$ oh yeah lol that makes sense, thank you. Can you make this an answer so that I can give you the credit? $\endgroup$
    – tmpys
    Oct 15, 2014 at 8:25

1 Answer 1

6
$\begingroup$

To prove that every chain $\langle P, \leqslant\rangle$ is a lattice, fix some $a, b \in P$ and w.l.o.g assume that $a \leqslant b$. From reflexivity of $\leqslant$ it follows that $a \leqslant a$, hence $a$ is a lower bound of the set $\{a,b\}$. To prove that it is the greatest lower bound note that if some $c \in P$ is another lower bound of $\{a,b\}$ then by the definition of a lower bound we have $c \leqslant a$. It means that $a$ is the greatest lower bound of $\{a,b\}$. Same reasoning shows that $b$ is the least upper bound of $\{a,b\}$.

To prove that every chain $\langle P, \leqslant\rangle$ is distributive, you should just consider all possible relations between three arbitrary elements $a, b, c \in P$ and check that distributive identity holds.

For example, let $a \leqslant b \leqslant c$, hence $a \wedge b = a \wedge c = a$ and $b \vee c = c$, so $$a \wedge (b \vee c) = a \wedge c = a = a \vee a = (a \wedge b) \vee (a \wedge c).$$

$\endgroup$

You must log in to answer this question.

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