Join and meet

Let \(\langle P, \leq \rangle\) be a par­tially or­dered set, and let \(S \subseteq P\). The join of \(S\) in \(P\), de­noted by \(\bigvee_P S\), is an el­e­ment \(p \in P\) satis­fy­ing the fol­low­ing two prop­er­ties:

  • p is an up­per bound of \(S\); that is, for all \(s \in S\), \(s \leq p\).

  • For all up­per bounds \(q\) of \(S\) in \(P\), \(p \leq q\).

\(\bigvee_P S\) does not nec­es­sar­ily ex­ist, but if it does then it is unique. The no­ta­tion \(\bigvee S\) is typ­i­cally used in­stead of \(\bigvee_P S\) when \(P\) is clear from con­text. Joins are of­ten called least up­per bounds or supre­mums. For \(a, b\) in \(P\), the join of \(\{a,b\}\) in \(P\) is de­noted by \(a \vee_P b\), or \(a \vee b\) when \(P\) is clear from con­text.

The dual con­cept of the join is that of the meet. The meet of \(S\) in \(P\), de­noted by \(\bigwedge_P S\), is defined an el­e­ment \(p \in P\) satis­fy­ing.

  • p is a lower bound of \(S\); that is, for all \(s\) in \(S\), \(p \leq s\).

  • For all lower bounds \(q\) of \(S\) in \(P\), \(q \leq p\).

Meets are also called in­fi­mums, or great­est lower bounds. The no­ta­tions \(\bigwedge S\), \(p \wedge_P q\), and \(p \wedge q\) are all have mean­ings that are com­pletely analo­gous to the afore­men­tioned no­ta­tions for joins.

Ba­sic example

Joins Failing to exist in a finite lattice

The above Hasse di­a­gram rep­re­sents a poset with el­e­ments \(a\), \(b\), \(c\), and \(d\). \(\bigvee \{a,b\}\) does not ex­ist be­cause the set \(\{a,b\}\) has no up­per bounds.\(\bigvee \{c,d\}\) does not ex­ist for a differ­ent rea­son: al­though \(\{c, d\}\) has up­per bounds \(a\) and \(b\), these up­per bounds are in­com­pa­rable, and so \(\{c, d\}\) has no least up­per bound. There do ex­ist sub­sets of this poset which pos­sess joins; for ex­am­ple, \(a \vee c = a\), \(\bigvee \{b,c,d\} = b\), and \(\bigvee \{c\} = c\).

Now for some ex­am­ples of meets.\(\bigwedge \{a, b, c, d\}\) does not ex­ist be­cause \(c\) and \(d\) have no com­mon lower bounds. How­ever, \(\bigwedge \{a,b,d\} = d\) and \(a \wedge c = c\).

Ad­di­tional Material

Fur­ther reading

Children:

Parents:

  • Order theory

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