Meets and joins

Definition and basic examples(9)
Exercise 1-85(2)

Let \(p \in P\) be an element in a preorder. Consider \(A = \{p\}\)

  1. Show that \(\wedge A \cong p\)

  2. Show that if \(P\) is a partial order, then \(\wedge A = p\)

  3. Are the analogous facts true when \(\wedge\) is replaced by \(\vee\)?

Solution(1)

    • The first condition of the meet gives us that \(\wedge A \leq p\).

    • The second condition is that \(\forall q \in P: q \leq p \implies q \leq \wedge A\).

      • Substituting \(p\) in for \(q\), the antecedent holds such that we get \(p \leq \wedge A\).

    • Therefore \(p \cong \wedge A\)

  2. The difference between a partial order and a preorder is that congruent elements are equal, so we directly get that \(p = \wedge A\)

  3. Yes, the argument is perfectly symmetric.

Meet and join(1)

For a preorder \((P, \leq)\), the meet and join of \(A \subseteq P\).

  • The meet \(\wedge A\) is an element such that

    • \(\forall a \in A: \wedge A \leq a\)

    • \(\forall q \in P: (\forall a \in A: q \leq a) \implies q \leq \wedge A\)

    • Think of as a GREATEST LOWER BOUND

  • The join \(\vee A\) is an element such that

    • \(\forall a \in A: a \leq \vee A\)

    • \(\forall q \in P: (\forall a \in A: a \leq q) \implies \vee A \leq q\)

    • Think of as a LEAST UPPER BOUND

Linked by

Meets and joins of bool(1)

In the booleans, the meet of any two elements is given by \(AND\) and the join of any two elements is given by \(OR\).

Linked by

Meets and joins of powerset(1)

In a power set, the meet of a collection of subsets is their intersection, while the join is their union.

Meets and joins of total order(1)

In a total order, the meet of a set is its infimum, while the join is the supremum.

Note that \(\mathbb{B}\) is a total order, to generalize Example 1.88.

Meets of subsets(2)

Suppose \((P,\leq)\) is a preorder and \(A \subseteq B \subseteq P\) are subsets that have meets. Then \(\bigwedge B \leq \bigwedge A\)

Solution(1)

  • Let \(m = \bigwedge A\) and \(n = \bigwedge B\).

  • For any \(a \in A\) we also have \(a \in B\), so \(n \leq A\) because \(n\) is a lower bound for \(B\).

  • Thus \(n\) is also a lower bound for \(A\) and hence \(n \leq m\) because \(m\) is \(A\)’s greatest lower bound.

Linked by

Back to observations and generative effects(5)
Monotone maps that preserve meets(1)

A monotone map \(P \xrightarrow{f} Q\) that preserves meets

  • \(f(a \land_P b) \cong f(a) \land_Q f(b)\)

  • Likewise, to preserve joins is for \(f(a \lor_P b) \cong f(a) \lor_Q f(b)\)

Generative effect(1)

A monotone map \(P \xrightarrow{f} Q\) has a generative effect

\(\exists a,b \in P: f(a) \lor f(b) \not\cong f(a \lor v)\)

Linked by

Exercise 1-94(2)

Prove that for any monotone map \(P \xrightarrow{f} Q\):

  • if there exist \(a \lor b \in P\) and \(f(a) \lor f(b) \in Q\):

  • \(f(a) \lor_Q f(b) \leq f(a \lor_P b)\)

Solution(1)

  • Let’s abbreviate \(f(a\ \lor_P\ b)\) as \(JF\) (join-first) and \(f(b)\ \lor_Q\ f(a)\) as \(JL\) (join-last)

    • This exercise is to show that \(JL \leq JF\)

  • The property of joins gives us, in \(P\), that \(a\ \leq\ (a \lor b)\) and \(b\ \leq\ (a \lor b)\)

    • Monotonicity then gives us, in \(Q\), that \(f(a) \leq JF\) and \(f(b) \leq JF\)

  • We also know from the property of joins, in \(Q\), that \(f(a) \leq JL\) and \(f(b) \leq JL\)

  • The only way that \(JF\) could be strictly smaller than \(JL\), given that both are \(\geq f(a)\) and \(\geq f(b)\) is for \(f(a) \leq JF < JL\) and \(f(b) \leq JF < JL\)

  • But, \(JL \in Q\) is the smallest thing (or equal to it) that is greater than \(f(a)\) and \(f(b)\), so this situation is not possible.