• EX 1.69:

Let $$X = \{0,1,2,3\}$$, $$Y = \{0,1,2\}$$, and $\begin{equation}\begin{split} &f : X \twoheadrightarrow Y \\ &f = \{(0,0),(1,1),(2,2),(3,0)\} \\ \end{split}\end{equation}$

Define partitions $\begin{equation}\begin{split} &P = \{\{0,1\},\{2\}\} \\ &Q = \{\{0\},\{1,2\}\} \\ \end{split}\end{equation}$

A partition can be expressed as a surjection (EG 1.26). So, for some $$Z = \{0,1\}$$, express $$P$$ as $\begin{equation}\begin{split} &s : Y \twoheadrightarrow Z \\ &s = \{(0,0),(1,0),(2,1)\} \\ \end{split}\end{equation}$

and $$Q$$ as $\begin{equation}\begin{split} &t : Y \twoheadrightarrow Z \\ &t = \{(0,0),(1,1),(2,1)\} \\ \end{split}\end{equation}$

Then $$f$$ induces the pullback along f, called $$f^*$$, by composing partitions on the left $\begin{equation}\begin{split} &f^* : \text{Prt}(Y) \rightarrow \text{Prt}(X) \\ &f^*(s) = s \circ f = \{(0,0),(1,0),(2,1),(3,0)\} \\ &f^*(t) = t \circ f = \{(0,0),(1,1),(2,1),(3,0)\} \\ \end{split}\end{equation}$

which can be expressed as partitions $\begin{equation}\begin{split} &f^*(P) = \{\{0,1,3\},\{2\}\} \\ &f^*(Q) = \{\{0,3\},\{1,2\}\} \\ \end{split}\end{equation}$

So $$f^*$$ sends a subset $$B \subseteq Y$$ to its preimage $$f^{-1}(B) \subseteq X$$.

• EX 1.94:

$$a \leq a \vee b$$ by definition of join (D 1.81), and likewise $$b \leq a \vee b$$. Since the monotone map $$f$$ preserves orders, we have $$f(a) \leq f(a \vee b)$$ and $$f(b) \leq f(a \vee b)$$, so by definition of join, $$f(a) \vee f(b) \leq f(a \vee b)$$.

