Definition of lattice require that any two elements of lattice should have LUB and GLB, while complete lattice extends it to, every subset should have LUB and GLB. But by induction , it is possible to show that if any two elements have LUB and GLB then every subset should have LUB and GLB. I read somewhere that the difference is because of infinite set, in that case it is possible that set along with some partial order is lattice but not complete lattice, can someone please elaborate it with one example?



Regular induction ("holds for $1$" and "if it holds for $k$ then it holds for $k+1$") only gives you that the result holds for every natural number $n$; it does not let you go beyond the finite numbers. For example, you can prove by induction that there are natural numbers that require $n$ digits to write down in base $10$ for every $n$, but this does not mean that there are natural numbers that require an infinite number of digits to write down in base $10$. "For all $n$" is not the same as "for all sizes, finite or infinite".

(There is a kind of induction that would allow you to prove something for all sizes, not just finite. This is called transfinite induction. You prove the result holds for $1$, and that whenever it holds for all $m\lt k$, then it also holds for $k$ (or, you prove it holds for $1$, that if it holds for an ordinal/cardinal $\alpha$ then it holds for $\alpha+1$, and that if it holds for all ordinals/cardinals strictly smaller than $\gamma$, then it holds for $\gamma$). However you would be unable to do such a proof with lattices, because it is false).

So, if you have a lattice, then any nonempty finite subset has a least upper bound and a greatest lower bound, by induction. Even if you have a $0$ and a $1$ (a minimum and a maximum element) so that every set has an upper and a lower bound, you still don't get that every set has a least upper bound. For example, take $P = \mathbb{Q}\cup\{-\infty,\infty\}$, with the usual order among rationals, $-\infty\leq q\leq \infty$ for all $q\in\mathbb{Q}$. This is a lattice, with operations $a\wedge b = \min\{a,b\}$ and $a\vee b = \max\{a,b\}$ (since it is a totally ordered set). Every finite subset has a least upper bound (the maximum) and a greatest lower bound (the minimum). But it is precisely the absence of suprema and infima for general sets that stops it from being a complete lattice: the set $\{q\in\mathbb{Q}\mid q^2\lt 2\}$ has no least upper bound and no greatest lower bound.


Normal induction doesn't "reach" infinity. So proving something for finite sets doesn't prove it for infinite sets.

Explicitly: the integers $\mathbb{Z}$ form a lattice, but it is incomplete, since there is no greatest (or least) integer.

  • $\begingroup$ I think that this example has the disadvantage that rather than addressing the difference between finite and infinite sets, you need to insist that you can form meets and joins only for non-empty finite sets. $\endgroup$ – Andrés E. Caicedo Jan 2 '11 at 19:35
  • $\begingroup$ @Andres: While a largest element is the meet of the empty set, the example still works: there are infinite sets of integers with no meet and no join, because $\mathbb{Z}$ has no least or greatest element. $\endgroup$ – Arturo Magidin Jan 2 '11 at 19:38
  • $\begingroup$ Arturo: My point is that ${\mathbb Z}$ is not a lattice if we insist that every finite set has a meet and a join, and if you add min and max to make it a lattice, the issue disappears. $\endgroup$ – Andrés E. Caicedo Jan 2 '11 at 19:51
  • $\begingroup$ @Andres: My understanding is that lattices are required to have meets and joins for pairs (and hence for nonempty finite sets), but are not required to have a max and a min; that's why there is the notion of $01$-lattices. But you "nonempty" point is certainly well taken; I need to fix my answer. $\endgroup$ – Arturo Magidin Jan 2 '11 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.