Join and meet: Examples

A union of sets and the least com­mon mul­ti­ple of a set of nat­u­ral num­bers can both be viewed as joins. In ad­di­tion, joins can be use­ful to the de­sign­ers of stat­i­cally typed pro­gram­ming lan­guages.

knows-req­ui­site(Real anal­y­sis):

The real numbers

Con­sider the par­tially or­dered set \(\langle \mathbb{R}, \leq \rangle\) of all real num­bers or­dered by the stan­dard com­par­i­son re­la­tion. For any non-empty \(X \subseteq \mathbb{R}\), \(\bigvee X\) ex­ists if and only if \(X\) has an up­per bound; this fact falls di­rectly out of the defi­ni­tion of the set of real num­bers. <div>

Subtyping

Stat­i­cally typed pro­gram­ming lan­guages of­ten define a poset of types or­dered by the sub­typ­ing re­la­tion; Scala is one such lan­guage. Con­sider the fol­low­ing Scala pro­gram.

A scala program with class inheritance

When a pro­gram­mer defines a class hi­er­ar­chy in an ob­ject-ori­ented lan­guage, they are ac­tu­ally defin­ing a poset of types. The above pro­gram defines the sim­ple poset shown in the fol­low­ing Hasse di­a­gram.

Hasse diagram for the nominal subtyping relation defined by the above program

com­ment: dot source:

di­graph G { node = 0.1, height = 0.1; edge = “none”; rankdir = BT; Dog → An­i­mal; Cat → An­i­mal; } <div>

Now con­sider the ex­pres­sion if (b) dog else cat. If b is true, then it eval­u­ates to a value of type Dog. If b is false, then it eval­u­ates 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 An­i­mal.

Power sets

Let \(X\) be a set. Con­sider the par­tially or­dered set \(\langle \mathcal{P}(X), \subseteq \rangle\), the power set of \(X\) or­dered by in­clu­sion. In this poset, joins are unions: for all \(A \subseteq \mathcal{P}(X)\), \(\bigvee A = \bigcup A\). This can be shown as fol­lows. Let \(A \subseteq \mathcal{P}(X)\). Then \(\bigcup A\) is an up­per bound of \(A\) be­cause a union con­tains each of its con­stituent sets. Fur­ther­more, \(\bigcup A\) is the least up­per bound of \(A\). For let \(Z\) be an up­per bound of \(A\). Then \(x \in \bigcup A\) im­plies \(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\) im­plies \(x \in Z\), we have \(\bigcup A \subseteq Z\). Hence, \(\bigvee A = \bigcup A\).

Divisibility

Con­sider the poset \(\langle \mathbb Z_+, | \rangle\) of di­visi­bil­ity on the pos­i­tive in­te­gers. In this poset, the up­per bounds of an in­te­ger are ex­actly its mul­ti­ples. Thus, the join of a set of pos­i­tive in­te­gers in \(\langle \mathbb Z_+, | \rangle\) is their least com­mon mul­ti­ple. Dually, the meet of a set of pos­i­tive in­te­gers in \(\langle \mathbb Z_+, | \rangle\) is their great­est com­mon di­vi­sor.

Parents:

  • Join and meet
    • Order theory

      The study of bi­nary re­la­tions that are re­flex­ive, tran­si­tive, and an­ti­sym­metic.