Join and meet: Exercises

Try these ex­er­cises to test your knowl­edge of joins and meets.

Tan­gled up

a big crazy poset

Deter­mine whether or not the fol­low­ing joins and meets ex­ist in the poset de­picted by the above Hasse di­a­gram.

\(c \vee b\)

This join does not ex­ist, be­cause \(i\) and \(j\) are in­com­pa­rable up­per bounds of \(\{ c, b \}\), and no smaller up­per bounds of \(\{ c, b \}\) ex­ist.

\(g \vee e\)

This join ex­ists. \(g \vee e = j\).

\(j \wedge f\)

This meet does not ex­ist, be­cause \(d\) and \(b\) are in­com­pa­rable lower bounds of \(\{ j, f \}\), and no larger lower bounds of \(\{ j, f \}\) ex­ist.

\(\bigvee \{a,b,c,d,e,f,g,h,i,j,k,l\}\)

This join ex­ists. It is \(l\).

Join fu

Let \(P\) be a poset, \(S \subseteq P\), and \(p \in P\). Prove that if both \(\bigvee S\) and \((\bigvee S) \vee p\) ex­ist then \(\bigvee (S \cup \{p\})\) ex­ists as well, and \((\bigvee S) \vee p = \bigvee (S \cup \{p\})\).

For any \(X \subset P\), let \(X^U\) de­note the set of up­per bounds of \(X\). The above propo­si­tion fol­lows from the fact that \(\{\bigvee S, p\}^U = (S \cup p)^U\), which is ap­par­ent from the fol­low­ing chain of bi-im­pli­ca­tions:

\(q \in \{\bigvee S, p\}^U \iff\)

for all \(s \in S, q \geq \bigvee S \geq s\), and \(q \geq p \iff\)

\(q \in (S \cup \{p\})^U\).

If two sub­sets of a poset have the same set of up­per bounds, then ei­ther they both lack a least up­per bound, or both have the same least up­per bound. <div><div>

Meet fu

Let \(P\) be a poset, \(S \subseteq P\), and \(p \in P\). Prove that if both \(\bigwedge S\) and \((\bigwedge S) \wedge p\) ex­ist then \(\bigwedge (S \cup \{p\})\) ex­ists as well, and \((\bigwedge S) \wedge p = \bigwedge(S \cup \{p\})\).

Note that the propo­si­tion we are try­ing to prove here is the dual of the one stated in join fu. Thanks to the du­al­ity prin­ci­ple, this the­o­rem there­fore comes for free with our solu­tion to join fu.

Quite a big join

In the poset \(\langle \mathbb N, | \rangle\) dis­cussed in Poset: Ex­am­ples, does \(\bigvee \mathbb N\) ex­ist? If so, what is it?

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.