\section[Adjungierte Funktoren]{Adjungierte Funktoren \hfill \small Peter
Uebele}

%\emph{Werbung:} Adjungierte Funktoren treten überall in der Mathematik auf. In
%diesem Abschnitt wollen und es gibt viele
%Möglichkeiten...

% XXX: adjungierte Funktoren in der Logik!


%Erinnerung: Äquivalenz von Kategorien $\cC, \cD$:\\
%$\exists F:\cD\rightarrow \cC$, $G:\cC\rightarrow \cD$ inverse Funktoren, d.h.
%$F\circ G\cong id_\cC$ und $G\circ G\cong id_\cD$

%\paragraph{Idee:} Hin- und herschieben von Morphismen zwischen $\cC, \cD$.\\
%$\rightsquigarrow$ Verallgemeinerung, s.d. $\cC,\cD$ nicht mehr äquivalent sein
%müssen.
\begin{defn}
Seien $F:\D\to\C$, $G:\C\to\D$ Funktoren. Genau dann heißt
\begin{itemize}
\item 
$F$ \emph{linksadjungiert zu} $G$ bzw.
\item 
$G$ \emph{rechtsadjungiert zu} $F$,
\end{itemize}
in Zeichen: $F \dashv G$, wenn es eine in~$X \in \Ob\C$ und~$Y \in \Ob\D$ natürliche
Isomorphie gibt:
\[ \Hom_\C(FY,X) \cong \Hom_\D(Y,GX) \]
\end{defn}
Dabei ist \emph{natürlich} gemäß Bemerkung~\ref{interpretnat} zu verstehen:
Linke und rechte Seiten der Isomorphie sind als Auswertungen der Funktoren
\[ \begin{array}{@{}rrcl@{}}
  \Hom_\C(F\freist,\freist) :&
    \D^\op \times \C &\longrightarrow& \Set \\
  & (Y,X) &\longmapsto& \Hom_\C(FY, X) \\\\
  \Hom_\D(\freist,G\freist) :&
    \D^\op \times \C &\longrightarrow& \Set \\
  & (Y,X) &\longmapsto& \Hom_\D(Y, GX)
\end{array} \]
zu lesen. Die Natürlichkeitsbedingung bedeutet dann, dass
für alle Morphismen $f:X\rightarrow X'$ in~$\C$ und
$g:Y'\rightarrow Y$ in~$\D$ das Diagramm
\[ \xymatrix{
  \Hom_\C(FY,X) \ar[d]_\cong \ar[r] & \Hom_\C(FY',X') \ar[d]^\cong \\
  \Hom_\D(Y,GX) \ar[r] & \Hom_\D(Y',GX')
} \]
kommutiert.

\begin{bsp}Sei~$F:\D \to \C$ quasi-invers zu~$G:\C \to \D$ (im Sinne von
Definition~\ref{cateqv}). Dann ist~$F$ links- und rechtsadjungiert
zu~$G$.\end{bsp}
Das Konzept zueinander adjungierter Funktoren ist also eine Verallgemeinerung
des Konzepts zueinander quasi-inverser Funktoren: Auch, wenn ein Funktor kein
Quasi-Inverses besitzt, kann man dennoch fragen, inwieweit man ihn zumindest
\emph{so gut wie möglich} invertieren kann. Das folgende Beispiel~\cite{smith}
soll diesen Gedanken illustrieren.

\begin{bsp}Sei~$i:\ZZ \to \QQ$ die Inklusion der ganzen in die rationalen Zahlen,
aufgefasst als partiell geordnete Mengen. Diese Abbildung besitzt keine
monotone Umkehrabbildung, aber zwei Beinahe-Inverse, nämlich die Auf- und
Abrundungsfunktionen:
\[ \begin{array}{@{}rrcl@{}}
  \lceil \freist \rceil : & \QQ &\longrightarrow& \ZZ \\
  & x &\longmapsto& \lceil x \rceil = \text{(kleinste ganze Zahl $\geq x$)} \\\\
  \lfloor \freist \rfloor : & \QQ &\longrightarrow& \ZZ \\
  & x &\longmapsto& \lfloor x \rfloor = \text{(größte ganze Zahl $\leq x$)}
\end{array} \]
Die von diesen monotonen Abbildungen induzierten Funktoren erfüllen tatsächlich
die Adjunktionsbeziehungen
\[ B\lceil\freist\rceil \dashv Bi \dashv B\lfloor\freist\rfloor, \]
siehe Aufgabe~1 von Übungsblatt~7.\end{bsp}


