1

I understand the defnition of complete lattice. But often times the argument that is given for showing something is complete lattice is it has a upper bound and a lower bound.

For eg The partial order <= under a set of rational numbers from (0,1) is a complete lattice because it has a universal upper bound 1and lower bound 0 But complete lattice requires that every subset should have Greatest lower bound and least upper bound.Having Upper bound doesnt ensure it has Greatest Upper bound right?

How to prove a lattice is complete?

Aravind
  • 21

1 Answers1

2

The open interval of rationals $(0,1) \cap \Bbb Q$ is not complete as a lattice. The extrema (greatest lower bound / least upper bound) of many of its subsets are not in the interval. For example, $(0, 1/2] \cap \Bbb Q$ and $[1/2, 1) \cap \Bbb Q$ has a greatest lower bound of $0$ and least upper bound of $1$ respectively, but $0,1 \not \in (0,1) \cap \Bbb Q$.

In fact, even the closed interval of rationals $[0,1] \cap \Bbb Q$ is not a complete lattice, even though its extrema are in the set. $e/3 \in [0,1]$ for instance, but the subset $[0,e/3) \cap \Bbb Q$ would not have a supremum in $[0,1] \cap \Bbb Q$.

More generally, a lattice $(S, \le)$ is complete when, for all $T \subseteq S$, the greatest lower bound $\inf(T)$ and the least upper bound $\sup(T)$ exist and are elements of $S$.

It is also clear after this that it is not at all sufficient for $(S,\le)$ to have upper/lower bounds as a whole if you wish to conclude completeness. In short: a lattice may be bounded, but that does not guarantee completeness.

PrincessEev
  • 43,815
  • Thank you but how to formally prove a lattice is complete? – Aravind Nov 24 '19 at 07:35
  • It's hard for me to really say other than you need to show all subsets of your lattice have an infimum and supremum (that lies in the lattice). As far as I know, anything beyond that relies on the properties of the elements of your lattice. [cont.] – PrincessEev Nov 24 '19 at 09:20
  • For example, you can show a power set $\mathcal P(X)$ of a set $X$ is a complete lattice ordered by inclusion (see here), but this relies on facts about sets and power sets. For example, it is closed under union and intersection. Thus for any subset of $\mathcal P(X)$, you can characterize the supremum as the union of all sets in that subset, and the infimum as their intersection. Both these union and intersection are in the power set as well, by the aforementioned closure. [cont.] – PrincessEev Nov 24 '19 at 09:20
  • But you see that this relies very heavily on the ideas/properties underlying unions, intersections, power sets, etc. If you wanted to verify something else was a lattice - for example, $[a,b] \cap \Bbb Z$ for $a,b \in \Bbb Z$, or the subgroups of a group ordered by inclusion (which results in a slightly different result than the subsets of a set), or various other examples - you'll have to make different considerations based on the properties you're working with. [cont.] – PrincessEev Nov 24 '19 at 09:20
  • In short, I don't think there's much you can do when it comes to proving a lattice is complete, other than directly applying the definition and making use of the properties of what you have on hand. What sort of properties you need to use and the overall intuition for the process is something you'll hone through practice. – PrincessEev Nov 24 '19 at 09:20