1.2: Meets and Joins

Last updated
Save as PDF

Page ID: 54892

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\dsum}{\displaystyle\sum\limits} $

$ \newcommand{\dint}{\displaystyle\int\limits} $

$ \newcommand{\dlim}{\displaystyle\lim\limits} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$\newcommand{\longvect}{\overrightarrow}$

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

As we have said, a preorder is a set P endowed with an order ≤ relating the elements. With respect to this order, certain elements of P may have distinctive characterizations, either absolutely or in relation to other elements. We have discussed joins before, but we discuss them again now that we have built up some formalism.

Definition and Basic Examples

Consider the preorder ($\mathbb{R}$, ≤) of real numbers ordered in the usual way. The subset $\mathbb{N}$ $\subseteq$ $\mathbb{R}$ has many lower bounds, namely −1.5 is a lower bound: every element of N is bigger than −1.5. But within all lower bounds for $\mathbb{N}$ $\subseteq$ $\mathbb{R}$, one is distinctive: a greatest lower bound also called a meet namely 0. It is a lower bound, and there is no lower bound for $\mathbb{N}$ that is above it. However, the set $\mathbb{N}$ $\subseteq$ $\mathbb{R}$ has no upper bound, and certainly no least upper bound which would be called a join. On the other hand, the set

$\left\{\frac{1}{n+1} \mid n \in \mathbb{N}\right\} \subseteq \mathbb{R}$

has both a greatest lower bound (meet), namely 0, and a least upper bound (join), namely 1. These notions will have correlates in category theory, called limits and colimits, which we will discuss in Chapter 3. More generally, we say these distinctive characterizations are universal properties, since, for example, a greatest lower bound is greatest among all lower bounds. For now, however, we simply want to make the definition of greatest lower bounds and least upper bounds, called meets and joins, precise.

Exercise 1.80.

Why is 0 a lower bound for $\left\{\frac{1}{n+1} \mid n \in \mathbb{N}\right\} \subseteq \mathbb{R}$
Why is 0 a greatest lower bound (meet)? ♦

Definition: 1.81.

Let (P, ≤) be a preorder, and let A $\subseteq$ P be a subset. We say that an element p $\in$ P is a meet of A if

for all a $\in$ A, we have p ≤ a, and
for all q such that q ≤ a for all a $\in$ A, we have that q ≤ p.

We write p = $\bigwedge$A, p = $\bigwedge_{a \in A}$a, or, if the dummy variable a is clear from context, just p = $\bigwedge_{A}$a.

If A just consists of two elements, say A = {a, b}, we can denote $\bigwedge$A simply by a $\land$ b.

Similarly, we say that p is a join of A if

for all a $\in$ A we have a ≤ p, and
for all q such that a ≤ q for all a $\in$ A, we have that p ≤ q.

We write p = $\begin{equation}V A\end{equation}$ or p = $V_{a \in A} a$a, or when A = {a, b} we may simply write p = a $\lor$ b.

Remark 1.82. In Definition 1.81, we committed a seemingly egregious abuse of notation. We will see next in Example 1.84 that there could be two different meets of A $\subseteq$ P, say p = $\bigwedge A$ and q =$\bigwedge$ A with p $\neq$ q, which does not make sense if p $\neq$ q!

But in fact, as we use the symbol $\bigwedge$ A, this abuse won’t matter because any two meets p, q are automatically isomorphic: the very definition of meet forces both p ≤ q and q ≤ p, and thus we have p $\cong$ q. So for any x $\in$ P, we have p ≤ x iff q ≤ x and x ≤ p iff x ≤ q. Thus as long as we are only interested in elements of P based on their relationships to other elements (and in category theory, this is the case: we should only care about things based on how they interact with other things, rather than on some sort of “internal essence”), the distinction between p and q will never matter.

This foreshadows a major theme of as well as standard abuse of notation in category theory, where any two things defined by the same universal property are automatically equivalent in a way known as ‘unique up to unique isomorphism’; this means that we generally do not run into trouble if we pretend they are equal. We’ll pick up this theme of ‘the’ vs ‘a’ again in Remark 3.85.

Example 1.83 (Meets or joins may not exist).

Note that, in an arbitrary preorder (P, ≤), a subset A need not have a meet or a join. Consider the three element set P = {p, q, r} with the discrete ordering. The set A = {p, q} does not have a join in P because if x was a join, we would need p ≤ x and q ≤ x, and there is no such element x.

Example 1.84 (Multiple meets or joins may exist).

It may also be the case that a subset A has more than one meet or join. Here is an example.

$Screen Shot 2021-01-07 at 6.35.42 PM.png$

