2
$\begingroup$

I have recently been introduced to lattices, but I am not clear on how to prove a partially ordered set is a lattice.

For example, let $B$ be any set and denote its power set by $2^{B}$. Let the partial order on $2^{B}$ be defined by the $\subseteq$ relation.

To prove that $2^{B}$ is a lattice I know I have to show that for any two sets $B_{1}, B_{2} \in 2^{B}$ there is a unique $A_{sup} = B_{1} \vee B_{2}$ and $A_{inf} = B_{1} \wedge B_{2}$ (is there anything else to show?).

I know from set theory that the smallest superset of $B_{1}, B_{2}$ will be $B_{1} \cup B_{2}$ and the largest subset will be $B_{1} \cap B_{2}$. It is also clear that these set will be in the powerset.

So what is there to show? The proof here seems to have different steps.

$\endgroup$
3
  • $\begingroup$ The linked page has the same steps, just dressed up a little differently. They show for any two subsets of $B$, there is a smallest (with respect to the inclusion partial order) common superset, and a largest common subset. That's all. $\endgroup$
    – Daniel Fischer
    Oct 8, 2015 at 19:59
  • $\begingroup$ Most generally, you need to show that for any $a,b$ in the ordering there is a $c$ s.t. for any $c'$, $c'\leq a,b\Rightarrow c'\leq c$; and also a similar property for $d\geq a,b$. I add this because it's often trivial to check with subset partial orders, but in case the ordering is different this is what really needs to be checked. $\endgroup$
    – Malice Vidrine
    Oct 9, 2015 at 5:43
  • $\begingroup$ (and of course the $c$ above is also $\leq a, b$. Forgot to write that part.) $\endgroup$
    – Malice Vidrine
    Oct 9, 2015 at 10:00

1 Answer 1

Reset to default
2
$\begingroup$

To show that a partial order is a lattice, you have to show that it has well-defined "meet" and "join" operations. Because the partial order here is $\subseteq$ and the underlying set is the full powerset, meet and join are $\cap$ and $\cup$ respectively.

To show that a set of sets $S$ is a lattice with respect to $\subseteq$, you have to show that it's closed under those operations. When "meet" and "join" are actual intersection and union, this amounts to showing: $\forall X, Y \in S$, both $X \cap Y \in S$ and $X \cup Y \in S$. When $S = \mathcal{P}(B) = 2^B$ is the powerset of a set $B$, there isn't a lot to actually "prove". You have to show that $X \cap Y$ is actually the largest set contained ($\subseteq$) in both $X$ and $Y$, and that $X \cup Y$ is actually the smallest set containing ($\subseteq$) in both $X$ and $Y$... and that both are actually subsets of $B$ :)

Note, however, that even when the underlying set is a set of sets, and the partial order is $\subseteq$, "meet' and 'join' may not actually be set-theoretic $\cap$ and $\cup$. Example: a four-element diamond lattice $\{\emptyset, \{0, 1\}, evenInts, \mathbb{N}\}$, where $evenInts$ is... the set of even integers. The "meet" of $\{0, 1\}$ and $evenInts$ is the bottom of the diamond, $\emptyset$, but of course their intersection is nonempty; similarly, the "join" of $\{0, 1\}$ and $evenInts$ is the top of the diamond, $\mathbb{N}$, but their union doesn't equal $\mathbb{N}$.

$\endgroup$
4
  • $\begingroup$ Okay great, thanks for your answer. In more general cases do I have free rein in deciding what to define as the join and meet? $\endgroup$
    – möbius
    Oct 8, 2015 at 20:01
  • $\begingroup$ Your explanation is not quite correct. The fact that the relation is given as inclusion does not mean that the meet and join need to be given by intersection and union (as can be seen by looking at suitable subsets of the powerset). $\endgroup$
    – Tobias Kildetoft
    Oct 8, 2015 at 20:04
  • $\begingroup$ @Tobias Yes I'm aware (see my previous comment) that the meet and join may not actually be intersection and union, but in this case (full powerset) they certainly are so I punted. I'll add a little to the answer. $\endgroup$
    – BrianO
    Oct 8, 2015 at 20:10
  • $\begingroup$ @möbius In general, yes, as long as they actually define a lattice. There are two ways to do that: (1) starting from a partial order in which every pair of elements has a lub and glb; and (2) algebraically: there are lattice axioms specifying how $\wedge$ and $\vee$ behave, which your operations will have to satisfy. Given a lattice $(L, \wedge, \vee)$ defined algebraically, the corresponding partial order is: $x \preceq y \Leftrightarrow x \wedge y = x$. $\endgroup$
    – BrianO
    Oct 8, 2015 at 20:31

You must log in to answer this question.

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