I have been told that under the product order, {(0,0),(1,0),(0,1),(2,1),(1,2),(2,2)} is not a lattice.
I know that a lattice is when joins and meets exist for any pair of elements, and I suspect the reason it is not a lattice is because (1,1) is not included in the set. Is this correct?
But say we take the pair of elements (1,0) and (0,1), we can find a join that is (2,1) which is indeed part of the set. Why does this not qualify?
Also, I was told that under the natural product order, {(0,0),(1,0),(0,1),(2,2)} is a complete lattice. And here we also do not have (1,1), how can this be?
Best Answer
A join of two elements in a poset is a least upper bound for them. In your first example, $(2,1)$ is an upper bound for $(1,0)$ and $(0,1)$, but it is not their join because $(1,2)$ is another upper bound and $(2,1)\not\leq (1,2)$. There is no upper bound for $(1,0)$ and $(0,1)$ that is less than or equal to every other upper bound, and thus they have no join in this poset.
In your second example, the join of $(0,1)$ and $(1,0)$ is $(2,2)$. Indeed, it is the only upper bound of $(0,1)$ and $(1,0)$ in the poset, so it is their least upper bound in the poset. What you are observing is that $A=\{(0,0),(1,0),(0,1),(2,2)\}$ is not a sublattice of the lattice $B=\{0,1,2\}^2$, since it is not closed under the join operation of that lattice (it contains $(1,0)$ and $(0,1)$ but not their join $(1,0)\vee_B(0,1)=(1,1)$). However, this does not prevent $A$ from being a lattice itself since its join and meet operations do not have to be the same as the join and meet operations of $B$ (only the order relation is inherited from $B$). In this case, the join of $(0,1)$ and $(1,0)$ in $A$ is different from their join in $B$, since even though $A$ and $B$ have the same order relation, $A$ does not contain all the upper bounds of $(0,1)$ and $(1,0)$ in $B$ (so a different one of them can be the least one in $A$).