Let A be the subset {a, b} in the preorder specified by this Hasse diagram. Then both c and d are meets of A: any element less than both a and b is also less than c, and also less than d. Note that, as in Remark 1.82, c ≤ d and d ≤ c, so c $\cong$ d. Such will always the case when there is more than one meet: any two meets of the same subset will be isomorphic.

Exercise 1.85.

Let (P, ≤) be a preorder and p $\in$ P an element. Consider the set A = {p} with one element.

Show that $\bigwedge$A $\cong$ p.
Show that if P is in fact a partial order, then $\bigwedge$A = p.
Are the analogous facts true when $\bigwedge$ is replaced by $V$?

Example 1.86.

In any partial order P, we have p $\lor$ p = p $\land$p = p.The reason is that our notation says p $\lor$ p means $V${p, p}. But {p, p} = {p} (see Section 1.2.1), so p $\lor$ p = p by Exercise 1.85.

Example 1.87.

In a power set P(X), the meet of a collection of subsets, say A, B $\subseteq$ X is their intersection A $\land$ B = A $\cap$ B, while the join is their union, A $\lor$ B = A $\cup$ B.

$Screen Shot 2021-01-07 at 6.45.05 PM.png$

Perhaps this justifies the terminology: the joining of two sets is their union, the meeting of two sets is their intersection.

Example 1.88.

In the booleans $\mathbb{B}$ = {false, true} (Example 1.34), the meet of any two elements is given by AND and the join of any two elements is given by OR (recall Exercise 1.7).

Example 1.89.

In a total order, the meet of a set is its infimum, while the join of a set is its supremum. Note that $\mathbb{B}$ is a total order, and this generalizes Example 1.88.

Exercise 1.90.

Recall the division ordering on N from Example 1.45: we write n|m if n divides perfectly into m. The meet of any two numbers in this preorder has a common name, that you may have learned when you were around 10 years old; what is it? Similarly the join of any two numbers has a common name; what is it? ♦

Proposition 1.91.

Suppose (P, ≤) is a preorder and A $\subseteq$ B $\subseteq$ P are subsets that have meets. Then $\bigwedge$B ≤ $\bigwedge$A. Similarly, if A and B have joins, then $V$A ≤ $V$B.

Proof. Let m = $\bigwedge$A and n = $\bigwedge$B. Then for any a $\in$ A we also have a $\in$ B, so n ≤ a because n is a lower bound for B. Thus n is also a lower bound for A and hence n ≤ m, because m is A’s greatest lower bound. The second claim is proved similarly. ♦

Back to observations and generative effects

In the thesis [Ada17], Adam thinks of monotone maps as observations. A monotone map Φ: P → Q is a phenomenon (we might say “feature”) of P as observed by Q. He defines the generative effect of such a map Φ to be its failure to preserve joins (or more generally, for categories, its failure to preserve colimits).

Definition: 1.92.

We say that a monotone map f : P → Q preserves meets if f (a $\land$ b) $\cong$ f (a) $\land$ f (b) for all a, b $\in$ P. We similarly say f preserves joins if f (a $\lor$ b) $\cong$ f (a) $\lor$ f (b) for all a, b $\in$ P.

Definition: 1.93.

We say that a monotone map f : P → Q has a generative effect if there exist elements a, b $\in$ P such that

f(a) $\lor$ f(b) $\cong$ f(a $\lor$ b).

In Definition 1.93, if we think of Φ as a observation or measurement of the systems a and b, then the left hand side f (a) $\lor$ f (b) may be interpreted as the combination of the observation of a with the observation of b. On the other hand, the right hand side f (a $\lor$ b) is the observation of the combined system a $\lor$ b. The inequality implies that we see something when we observe the combined system that we could not expect by merely combining our observations of the pieces. That is, that there are generative effects from the interconnection of the two systems.

Exercise 1.94.

In Definition 1.93, we defined generativity of f as the inequality f(a $\lor$ b) $\neq$ f(a) $\lor$ f(b), but in the subsequent text we seemed to imply there would be not just a difference,but more stuff in f(a $\lor$ b) than in f(a) $\lor$ f(b). Prove that for any monotone map f : P → Q, if a, b $\in$ P have a join and f(a), f(b) $\in$ Q have a join, then indeed f(a) $\lor$ f(b) ≤ f(a $\lor$ b). ♦

In his work on generative effects, Adam restricts his attention to generative maps that preserve meets (but do not preserve joins). The preservation of meets implies that the map Φ behaves well when restricting to subsystems, even though it can throw up surprises when joining systems.

This discussion naturally leads into Galois connections, which are pairs of monotone maps between preorders, one of which preserves all joins and the other of which preserves all meets.

Search

Text Color

Text Size

Margin Size

Font Type