Join and meet examples

Subtyping

Statically typed programming languages often define a poset of types ordered by the subtyping relation; Scala is one such language. Consider the following Scala program.

When a programmer defines a class hierarchy in an object-oriented language, they are actually defining a poset of types. The above program defines the simple poset shown in the following Hasse diagram.

Now consider the expression if (b) dog else cat. If b is true, then it evaluates to a value of type Dog. If b is false, then it evaluates to a value of type Cat. What type, then, should if (b) dog else cat have? Its type should be the join of Dog and Cat, which is Animal.

Power sets

Let $X$ be a set. Consider the poset $\langle \mathcal{P}(X), \subseteq \rangle$, the power set of $X$ ordered by inclusion. In this poset, joins are unions: for all $A \subseteq \mathcal{P}(X)$, $\bigvee A = \bigcup A$. This can be shown as follows. Let $A \subseteq \mathcal{P}(X)$. Then $\bigcup A$ is an upper bound of $A$ because a union contains each of its constituent sets. Furthermore, $\bigcup A$ is the least upper bound of $A$. For let $Z$ be an upper bound of $A$. Then $x \in \bigcup A$ implies $x \in Y$ for some $Y \in A$, and since $Y \subseteq Z$, we have $x \in Y \subseteq Z$. Since $x \in \bigcup A$ implies $x \in Z$, we have $\bigcup A \subseteq Z$. Hence, $\bigvee A = \bigcup A$.

Divisibility

Consider the poset $\langle \mathbb Z_+, \mid \rangle$ of divisibility on the positive integers. In this poset, the upper bounds of an integer are exactly its multiples. Thus, the join of a set of positive integers in $\langle \mathbb Z_+, \mid \rangle$ is their least common multiple. Dually, the meet of a set of positive integers in $\langle \mathbb Z_+, \mid \rangle$ is their greatest common divisor.