AlgebrasNotes.tex

\documentclass[11pt]{amsart}          
\usepackage[a4paper,verbose]{geometry}
\geometry{top=3cm,bottom=3cm,left=3cm,right=3cm,textheight=595pt}
\setlength{\parskip}{0.3em}
% ==============================
% PACKAGES
% ==============================

\usepackage{amsfonts}
\usepackage{amssymb}  
\usepackage{amsthm} 
\usepackage{amsmath} 
\usepackage{caption}
\usepackage[inline]{enumitem}
\setlist{itemsep=0em, topsep=0em, parsep=0em}
\setlist[enumerate]{label=(\alph*)}
\usepackage{etoolbox}
\usepackage{stmaryrd} 
\usepackage[dvipsnames]{xcolor}
\usepackage[]{hyperref}
\hypersetup{
  colorlinks,
  linkcolor=blue,
  citecolor=blue,
  urlcolor=blue}
\usepackage{graphicx}
\graphicspath{{assets/}}
\usepackage{mathtools}

\usepackage{tikz-cd}
\usepackage{minted}
\usepackage{float}
\usetikzlibrary{
  matrix,
  arrows,
  shapes
}

\setcounter{tocdepth}{1} % Sets depth for table of contents. 

% ======================================
% MACROS
%
% Add your own macros below here
% ======================================

\newcommand{\rr}{{\mathbb{R}}}
\newcommand{\nn}{{\mathbb{N}}}
\newcommand{\iso}{\cong}
\newcommand{\too}{\longrightarrow}
\newcommand{\tto}{\rightrightarrows}
\newcommand{\To}[1]{\xrightarrow{#1}}
\newcommand{\Too}[1]{\To{\;\;#1\;\;}}
\newcommand{\from}{\leftarrow}
\newcommand{\From}[1]{\xleftarrow{#1}}
\newcommand{\Cat}[1]{\mathbf{#1}}
\newcommand{\cat}[1]{\mathcal{#1}}
\newtheorem*{remark}{Remark}
\renewcommand{\ss}{\subseteq}
\newcommand{\hask}[1]{\mintinline{Haskell}{#1}}
\newenvironment{haskell}
  {\VerbatimEnvironment
  	\begin{minted}[escapeinside=??, mathescape=true,frame=single, framesep=5pt, tabsize=1]{Haskell}}
  {\end{minted}}

% ======================================
% FRONT MATTER
% ======================================

\author{Bartosz Milewski}
\title{Random Notes}

\begin{document}

\section{Random things}
\subsection{Initial algebra structure map}
\[j \colon f (\mu f) \to \mu f\]
\[C\Big(f (\mu f), \int_b b^{C(f b, b)}\Big)\]
is a member of
\[\int_b C\Big(f (\mu f), b^{C(f b, b)}\Big)\]
Using the definition of the power
\[ C(x, a^s) \cong Set(s, C(x, a)) \]
we get
\[\int_b Set\Big(C(f b, b), C\big( f (\mu f), b\big) \Big)\]
Using Yoneda lemma we replace $b$ with $f (\mu f)$ (not really!)
\[C(f (f (\mu f)), f (\mu f)) \]

\subsection{Terminal coalgebra structure map}
\[k \colon \nu f \to f (\nu f)\]
is a member of
\[ C\Big( \int^a C(a, f a) \cdot a, f  (\nu f) \Big)\]
\[ \int_a C\Big( C(a, f a) \cdot a, f  (\nu f) \Big)\]
Using the definition of the copower
\[ C(s \cdot a, x) \cong Set(s, C(a, x))\]
we get
\[ \int_a Set\Big( C(a, f a), C\big( a, f  (\nu f) \big) \Big)\]
Yoneda lemma  (not really!)
\[ C(f(\nu f), f ( f (\nu f))) \]

\subsection{Kan extensions}
\[\mu f = \int_a a^{C(f a, a)}\]
\[\nu f = \int^a C(a, f a) \cdot a \]
These formulas are reminiscent of Kan extensions. 
For comparison, the right  Kan extension of $g$ along $f$ is given by
\[(Ran_f g) c = \int_a (g a)^{C(c, f a)}\]
The left Kan extension is
\[(Lan_f g) c = \int^a C(f a, c) \cdot g a \]
If $f$ has left and right adjoints, they are given by
\[Ran_f Id \dashv f \dashv Lan_f Id\]
In particular, using the adjunction
\[(Lan_f Id) c = \int^a C(a, (Lan_f Id) c) \cdot a\]
This shows that $(Lan_f Id) c$ is a fixed point of the functor
\[ \Phi(x) = \int^a C(a, x) \cdot a \]

\subsection{Ends as limits}

Twisted arrow category on $\textit{Tw}(\Cat C)$ has, as objects, morphisms in $\Cat C$ (or, strictly speaking, triples $(a, b, f \colon a \to b)$). A morphism from $f \colon a \to b$ to $g \colon a' \to b'$ is a pair of morphisms 
\[(h \colon a' \to a, h' \colon b \to b')\]
For every profunctor $p \colon C^{op} \times C \to \Cat{Set}$ define a functor $\bar p \colon \textit{Tw}(\Cat C) \to Set$. On objects
\[\bar p (a, b, f) = p a b\]
and on morphisms, it's just profunctor lifting.

It can be shown that the end is just a limit over the twisted arrow category
\[\int_c p c c \cong \lim_{Tw(C)} \bar p\]
Similarly, the coend is a colimit over $Tw(C^{op} )^{op}$
\[\int^c p c c \cong \underset {Tw(C^{op})^{op}}  { \mbox{colim}} \bar p\]

\subsection{Iterative solution}
Terminal coalgebra is a limit, and initial algebra is a colimit of these two chains
\begin{figure}[H]
\centering
\begin{tikzcd}
  f (\nu f)
  \\
  \nu f
  \arrow[u, "k"]
  \arrow[d, "\pi_1"]
  \arrow[dr, "\pi_{(f 1)}"]
  \arrow[drr, bend left, "\pi_{(f^2 1)}"]
  \\
  1
  & f 1
  \arrow[l, "\mbox{!`}"]
  & f^2 1
  \arrow[l, "f \mbox{!`}"]
  & ...
  \arrow[l, dashed]
   \\
  0
   \arrow[u, "!"]
  \arrow[r, "!"]
  \arrow[d, ""]
   \arrow[d, "\iota_0"]
   &f 0
   \arrow[u, "f !"]
   \arrow[r, "f !"]
   \arrow[dl, "\iota_{(f 0)}"]
   &f^2 0
   \arrow[u, "f^2 !"]
   \arrow[r, dashed]
   \arrow[dll, bend left, "\iota_{(f^2 0)}"]
   & ...
   \\
   \mu f
   \arrow[uuu, bend left, "\varphi"]
   \\ 
   f (\mu f)
   \arrow[u, "j"]
\end{tikzcd}
\end{figure}

\end{document}
\maketitle{}