• EX 1.125:
1. Define the preorder relation on $$S = \{1,2,3\}$$ $\begin{equation}\begin{split} &\leq : S \times S \rightarrow \text{Bool} \\ &\leq(2,1) = \text{False} \\ &\leq(3,1) = \text{False} \\ &\leq(3,2) = \text{False} \\ \end{split}\end{equation}$ and all other tuples map to True. Define the image of ≤ under the inclusion $$\mathbf{Pos}(S) \rightarrow \mathbf{Rel}(S)$$ $\begin{equation}\begin{split} &U(\leq) : \text{P}(S \times S) \\ &U(\leq) = \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\} \\ \end{split}\end{equation}$
2. Define $\begin{equation}\begin{split} &Q : \text{P}(S \times S) \\ &Q = \{(1,2)\} \\ \end{split}\end{equation}$ and $\begin{equation}\begin{split} &Q' : \text{P}(S \times S) \\ &Q' = \{(2,1),(3,1),(3,2)\} \\ \end{split}\end{equation}$ such that $$Q \subseteq U(\leq)$$ and $$Q' \not \subseteq U(\leq)$$.
3. Define $\begin{equation}\begin{split} &\text{Cl} : \mathbf{Rel}(S) \rightarrow \mathbf{Pos}(S) \\ &\text{Cl}(Q) = \leq_Q \\ \end{split}\end{equation}$ where $\begin{equation}\begin{split} &\leq_Q : S \times S \rightarrow \text{Bool} \\ &\leq_Q(1,1) = \text{True} \\ &\leq_Q(1,2) = \text{True} \\ &\leq_Q(2,2) = \text{True} \\ \end{split}\end{equation}$ and so $$\text{Cl}(Q) \sqsubseteq \leq$$ by definition.
4. Define $\begin{equation}\begin{split} &\text{Cl} : \mathbf{Rel}(S) \rightarrow \mathbf{Pos}(S) \\ &\text{Cl}(Q') = \leq_{Q'} \\ \end{split}\end{equation}$ where $\begin{equation}\begin{split} &\leq_{Q'} : S \times S \rightarrow \text{Bool} \\ &\leq_{Q'}(1,1) = \text{True} \\ &\leq_{Q'}(2,1) = \text{True} \\ &\leq_{Q'}(2,2) = \text{True} \\ &\leq_{Q'}(3,1) = \text{True} \\ &\leq_{Q'}(3,2) = \text{True} \\ \end{split}\end{equation}$ and so $$\text{Cl}(Q') \not \sqsubseteq \leq$$ as $$\{(2,1),(3,1),(3,2)\}$$ are not in the domain of $$\leq$$.
• PS1 1: In the poset on set $$\mathbb{N}$$, with $$d \leq n$$ when $$d \mid n$$, the meet is the GCD, the join is the LCM.
• PS1 2: Intuition (see EG 1.117 for an example):

• $$f^*$$: elements in $$X$$ that are in the preimage of a subset of $$Y$$.
• $$f_!$$: elements in $$Y$$ that are in the image of a subset of $$X$$.
• $$f_*$$: elements in $$Y$$ that are in the image of a subset of $$X$$, and are "injective between partitions" (two elements from the same partition can map to the same element, but two elements in different partitions cannot map to the same element).

Let $$X = \{0,1,2,3\}$$, $$Y = \{0,1,2\}$$, and $\begin{equation}\begin{split} &f : X \twoheadrightarrow Y \\ &f = \{(0,0),(1,1),(2,2),(3,0)\} \\ \end{split}\end{equation}$

1. Let $$B_1 = \{0,1\}$$ and $$B_2 = \{2\}$$. Then, according to EX 1.69 $\begin{equation}\begin{split} &f^*(B_1) = \{0,1,3\} \\ &f^*(B_2) = \{2\} \\ \end{split}\end{equation}$
2. Let $$A_1 = \{0,1\}$$ and $$A_2 = \{2,3\}$$. Then $\begin{equation}\begin{split} &f_!(A_1) = \{0,1\} \\ &f_!(A_2) = \{0,2\} \\ \end{split}\end{equation}$
3. Let $$A_1 = \{0,1\}$$ and $$A_2 = \{2,3\}$$. Then $\begin{equation}\begin{split} &f_*(A_1) = \{1\} \\ &f_*(A_2) = \{2\} \\ \end{split}\end{equation}$
4. $$f_!$$ is left adjoint to $$f^*$$, since
• $$(\Rightarrow)$$: Assume $$f_!(A) \leq B$$. Since $$f^*$$ is a monotone map, it preserves order: $$f^*(f_!(A)) \leq f^*(B)$$. Since $\begin{equation}\begin{split} & &&A \\ &\leq &&A \cup \text{other elements that map to the image of}\ f\ \text{on}\ A \\ &= &&\{a \in X \mid f(a) \in \text{the image of}\ f\ \text{on}\ A\} \\ &= &&\{a \in X \mid f(a) \in \{y \in Y \mid \exists a \in A \ \text{s.t.}\ f(a) = y\}\} \\ &= &&f^*(f_!(A)) \\ \end{split}\end{equation}$ then by transitivity, $$A \leq f^*(B)$$.
• $$(\Leftarrow)$$: Assume $$A \leq f^*(B)$$. Since $$f_!$$ is a monotone map, it preserves order: $$f_!(A) \leq f_!(f^{-1}(B))$$. Since $\begin{equation}\begin{split} & &&f_!(f^{-1}(B)) \\ &= &&\{y \in Y \mid \exists a \in \{a \in X \mid f(a) \in B\} \ \text{s.t.}\ f(a) = y\} \\ &= &&\{y \in Y \mid f(a) \in B \ \text{and}\ f(a) = y\} \\ &\leq &&B \\ \end{split}\end{equation}$ then by transitivity, $$f_!(A) \leq B$$.
• So $$f_!(A) \leq B$$ iff $$A \leq f^*(B)$$.
5. $$f_*$$ is right adjoint to $$f^*$$, since
• $$(\Rightarrow)$$: Assume $$f^*(B) \leq A$$. Since $$f_*$$ is a monotone map, it preserves order: $$f_*(f^*(B)) \leq f_*(A)$$. Since $\begin{equation}\begin{split} & &&B \\ &\leq &&B \cup \text{other elements that are in the image of}\ f \\ &= &&\{y \in Y \mid \forall a \in X\ \text{s.t.}\ f(a) = y, f(a) \in B\} \\ &= &&\{y \in Y \mid \forall a \in X\ \text{s.t.}\ f(a) = y, a \in \{a \in X \mid f(a) \in B\}\} \\ &= &&f_*(f^*(B)) \\ \end{split}\end{equation}$ then by transitivity, $$B \leq f_*(A)$$.
• $$(\Leftarrow)$$: Assume $$B \leq f_*(A)$$. Since $$f^*$$ is a monotone map, it preserves order: $$f^*(B) \leq f^*(f_*(A))$$. Since $\begin{equation}\begin{split} & &&f^*(f_*(A)) \\ &= &&\{a \in X \mid f(a) \in f_*(A)\} \\ &\leq &&A \\ \end{split}\end{equation}$ then by transitivity, $$f^*(B) \leq A$$.
• So $$f^*(B) \leq A$$ iff $$B \leq f_*(A)$$.
• PS1 3: Within the context of the pictures in EX 1.99, where all dotted arrows are counterclockwise: WTS: $$f$$ is a left adjoint iff the arrows do not cross.
• $$(\Rightarrow)$$: Assume $$f$$ is a left adjoint. Also assume there are two arrows that cross. Let $$p_i \in P$$ and $$q_i \in Q$$ be their start- and end-points respectively. Since $$P$$ and $$Q$$ are total orders, we can let $$p_0 \leq p_1$$ and $$q_0 \leq q_1$$. Split by cases

1. Both arrows point right. Then $$f(p_0) = q_1 \not \leq q_0$$ yet $$p_0 \leq p_1 = g(q_0)$$, so $$f$$ is not a left adjoint.
2. Both arrows point left. Then $$f(p_1) = q_0 \leq q_1$$ yet $$p_1 \not \leq p_0 = g(q_1)$$, so $$f$$ is not a left adjoint.

In both cases, $$f$$ is not a left adjoint. Contradiction! So, there are no two arrows that cross.

• $$(\Leftarrow)$$: Assume there are no two arrows that cross. Since $$P$$ and $$Q$$ are total orders, we can let $$p_i \leq p_{i+1}$$ and $$q_i \leq q_{i+1}$$. For each $$p_i$$, for all $$q_i$$, there are two cases

1. $$f(p_i) \leq q_i$$. Then, $$p_i \leq g(q_i)$$.
2. $$f(p_i) \not \leq q_i$$. Then, $$p_i \not \leq g(q_i)$$.

So, $$f(p_i) \leq q_i$$ iff $$p_i \leq g(q_i)$$. So, $$f$$ is a left adjoint.

• The crossed arrows represents a reversal of order, while $$f$$ and $$g$$ being adjoint represent a preservation of order.
• PS1 4: $$S$$ is left adjoint to $$L$$, so for each $$u \in U$$ and $$W' \subseteq W$$, $$W' \leq L(u)$$ iff $$S(W') \leq u$$.
1. Split by cases on $$W'$$, where we define $$S$$ such that the bijection holds. The bijection only needs to hold for when $$L(u)$$ is defined.
• $$\varnothing \leq \text{all}\ W' \in \text{P}(W)$$, so define $$S(\varnothing) = \texttt{nothing}$$ s.t. $$\texttt{nothing} \leq \text{all}\ u \in U$$
• $$\{\square\} \leq \text{only all of}\ \{\square\}, \{\square, \blacksquare\}, \{\square, \circ\}, \{\square, \blacksquare, \circ\}$$, so define $$S(\{\square\}) = \texttt{white_square}$$ s.t. $$\texttt{white_square} \leq \text{only all of}\ \texttt{white_square}, \texttt{square}, \texttt{white_object}, \texttt{object}$$
• $$\{\blacksquare\} \leq \text{only all of}\ \{\square, \blacksquare\}, \{\square, \blacksquare, \circ\}$$, so define $$S(\{\blacksquare\}) = \texttt{square}$$ s.t. $$\texttt{square} \leq \text{only all of}\ \texttt{square}, \texttt{object}$$
• $$\{\circ\} \leq \text{only all of}\ \{\square, \circ\}, \{\square, \blacksquare, \circ\}$$, so define $$S(\{\circ\}) = \texttt{white_object}$$ s.t. $$\texttt{white_object} \leq \text{only all of}\ \texttt{white_object}, \texttt{object}$$
• $$\{\square, \blacksquare\} \leq \text{only all of}\ \{\square, \blacksquare\}, \{\square, \blacksquare, \circ\}$$, so define $$S(\{\square, \blacksquare\}) = \texttt{square}$$ s.t. $$\texttt{square} \leq \text{only all of}\ \texttt{square}, \texttt{object}$$
• $$\{\square, \circ\} \leq \text{only all of}\ \{\square, \circ\}, \{\square, \blacksquare, \circ\}$$, so define $$S(\{\square, \circ\}) = \texttt{white_object}$$ s.t. $$\texttt{white_object} \leq \text{only all of}\ \texttt{white_object}, \texttt{object}$$
• $$\{\blacksquare, \circ\} \leq \text{only}\ \{\square, \blacksquare, \circ\}$$, so define $$S(\{\blacksquare, \circ\}) = \texttt{object}$$ s.t. $$\texttt{object} \leq \text{only all of}\ \texttt{object}$$
• $$\{\square, \blacksquare, \circ\} \leq \text{only}\ \{\square, \blacksquare, \circ\}$$, so define $$S(\{\square, \blacksquare, \circ\}) = \texttt{object}$$ s.t. $$\texttt{object} \leq \text{only}\ \texttt{object}$$
2. The pragmatic speaker can only say utterances that the literal listener can understand. An utterance must be the least generic term used to describe the object.
3. $$L'$$ is left adjoint to $$S$$, so for each $$u \in U$$ and $$W' \subseteq W$$, $$u \leq S(W')$$ iff $$L'(u) \leq W'$$. Split by cases on $$u$$, where we define $$L'$$ such that the bijection holds. The bijection only needs to hold for when $$S(W')$$ is defined.

• $$\texttt{nothing} \leq \text{all}\ u \in U$$, so define $$L'(\texttt{nothing}) = \varnothing$$ s.t. $$\varnothing \leq \text{all}\ u \in U$$
• $$\texttt{white_square} \leq \text{only all of}\ \texttt{white_square}, \texttt{square}, \texttt{white_object}, \texttt{object}$$, so define $$L'(\texttt{white_square}) = \{\square\}$$ s.t. $$\{\square\} \leq \text{only all of}\ \{\square\}, \{\square, \blacksquare\}, \{\square, \circ\}, \{\square, \blacksquare, \circ\}$$
• $$\texttt{square} \leq \text{only all of}\ \texttt{square}, \texttt{object}$$, so define $$L'(\texttt{square}) = \{\square, \blacksquare\}$$ s.t. $$\{\square, \blacksquare\} \leq \text{only all of}\ \{\square, \blacksquare\}, \{\square, \blacksquare, \circ\}$$
• $$\texttt{white_object} \leq \text{only all of}\ \texttt{white_object}, \texttt{object}$$, so define $$L'(\texttt{white_object}) = \{\square, \circ\}$$ s.t. $$\{\square, \circ\} \leq \text{only all of}\ \{\square, \circ\}, \{\square, \blacksquare, \circ\}$$
• $$\texttt{object} \leq \text{only all of}\ \texttt{object}$$, so define $$L'(\texttt{object}) = \{\square, \blacksquare, \circ\}$$ s.t. $$\{\square, \blacksquare, \circ\} \leq \text{only all of}\ \{\square, \blacksquare, \circ\}$$

The pragmatic listener only considers the least set of possibilities that the object corresponding to the utterance can be. The literal listener is the pragmatic listener (by coincidence?).

Created: 2020-01-22 Wed 18:39