A join-semilattice is a set S equipped with a binary operation called join, denoted by the symbol vee. This operation must satisfy three key properties: First, associativity, which means the grouping of operations doesn't matter. Second, commutativity, which means the order of elements doesn't matter. And third, idempotence, which means joining an element with itself gives the same element. The diagram on the right shows a simple example of a join-semilattice represented as a Hasse diagram, where the join of elements a and b is at the top.
Alternatively, a join-semilattice can be defined from the perspective of partial orders. It is a partially ordered set where every pair of elements has a least upper bound, also called a supremum. The join operation and the partial order are closely related: x is less than or equal to y if and only if the join of x and y equals y. In the diagram, we can see examples of least upper bounds: the join of a and b is the top element, while the join of an element with itself is just that element. This partial order perspective provides an equivalent way to understand join-semilattices.
Let's look at some common examples of join-semilattices. First, the power set of a set X, equipped with the union operation, forms a join-semilattice. Here, the join of two sets is their union. For instance, the union of singleton sets {a} and {b} is the set {a,b}. Another example is the set of natural numbers with the least common multiple operation. For instance, the LCM of 2 and 3 is 6, which is their join in this semilattice. Similarly, natural numbers with the greatest common divisor also form a join-semilattice. These examples demonstrate how join-semilattices appear naturally in various mathematical contexts.
Let's explore concepts related to join-semilattices. First, a meet-semilattice is the dual concept, where the binary operation finds the greatest lower bound or infimum of elements. When a set is both a join-semilattice and a meet-semilattice, it forms a lattice. In a lattice, every pair of elements has both a least upper bound and a greatest lower bound. In our diagram, the join of a and b is the top element, while their meet is the bottom element. A complete lattice is even stronger - it requires that every subset, not just pairs, has both a supremum and an infimum. These structures are fundamental in order theory and have applications in computer science and algebra.
To summarize what we've learned about join-semilattices: They are algebraic structures defined by a binary operation that satisfies associativity, commutativity, and idempotence. Alternatively, they can be viewed as partially ordered sets where every pair of elements has a least upper bound. We've seen examples like power sets with union, natural numbers with least common multiple, and divisibility with greatest common divisor. Join-semilattices are closely related to meet-semilattices and lattices, forming fundamental structures in order theory with important applications in mathematics and computer science.