Lattices and Boolean algebra

Question

I have read in a text book that the set of natural numbers form a lattice under divisibility. How can it possibe, since there is no upper bound and therefore a Sup of the set?

Answer 1

Yes, there is an upper bound. It's $0$ (although some consider $0$ not to be natural) since $0$ is a multiple of every integer ($0n=0$, thus $n|0$).

So in this case, $1$ is the minimum element and $0$ is the maximum. With this order ($n \leq m$ iff $n|m$), $n \wedge m = \gcd(n,m)$ and $n \vee m = \mathrm{lcm}(n,m)$.

The atoms of this lattice are the prime numbers.

Answer 2

Let's consider a vastly simpler lattice: the set of real numbers in the open interval $(0, 1)$ under the usual ordering. (In addition to being a lattice order, this is a total order.)

Clearly this is a lattice: $x\wedge y =\min(x, y)$ which is always going to exist and similar for the supremum. In fact, if $S$ is a finite subset of $(0, 1)$ then $\bigwedge S$ will exist.

But what if $S$ is infinite? For example, if $S = (0, 1)$ then $\bigwedge S = 0$ which is not in the lattice. This means that the lattice is not complete.

This example shows us that it's possible for any two elements to have an infimum, and even for any finite set to have an infimum, in a lattice where infinite sets lack an infimum.

Going back to your example: every two elements have a least common multiple, and in fact any finite set of integers have a least common multiple, but an infinite set may not.

This difference between finite and infinite sets is very important, for example in the difference between $\sigma$-algebras and set algebras, so it's worth understanding well.