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?
regards
Best Answer
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.