Let \((A, \preccurlyeq)\) be a poset. Let \(a, b\in A\text{.}\) The join of \(a\) and \(b\text{,}\) denoted \(a \wedge b\text{,}\) is the least upper bound of \(\{a, b\}\text{,}\) if the least upper bound exists; the join is not defined if the least upper bound does not exist. The meet of \(a\) and \(b\text{,}\) denoted \(a \wedge b\text{,}\) is the greatest lower bound of \(\{a, b\}\text{,}\) if the greatest lower bound exists; the meet is not defined if the greatest lower bound does not exist.
Definition8.19.Lattice.
A poset \((A, \preccurlyeq)\) is a lattice if \(a \wedge b\) and \(a \wedge b\) exist for all \(a, b\in A\text{.}\)
Example8.20.
The sets \(\N, \Z, \Q\) and \(\R\) with the relation \(\leq \) are all lattices. We know from Example 7.4.2 (3) that these sets with the relation \(\leq \) are all posets. Let \(x\) and \(y\) be two numbers in any one of these sets. If \(x = y\) then \(x \wedge y = x = y\) and \(x \wedge y = x = y\text{;}\) if \(x \neq y\text{,}\) then \(x \wedge y\) is the smaller of the two numbers, and \(x \wedge y\) is the larger. More generally, any totally ordered set is a lattice, by the same argument.
Let \(A\) be a set. The poset \((\cP(A), \subseteq )\) is a lattice. If \(X,Y\in\cP(A)\text{,}\) then \(X \wedge Y = X \cap Y\) and \(X \wedge Y = X \cup Y\text{.}\)
As shown in Example 7.4.2 (5), the set \(\N\) with the relation “\(a|b\)” is a poset. This poset is a lattice. If \(a, b\in\N\text{,}\) then \(a \wedge b\) is the greatest common divisor of \(a\) and \(b\text{,}\) and \(a \wedge b\) is the least common multiple.
Theorem8.21.
Let \((L, \preccurlyeq)\) be a lattice, and let \(x, y, z\in L\text{.}\)
\(x \wedge x = x\) and \(x \vee x = x\) (Idempotent Laws).
\(x \wedge y = y \wedge x\) and \(x \vee y = y \vee x\) (Commutative Laws).
Let \(A\) be a set, and let \(u : A \times A \to A\) and \(t : A \times A \to A\) be binary operations on \(A\text{.}\) Suppose that \(\sqcup\) and \(\sqcap\) satisfy the following properties. Let \(x, y, z\in A\text{.}\)
\(x\sqcup y = y\sqcup x\) and \(x\sqcap y = y\sqcap x\text{.}\)
Let \(\preccurlyeq\) be the relation on \(A\) defined by \(x\preccurlyeq y\) if and only \(if x\sqcup y = x\text{,}\) for all \(x, y\in A\text{.}\) Then \((A, \preccurlyeq)\) is a lattice, with \(\sqcup\) and \(\sqcap\) the meet and join of the lattice, respectively.
We follow [Bir48] and [LP98] in part. As a preliminary, we prove the following two facts: (1) \(x\sqcup x = x\) for all \(x\in A\text{;}\) and (2) \(x\sqcup y = x\) if and only if \(x\sqcap y = y\text{,}\) for all \(x, y\in A\text{.}\) Let \(x, y, z\in A\text{.}\) Using both parts of Property (c), we see that \(x\sqcup x = x\sqcup (x\sqcap (x\sqcup x)) = x\text{,}\) which proves Fact (1). Suppose that \(x\sqcup y = x\text{.}\) Then by Properties (a) and (c) we see that \(x\sqcap y = (x\sqcup y)\sqcap y = y\sqcap (y\sqcup x) = y\text{,}\) which proves one of the implications in Fact (2); a similar argument proves the other implication, and we omit the details.
We now show that \((A, \preccurlyeq)\) is a poset. Because \(x\sqcup x = x\) by Fact (1), it follows from the definition of \(\preccurlyeq\) that \(x\preccurlyeq x\text{.}\) Hence \(\preccurlyeq\) is reflexive. Now suppose that \(x\preccurlyeq y\) and \(y\preccurlyeq z\text{.}\) Then \(x\sqcup y = x\) and \(y\sqcup z = y\text{.}\) By Property (b) we see that \(x\sqcup z = (x\sqcup y)\sqcup z = x\sqcup (y\sqcup z) = x\sqcup y = x\text{.}\) It follows that \(x\preccurlyeq z\text{.}\) Therefore \(\preccurlyeq\) is transitive. Next, suppose that \(x\preccurlyeq y\) and \(y\preccurlyeq x\text{.}\) Then \(x\sqcup y = x\) and \(y\sqcup x = y\text{.}\) It follows from Property (a) that \(x = y\text{.}\) Therefore \(\preccurlyeq\) is antisymmetric. We conclude that \((A, \preccurlyeq)\) is a poset.
Finally, we show that \(\sqcup\) and \(\sqcap\) are the meet and join of \((A, \preccurlyeq)\text{,}\) respectively. It will then follow from this fact that meet and join always exist for any two elements of \(A\text{,}\) and hence \((A, \preccurlyeq)\) is a lattice. We start with \(\sqcup\text{.}\) Using Property (b) and Fact (1) we see that \((x\sqcup y)\sqcup y = x\sqcup (y\sqcup y) = x\sqcup y\text{.}\) Hence \(x\sqcup y\preccurlyeq y\text{.}\) Because \(x\sqcup y = y\sqcup x\) by Property (a), a similar argument shows that \(x\sqcup y\preccurlyeq x\text{.}\) Therefore \(x\sqcup y\) is a lower bound of \(\{x, y\}\text{.}\) Now suppose that \(z\in A\) is a lower bound of \(\{x, y\}\text{.}\) Then \(z\preccurlyeq x\) and \(z\preccurlyeq y\text{,}\) and therefore \(z\sqcup x = z\) and \(z\sqcup y = z\text{.}\) By Property (b) we see that \(z\sqcup (x\sqcup y) = (z\sqcup x)\sqcup y = z\sqcup y = z\text{.}\) Hence \(z\preccurlyeq (x\sqcup y)\text{.}\) It follows that \(x\sqcup y\) is the greatest lower bound of \(\{x, y\}\text{,}\) which means that \(x\sqcup y\) is the meet of \(x\) and \(y\text{.}\)
We now turn to \(\sqcap\text{.}\) By Property (c) we know that \(x\sqcup (x\sqcap y) = x\text{.}\) Hence \(x\preccurlyeq x\sqcap y\text{.}\) Because \(x\sqcap y = y\sqcap x\) by Property (a), a similar argument shows that \(y\preccurlyeq x\sqcap y\text{.}\) Hence \(x\sqcap y\) is an upper bound of \(\{x, y\}\text{.}\) Now suppose that \(w\in A\) is an upper bound of \(\{x, y\}\text{.}\) Then \(x\preccurlyeq w\) and \(y\preccurlyeq w\text{,}\) and therefore \(x\sqcup w = x\) and \(y\sqcup w = y\text{.}\) By Fact (2) we deduce that \(x\sqcap w = w\) and \(y\sqcap w = w\text{.}\) Property (b) then implies that \((x\sqcap y)\sqcap w = x\sqcap (y\sqcap w) = x\sqcap w = w\text{.}\) Hence \((x\sqcap y)\sqcup w = x\sqcap y\) by Fact (2). Therefore \(x\sqcap y \preccurlyeq w\text{.}\) It follows that \(x\sqcap y\) is the least upper bound of \(\{x, y\}\text{,}\) which means that \(x\sqcap y\) is the join of \(x and y\text{.}\)
Definition8.23.
Let \((L, \preccurlyeq)\) and \((M, \preccurlyeq′)\) be lattices, and let \(f : L \to M\) be a function. Let \(\wedge\) and \(\vee\) be the meet and join for \(L\text{,}\) and let \(\wedge ′\) and \(\vee ′\) be the meet and join for \(M\text{.}\) The function \(f\) is a meet homomorphism if \(f (x \wedge y) = f (x) \wedge ′ f (y)\) for all \(x, y\in L\text{.}\) The function \(f\) is a join homomorphism if \(f (x \vee y) = f (x) \vee ′ f (y)\) for all \(x, y\in L\text{.}\)
Example8.24.
The function \(f : D \to\cP(A)\) in Example 7.4.17 (2) is both a meet homomorphism and a join homomorphism, as the reader can verify.
The function \(s : PF (N) \to Z\) in Example 7.4.17 (1) is an order homomorphism, as was stated in that example. However, this function is neither a meet homomorphism nor a join homomorphism. For example, let \(X = \{5, 7\}\text{,}\) and let \(Y = \{7, 9\}\text{.}\) Then, as in Example 7.5.2 (2), we see that \(X \wedge Y = X \cap Y = \{7\}\text{,}\) and \(X \vee Y = X \cup Y = \{5, 7, 9\}\text{.}\) Hence \(s(X \wedge Y ) = 1\) and \(s(X \vee Y ) = 3\text{.}\) However, as discussed in Example 7.5.2 (1), we see that \(s(X) \wedge s(Y ) = 2 \wedge 2 = 2\text{,}\) and \(s(X) \vee s(Y ) = 2 \vee 2 = 2\text{.}\) Hence \(s(X \wedge Y ) \neq s(X) \wedge s(Y )\) and \(s(X \vee Y ) \neq s(X) \vee s(Y )\text{.}\)
Theorem8.25.
Let \((L, \preccurlyeq)\) and \((M, \preccurlyeq′)\) be lattices, and let \(f : L \to M\) be a function.
If \(f\) is a meet homomorphism or a join homomorphism, then it is an order homomorphism.
If \(f\) is bijective and a meet (respectively, join) homomorphism, then \(f\inv\) is a meet (respectively, join) homomorphism.
The function \(f\) is an order isomorphism if and only if \(f\) is bijective and a meet homomorphism if and only if \(f\) is bijective and a join homomorphism.
Suppose that \(f\) is a meet homomorphism. Let \(\wedge and \wedge′\) denote the meet for \(L\) and \(M\text{,}\) respectively. Let \(x, y\in L\text{.}\) Suppose that \(x\preccurlyeq y\text{.}\) Then by Theorem 7.5.3 (6) we know that \(x = x \wedge y\text{.}\) Then \(f (x) = f (x \wedge y) = f (x) \wedge ′ f (y)\text{,}\) because \(f\) is a meet homomorphism. Using Theorem 7.5.3 (6) again, we deduce that \(f (x) \preccurlyeq′ f (y)\text{.}\) It follows that \(f\) is an order homomorphism. A similar argument works if \(f\) is a join homomorphism; we omit the details.
Theorem8.26.
Let \((L, \preccurlyeq)\) be a lattice, and let \(f : L \to L\) be an order homomorphism. Suppose that the least upper bound and greatest lower bound exist for all non-empty subsets of \(L\text{.}\) Then there is some \(a\in L\) such that \(f(a) = a\text{.}\)
Let \(C = \{x\in L | x\preccurlyeq f (x)\}\text{.}\) Observe that \(L\) is non-empty because it is a poset, and all posets are assumed to be non-empty. Let \(m\) be the greatest lower bound of \(L\text{,}\) which exists by hypothesis. Then \(m\) is a lower bound of \(L\text{,}\) and therefore \(m\preccurlyeq x\) for all \(x\in L\text{.}\) In particular, we see that \(m\preccurlyeq f(m)\text{.}\) It follows that \(m\in C\text{,}\) and so \(C\) is non-empty.
Let \(a\) be the least upper bound of \(C\text{.}\) Let \(x\in C\text{.}\) Then \(a\) is an upper bound of \(C\text{,}\) and therefore \(x\preccurlyeq a\text{.}\) Using the definition of \(C\) and the fact that \(f\) is an order homomorphism, we deduce that \(x\preccurlyeq f (x)\preccurlyeq f(a)\text{.}\) It follows that \(f(a)\) is an upper bound for \(C\text{.}\) Because \(a\) is the least upper bound of \(C\text{,}\) we deduce that \(a\preccurlyeq f(a)\text{.}\) Because \(f\) is an order homomorphism, it follows that \(f(a)\preccurlyeq f ( f(a))\text{.}\) Hence \(f(a)\in C\text{,}\) and therefore \(f(a)\into a\text{,}\) because \(a\) is an upper bound of \(C\text{.}\) By antisymmetry, we deduce that \(f(a) = a\text{.}\)
Corollary8.27.
Let \((L, \preccurlyeq)\) be a lattice, and let \(f : L \to L\) be an order homomorphism. If \(L\) is finite, then there is some \(a\in L\) such that \(f(a) = a\text{.}\)
