Exercises 2: Adjunctions

EX 1: Free monoids and categories

1.

Show that the forgeful functor $U: Mon ⟶ Set$ admits a left adjoint $F: Set ⟶ Mon$.

Unity / Conunity?

The functor $F$ given by:

  • $F(X) ≝ X^\ast$ (words of elements of $A$)
  • $F(\underbrace{f}_{∈Hom(X,Y)}) ≝ x_1 ⋯ x_r ⟼ f(x_1) ⋯ f(x_r): FX ⟶ FY$

Let’s show that:

\[Mon(FX, Y) ≃ Set(X, UY)\] \[φ_{X, Y}: \begin{cases} Set(X, UY) &⟶ Mon(FX, Y) \\ f: X ⟶ Y &\mapsto \begin{cases} X^\ast &⟶ Y \\ x_1 ⋯ x_r &\mapsto f(x_1) ⋯ f(x_r) \end{cases} \end{cases}\]

it is a bijection:

\[φ^{-1}_{X, Y}: Mon(FX, Y) \ni f ⟼ (x ⟼ f([x]))\]

The transofrmation is natural:

if $f∈ Set(X, X’), \; g∈ Mon(Y, Y’)$:

\[\begin{xy} \xymatrix{ Mon(FX, Y)\ar[d]_{φ_{X,Y}} && Mon(FX', Y) \ar[ll]_{\_ \circ Ff} \ar[d]^{φ_{X',Y}} \\ Set(X, UY) && Set(X', UY) \ar[ll]_{\_ \circ f} } \end{xy}\]

and

\[\begin{xy} \xymatrix{ Mon(FX, Y) \ar[rr]^{g \circ \_} \ar[d]_{φ_{X,Y}} && Mon(FX, Y') \ar[d]^{φ_{X,Y'}} \\ Set(X, UY)\ar[rr]^{Ug \circ \_} && Set(X, UY') } \end{xy}\]

Or:

\[\begin{xy} \xymatrix{ Mon(FX', Y) \ar[rr]^{g \circ \_ \circ Ff} \ar[d]_{φ_{X',Y}} && Mon(FX, Y') \ar[d]^{φ_{X,Y'}} \\ Set(X', UY)\ar[rr]^{Ug \circ \_ \circ f} && Set(X, UY') } \end{xy}\]

Since

\[Ug \circ φ_{X',Y}(\_) \circ f = φ_{X,Y'}(g \circ \_ \circ Ff)\]

2.

Forgetful functor $U: Cat ⟶ Graph$

  • vertices of the graph are the objects of the category
  • edges are morphisms

A graph: $G ≝ (G_0, G_1, s, t)$

\[s, t: G_1 ⟶ G_0\]

The adjunction we’re looking for generalizes $F: Set ⟶ Mon$

  • $FG$: the category:

    • objects: vertices of $G$
    • morphisms: paths in the graph (identity: empty paths from a vertex to itself)

3/4.

\[U: Top ⟶ Set\]

admits a left and a right adjoint.

Discrete topology:

\[F: \begin{cases} Set ⟶ Top \\ A \mapsto (A, ℙ(A)) \end{cases}\]

Any function in $FA ⟶ B$ is continuous, so

\[Top(FA, B) ≃ Set(A, UB)\]

Coarsest topology:

\[F: \begin{cases} Set ⟶ Top \\ A \mapsto (A, \lbrace A, ∅ \rbrace) \end{cases}\]

Any function in $A ⟶ FB$ is continuous (since $f^{-1}(∅) = ∅, \; f^{-1}(FB) = A$), so

\[Top(A, FB) ≃ Set(UA, B)\]

EX2

1.

The terminal functor $T: 𝒞 ⟶ 1$ has a right adjoint iff $𝒞$ has a terminal object.

If there’s a terminal object $1_𝒞$:

\[G: 1 \ni \ast ⟼ 1_𝒞 ∈ 𝒞\]

is a right adjoint of $T$:

\[∀A∈ G, 𝒞(A, \underbrace{G\ast}_{= 1_𝒞}) ≃ 1(\underbrace{TA}_{= \ast}, \ast)\]

It is the definition of the terminal object.

2.

\[D: \begin{cases} 𝒞 &⟶ 𝒞 × 𝒞 \\ a &\mapsto (a, a) \\ f &⟼ (f, f) \end{cases}\] \[φ: 𝒞(a, G((x, y))) ≃ 𝒞×𝒞((a, a), (x, y)) ≃ 𝒞(a, x) × 𝒞(a, y)\]

With $a = G((x, y))$, we have the projections.

With the naturality, we have the universality of the product.

If $f: A ⟶ B, \; g: A ⟶ C$:

\[⟨f, g⟩ ≝ φ_{A, (B,C)}((f,g))\]

EX 3

1.

If $f: X ⟶ Y$:

\[Δ_f ≝ f^{-1}: \begin{cases} ℙ(Y) &⟶ ℙ(X) \\ S &\mapsto f^{-1}(S) \\ S ⊆ S' &\mapsto f^{-1}(S) ⊆ f^{-1}(S') \\ \end{cases}\]

The functoriality stems from the fact that the homsets contain at most one element.

EX 5:

1/2.

  • $U: pSet ⟶ Set$ is the forgetful functor
  • \[F: \begin{cases} Set &⟶ pSet \\ A \sqcup \lbrace \ast \rbrace &⟼ (A \sqcup \lbrace \ast \rbrace, \ast) \\ f: A ⟶ B &⟼ \begin{cases} (A \sqcup \lbrace \ast \rbrace, \ast) ⟶ (B \sqcup \lbrace \ast \rbrace, \ast) \\ a ∈ A ⟼ f(a) \\ \ast ⟼ \ast \end{cases} \\ \end{cases}\]
\[φ_{A, B}: pSet(FA, <B) ≃ Set(A, UB)\]
  • $φ_{A, B}(f) = f_{ A}$
  • \[ψ_{A, B}(g) ≝ \begin{cases} (A \sqcup \lbrace \ast \rbrace, \ast) ⟶ (B, b) \\ a ∈ A ⟼ g(a) \\ \ast ⟼ b \end{cases}\]

4.

Leave a comment