\subsection{Beispiele für adjungierte Funktoren}

Wenn man einmal gelernt hat, adjungierte Funktoren zu erkennen, so trifft man
ständig auf sie. Im Folgenden wollen wir eine lächerlich kurze Beispielliste
aus verschiedenen Teilgebieten der Mathematik zusammenstellen.

\subsubsection*{Beispiel aus der Algebra: Freie Konstruktionen}

Sei~$K$ ein Körper (oder Ring), $U : \Vect{K} \to \Set$ der
Vergissfunktor und~$F : \Set \to \Vect{K}$ der Funktor, der jeder Menge~$X$
den sog. \emph{freien Vektorraum über~$X$}
\[ F(X) := \Biggl\{ \sum_{i=1}^n \lambda_i x_i \,\Bigg|\,
  n \geq 0, \lambda_1, \ldots, \lambda_n \in K, x_1, \ldots, x_n \in X \Biggr\} \]
zuordnet. Dessen Elemente sind sog. formale (endliche) Linearkombinationen der
Elemente von~$X$; addiert wird also nicht wirklich, man notiert lediglich vor
jedes Element aus~$X$ einen Koeffizienten aus~$K$.\footnote{In konstruktiver
Mathematik realisiert man~$F(X)$ als Menge von Wörtern über~$K \times X$ modulo
einer geeigneten Äquivalenzrelation, wenn man nicht voraussetzen möchte,
dass~$X$ als Menge diskret ist.} Die Elemente von~$X$ bilden dann eine Basis
von~$F(X)$.
Eine Abbildung~$f : X \to X'$ von Mengen induziert eine lineare Abbildung
zwischen den zugehörigen freien Vektorräumen:
\[ F(f) : F(X) \to F(X'),\ \sum_{i=1}^n \lambda_i x_i \mapsto
  \sum_{i=1}^n \lambda_i f(x_i). \]

Die Konstruktion des freien Vektorraums über einer Menge~$X$ ist die
\emph{ökonomischste Art und Weise}, um aus der Menge~$X$ einen
Vektorraum~$F(X)$ zu basteln: Denn wenn die Elemente~$x \in X$ zu Vektoren
werden sollen, müssen in~$F(X)$ auch Linearkombinationen von ihnen enthalten
sein; weitere Vektoren werden von den Vektorraumaxiomen aber nicht gefordert.
Ferner sollten in~$F(X)$ genau die Rechenregeln erfüllt sein, die von den
Vektorraumaxiomen vorgeschrieben werden, aber keine willkürlichen
weiteren. Die im vorherigen Absatz gegebene Konstruktion
bewerkstelligt das gerade\footnote{Das ist eine gute anschauliche Vorstellung, man kann sie
allerdings nicht zu wörtlich nehmen: Etwa folgt aus den Vektorraumaxiomen für
kein~$n \geq 0$ die Aussage "`der Vektorraum ist~$n$-dimensional"', da es ja
Vektorräume beliebiger Dimension gibt. Aber für endliches~$X$ erfüllt~$F(X)$
diese Aussage doch, für~$n = |X|$. Nur wenn man bereit ist, den Topos, in dem man
arbeitet, zu wechseln, kann man einen völlig generischen Vektorraum
konstruieren.}. Formal kann man das durch folgende Adjunktionsbeziehung
ausdrücken:
\begin{prop}Der Funktor~$F$ ist
linksadjungiert zum Vergissfunktor~$U$, d.\,h. $F \dashv U$.
\end{prop}
\begin{proof}
Wir geben den in~$Y \in \Ob\Set$ und~$V \in \Ob\Vect{K}$ natürlichen
Isomorphismus explizit an:
\[ \begin{array}{@{}rcl@{}}
  \Hom_{\Vect{K}}(F(Y), V) &\longrightarrow& \Hom_\Set(Y, U(V)) \\
  \varphi &\longmapsto& \varphi|_Y
\end{array} \]
Die Bijektivität dieser Zuordnung drückt gerade aus, dass die Werte auf einer
Basis genügen, um eine lineare Abbildung eindeutig festzulegen. Die
Natürlichkeitsbedingung besagt, dass für alle~$f:V \to V'$ in~$\Vect{K}$ und~$g:Y' \to Y$
das Diagramm
\[ \xymatrix{
  \Hom_{\Vect{K}}(F(Y),V) \ar[r] \ar[d]_\cong & \Hom_{\Vect{K}}(FY',U(V')) \ar[d]^\cong \\
  \Hom_\Set(Y,U(V)) \ar[r] & \Hom_\Set(Y',U(V'))
} \]
kommutiert, d.\,h. dass für alle~$\varphi \in \Hom_{\Vect{K}}(F(Y),V)$ die Gleichung
\[
  (f \circ \varphi \circ F(g))|_{Y'} = f \circ \varphi|_Y \circ g
\]
erfüllt ist. Das ist offensichtlich der Fall.
\end{proof}

% Erklären: Da es eben KEINE willkürlichen Relationen gibt, lässt sich jede
% Abbildung Y --> U(V) zu einer linearen Abbildung F(Y) --> V liften.

Auf ähnliche Art und Weise kann man viele \emph{freie Konstruktionen}
durchführen: freie Monoide (siehe Übungsblatt~7, Aufgabe~2), freie Gruppen,
freie Ringe, \ldots; manche Theorien lassen aber auch keine freien
Konstruktionen zu, etwa die der Körper (siehe Übungsblatt~7, Aufgabe~3). Im
Rahmen der universellen Algebra ist dieses Phänomen vollständig verstanden.
% XXX: "und nicht besonders schwer"

\begin{aufg}Wie kann der freie Ring über einer Menge~$X$ realisiert werden?
\emph{Ring} soll dabei, wie sonst in diesem Skript auch, genauer
\emph{kommutativer Ring mit Eins} bedeuten.\end{aufg}


\subsubsection*{Beispiel aus der Kategorientheorie}

Der Vergissfunktor~$U : \Cat \to \Set$, der einer kleinen Kategorie
ihre Menge von Objekten zuordnet, besitzt sowohl einen Links-, als auch einen
Rechtsadjungierten, nämlich
\[ \begin{array}{@{}rrclrcl@{}}
  L : & \Set &\longrightarrow& \Cat, & X &\longmapsto& \text{diskrete Kategorie auf~$X$,} \\
  R : & \Set &\longrightarrow& \Cat, & X &\longmapsto& \text{indiskrete Kategorie auf~$X$.}
\end{array} \]
Denn man hat natürliche Isomorphismen
\[ \Hom_\Cat(L(X), \E) \cong \Hom_\Set(X, \Ob\E)
  \quad\text{und}\quad
  \Hom_\Set(\Ob\E, Y) \cong \Hom_\Cat(\E, R(Y)). \]

% Limitenfunktor


\subsubsection*{Beispiel aus der Topologie}

Analog hat der Vergissfunktor~$U : \Top \to \Set$, der jedem
topologischen Raum seine zugrundeliegende Menge von Punkten zuordnet, einen
Links- und Rechtsadjungierten: die Konstruktion des diskreten bzw. indiskreten
topologischen Raums auf einer Menge.


\subsubsection*{Beispiel aus der Logik}

Lawvere hat beobachtet, dass existenzielle und
universelle Quantifikation als Links- bzw. Rechtsadjungierte interpretiert
werden können:
\[ \exists \dashv f^* \dashv \forall. \]
Hier ist nicht der Platz, um in den nötigen Hintergrund einzuführen, sodass wir
diese
zelebrierte Adjunktionskette formal diskutieren könnten. Aber eine intuitive Analyse ist durchaus
möglich. Dazu müssen wir zunächst verstehen, wie Logiker die fundamentale
Schlussregel für den Existenzquantor ausdrücken:
\begin{center}
  \def\labelSpacing{8pt}
  \Axiom$\exists y\mathpunct{:}\,\! \varphi\ \fCenter\seq{\vec x} \psi$\doubleLine
  \RightLabel{\scriptsize (wenn~$y$ nicht in~$\psi$ vorkommt)}
  \LeftLabel{\phantom{\scriptsize (wenn~$y$ nicht in~$\psi$ vorkommt)}}
  \UnaryInf$\varphi\ \fCenter\seq{\vec x, y} \psi$
  \DisplayProof
\end{center}
Der Doppelstrich deutet an, dass diese Regel sowohl von oben nach unten als
auch umgekehrt angewendet werden kann. Ausformuliert besagt sie:
\begin{indentblock}
Seien~$x_1,\ldots,x_n$ (kurz~$\vec x$) sowie~$y$ Variablen.
Sei~$\varphi$ eine logische Formel in den Variablen~$\vec x$ sowie~$y$ und
sei~$\psi$ eine logische Formel in~$\vec x$. Genau dann
kann man
\[ \text{im Kontext der Variablen~$\vec x$ aus $(\exists y{:}\ \varphi)$ die
Aussage~$\psi$ folgern,} \]
wenn man
\[ \text{im Kontext der Variablen~$\vec x, y$ aus $\varphi$ die Aussage~$\psi$
folgern kann.} \]
\end{indentblock}
Mit anderen Worten: Wenn man die Aussage~$(\exists y{:}\ \varphi)$ als
Voraussetzung gegeben hat und aus ihr die Aussage~$\psi$ folgern möchte, dann
kann man die Existenz eines Werts~$y$, der die Eigenschaft~$\varphi$ hat,
voraussetzen und unter diesem Kontext die Aussage~$\psi$ folgern. Umgekehrt
geht es auch. Diese Schlussregel wendet man also ständig an, man reflektiert
sie nur selten.

Unter dem Doppelstrich wird die Formel~$\psi$, in der die Variable~$y$ nicht
vorkommt, im Kontext~$\vec x, y$ betrachtet. Diesen Prozess modelliert man in
einem geeigneten Sinn als Rückzug längs eines Projektionsmorphismus~$X_1 \times
\cdots \times X_n \times Y \to X_1 \times \cdots \times X_n$, wobei~$X_i$ die
Typen der Variablen~$x_i$ und~$Y$ der Typ von~$y$ ist. So lässt sich die
Schlussregel für den Existenzquantor also auch als Ausdruck einer
Adjunktionsbeziehung verstehen:
\[ \Hom_{\vec x}((\exists y{:}\, \varphi),\ \psi) \cong
  \Hom_{\vec x, y}(\varphi,\ \psi). \]

\begin{aufg}Formuliere die fundamentale Schlussregel für den
Allquantor.\end{aufg}

% XXX: Syntax vs. Semantik


\subsection{Zusammenspiel von adjungierten Funktoren und (Ko-)Limiten}

\begin{prop}\label{limitenbeiadjunktionen}%
Sei $F:\C\to\D$ linksadjungiert zu $G:\D\to\C$. Dann gilt:
\begin{enumerate}
\item $F$ erhält Kolimiten von $\C$.
\item $G$ erhält Limiten von $\D$.
\end{enumerate}
\end{prop}

\begin{bsp}\label{vergissstetig}
\begin{enumerate}
\item Der Vergissfunktor $U:\Vect{K} \to \Set$ erhält Limiten.
Da er aber nicht Kolimiten erhält (Beispiel~\ref{vectvergiss}), kann er keinen
Rechtsadjungierten besitzen.
\item \label{vergisscat}Der Vergissfunktor $U:\Cat \to \Set$ erhält Limiten und Kolimiten.
\item Der Vergissfunktor $U:\Top \to \Set$ erhält Limiten und Kolimiten.
\end{enumerate}
\end{bsp}

\begin{proof}[Beweis der Proposition]
Der übliche Beweis geht so: Sei $D:\I\to\D$ ein Diagramm, mit Limes~$\lim_i D(i)$.
Dann folgt aus der in~$Y \in \Ob\D$ natürlichen Isomorphiekette
\begin{align*}
  \Hom_\D(Y,G(\lim_i D(i))) &\cong
  \Hom_\C(F(Y),\lim_i D(i)) \cong
  \lim_i \Hom_\C(F(Y), D(i)) \\
  & \cong
  \lim_i \Hom_\D(Y, G(D(i))) \cong
  \Hom_\D(Y, \lim_i G(D(i)))
\end{align*}
mit dem Yoneda-Lemma die Behauptung: $G(\lim_i D(i)) \cong \lim_i G(D(i))$.

Dieser Beweis hat aber noch zwei Lücken: Zum einen wurde die Existenz des
Limes~$\lim_i G(D(i))$ ohne Beweis verwendet, zum anderen wurde nur die
Isomorphie der Kegelspitzen nachgewiesen; das ist aber eine schwächere Aussage
als die eigentliche Behauptung der Limesbewahrung. Es gibt verschiedene
Möglichkeiten, die Lücken zu schließen, siehe etwa~\cite{gaillard,lin}; es ist
eine gute Übungsaufgabe, das auszuführen.
%Sei~$\lim_i D(i)$ Limes eines Diagramms~$D:\I\to\D$, zusammen mit den
%Projektionsmorphismen~$\pi_i : \lim_i D(i) \to D(i)$. Wir müssen nachweisen, dass
%der induzierte Kegel bestehend aus den Morphismen
%\[ G(\pi_i) : G(\lim_i D(i)) \longrightarrow G(D(i)) \]
%ein Limes ist. Sei dazu ein beliebiger Kegel~$K$ bestehend aus Morphismen
%\[ \mu_i : K \longrightarrow G(D(i)) \]
%gegeben. Dann induziert für jedes Objekt~$Y \in \D$ der Hom-Funktor einen Kegel
%\[ (\mu_i)_\star : \Hom_\D(Y,K) \longrightarrow \Hom_D(Y,G(D(i))). \]
%Das obige Argument zeigt zumindest, dass~$\Hom_\D(A,G(\lim_i D(i)))$ zusammen
%mit den induzierten Projektionsmorphismen ein Limes (in~$\Set$) ist.
\end{proof}


\subsection{Kriterien für die Existenz eines adjungierten Funktors}


\subsection{Weitere Aspekte}

Zu einem abgerundeten Verständnis von Adjunktionen gehören mindestens noch folgende
Aspekte:
\begin{itemize}
\item Eins und Koeins von Adjunktionen
\item Monaden aus Adjunktionen
% XXX
\end{itemize}
Diese können hier nicht behandelt werden, sind aber nachzulesen in XXX.


\endinput
\begin{exmp}
$\cC=Grp$, $\cD=Grp^2=Grp\times Grp$
\begin{align*}
F: & Grp^2\rightarrow Grp &\mbox{Produktfunktor}\\
  & (G_1,G_2) \mapsto G_1\times G_2\\
G: & Grp \rightarrow Grp^2 &\mbox{Diagonalfunktor}\\
  & G \mapsto (G,G)
\end{align*}
\paragraph{Beh:} $F\vdash G$
\[
\Hom_{Grp^2}((G,G),(H_1,H_2))\cong \Hom_{Grp}(G,H_1\times H_2)
\]
wobei
\begin{itemize}
\item $\Hom_{Grp^2}((G,G),(H_1,H_2))=\{\mbox{Gruppen-Homomorphismen}\}$
\item $ \Hom_{Grp}(G,H_1\times H_2) =\{G\rightarrow H_1\times H_2 \mbox{
Gruppen-Homomorphismen}\}$
\end{itemize}
\end{exmp}
\endinput

% XXX: Wie WÜRDE ein Rechtsadjungierter zu U : Vect --> Set aussehen?

% Aufgaben: http://people.mpim-bonn.mpg.de/carchedi/HW2.pdf 2(a)(b)
