# Join and meet: Examples

https://arbital.com/p/join_examples

by Kevin Clancy May 27 2016 updated Jun 20 2016

A union of sets and the least common multiple of a set of natural numbers can both be viewed as joins. In addition, joins can be useful to the designers of statically typed programming languages.

%%%knows-requisite(Real analysis):

## The real numbers

Consider the Partially ordered set $\langle \mathbb{R}, \leq \rangle$ of all real numbers ordered by the standard comparison relation. For any non-empty $X \subseteq \mathbb{R}$, $\bigvee X$ exists if and only if $X$ has an upper bound; this fact falls directly out of the definition of the set of real numbers. %%%

## 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. %%%comment:
dot source:

digraph G {
node [width = 0.1, height = 0.1];
rankdir = BT;
Dog -> Animal;
Cat -> Animal;
}
%%%

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 Partially ordered set $\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_+, | \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_+, | \rangle$ is their least common multiple. Dually, the meet of a set of positive integers in $\langle \mathbb Z_+, | \rangle$ is their greatest common divisor.