\documentclass[12pt]{article}
%AMS-TeX packages
\usepackage{amssymb,amsmath,amsthm}
%geometry (sets margin) and other useful packages
\usepackage[margin=1.25in]{geometry}
\usepackage{graphicx,ctable,booktabs}
\usepackage[sort&compress,square,comma,authoryear]{natbib}
\bibliographystyle{plainnat}
%
%Redefining sections as problems
%
\makeatletter
\newenvironment{problem}{\@startsection
{section}
{1}
{-.2em}
{-3.5ex plus -1ex minus -.2ex}
{2.3ex plus .2ex}
{\pagebreak[3]%forces pagebreak when space is small; use \eject for better results
\large\bf\noindent{Problem }
}
}
{%\vspace{1ex}\begin{center} \rule{0.3\linewidth}{.3pt}\end{center}}
\begin{center}\large\bf \ldots\ldots\ldots\end{center}}
\makeatother
%
%Fancy-header package to modify header/page numbering
%
\usepackage{fancyhdr}
\pagestyle{fancy}
%\addtolength{\headwidth}{\marginparsep} %these change header-rule width
%\addtolength{\headwidth}{\marginparwidth}
\lhead{Problem \thesection}
\chead{}
\rhead{\thepage}
\lfoot{\small\scshape EECS 598: Category Theory}
\cfoot{}
\rfoot{\footnotesize PS 1}
\renewcommand{\headrulewidth}{.3pt}
\renewcommand{\footrulewidth}{.3pt}
\setlength\voffset{-0.25in}
\setlength\textheight{648pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%Contents of problem set
%
\begin{document}
\newcommand{\skipp}{\textrm{skip}}
\newcommand{\Set}{\textrm{Set}}
\newcommand{\Cat}{\textrm{Cat}}
\newcommand{\Cayley}{\textrm{Cayley}}
\newcommand{\Preds}{\mathcal{P}}
\newcommand{\triple}[3]{\{#1\}{#2}\{#3\}}
\newcommand{\Triple}{\textrm{Triple}}
\newcommand{\Analyse}{\textrm{Analyse}}
\newcommand{\command}{\textrm{command}}
\title{Problem Set 1}
\date{January 13, 2022}
\maketitle
Homework is due midnight before next Thursday's class. Starred
assignments will be presented in class. Turn in your homework on
Canvas. You may work alone or in groups of two. I highly encourage you
to write your solution in LaTeX. The LaTeX packages tikz and tikz-cd
are useful for typesetting commutative diagrams, and there are WYSIWYG
editors online that produce LaTeX code such as https://q.uiver.app/
and https://tikzcd.yichuanshen.de/ .
\thispagestyle{empty}
%Example problems
\begin{problem}{}
Give an example of a category not covered in class from an area of
mathematics or computer science that interests you.
Next, give an example of an interesting functor whose domain is your
category and another whose codomain is your category.
\end{problem}
\begin{problem}{(*) Cayley Representation}
In class, we defined the Cayley representation of a category to
show that all categories are subcategories of the category of sets
and functions.
This was defined as follows. Given a small category $C$ we can
define a functor $\Cayley : C \to \Set$ by
\begin{enumerate}
\item $\Cayley(A) = \{ (B, f) | B \in C_0, f \in C_1(B, A) \}$
\item $\Cayley(f : A \to B)(g) = f \circ g$
\end{enumerate}
Then we can define a category $\overline C$ whose objects are sets
of the form $\Cayley(A)$ for some $A$ and whose arrows are
functions of the form $\Cayley(f)$ for some $f$. This is a
subcategory of $\Set$ and is isomorphic as a category to
$C$.
Consider the following properties of functors and either (1) prove
the functor $\Cayley$ always satisfies the given property or
(2) give an counter-example: a category $C$ where $\Cayley$
does not satisfy the given property.
\begin{enumerate}
\item A functor $F: C \to D$ is \emph{faithful} if for every $A, B
\in C$, $F_1 : C_1(A,B) \to D_1(F_0 A, F_0 B)$ is injective.
Is $\Cayley$ always faithful?
\item A functor $F: C \to D$ is \emph{full} if for every $A, B \in
C$, $F_1 : C_1(A,B) \to C_1(F_0 A, F_0 B)$ is surjective.
Is $\Cayley$ always full?
\item A functor $F : C \to D$ is \emph{pseudomonic} if objects $A,
B$ are isomorphic in $C$ if and only if $F_0 A$ and $F_0 B$ are
isomorphic in $D$.
Is $\Cayley$ always pseudomonic?
\item A functor $F : C \to D$ is \emph{conservative} if a morphism
$f : A \to B$ is an isomorphism if and only if $F_1 f : F_0 A \to
F_0 B$ is an isomorphism in $D$.
Is $\Cayley$ always conservative?
\end{enumerate}
\end{problem}
\begin{problem}{(*) Hoare Logic as a Functor}
This problem is inspired by \citet{mz2015functors}.
We can consider any monoid to be a model of a sequential untyped
programming language, where we think of the elements of the monoid
as (sequences of) statements and the operation as sequencing. In
this case we would write the monoid operation as a semicolon: $m; n$
and the monoid identity as a ``no-op'' operation, which we write as
$\skipp$.
Define a \emph{Hoare logic} \citep{hoare69} (P, T) over a monoid $M$ as
\begin{enumerate}
\item A set $\Preds$ of ``assertions''
\item A relation $T \subseteq \Preds \times M \times \Preds$
of ``entailment''. To match Hoare's notation, we can write
$(P,s,Q) \in T$ as
\[\{P\} s \{Q\}\]
\item Satisfying the ``skip rule'': for every predicate $P \in
\Preds$:
\[ \triple{P}{\skipp}{P} \]
\item And satisfying the ``entailment rule'': if $\triple{P}{s}{Q}$
and $\triple{Q}{s'}{R}$ then
\[ \triple{P}{s;s'}{R} \]
\end{enumerate}
Show that Hoare logics over a monoid $M$ are ``essentially the same'' as
faithful functors with codomain $M$ (viewed as a one-object
category).
\begin{enumerate}
\item First, for any Hoare logic $(\Preds, T)$ over $M$ define a category
$\Triple(\Preds,T)$ with a faithful functor $\command :
\Triple(\Preds, T) \to M$.
\item Next, for any category $C$ and faithful functor $F : C \to M$,
define a Hoare logic $\Analyse(C,F)$ over $M$.
\item Define a category of Hoare logics as follows. The objects are
Hoare logics, and a morphism from $(\Preds, T)$ to $(\Preds', T')$
consists of
\begin{enumerate}
\item A function $\phi : \Preds \to \Preds'$
\item Such that if $\triple{P}s{Q}$ then $\triple{\phi(P)}s{\phi{Q}}$
\end{enumerate}
Composition is given by composition of the underlying functions,
and identity is the identity function.
Show that for any Hoare logic $(\Preds, T)$ over $M$,
$\Analyse(\Triple(\Preds, T), \command)$ is isomorphic to $(\Preds, T)$ in
this category of Hoare logics.
\item Show that for any category $C$ and faithful functor $F : C \to
M$, $\Triple(\Analyse(C, F), \command)$ is isomorphic to $(C, F)$
in the slice category $\Cat/M$.
\end{enumerate}
\end{problem}
\bibliography{cats}
\end{document}