%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\RequirePackage{fix-cm}%
\documentclass[automark,paper=a4,fontsize=12pt,twoside,%
%openright,% only use together with scrreprt
cleardoublepage=empty,headinclude,
listof=totoc,bibliography=totoc,index=totoc,BCOR13.0mm%
]{scrartcl}%{scrreprt}%{scrbook} % use for final version
%,draft]{scrartcl}%{scrreprt}%{scrbook} % use for draft version
%language and encoding related stuff
\usepackage[latin1]{inputenc}%
\usepackage[T1]{fontenc}%
\usepackage{lmodern,fixltx2e}%
\usepackage{etex}%
\usepackage[german, british]{babel} % the last language is active (change the active language with \selectlanguage{german})
\newif\ifforceblacklinks\forceblacklinksfalse
\newcommand{\Printversion}{\forceblacklinkstrue}
%\Printversion % uncomment this to get b/w links for better printing
%
\def\PublicationTitle{Dynamical Systems in Categories}%
\def\CorrespondingAuthor{Mike Behrisch}%
\def\AuthorsList{\mbox{\CorrespondingAuthor}\and%
\mbox{Sebastian Kerkhoff}\and%
\mbox{Reinhard Pöschel}\and%
\mbox{Friedrich Martin Schneider}\and
\mbox{Stefan Siegmund}}
\day=12%
\month=11%
\year=2013%
\def\TUDname{\foreignlanguage{german}{%
Tech\-ni\-sche Uni\-ver\-si\-t\"{a}t Dres\-den}}%
\def\InstitutALG{\foreignlanguage{german}{%
In\-sti\-tut f\"{u}r Al\-ge\-bra}}%
\def\InstitutANA{\foreignlanguage{german}{%
In\-sti\-tut f\"{u}r Ana\-ly\-sis}}%
\def\Postleitzahletc{\mbox{D-01062} Dres\-den, Germany}%
\def\PublicationTopic{Modelling dynamical systems in finite
product categories, relationship to coalgebras}%
\def\PublicationKeywords{Dynamical system,
theory of systems,
finite product category,
coalgebra}%
%
% Pakete
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{enumerate}
\usepackage{calc}
\usepackage{comment}
\usepackage[mathscr]{eucal}
\usepackage{dsfont}
\usepackage{graphicx} % for graphics from outside
\usepackage{scrpage2} % for headings and stuff
\usepackage{xspace}
% \usepackage[prefix,intoc]{nomencl} % Symbolverzeichnis (nomenclature)
% Quick guide ("file" is the prefix of your tex file!)
% 1) run (pdf)latex file.tex
% 2) run makeindex file.nlo -s nomencl.ist -o file.nls
% 3) run (pdf)latex file.tex
% \usepackage{makeidx} % Index
% Quick guide ("file" is the prefix of your tex file! "makeidx.sty" has to be in the search path, e.g. in the current directory.)
% 1) run (pdf)latex file.tex
% 2) run makeindex file.idx -s makeidx.sty -o file.ind
% 3) run (pdf)latex file.tex
% \usepackage{showidx} % Index auf dem Rand anzeigen
\usepackage{url} % urls als typewriter schreiben
% \url{http://www.tu-dresden.de}
% \usepackage{rotating}
\usepackage[arrow, matrix, curve]{xy}
\CompileMatrices%
% % \def\pgfsysdriver{pgfsys-dvipdfm.def} % using dvi?
% \usepackage{tikz}[2.10] % Für Graphiken
% \pgfrealjobname{monadic_coalgebras} % this has to match the file name without the extension, i.e. if your file is called "cLoNe.tex" it should be "cLoNe".
% other useful packages:
% http://en.wikibooks.org/wiki/LaTeX/Tables
% \usepackage{colortbl}
\usepackage{longtable}
% \usepackage{tabularx}
\usepackage{booktabs} % for professional looking tables
% \usepackage{subfig} % for subfigures
% \usepackage{wrapfig} % for in-text figures
% \usepackage{listings} % for source-codes
% \usepackage{etex} % overcoming some incapabilities of latex
%\usepackage{showkeys}
\usepackage{ifthen}
\usepackage{ifdraft}
\usepackage{xcolor}
\usepackage{tudcolors}
%\usepackage[obeyDraft,backgroundcolor=orange!30]{todonotes}
\usepackage[backgroundcolor=orange!30]{todonotes}
\newcommand{\insertref}[2][]{\todo[color=green!40, #1]{#2}}
\newcommand{\givedetails}[2][]{\todo[color=blue!50, #1]{#2}}
\newcommand{\makeremark}[2][]{\todo[color=blue!30, #1]{#2}}
\newcommand{\fixthis}[2][]{\todo[color=red!70, #1]{#2}}
\newcommand{\needsassumption}[2][]{\todo[color=magenta!70, #1]{#2}}
\newcommand{\note}[1]{\makeremark[inline]{#1}}
\newcommand{\continuehere}{\fixthis[inline]{Continue here!}}
% \usepackage{bbm}
\makeatletter
% no labels in the final version
\ifdraft{\usepackage{showkeys}}{\def\showkeyslabelformat{}}
\usepackage[strict]{changepage}%
\def\url@keystyle{%
\def\UrlFont{\footnotesize\ttfamily}
\def\UrlBreaks{\do\a\do\b\do\c\do\d\do\e\do\f\do\g\do\h\do\i%
\do\j\do\k\do\l\do\m\do\n\do\o\do\p\do\q\do\r\do\s\do\t\do\u\do\v\do\w%
\do\x\do\y\do\z\do\&\do\1\do\2\do\3\do\4\do\5\do\6\do\7\do\8\do\9\do\0
}
\def\do@url@hyp{\do\-}
}%
\DeclareUrlCommand\urlkey{\urlstyle{key}}%
\newlength{\lkeymargin}%
\renewcommand{\showkeyslabelformat}[1]{%
\checkoddpage%
\ifoddpage%
\setlength{\lkeymargin}{1in + \oddsidemargin - 2\marginparsep}%
\else%
\setlength{\lkeymargin}{1in + \evensidemargin - 2\marginparsep}%
\fi%
\bgroup%
\hbadness=10000%
\fbox{\parbox{\lkeymargin}{\normalfont\tiny\ttfamily\urlkey{#1}}}%
\egroup%
}%
\def\SK@@ref#1>#2\SK@{%
{\@inlabelfalse\leavevmode\vbox to\z@{%
\vss%
\SK@refcolor%
\rlap{\vrule\raise .76em%
\hbox{\normalfont\tiny\ttfamily#2}}}}%
}%
\makeatother
\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it}
\newcommand{\catlayout}[1]{\mathpzc{#1}} %customizable way to typeset categories
%\newcommand{\catlayout}[1]{\mathbbmss{#1}} %requires package bbm
\newcommand{\cat}{\ensuremath{\catlayout{C}}} %generic category symbol
\newcommand{\catd}{\ensuremath{\catlayout{D}}} %generic category symbol
\newcommand{\op}[1]{\ensuremath{{#1}^{\partial}}}
\newcommand{\catop}{\op{\cat}} %dual of generic category
\newcommand{\Set}{\ensuremath{\catlayout{Set}}} %sets
\newcommand{\Top}{\ensuremath{\catlayout{Top}}} %topological spaces
\newcommand{\Metric}{\ensuremath{\catlayout{Met}_0}} %metric spaces (cont. maps)
\newcommand{\Met}{\ensuremath{\catlayout{Met}}} %metrisable spaces
\newcommand{\Unif}{\ensuremath{\catlayout{Unif}}} %uniformisable spaces
\newcommand{\Uniform}{\ensuremath{\catlayout{Unif}\!_{0}}} %uniform spaces (cont. maps)
\newcommand{\cats}{\ensuremath{\catlayout{Cat}}}
\newcommand{\Mea}{\ensuremath{\catlayout{Measrbl}}}
\newcommand{\LComp}{\ensuremath{\catlayout{LComp}}} %topological spaces
\newcommand{\tpl}[1]{\ensuremath{\left\langle{#1}\right\rangle}} %tupling of morphisms
\newcommand{\mor}[3]{\ensuremath{{#1}\xrightarrow{{#2}}{#3}}} %morphism
\newcommand{\ladjoint}{\dashv}%
\newcommand{\condition}[2][\bgroup\cat\egroup]{%
\noindent{\tiny\textsl{%
Conditions on the involved category \m{#1}:} #2}}
\let\uglyphi\phi
\let\uglyepsilon\epsilon
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\phi}{\varphi}
\newcommand{\pHi}{\nu} % used to be \phi
\newcommand{\aLpha}{\varphi}% used to be \alpha
\newcommand{\bEta}{\psi}% used to be \beta
\newcommand{\tdelta}{\ensuremath{\tilde{\delta}}}
\newcommand{\teta}{\ensuremath{\tilde{\eta}}}
\newcommand{\vheta}{\ensuremath{\vartheta}}
%
\makeatletter
\let\stckrel\stackrel%
\newlength{\stckrel@movelen}%
\renewcommand{\stackrel}[3][\@empty]{%
\ifx\@empty#1
\stckrel{#2}{#3}%
\else%
\bgroup%
\setlength{\stckrel@movelen}{%
\widthof{$\displaystyle ^{#2}$} * \real{-0.5} + %
\widthof{$\displaystyle{}\mathrel{\mathop{#3}}{}$} * \real{0.5}%
}%
\mathrel{\hspace*{\stckrel@movelen}\stckrel{#2}{#3}}{}%
\egroup%
\fi%
}
\newcommand{\bydef}[2][\@empty]{\ensuremath{\stackrel[#1]{\text{{\tiny def
}} {#2}}{=}}}
\newcommand{\bynt}[2][\@empty]{\ensuremath{\stackrel[#1]{\text{\eqref{diag:trans-#2}}}{=}}}
\newcommand{\vs}[1][\@empty]{\ensuremath{\stackrel[#1]{\text{v.s.}}{=}}}
% only eta delta zeta epsilon vheta mu teta or tdelta are reasonable arguments
\makeatother
%
\newcommand{\hl}[1]{\underline{#1}} % highlight changes in calculations
\newcommand{\acceptoverfulbox}[1]{\hspace*{#1}}%
\newcommand{\ovflhbx}[1]{\hspace*{-#1}}% for neg hspace in formulae
\newcommand{\emPh}[1]{{#1}}%\emph{#1}} % emphasise only in results
%%%%%%%%%%%%%%%%%% general commands %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\subs}{\subseteq} % just an abbreviation
\newcommand{\apply}[1]{\ensuremath{\left( #1 \right)}} % automatically resizing brackets
\newcommand{\fapply}[1]{\ensuremath{\left[ #1 \right]}} % automatically resizing brackets
\newcommand{\gapply}[1]{\ensuremath{\left\langle #1 \right\rangle}}
\newcommand{\abs}[1]{\ensuremath{\left\lvert#1\right\rvert}}%
\newcommand{\defeq}{\mathrel{\mathop:}=} % define someting
\newcommand{\eqdef}{\mathrel{\mathopen={\mathclose:}}} % something be defined
\DeclareRobustCommand{\lset}[2]{\ensuremath{\left\{\left.#1\ \vphantom{#2}\right|\ #2\right\}}}
% the following is for compatibility only, it is identical to \lset
\DeclareRobustCommand{\rset}[2]{\ensuremath{\left\{\left.#1\ \vphantom{#2}\right|\ #2\right\}}}
\newcommand{\set}[1]{\ensuremath{\left\{ #1 \right\}}}
\newcommand{\function}[5]{\ensuremath{\begin{array}{cccc}
#1\colon & #2 & \longrightarrow & #3 \\
& #4 & \longmapsto & \displaystyle #5
\end{array}}}
\newcommand{\functionhead}[3]{\ensuremath{#1\colon #2 \to #3}}
% non-line-breaking dash
\newcommand{\nbd}[1]{{#1}\nobreakdash-\hspace{0pt}}
\newcommand{\nbdd}[1]{\nbd{\m{#1}}}%
\newcommand{\dash}{\nolinebreak\hspace{0pt}-\hspace{0pt}}
\def\alg{\Algebra}
\newcommand{\m}[1]{\mbox{$#1$}}
\newcommand{\powerset}[1]{\ensuremath{\mathfrak{P} \apply{#1}}}
\newcommand{\Algebra}[2][]{% first arg is optional set of Functions
%\Algebra{A} --> \mathbf{A}
%\Algebra[F]{A} --> \mathbf{A} = \gapply{A; F}
\ifthenelse{\equal{#1}{}}{% first argument not set
\ensuremath{\mathbf{#2}}
}{%
\ensuremath{\mathbf{#2} = \gapply{#2; #1}}
}
}
\newcommand{\ie}{i.e.\xspace}
\newcommand{\eg}{e.g.\xspace}
\newcommand{\cf}{cf.\xspace}
\newcommand{\wrt}{w.r.t.\xspace}
\newcommand{\vsup}{v.s.\xspace}
\newcommand{\vi}{v.i.\xspace}
\newcommand{\name}[1]{#1}%{\textsc{#1}}%
\newcommand{\EM}[1]{{\color{blue} #1}}
\newcommand{\topSp}[1]{\ensuremath{\boldsymbol{#1}}} % topological spaces
\newcommand{\bt}{\topSp{T}} % a few abbreviations
\newcommand{\bx}{\topSp{X}}
\newcommand{\by}{\topSp{Y}}
\newcommand{\meaSp}[1]{\ensuremath{\mathbb{#1}}} % measurable spaces
\newcommand{\measrSp}[1]{\ensuremath{\mathds{#1}}} % measure spaces
\newcommand{\dirac}[1]{\ensuremath{\delta_{#1}}} % dirac measure
\newcommand{\affextReals}{\overline{\R}_{\geq 0}}
\newcommand{\neigh}[2]{\ensuremath{\mathcal{U}_{#1}\apply{#2}}}
\newcommand{\continuous}[1]{\ensuremath{C\apply{#1}}} % continuous maps
\newcommand{\cont}[2]{\continuous{#1,#2}} % continuous maps
\newcommand{\cotop}[2]{\ensuremath{\kappa\apply{#1,#2}}} % compact-open topology
\newcommand{\comp}[1]{\ensuremath{K\apply{#1}}} % compact subsets
\newcommand{\cosb}[2]{\ensuremath{\fapply{#1,#2}}} % compact-open
% subbasic set
\newcommand{\ccbs}[3]{\ensuremath{\fapply{#1,#2,#3}}} % compact-convergence
% basic set
%
\newcommand{\myContact}[3]{% name, address, email
\medskip
\textbf{\textsf{#1}}
#2\par
\emph{E-mail address:} \url{#3}\par
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% Math Operators
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\DeclareMathOperator{\EndOp}{End}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Stab}{Stab}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\Sub}{Sub}
\DeclareMathOperator{\Id}{Id}
\DeclareMathOperator{\ari}{ar}
\DeclareMathOperator{\im}{Im}
\DeclareMathOperator{\pr}{pr}
\DeclareMathOperator{\interiorOp}{int}
\newcommand{\interior}[2][{\bx}]{\interiorOp_{#1}\apply{#2}}
\DeclareMathOperator{\topo}{top}
\DeclareMathOperator{\dom}{dom}
\DeclareMathOperator{\codom}{codom}
\newcommand{\excl}{\ensuremath{\mathord{!}}}%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% Theorems etc.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\numberwithin{equation}{section} % use chapter if using scrreprt
% use section if using scrartcl
\swapnumbers
\newtheorem{regelsatz}{NEVER\_USE\_THIS}[subsection] % a dummy thm-env. that is never actually used
% use "section" as optional argument if working with scrreprt
% use "subsection" as optional argument if working with scrartcl
\theoremstyle{definition}
\newtheorem{remark}[regelsatz]{Remark}
% \newtheorem{conjecture}[regelsatz]{Conjecture}
\theoremstyle{definition}
\newtheorem{example}[regelsatz]{Example}
% \newtheorem{notation}[regelsatz]{Notation}
\newtheorem{Defn}[regelsatz]{Definition}
\theoremstyle{plain}
\newtheorem{proposition}[regelsatz]{Proposition}
\newtheorem{lemma}[regelsatz]{Lemma}
\newtheorem{theorem}[regelsatz]{Theorem} % Am 18.8 eingefügt
\newtheorem{corollary}[regelsatz]{Corollary}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% Environment defintions
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\makeatletter
\renewenvironment{proof}[1][\proofname]{\par
\pushQED{\qed}%
\normalfont \topsep6\p@\@plus6\p@\relax
\trivlist
\item[\hskip\labelsep
\bfseries
#1\@addpunct{:}]\ignorespaces
}{%
\popQED\endtrivlist\@endpefalse
}
\makeatother
\newenvironment{definition}[1][]{%
\begingroup
\renewcommand{\qedsymbol}{$\Diamond$}%
\pushQED{\qed}%
\begin{Defn}[{#1}]
}{%
\popQED\end{Defn}\renewcommand{\qedsymbol}{\qed}\endgroup
}
\newcommand{\Diamondhere}{\qedhere}
% Links zum Klicken
\usepackage{ifpdf}
\ifpdf% pdfTEX is running in pdf mode
\usepackage[pdftex,breaklinks]{hyperref} % Für Links
\else% TEX or pdfTEX in dvi mode
\usepackage[breaklinks]{hyperref} % Für Links
\fi
%open page at chapter 3
\providecommand{\texorpdfstring}[2]{#1}% for later use with other classes
% that do not load hyperref
\hypersetup{
% bookmarks=true, % show bookmarks bar?
unicode=true, % non-Latin characters in Acrobat’s bookmarks
pdftoolbar=true, % show Acrobat’s toolbar?
pdfmenubar=true, % show Acrobat’s menu?
pdffitwindow=false, % window fit to page when opened
pdfstartview={FitH}, % fits the width of the page to the window
% pdfstartpage={15},
pdftitle={\PublicationTitle}, % title
pdfauthor={\CorrespondingAuthor\ et al.}, % author
pdfsubject={Preprint: \PublicationTopic}, % subject of the document
% pdfcreator={Mike Behrisch}, % creator of the document
% pdfproducer={Mike Behrisch}, % producer of the document
pdfkeywords={\PublicationKeywords}, % list of keywords
pdfnewwindow=true, % links in new window
pdfdisplaydoctitle=true, % display document title instead of file name in title bar
linktocpage=true, % im Inhaltsverzeichnis sind nur die Seitenzahlen links, nicht der Text
colorlinks=true, % false: boxed links; true: colored links
linkcolor=HKS36K100, % color of internal links
citecolor=HKS41K100, % color of links to bibliography
filecolor=HKS33K100, % color of file links
urlcolor=HKS44K100 % color of external links
}
\ifforceblacklinks%
\hypersetup{%
linkcolor=black, % color of internal links
citecolor=black, % color of links to bibliography
filecolor=black, % color of file links
urlcolor=black % color of external links
}%
\fi%
% Layout
%\hbadness=10000 % do not complain about underful \hboxes
% \mywarning{hbadness set to 10000}
\usepackage{algpreprint}
\pagestyle{scrheadings}
\setheadsepline{0.4pt}
\flushbottom % KOMA-Script!
% \raggedbottom specifies that the last line of a page should be positioned
% wherever it was calculated. This means that the position of this line can be
% different on each page, up to the height of one line?-in combination of the
% end of the page with titles, figures, tables or similar, even more. In
% double-sided documents this is usually undesirable. \flushbottom makes sure
% that the last line is always at the lower edge of the text block.
% Hyphenation
\hyphenation{more-over}
\hyphenation{More-over}
\hyphenation{prod-uct}
\hyphenation{prod-ucts}
\hyphenation{semi-group}
\hyphenation{semi-groups}
\hyphenation{semi-lat-tice}
\hyphenation{semi-lat-tices}
\hyphenation{iso-morph-ic} % last hyphen probably not recognised due to
% global settings
\hyphenation{non-au-ton-o-mous}
\hyphenation{im-pli-ca-tion}
\hyphenation{im-pli-ca-tions}
\hyphenation{def-in-ition}
\hyphenation{Def-in-ition}
\hyphenation{def-in-itions}
\hyphenation{Def-in-itions}
\hyphenation{com-mu-ta-tive}
\hyphenation{com-mu-ta-tiv-ity}
\hyphenation{top-ology}
\hyphenation{Top-ology}
\hyphenation{topo-logic-al}
\hyphenation{topo-logic-al-ly}
\hyphenation{top-olo-gies}
\hyphenation{Top-olo-gies}
\hyphenation{tau-tol-ogy}
\hyphenation{tau-tolo-gies}
\hyphenation{tauto-logic-al}
\hyphenation{tauto-logic-al-ly}
\hyphenation{tau-tolo-gous}
\hyphenation{as-so-cia-tive}
\hyphenation{as-so-cia-tiv-ity}
\hyphenation{equiva-lence}
\hyphenation{equiva-lences}
\hyphenation{equiva-lent}
\hyphenation{equiva-lent-ly}% (2!)
% Index and Nomenclature
%\makeindex
% \makenomenclature
\begin{document}
% notwendige Befehle:
%--------------------
\bgroup
\def\and{, }%
\Autor{\AuthorsList}
\Titel{\PublicationTitle}
\MathAlNummer{05} % Einstellen der Preprintnummer
\ifdraft{\AlsManuskriptGedruckt}{} % is automatically removed in the final
% version
%
%
% optionale Befehle:
%--------------------
\TUDfonts % falls TU-Schriften verwendet werden sollen,
% optionaler Befehl, Standard = Computer Modern
%\TitelFussnote{\foreignlanguage{german}{%
% Diese Arbeit wurde durch \ldots
% die Deutsche Forschungsgemeinschaft,
% Projektnr.\ PO~434/6-1,
% gefördert.}}%
%\TechnicalReport % ersetzt den Schriftzug "PREPRINT" durch
% "TECHNICAL REPORT"
% \Jahr{2009} % Jahr definieren. Default = Systemjahr, optionaler Befehl
% \Monat{Januar} % Monat definieren. Default = Systemmonat in deutscher Sprache, optionaler Befehl
% \SetzeVoffset{4mm} % zur Korrektur schlecht eingestellter Drucker, Werte lassen sich mit \Offsetmessung und einem Probeausdruck bestimmen
% \SetzeHoffset{1mm} % (bei A4-Papier und automatischem Broschürendruck keine Gewähr); Das Argument ist eine Länge
% \Offsetmessung % Dient zur Bestimmung der Offsets. Dabei wird NUR die Titelseite gedruckt.
%
%
\Deckblatt % sonst erscheint kein Deckblatt
\egroup
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% Titlepage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \frontmatter
%\pagenumbering{roman}
%\thispagestyle{empty}
\selectlanguage{british}
\title{\PublicationTitle}
\author{\CorrespondingAuthor%
\thanks{\TUDname, \InstitutALG}\and
Sebastian Kerkhoff\footnotemark[1]\and
Reinhard Pöschel\footnotemark[1]\and
Friedrich Martin Schneider\footnotemark[1]\and
Stefan Siegmund%
\thanks{\TUDname, \InstitutANA}}%
\date{\today}
\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% Abstract / Summary %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
In this article we establish a bridge between dynamical systems,
including topological and measurable dynamical systems as well as
continuous skew product flows and nonautonomous
dynamical systems; and coalgebras in categories having all finite products.
We introduce a straightforward unifying definition of
abstract dynamical system on finite product categories.
Furthermore, we prove that such systems are in a unique % aka one-to-one
correspondence with monadic algebras whose signature functor takes
products with the time space.
We substantiate that the categories of topological spaces, metrisable and
uniformisable spaces have exponential objects \wrt\ locally compact
\name{Hausdorff}, \nbdd{\sigma}compact or arbitrary time spaces as
exponents, respectively.
Exploiting the adjunction between taking products and exponential objects,
we demonstrate a one\dash{}to\dash{}one correspondence between monadic
algebras (given by dynamical systems) for the left\dash{}adjoint functor
and comonadic coalgebras for the other.
This, finally, provides a new, alternative perspective on dynamical
systems.
\bgroup
\let\thefootnote\relax%
\footnote{%
\noindent\emph{AMS Subject Classification} (2010):
% primary:
37B99, %
68Q65 % Computer science, Theory of computing,
% Abstract data types; algebraic specification
% secondary:
(37B55, % Dynamical systems and ergodic theory, Topological dynamics,
% Nonautonomous dynamical systems
37H05, % Dynamical systems and ergodic theory, Random dynamical systems,
% Foundations, general theory of cocycles, algebraic ergodic
% theory
08A02, % General algebraic systems, Algebraic structures,
% Relational systems, laws of composition
18B30, % Category theory; homological algebra, Special categories,
% Categories of topological spaces and continuous mappings
18C15, % Category theory; homological algebra, Categories and theories,
% Triples, algebras for a triple, homology and derived functors
% for triples
18D15% % Category theory; homological algebra, Categories with structure,
% Closed categories (closed monoidal and Cartesian closed
% categories, etc.)
).\par%
\noindent\emph{Key words and phrases:} \PublicationKeywords}%
\setcounter{footnote}{0}%
\egroup
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% Table of Contents %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\tableofcontents
%\ohead{\headmark}
%\addtocontents{toc}{\protect\enlargethispage{\baselineskip}}
%\input{remarksForCoauthors.tex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% Introduction %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%\pagenumbering{arabic}
%\setcounter{page}{1}
Dynamical behaviour of state based systems is a central research topic
common to both computer science and dynamical systems theory. The former
discipline studies such structures in a multitude of manifestations, \eg\
as infinite state transition systems
(\cite{MinskyFiniteInfiniteMachines,%
RabinDecidabilityMSOInfTrees,%
ThomasAutomataOnInfiniteObjects,%
ThomasAutomataTheoryOnInfiniteTransitionSystems,%
ThomasReachabilityOverInfiniteGraphs}),
Kripke structures
(\cite{KripkeSemanticalConsiderationsOnMondalLogic,%
BrowneClarkeGruembergFiniteKripkeStructuresPTL}),
Petri nets
(\cite{EsparzaDecidabilityOfModelCheckingForInfiniteStateConcSystems}),
event systems
(\cite{TornambeDiscreteEventSystemTheory,%
CassandrasLafortuneEventSystems}),
finite state machines, various kinds of automata
(\cite{KleeneAutomata,%
RabinScottSyntacticMonoid,%
SchutzenbergerSyntacticMonoid,%
McNaughtonStarFreeLanguages,%
DrosteKuichVoglerHandbookOfWeightedAutomata}),
Turing machines
(\cite{MinskyTuringMachines}), etc.,
the latter one devotes its main attention to the
understanding and the description of different facets, such as
long\dash{}time behaviour, of complex dynamical systems on topological,
metric, measurable or probability spaces
(see
\eg~\cite{Hedlund,Sell71TopDynODE,AkinGlasnerTopDyn,%
AkinHurleyKennedyTopDyn,ArnoldRandomDS}).
\par
A problem common to both fields is to describe the transition of
states, which may or may not be deterministic. For that
the two fields have developed specific concepts and methods. Dynamical
systems theory, for example, applies ideas from topology, functional
analysis, measure theory or differential equations. Computer
science exploits concepts from the theory of formal languages
or various modal and timed logics to describe dynamical behaviour.
\par
Already during the 1970ies the relationship between automata theory and
linear control systems has been studied
(\cite{ArbibManesMachinesExpository,ArbibManesMachinesInACat}) in category
theoretic language.
Later, Rutten in~\cite{RuttenUniversalCoalgebra} proposed the theory of
coalgebra, a branch of category theory already used for a uniform
treatment of different sorts of state based systems in programming
semantics, to investigate techniques and concepts of computer science, as
well as dynamical systems theory, in a common setting.
\par
In this paper we follow Rutten's suggestion and explore which types of
dynamical systems are suitable to be modelled as coalgebras in appropriate
categories. For those we give a detailed account of the
translation process, involving certain monadic algebras as an intermediate
step. Finally, we find out that our construction can be regarded as an
instance of a quite general category theoretic result on the relationship
of algebras and coalgebras. In the end the coalgebraic point of view
offers one free parameter: the signature. With only small modifications
dynamical behaviour containing observations or non\dash{}determinism can
be described. Making such variability available for the study of
classical dynamical systems constitutes one motivation for the origination
of this paper.
\par
The structure of the text is as follows: to ease readability for
researchers from the areas of dynamical systems and computer science, and
to keep the presentation of the material mostly self\dash{}contained, we
gather in Section~\ref{sect:notation} basic concepts from topology,
measure theory and category theory, as well as a number of variants of
dynamical systems appearing in the literature. In
Section~\ref{sect:dyn-sys-abstr-cat} we pursue a straightforward
modelling of these existing notions in so\dash{}called finite product
categories. In this context we observe a very general connection between
nonautonomous dynamical systems and dynamical systems on product spaces.
In Section~\ref{sect:dyn-sys-alg-coalg}, finally, we translate the coined
definitions into the language of coalgebra.
\par
In this respect we first exhibit a connection to monadic algebras \wrt\ an
endo\dash{}functor that takes products with a time space
(Subsections~\ref{subsect:monoids-to-monads}
and~\ref{subsect:abs-dyn-sys-to-mon-algs}). As a by\dash{}product we
recognise the notion of topological conjugacy as the natural category
theoretic concept of isomorphism between algebras. In a similar way other
category theoretic constructions can become meaningful for particular
cases of dynamical systems.
\par
Subsequently, we verify that for our main examples the mentioned
endo\dash{}functor fulfils a specific property, known as
left\dash{}adjointness. Based on this general assumption, we demonstrate
how to transform monadic algebras in a one\dash{}to\dash{}one fashion into
so\dash{}called comonadic coalgebras. Thereby we exhibit the particular
transformation of monadic algebras arising from dynamical systems into
coalgebras as a special case of a well\dash{}understood abstract result in
category theory: if \m{F}, \m{G} is a pair of endo\dash{}functors where
\m{F} is left\dash{} and \m{G} is right\dash{}adjoint, then monads for
\m{F} and comonads for \m{G}, as well as monadic \nbdd{F}algebras and
comonadic \nbdd{G}coalgebras, are in bijective correspondence (cf.\
Propositions~\ref{prop:Falg-Gcoalg},
\ref{prop:Gcoalg-Falg} and~\ref{prop:G->F--F->G--invers}).
\par
Due to the presence of adjointness, for the specific structures arising
from dynamical systems it makes no difference if they are considered as
algebras or as coalgebras. However, from the coalgebraic understanding of
transition systems in computer science, there are coalgebras known that
look quite similar to those stemming from our construction, yet which
may fail to satisfy the adjointness condition. Thus, they lack a
corresponding equivalent on the side of algebras, \ie\ a definition in the
standard sense of dynamical systems, but they still represent dynamical
behaviour. We pose it as a problem for future investigations to
further discover all benefits coming from the realm of coalgebra to \eg\
topological or symbolic dynamics.
\par
\paragraph{Acknowledgements:}
The authors would like to thank Horst Reichel, Maik Grö\-ger,
Jan Rutten, Milad Niqui and Luu Hoang Duc for critical comments and
helpful discussions on the topic.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%% Preliminaries and Notations %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminaries and Notation}\label{sect:notation}
In this part we will make the reader familiar with some notation and
conventions used throughout the following text.
We start with recalling standard concepts from topology and measure theory.
As our aim for later is to build a bridge from dynamical systems to
coalgebra, the further necessary prerequisites
are two\dash{}fold: first we will introduce fundamental concepts from
category theory needed for abstractly modelling dynamical systems and to
understand the translation process from the standard definition of
dynamical system %(as far as there is a coherent one%
%\todo{delete this expression?}%
%)
to the field of coalgebra.
Second, we present key definitions from the wide\dash{}spread theory of
dynamical systems to see which examples fall under the scope of the method
to be presented later on.
\par\smallskip
To summarise some basic notation, we write \m{\emptyset} for the
\emph{empty set}, and \m{\powerset{X}} for the \emph{powerset} of some set
\m{X}. Moreover, we use \m{X\subs Y} to express \emph{set inclusion}, as
opposed to \m{X\subset Y} for \emph{proper set inclusion}. If
\m{\functionhead{f}{X}{Y}} is a function from \m{X} to \m{Y} and
\m{U\subs X} and \m{V\subs Y} are subsets, we write \m{f\fapply{U}} for
the \emph{image} of \m{U} under \m{f} and
\m{f^{-1}\fapply{V}\defeq\lset{x\in X}{f(x)\in V}} for the
\emph{preimage} of \m{V} \wrt\ \m{f}. Furthermore, we use \m{\N}, \m{\Z}
and \m{\R} to denote the sets of \emph{natural numbers including zero},
\emph{integers} and \emph{reals}, respectively. For
\m{\mathbb{T}\in \set{\Z,\R}} we abbreviate by \m{\mathbb{T}_{\geq 0}} and
\m{\mathbb{T}_{\leq 0}} the respective non\dash{}negative and
non\dash{}positive numbers.
\par
\subsection{Preliminaries related to topology and measure theory}%
\label{subsect:topological-prelims}
Dynamical systems in topological spaces constitute an example of special
importance in the following section. We therefore begin by recollecting
some standard notions from topology. The more involved concepts occurring
thereafter will mainly be needed in
Subsection~\ref{subsect:exp-obj-for-TopLocComp}.
\par
As usual a \emph{topological space} is a pair
\m{\bx = \apply{X,\tau}} where \m{X} is a set and
\m{\tau\subs\powerset{X}} is a \emph{topology on \m{X}}, \ie\ a collection
of subsets of \m{X} that is closed under finite intersections and
arbitrary unions. The members of \m{\tau} are called \emph{open sets} of
\m{\bx}, the elements of \m{X} are often referred to as \emph{points}.
If \m{\tau=\powerset{X}}, \ie\ the largest possible topology on \m{X}, the
topology \m{\tau} and the space \m{\bx} are said to be \emph{discrete}.
Contrarily, the least topology on \m{X} is \m{\tau=\set{\emptyset,X}},
which is called \emph{indiscrete topology}.
A subcollection \m{\mathcal{U}\subs\powerset{X}} is called a \emph{base}
for the topology \m{\tau} if
\m{\tau = \lset{\bigcup\mathcal{V}}{\mathcal{V}\subs\mathcal{U}}}. A set
\m{\mathcal{V}\subs\powerset{X}} is a \emph{subbase} of \m{\tau} if
\m{\lset{\bigcap\mathcal{V}'}{%
\mathcal{V}'\subs\mathcal{V} \text{ finite}}}
is a base of \m{\tau}.
A topological space for whose topology there exists a countable base is
said to be \emph{second\dash{}countable} or \emph{completely separable}.
\par
For a subset \m{V\subs X} its \emph{interior}, denoted by
\m{\interior{V}}, is the largest open set contained in \m{V}, \ie\
\m{\interior{V}=\bigcup\lset{U\in\tau}{U\subs V}}.
\par
If \m{x\in X} is a point, then a subset \m{V\subs X} is called a
\emph{neighbourhood} of \m{x} if there is some open set \m{U\in\tau} such
that \m{x\in U\subs V}. A neighbourhood is said to be \emph{open} if it
belongs to \m{\tau} itself. The collection of all neighbourhoods of a
point \m{x\in X} is denoted by \m{\mathcal{U}_{x}\apply{\bx}}. A
subcollection \m{\mathcal{V}\subs\mathcal{U}_{x}\apply{\bx}} is called a
\emph{neighbourhood base at the point \m{x}} if for every
\m{U\in\mathcal{U}_{x}\apply{\bx}} there exists some \m{V\in\mathcal{V}}
such that \m{V\subs U}. Thus,
\m{\mathcal{V}\subs\mathcal{U}_{x}\apply{\bx}} is a neighbourhood base at
\m{x} if and only if
\m{\mathcal{U}_{x}\apply{\bx}
= \lset{U\subs X}{\exists V\in\mathcal{V}\colon V\subs U}}.
\par
For topological spaces \m{\bx=\apply{X,\tau}} and \m{\by=\apply{Y,\sigma}},
a map \m{\functionhead{f}{X}{Y}} is said to be \emph{continuous (\wrt\
\m{\bx} and \m{\by})}, or \emph{\nbdd{\tau}\nbdd{\sigma}continuous}, if
\m{f^{-1}\fapply{U}\in\tau} for any \m{U\in\sigma}. A map
\m{\functionhead{f}{X}{Y}} is said to be \emph{continuous at a point
\m{x\in X}} if \m{f^{-1}\fapply{U}\in \mathcal{U}_{x}\apply{\bx}} for any
\m{U\in\mathcal{U}_{f(x)}\apply{\by}}. Clearly, \m{\functionhead{f}{X}{Y}}
is continuous (\wrt\ \m{\bx} and \m{\by}) if and only if it is continuous
at any point \m{x\in X}.
We collect all \nbdd{\tau}\nbdd{\sigma}continuous functions
\m{\functionhead{f}{X}{Y}} in the set \m{\cont{\bx}{\by}}.
%We put
% \m{\cont{\bx}{\by} \defeq
% \lset{ f \in Y^{X}}{\text{\m{f} is
% \m{\tau}-\m{\sigma}-continuous}}}.
If \m{f\in \cont{\bx}{\by}} is bijective and its inverse is continuous,
too, then \m{f} is called a \emph{homeomorphism between \m{\bx} and
\m{\by}}.
\par
A topological space \m{\bx} is said to be \emph{Hausdorff} if any two
distinct points \m{x,y\in X}, \m{x\neq y}, can be separated by disjoint
(open) neighbourhoods, \ie\ if there exist
\m{U\in\mathcal{U}_{x}\apply{\bx}} and \m{V\in\mathcal{U}_{y}\apply{\bx}}
such that \m{U\cap V = \emptyset}.
A subset \m{K\subs X} is called \emph{compact} if for any
\m{\mathcal{U}\subs\tau} such that \m{K\subs \bigcup\mathcal{U}} there
exists a finite subset \m{\mathcal{U}'\subs\mathcal{U}} such that
\m{K\subs \bigcup\mathcal{U}'}. We denote the set of all compact
subsets of \m{\bx} by \m{\comp{\bx}}. The topological space \m{\bx} is
called \emph{compact} if \m{X\in \comp{\bx}}. Moreover, we call the
space \m{\bx} \emph{locally compact} if, for any point \m{x\in X}, it
possesses a neighbourhood base
\m{\mathcal{V}\subs\mathcal{U}_{x}\apply{\bx}} satisfying
\m{\mathcal{V}\subs \comp{\bx}}.
\par
A special case of locally compact spaces are \emph{\nbdd{\sigma}compact
spaces} introduced in the following definition.
\par
\begin{definition}\label{def:sigma-compact}
A topological space \m{\bx} is said to be \emph{\nbdd{\sigma}compact} if
it admits a \emph{countable exhaustion by compact subsets}.
That is, there exists a sequence
\m{\apply{K_n}_{n \in \N}} of subsets of \m{X} such that
\begin{enumerate}[(1)]
\item \m{K_n} is compact for each \m{n \in \N},
\item \m{K_n \subseteq \interior{K_{n+1}}} for each \m{n \in \N},
\item \m{X = \bigcup_{n \in \N} K_n}. \qedhere
\end{enumerate}
\end{definition}
\par
A \nbdd{\sigma}compact \name{Hausdorff} space is necessarily
locally compact. In fact, the following lemma holds (we refer
to~\cite[Satz~8.19(b), p.~111]{Boto-nicht-Bodo} for a proof):
%\todo[size=\small]{Try to find an English reference for this fact, \eg\ in
% Munkres, Steen \& Seebach or Willard}
\par
\begin{lemma}\label{lem:char-sigma-compact}
For every \name{Hausdorff} space \m{\bx} the following are equivalent:
%Let \m{\bx} be a topological space. The following are equivalent:
\begin{enumerate}[(i)]
\item \m{\bx} is \m{\sigma}-compact,
\item \m{\bx} is locally compact %Martin says, Hausdorff is not needed.
and there exists a sequence \m{\apply{K_{n}}_{n\in\N}} of
compact subsets of \m{X} such that \m{X = \bigcup_{n \in \N} K_n}.
\end{enumerate}
\end{lemma}
\begin{comment}
\begin{proof}
Certainly, \nbdd{\sigma}compactness as in
Definition~\ref{def:sigma-compact} implies the existence of a sequence
\m{\apply{K_{n}}_{n\in\N}\in\comp{\bx}^{\N}} whose union exhausts \m{X}.
Moreover, we need to show that \m{X} is locally compact. First of all,
\m{X} is weakly locally compact in the sense that every point \m{x\in X}
has a compact neighbourhood, namely \m{x\in K_n\subs\interior{K_{n+1}}}
for some \m{n\in\N}, \ie\ \m{K_{n+1}} is a compact neighbourhood of \m{x}.
This fact together with the \name{Hausdorff} property implies that \m{\bx}
is locally compact. Following the argument
of~\cite[Chapter~8]{Boto-nicht-Bodo} a weakly locally compact
\name{Hausdorff} space is regular\footnote{This needs the
\name{Hausdorff} assumption.} (Satz~8.15, p.~109), \ie\ it has a
neighbourhood base consisting of all closed neighbourhoods of a point.
Intersecting this neighbourhood base with a compact neighbourhood of a
point, yields a neighbourhood base of that point, which consists of
compact sets. Hence, every point has a neighbourhood base of compact sets,
thus \m{\bx} is locally compact.
\par
Moreover, every locally compact \name{Hausdorff} space clearly is a weakly
locally compact \name{Hausdorff} space. Adding the assumption that \m{X}
can be written as a countable union of compact sets, we have gathered all
conditions from Satz~8.19(b) in~\cite{Boto-nicht-Bodo}. The latter states
that \m{X} has a countable exhaustion with open sets, having compact
closure, being contained in the subsequent set of the sequence. The
sequence of closures of these open sets fulfils the conditions in
Definition~\ref{def:sigma-compact}, and we are done.
\end{proof}
\end{comment}
\par
One of the main constructions concerning topological spaces that we will
use later is that of \emph{product spaces}. If \m{I} is an index set and
for each \m{i\in I} the pair \m{\bx_i = \apply{X_i,\tau_i}} is a
topological space, then we may define a topology \m{\tau} on the Cartesian
product \m{X\defeq \prod_{i\in I} X_i} by the subbase \m{\bigcup_{i\in
I}\lset{\hat{U_i}}{U_i\in \tau_i}}. Here
\m{\hat{U_i}}\label{page:cylinder-sets} stands for the
product \m{\prod_{j\in I}V_j} where \m{V_j = U_i} if \m{j=i} and
\m{V_j = X_j}, otherwise.
In this way \m{\tau} is the least topology on \m{X} such that all
coordinate projections \m{\functionhead{p_i}{X}{X_i}}, \m{i\in I}, defined
by \m{p_i\apply{\apply{x_j}_{j\in I}} \defeq x_i} are continuous. We write
\m{\prod_{i\in I} \bx_i} for the pair \m{\apply{X,\tau}} and call it
\emph{product space} of \m{\apply{\bx_i}_{i\in I}}.
We mention that for \m{I=\emptyset} the resulting space is the indiscrete
space on the one\dash{}element set.
\par\smallskip
Moreover, in the following we need spaces with a richer structure than
just a topology, namely metric and uniform spaces. A \emph{metric space},
as usual, is a pair \m{\apply{X, d}} where \m{X} is a set and
\m{\functionhead{d}{X^2}{\R_{\geq 0}}} is a \emph{metric}, \ie\ a map
satisfying \m{d(x,y) = d(y,x)}, \m{d(x,y)= 0} exactly if \m{x=y}, and
\m{d(x,z)\leq d(x,y)+d(y,z)}, each requirement for all \m{x,y,z\in X}.
With every metric space we can associate an underlying topological space
\m{\apply{X,\tau}} given by the base \m{\lset{U(x,\epsilon)}{x\in X,
\epsilon\in\R_{> 0}}} where \m{U(x,\epsilon)
\defeq \lset{y\in X}{d(x,y)<\epsilon}} denotes the \emph{open ball} around
\m{x\in X} with radius \m{\epsilon >0}.
Topological spaces arising in this way are called \emph{metrisable}.
\par
A slight generalisation of metric spaces are \emph{uniform spaces}.
\par
\begin{definition}\label{def:uniform-space}
A \emph{uniform space} \m{(X,\Theta)} is a set \m{X} equipped with a
non-empty family \m{\Theta} of subsets of the Cartesian product \m{X
\times X} (\m{\Theta} is called the \emph{uniform structure} or
\emph{uniformity} of \m{X} and its elements \emph{entourages}) that
satisfies the following axioms:
\begin{enumerate}[(1)]
\item\label{item:reflexivity}
Every entourage \m{U\in\Theta} is \emph{reflexive}, \ie\
\m{U\supseteq\lset{(x,x)}{x\in X}}.
\item\label{item:upwards-closed}
\m{\Theta} is \emph{upwards closed}, \ie\ if \m{U\in\Theta} and
\m{U\subs V\subs X\times X}, then also \m{V\in\Theta}.
\item \m{\Theta} is \emph{closed \wrt\ finite intersections}, \ie\
\m{U,V\in\Theta} always implies \m{U\cap V\in\Theta}.
\item\label{item:triangle-inequality}
If \m{U\in\Theta}, then there exists \m{V\in\Theta} such that%
\footnote{It follows from reflexivity of \m{V} (see
condition~\eqref{item:reflexivity}) that \m{V\subs U}.},
whenever \m{(x,y), (y,z)\in V}, then \m{(x,z)\in U}.%
\footnote{%
Condition~\eqref{item:triangle-inequality} may also be rewritten
as follows: for every \m{U\in \Theta} there is some \m{V\in\Theta}
such that \m{V\subs V\circ V\subs U}, where
\m{V\circ V = \lset{\apply{x,z}\in X\times X}{%
\exists y\in X\colon \apply{x,y},\apply{y,z}\in V}}
denotes the binary relational product of \m{V} with itself.
}%
\item \m{\Theta} is \emph{closed under inverses (transposes)}:
for every \m{U\in\Theta}, always the \emph{inverse entourage}
\m{U^{-1} = \lset{(y,x)}{(x, y) \in U}} is a member of \m{\Theta},
as well.
\end{enumerate}
For \m{x \in X} and \m{U \in \Theta}, we write \m{U[x]} to indicate
\m{\rset{y\in X}{ (x,y) \in U}}.
\end{definition}
\par
Every uniform space \m{\apply{X,\Theta}} gives rise to a topological
space on \m{X}, by defining a subset \m{U \subseteq X} to be open if and
only if for every \m{x \in U} there exists an entourage \m{V\in\Theta}
such that \m{V[x] \subseteq U}.\label{page:top-of-uniform-space}
\par
In this topology, the neighbourhood filter of a point \m{x} is
\m{\rset{V[x]}{ V \in \Theta}}.
The topology defined by a uniform structure is said to be
\emph{generated by the uniformity}.
Topological spaces whose topology is induced by a uniformity are said to
be \emph{uniformisable}.
\par\medskip
Another important class of structures are \emph{measurable spaces}, \ie\
pairs \m{\apply{X,\Sigma}} where \m{X} is a set and \m{\Sigma} is a
\emph{\nbdd{\sigma}algebra} on \m{X}, which is a non\dash{}empty
collection \m{\Sigma\subs\powerset{X}} being closed \wrt\ countable unions
and intersections, and complementation. Clearly, arbitrary intersections
of \nbdd{\sigma}algebras on \m{X} form again a \nbdd{\sigma}algebra
wherefore there always exists a least \nbdd{\sigma}algebra on \m{X}
containing a given collection of subsets \m{\mathcal{U}\subs\powerset{X}},
said to be \emph{generated by} \m{\mathcal{U}}. Especially,
\m{\mathcal{U}=\emptyset} generates the least possible
\nbdd{\sigma}algebra on \m{X}, namely \m{\set{\emptyset, X}}.
\par
A map \m{\functionhead{f}{X}{Y}} between the carrier sets of two
measurable spaces \m{\meaSp{X} = \apply{X,\Sigma}} and
\m{\meaSp{Y} = \apply{Y,\Omega}} is said to be \emph{measurable} if
we have \m{f^{-1}\fapply{U}\in\Sigma} for all \m{U\in\Omega}.
\par
If \m{\bx=\apply{X,\tau}} is a topological space, then the
\nbdd{\sigma}algebra generated by the topology \m{\tau} is called
\emph{\name{Borel} \nbdd{\sigma}algebra} belonging to \m{\bx}.
\par
Furthermore, as for topological spaces we need to deal with products of
measurable spaces \m{\meaSp{X}_i = \apply{X_i,\Sigma_i}}, \m{i\in I}. We
simply put
\m{\prod_{i\in I} \meaSp{X}_i \defeq \apply{\prod_{i\in I}X_i, \Sigma}}
where \m{\Sigma} is generated by the collection
\m{\bigcup_{i\in I}\lset{\hat{U}_i}{U_i \in \Sigma_i}} and the sets
\m{\hat{U}_i} are defined analogously as for products of topological
spaces (\cf\ page~\pageref{page:cylinder-sets}).
We call \m{\Sigma} \emph{product \nbdd{\sigma}algebra} and
\m{\prod_{i\in I}\meaSp{X}_i} \emph{product space} of
\m{\apply{\meaSp{X}_{i}}_{i\in I}}. The definition above ensures that all
projection maps \m{\functionhead{p_i}{\prod_{j\in I}X_{j}}{X_i}},
\m{i\in I}, are indeed measurable.
\par\smallskip
Measurable spaces \m{\apply{X,\Sigma}} form the basis to define
\emph{measures}, which are mappings
\m{\functionhead{\mu}{\Sigma}{\affextReals}} into the set
\m{\affextReals=\fapply{0, \infty}} of \emph{affinely extended}
non\dash{}negative real numbers satisfying \m{\mu\apply{\emptyset}=0} and
the axiom of \emph{\nbdd{\sigma}additivity}: for every countable sequence
\m{\apply{U_i}_{i\in I} \in \Sigma^{\N}} of pairwise disjoint measurable
sets, one requires the equality
\m{\mu\apply{\bigcup_{i\in \N}U_i} = \sum_{i\in\N}\mu\apply{U_i}} to hold.
A triple \m{\apply{X, \Sigma, \mu}} such that \m{\apply{X, \Sigma}} is a
measurable space and \m{\mu} is a measure on \m{\apply{X, \Sigma}}
constitutes a \emph{measure space}. If \m{\mu\apply{X}=1}, the map \m{\mu}
is called a \emph{probability measure} and \m{\apply{X, \Sigma, \mu}} a
\emph{probability space}.
\par
Particularly simple examples of (probability) measures are so\dash{}called
\emph{\name{Dirac} measures}: for a given element \m{x\in X} the
\emph{\name{Dirac} measure \m{\dirac{x}} centred in \m{x}} maps a
measurable set \m{U\in\Sigma} to \m{1} if \m{x\in U} and to \m{0},
otherwise.
\par
If \m{\apply{X,\Sigma}} and \m{\apply{Y,\Omega}} are measurable spaces and
\m{\functionhead{f}{\apply{X,\Sigma}}{\apply{Y,\Omega}}} is a measurable
map between them, then every measure \m{\mu} on \m{\apply{X,\Sigma}}
induces one on \m{\apply{Y,\Omega}}, the \emph{push\dash{}forward measure}
\m{\mu\circ f^{-1}}. By definition it satisfies
\m{\apply{\mu\circ f^{-1}}\apply{V}\defeq \mu\apply{f^{-1}\fapply{V}}} for
every \m{V\in\Omega}. For measure spaces \m{\apply{X, \Sigma, \mu}} and
\m{\apply{Y, \Omega, \nu}} a measurable map
\m{\functionhead{f}{\apply{X,\Sigma}}{\apply{Y,\Omega}}} is called
\emph{measure preserving}\label{page:measure-preserving-map} if
\m{\nu = \mu\circ f^{-1}}.
\par
\subsection{Basic notions from category theory}\label{subsect:category-prelims}
Driven by the wish to keep the presentation of the material as
self\dash{}contained as possible, we outline here a collection of
fundamental concepts from category theory, always with a view on
applications to dynamical systems. Of course, this cannot replace a look
in a standard introductory monograph on category theory such
as~\cite{cats} or~\cite{AwodeyCategoryTheory}. In the following we will
cover concepts such as category, monomorphism, epimorphism,
isomorphism, terminal object, product, functor, natural transformation,
natural equivalence, adjunction, monads, comonads.
\par\smallskip
A category can be seen as an abstraction of a number of different things.
The most intuitive for our purposes is the one coming from sets (as
objects), together with functions between them (as morphisms) and
composition of functions (as composition).
\par
\begin{definition}\label{def:cat}
A category is given by a class \m{\cat} of \emph{objects} together with a
class of \emph{morphisms} (or \emph{arrows}, or \emph{maps}) and a notion
of \emph{composition} between morphisms satisfying the following axioms:
\begin{enumerate}[(1)]
\item Every morphism \m{f} belonging to \m{\cat} is uniquely associated
with two objects from \m{\cat}, representing a unique starting point
\m{\dom(f)} and an end point \m{\codom(f)}. Denoting \m{\dom(f)} by
\m{A} and \m{\codom(f)} by \m{B}, then \m{f} is often written as
\m{\mor{A}{f}{B}}. It is part of the definition that for any two
objects \m{A, B} in \m{\cat}, the collection of morphisms \m{f}
satisfying \m{\dom(f)=A} and \m{\codom(f)=B} forms a set as opposed
to a proper class. This set is usually written as
\m{\cat\apply{A,B}} or \m{\Hom\apply{A,B}}.
\item Every object \m{A} in \m{\cat} is associated with a distinguished
\emph{identity morphism} \m{\mor{A}{1_A}{A}}.
\item Whenever \m{A,B,C} are objects of \m{\cat} and \m{\mor{A}{f}{B}} and
\m{\mor{B}{g}{C}} are morphisms, then there is a unique morphism
\m{\mor{A}{h}{C}}, called \emph{composition of \m{f} and \m{g}}. We
will denote the composite \m{h} just by juxtaposition of both
factors, \ie\ \m{\mor{A}{h}{C} =\mor{A}{fg}{C}}.
\item The composition rule has to obey two laws: for all objects
\m{A, B, C, D} in \m{\cat} and morphisms \m{\mor{A}{f}{B}},
\m{\mor{B}{g}{C}} and \m{\mor{C}{h}{D}}, we have
\begin{align}
\mor{A}{\apply{fg}h}{D} &= \mor{A}{f\apply{gh}}{D}
\tag{\text{associativity}}\\
\mor{A}{f1_B}{B} &= \mor{A}{f}{B} \tag{\text{right neutrality}}\\
\mor{A}{1_Af}{B} &= \mor{A}{f}{B} \tag{\text{left neutrality}}
\mbox{\qedhere}
\end{align}
\end{enumerate}
\end{definition}
The definition of category enables a strong duality principle that allows
to transform many concepts or statements into dual ones:
\par
\begin{remark}\label{rem:opp-cat}
From every category \m{\cat} one can naturally derive the so\dash{}called
\emph{opposite category \m{\catop}} by reversing the direction of
morphisms and swapping the order of composition. By definition, the object
class of \m{\catop} coincides with that of \m{\cat}, and so does the class
of all morphisms. However, the role of domain and codomain is swapped: if
\m{A} and \m{B} are objects of \m{\cat} and \m{\mor{A}{f}{B}} is a
morphism in \m{\cat}, then (and only then) \m{\mor{B}{f}{A}} is a morphism
in \m{\catop}. This is to say more precisely, that
\m{\op{\dom}(f)\defeq \codom(f)} and \m{\op{\codom}(f)\defeq \dom(f)} for
any morphism of \m{\cat}, \ie\ \m{\catop\apply{A,B}\defeq\cat\apply{B,A}}
for all objects \m{A} and \m{B} of \m{\cat}. The identical morphisms
\m{1_A} for \m{A} in \m{\cat} remain the distinguished identical morphisms
of \m{\catop}. Yet, the composition operation of \m{\catop} now needs to
swap factors, in order to be well\dash{}defined: whenever \m{A}, \m{B} and
\m{C} are objects of \m{\cat} and \m{\mor{A}{f}{B}} and \m{\mor{B}{g}{C}}
are morphisms in \m{\catop}, then, according to the definition,
\m{\mor{C}{g}{B}} and \m{\mor{B}{f}{A}} are morphisms of \m{\cat}, such
that \m{\mor{C}{gf}{A}} is again a morphism of \m{\cat}. Therefore,
\m{\mor{A}{gf}{C}} is a morphism of \m{\catop}, and this is the one that
one defines as the composition of \m{f} with \m{g} in \m{\catop}. If one
would not use juxtaposition for the product of morphisms and write more
exactly \m{g\ast_{\cat}f} and \m{f\ast_{\catop} g} for the composition in
\m{\cat} and \m{\catop}, respectively, then the previous definition can
simply be given by \m{f\ast_{\catop}g\defeq g\ast_{\cat}f}. It is
straightforward to verify that \m{\catop} defined in this way yields
again a category.\par
Thereby, now any statement or concept that is purely written in the axioms
of category theory, can be transformed into a dual one. Namely, one
instantiates the definition or statement in \m{\catop} and reinterprets
the meaning in \m{\cat}. Dual definitions arising in this way often
receive the prefix \emph{co} in their names, \eg\ \emph{product} and
\emph{coproduct}, \emph{algebra} and \emph{coalgebra} etc.
\end{remark}
\par
To create some intuition for categories, we present a few examples. The
conditions from Definition~\ref{def:cat} are verified without any
difficulties.
\begin{example}\phantomsection{}\label{ex:cats}%needed to have correct
% % hyperlinking
\begin{enumerate}[(a)]
\item\label{item:Set}
The category \m{\Set} consists of all sets (as objects),
functions as morphisms, ordinary composition of functions, and
identical maps as identity morphisms.
\item\label{item:Top}
Taking all topological spaces as objects, all continuous
maps\footnote{To mention a technical fact, one cannot use just
functions. In order to have a unique domain and codomain associated
with each morphism, it is formally necessary to use triples
\m{\apply{A,f,B}} consisting of the continuous function and the two
topological spaces \m{A} and \m{B} specifying the topologies \wrt\
which \m{f} is continuous.
This kind of formalisation is tacitly assumed in all our examples
without explicitly mentioning it.}
between them, together with ordinary composition of functions and
identical functions, then this structure forms the category \m{\Top}
of topological spaces.
\item\label{item:Mea}
Similarly, all measurable spaces with measurable maps, standard
composition and identity maps form a category \m{\Mea}, namely that
of measurable spaces.
\item\label{item:Met-LComp-Unif}
Instead of topological spaces one may also take just all
metric spaces as objects, and continuous maps between them.
That is, besides changing the class of objects, we keep everything
as it is defined in \m{\Top}. In this way the category \m{\Metric} of
metric spaces with continuous maps is obtained. If we
forget the information about the metric, and view each of
these spaces just as a topological space, we get the
category \m{\Met} of metrisable spaces (with continuous
mappings).
\par
Similarly, one can restrict the structure of \m{\Top} to
all locally compact Hausdorff spaces, yielding the category
\m{\LComp}.
\par
Another popular example which is interesting for studying dynamics
are uniform spaces, that, together with continuous
maps\footnote{One would have a choice for uniformly continuous maps
here, too, yielding a different category.}, form the category
\m{\Uniform}. As with metric
spaces, we may also look at the underlying topological spaces of
these, which yields the category \m{\Unif} of uniformisable
topological spaces.
\end{enumerate}
\end{example}
\par
The idea used in the last mentioned example is part of a general scheme:
\begin{definition}\label{def:subcat}
A category \m{\catd} is a \emph{subcategory} of a category
\m{\cat}, if the objects and morphisms of \m{\catd} form
subclasses of those of \m{\cat} and the composition rule and identical
morphisms of \m{\catd} are given by restriction of the respective
concepts from \m{\cat}.\par
If for all \m{A,B} from \m{\catd} we have
\m{\catd\apply{A,B}=\cat\apply{A,B}}, then \m{\catd} is
called a \emph{full subcategory} of \m{\cat}.
\end{definition}
\par
Clearly, full subcategories are uniquely given their class of objects, as
seen \eg\ in the case of locally compact Hausdorff spaces in relation to
\m{\Top}. A second example of full subcategories are those of metrisable
spaces \m{\Met} or uniformisable spaces \m{\Unif} in \m{\Top}.
\par
\smallskip
One advantage of category theory is that it allows to formally speak about
aspects that are ``almost the same'' or ``very similar'' in very different
settings. With its abstract view, category theory does not only provide a
language for these kinds of observations, it also enables an axiomatic
treatment of certain properties, and to transport knowledge between
different fields. Examples for this are the following notions:
\par
\begin{definition}\label{def:mono-epi-iso}
Let \m{\cat} be a category, \m{A,B} objects in \m{\cat} and
\m{\mor{A}{f}{B}} a morphism from \m{A} to \m{B}.
\begin{enumerate}[(1)]
\item \m{f} is called \emph{monic} or a \emph{monomorphism} if for all
objects \m{C} of \m{\cat} and morphisms \m{\mor{C}{g}{A}},
\m{\mor{C}{h}{A}}, the equality \m{gf=hf} implies \m{g=h}.
\item Dually, \m{f} is called \emph{epi} or an \emph{epimorphism} if for
all objects \m{C} of \m{\cat} and morphisms \m{\mor{B}{g}{C}},
\m{\mor{B}{h}{C}}, the equality \m{fg=fh} implies \m{g=h}.
\item \m{f} is an \emph{isomorphism} if there exists a morphism
\m{\mor{B}{f'}{A}} such that \m{ff'=1_A} and \m{f'f=1_B}.
\qedhere
\end{enumerate}
\end{definition}
\par
Shortly speaking, monomorphisms are those morphisms which can be cancelled
from the right, and epimorphisms are those which can be cancelled from the
left \wrt\ composition. We remark that monomorphisms and epimorphisms
form an instance of the duality principle described in
Remark~\ref{rem:opp-cat}: epimorphisms in a category \m{\cat} are
precisely those morphisms that are monomorphisms in \m{\catop}, and vice
versa, of course. It is for historic reasons and for their fundamental
role, that they are not just called \emph{co\dash{}monomorphisms}.
Isomorphisms are those morphisms having an ``inverse'' morphism (which is
necessarily unique).
\par
Let us now see, what is encoded in these notions in concrete examples. In
the category of sets, monomorphisms are exactly the injective maps, and
epimorphisms are the surjective ones. An isomorphism in \m{\Set} is of
course nothing but a bijection, thus an epimorphism and a monomorphism.
This is a fact that only generalises in that every isomorphism must be
monic and epi, but not conversely. For instance, in the category of
topological spaces, the identical map \m{1_X} from a set \m{X} equipped
with the discrete topology to \m{X} equipped with the indiscrete topology
is an isomorphism precisely if \m{X} has at most one element. This is so
because the inverse map, which is again the identical mapping, fails to be
continuous for \m{\abs{X}>1}. Nevertheless, the mentioned map is both epi
and monic.
\par
It is easy to see that the isomorphisms in \m{\Top} are exactly the
homeomorphisms. Moreover, using the discrete topology on the
two\dash{}element topological space, one can show that monomorphisms in
\m{\Top} are exactly those continuous maps, that are injective (as maps
in \m{\Set}). Analogously, with the help of the indiscrete
two\dash{}element topological space, one can prove that epimorphisms in
\m{\Top} are precisely those continuous maps having underlying surjective
functions. \par
With almost the same arguments, it can be seen that for the
category \m{\Mea} of measurable spaces with measurable maps, epimorphisms
and monomorphisms are exactly the measurable maps being surjective, and
injective, respectively. Isomorphisms are such bijective maps where images
and preimages of measurable sets are measurable.
\par
Characteristic properties that occur in a very similar fashion in
different places are not limited to morphisms. They may also be found
\wrt\ to objects, or objects and morphisms. Examples for this are terminal
objects or products which are presented next.
\par
\begin{definition}\label{def:terminal-obj}
An object \m{I} in a category \m{\cat} is said to be \emph{terminal} if
for every other object \m{X} of \m{\cat} there exists \emph{exactly} one
morphism from \m{X} to \m{I}. Assuming that the terminal object is fixed,
we denote this unique morphism here by
\m{\mor{X}{\excl_X}{I}}.
\end{definition}
\par
It easily follows from the definition that terminal objects, if they
exist, are uniquely determined up to isomorphism. Therefore, one usually
picks a canonical representative and speaks about \emph{the} terminal
object of a category \m{\cat}. This also motivates why we have suppressed
the terminal object in the notation for the unique morphisms into terminal
objects.
\par
Again, it is good to have some examples for terminal objects. In \m{\Set}
every one\dash{}element set is a terminal object, in \m{\Top} the
one\dash{}element topological space with the indiscrete topology is
terminal, and in \m{\Mea} the one\dash{}element measurable space with the
\nbd{\m{\sigma}}algebra consisting of the full and the empty set is terminal.
\par
It turns out that terminal objects can also be seen as products with no
factors. The corresponding definition of a product is as follows.
\begin{definition}\label{def:prod}
Let \m{\cat} be a category and \m{\apply{X_i}_{i\in I}} be a
set\dash{}indexed family of objects from \m{\cat}. An object \m{P} of
\m{\cat} together with a family of morphisms
\m{\apply{\mor{P}{p_i}{X_i}}_{i\in I}} is called a \emph{product} of
\m{\apply{X_i}_{i\in I}} if for any (other) object \m{Q} of \m{\cat}
together with morphisms \m{\apply{\mor{Q}{q_i}{X_i}}_{i\in I}} there
exists \emph{exactly} one morphism \m{\mor{Q}{h}{P}} such that
\m{q_i = h p_i} holds for all \m{i\in I}. This unique morphism \m{h} is
called \m{tupling} of the morphisms \m{\apply{q_i}_{i\in I}} and,
considering the product as fixed, denoted here by \m{\tpl{q_i}_{i\in I}}.
The members of the family \m{\apply{\mor{P}{p_i}{X_i}}_{i\in I}} are
usually named \emph{projection morphisms} or simply \emph{projections}.
\par
If we have \m{X_i=X} for all \m{i\in I} and one object \m{X}, then a
product of \m{\apply{X_i}_{i\in I}} is usually called \emph{\nbdd{I}th
power of \m{X}}.
\end{definition}
\par
Again it is routine to verify that any two products of a family
\m{\apply{X_i}_{i\in I}} are isomorphic. So one commonly chooses a certain
construction of a product and calls it \emph{the} product
\m{\prod_{i\in I} X_i} of \m{\apply{X_i}_{i\in I}}. Moreover, also the
corresponding projection morphisms are then usually left implicit,
although they are technically important to distinguish the product.
\par
In the case of finite index sets \m{I=\set{\nu_1,\dotsc,\nu_n}}, we also
write \m{X_{\nu_1}\times\dotsm\times X_{\nu_n}} instead of
\m{\prod_{i=1}^n X_{\nu_i}}, and often \nbdd{I}th powers are abbreviated
as \m{X^I}, \eg\ \m{X^2} is written for \m{X\times X}. In this article we
try to avoid the notation \m{X^I} for powers since it clashes with the
also common notation \m{X^Y} for exponential objects occurring in
Subsections~\ref{subsect:currying} et seqq.
\par
For completeness we also mention
that the dual notion of product and power is that of a \emph{coproduct}
and \emph{copower}. Since these only appear in a short side\dash{}remark
in this paper, we refer the reader to the literature,
\eg~\cite{cats,AwodeyCategoryTheory}, for further details.
\par
In the familiar categories we mentioned earlier, products exist and are
given by the constructions that one expects. In \m{\Set} the Cartesian
product \m{\prod_{i\in I} X_i} of sets \m{\apply{X_i}_{i\in I}} together
with the maps \m{\functionhead{p_i}{\prod_{j\in I}X_j}{X_i}},
\m{\apply{x_j}_{j\in I}\mapsto x_i} is indeed
a product of \m{\apply{X_i}_{i\in I}} in the sense of category theory.
The tupling of mappings \m{\functionhead{q_i}{Q}{X_i}}, \m{i\in I}, is
given by \m{h(q)\defeq \apply{q_i(q)}_{i\in I}} for \m{q\in Q}. The
defining property from Definition~\ref{def:prod} can now readily be
checked.
\par
In the category \m{\Top} of topological spaces the product of topological
spaces \m{\apply{X_i}_{i\in I}} is given by the topological space on the
Cartesian product of the carrier sets, carrying the product topology.
Similarly, in \m{\Mea} the product is the measurable space on the product
of the carrier sets of the factors (as in \m{\Set}), equipped with the
product \nbd{$\sigma$}algebra. In both cases the choice of the product
topology (and the product \nbd{$\sigma$}algebra, respectively) ensures that
the tupling as calculated in \m{\Set} is actually continuous (measurable,
respectively) such that it can act as a tupling in \m{\Top} (and
\m{\Mea}), too.
\par
Next, we show a simple observation how the uniqueness property of a
product can be exploited to prove that two morphisms from one object into
a product are identical. We shall use this fundamental relationship
several times in later proofs.
\par
\begin{remark}\label{rem:equality-of-morphisms-prod}
Suppose that \m{I} is any index set, \m{A} and \m{\apply{P_i}_{i\in I}}
are objects in a category \m{\cat} such that a product
\m{\prod_{i\in I}P_i} with projections
\m{\apply{\mor{\prod_{j\in I}P_j}{p_i}{P_i}}_{i\in I}} exists. Then for
any two morphisms \m{\mor{A}{f,g}{\prod_{i\in I}P_i}}, checking the
equality \m{f=g} is equivalent to verifying
\m{fp_i = gp_i} for all \m{i\in I}.
\par
Certainly, if \m{f} equals \m{g}, then the described condition follows by
composition with the projections. Thus, we only need to explain the
converse direction. If we have \m{fp_i= gp_i} for \m{i\in I}, we simply put
\m{q_i\defeq fp_i=gp_i}, and hence the object \m{A} together with
\m{\apply{\mor{A}{q_i}{P_i}}_{i\in I}} plays the role of the object \m{Q}
in Definition~\ref{def:prod} \wrt\ the product \m{\prod_{i\in I}P_i}. By
definition of the product, there now exists a
unique morphism \m{\mor{A}{h}{\prod_{i\in I}P_i}} such that \m{hp_i = q_i}
for all \m{i\in I}. By our assumption we already have two candidates
fulfilling this requirement, namely \m{f} and \m{g}. Thus, by uniqueness,
these two morphisms must be equal (to \m{h}).
\end{remark}
\par
With the following definition, we simply introduce a bit of jargon for
categories where we can construct finite products at will. We have
already seen that concrete instances of this definition are given, for
example, by the categories \m{\Set}, \m{\Top} and \m{\Mea}.
\par
\begin{definition}\label{def:product-category}
We say that a category \m{\cat} \emph{has binary products} if for any two
objects \m{X,Y} from \m{\cat} a product \m{X\times Y} (with corresponding
projection morphisms) exists. \par
Moreover, we speak of a category \emph{having finite products} (or
of a \emph{finite product category}, also called \emph{Cartesian
(monoidal) category} by some authors) if it has binary products and a
terminal object.
\end{definition}
\par
By iterating the binary product construction and using the terminal
object as the product with no factors, it is clear that in a finite
product category, indeed, products
\m{(\dotsm((X_1\times X_2)\times X_3) \times\dotsm )\times X_n}
of any finite number \m{n\geq 0} of objects \m{X_1,\dotsc, X_n} exist.
\par
\medskip
So far we have introduced very basic category theoretic notions, like
special sorts of objects, morphisms or combinations thereof.
In the next step we touch a source of much deeper theoretic results,
namely ``morphisms between categories'' (functors) and ``morphisms between
those'' (natural transformations). This lays the foundations for the
definition of more interesting notions, such as algebras, coalgebras,
monads, comonads, and monadic algebras and comonadic coalgebras,
respectively. Furthermore, it paves the way for speaking about
powerful concepts such as adjointness.
\par
\begin{definition}\label{def:functor}
If \m{\cat} and \m{\catd} are categories, then a functor
\m{\mor{\cat}{F}{\catd}} associates with every object \m{X} of
\m{\cat} an object \m{F(X)} belonging to \m{\catd} and with every
morphism \m{\mor{X}{f}{Y}} between objects \m{X,Y} of \m{\cat} a morphism
\m{\mor{F(X)}{F(f)}{F(Y)}} in \m{\catd} such that the following
axioms are satisfied:
\begin{enumerate}[(1)]
\item \m{F(1_X) = 1_{F(X)}} holds for all \m{X} from \m{\cat}.
\item \m{F(fg) = F(f)F(g)} for all morphisms \m{\mor{X}{f}{Y}} and
\m{\mor{Y}{g}{Z}} between objects \m{X}, \m{Y} and \m{Z} belonging
to \m{\cat}. Here the composition on the left\dash{}hand side is
done in \m{\cat} and the one between \m{F(f)} and \m{F(g)} is
carried out in \m{\catd}.
\end{enumerate}
It is customary to agree on omission of brackets for \m{F(f)} and \m{F(X)}
if the argument consists of just one symbol.\par
Moreover, if \m{\cat=\catd}, then the functor \m{F} is said to be an
\emph{endo\dash{}functor} of the category \m{\cat}. We write \m{\EndOp\cat} for
the class of all endo\dash{}functors of \m{\cat}.
\end{definition}
\par
Thus, a functor is like a mapping between categories that is structurally
compatible: the first condition ensures compatibility with the identical
morphisms and the second one compatibility with composition. Intuitively,
functors should be viewed as morphisms between the categories \m{\cat} and
\m{\catd}. We mention that this intuition can even be made precise
by forming the class \m{\cats} of small categories, \ie\ those, whose
object class is a set rather than a proper class. Equipping
\m{\cats} with the functors as morphisms and the canonical composition of
functors as explained in Remark~\ref{rem:comp-functors}, \m{\cats} indeed
forms a category.
\par
\begin{remark}\label{rem:comp-functors}
If \m{\cat}, \m{\catd} and \m{\catlayout{E}} are categories and
\m{\mor{\cat}{F}{\catd}} and \m{\mor{\catd}{G}{\catlayout{E}}} are
functors, one can easily check that putting \m{GFX\defeq G(F(X))} and
\m{GFf\defeq G(F(f))} for a morphism \m{\mor{X}{f}{Y}} and objects \m{X}
and \m{Y} of \m{\cat} defines a functor \m{\mor{\cat}{GF}{\catlayout{E}}}.
We admit that viewing functors as morphisms between categories, it would
have been more natural to write \m{FG} for this functor (cf.\ our notation
for composition of morphisms in categories~\ref{def:cat}). Yet, in later
sections, we will be concerned with quite a few object\dash{}wise
calculations involving functors,
which motivates the slightly inconsistent notation we have chosen here.
\end{remark}
\par
Many important constructions in mathematics are in fact functors. For
instance associating with any Lie group its Lie algebra is functorial,
sending a group to its abelianization is a functor from groups to the
category of Abelian groups, Stone-\v{C}ech-compactification can be viewed
as a functor from \m{\Top} to the category of compact Hausdorff spaces,
taking the fundamental group at a certain base point is a functor from
\m{\Top} to the category of groups, and many more.
\par
In the following example, we present simpler cases, which at the same have
greater relevance for our topic.
\begin{example}\phantomsection{}\label{ex:functors}% needed to have correct
% % hyperlinking
\begin{enumerate}[(a)]
\item\label{item:identical-functor}
There is a trivial endo\dash{}functor associated with every category
\m{\cat}. The \emph{identical functor} \m{\mor{\cat}{1_{\cat}}{\cat}}
maps objects and morphisms of \m{\cat} identically.
\item\label{item:constant-functor}
Similarly obvious are \emph{constant functors}: if \m{T} is an object
of category \m{\catd}, then mapping any object \m{X} of another
category \m{\cat} to \m{T} and any \nbdd{\cat}morphism
\m{\mor{X}{f}{Y}} to \m{\mor{T}{1_{T}}{T}} certainly yields a functor
\m{\mor{\cat}{T}{\catd}} that is usually denoted with the same
symbol as the object uniquely determining it. In the special case
that \m{\cat=\catd}, one has, of course, a constant
endo\dash{}functor.
\item\label{item:forgetful-functor}
Another easy, but useful instance of functors are \emph{forgetful
functors}. These simply forget some structure of the objects and
morphisms. For instance, with every topological space
\m{\bx=\apply{X,\tau}} we may associate the underlying
carrier set \m{U\apply{\bx}\defeq X}, and with every
\nbdd{\Top}morphism (continuous map)
\m{\mor{\apply{X,\tau}}{f}{\apply{Y,\sigma}}} the underlying map
\m{\mor{X}{f}{Y}} in \m{\Set}. It is evident that this definition
yields a functor \m{\mor{\Top}{U}{\Set}} as \nbdd{\Top}morphisms are
composed in the same way as mappings and the identical
\nbdd{\Top}morphisms map elements identically.
\item\label{item:product-bifunctor}
The fourth example will play a central role in
Subsection~\ref{subsect:monoids-to-monads} et seqq. We assume a category
\m{\cat} such that a product \m{X\times Y} exists for any two
objects \m{X} and \m{Y} from \m{\cat}. Since products are only
unique up to isomorphism, we consider now one particular choice for
\m{X\times Y} (together with corresponding projection morphisms) as
fixed for any \m{X,Y} in \m{\cat}. Furthermore, for objects
\m{X,Y,U,V} and \nbdd{\cat}morphisms \m{\mor{X}{f}{U}} and
\m{\mor{Y}{g}{V}}, we define
\m{\mor{X\times Y}{f\times g}{U\times V}} by
\m{f\times g \defeq \tpl{\pr_X f,\pr_Y g}} where \m{\mor{X\times
Y}{\pr_X}{X}} and \m{\mor{X\times Y}{\pr_Y}{Y}} are the projection
morphisms coming with \m{X\times Y}. Hence, \m{f\times g} is the
unique morphism \m{\mor{X\times Y}{h}{U\times V}} making the
diagram
\begin{equation*}
\begin{xy}
\xymatrix{%
X\ar[r]^{f}& U\\
X\times Y \ar@{-->}[r]^{h}\ar[d]_{\pr_Y}\ar[u]^{\pr_X}
& U\times V\ar[d]^{\pr'_{V}}\ar[u]_{\pr'_{U}}\\
Y \ar[r]^{g}& V
}%
\end{xy}
\end{equation*}
commute, in which \m{\mor{U\times V}{\pr'_U}{U}} and
\m{\mor{U\times V}{\pr'_V}{V}} are the projections of \m{U\times V}.
\par
Since the morphism \m{h} is unique with respect to this property,
it is evident, that \m{1_{X}\times 1_{Y} = 1_{X\times Y}}, as the
latter indeed ensures commutativity of the corresponding diagram.
Moreover, given
morphisms \m{\mor{X}{f_1}{U}}, \m{\mor{U}{f_2}{W}} and
\m{\mor{Y}{g_1}{V}}, \m{\mor{V}{g_2}{Z}},
putting the two commutative diagrams for \m{f_1\times g_1} and
\m{f_2\times g_2} together, it is clear that
\m{\apply{f_1\times g_1}\apply{f_2\times g_2}} makes the whole
diagram
\begin{equation*}
\begin{xy}\xymatrix{%
X\ar[r]^{f_1}\ar@/^1.8em/[rr]^{f_1f_2}
& U\ar[r]^{f_2} & W\\
X\times Y \ar[r]^{f_1\times g_1}\ar[u]^{\pr_X}\ar[d]_{\pr_Y}
%\ar@{-->}@/^5em/[rr]^{%
% T\times (fg)=\apply{T\times f}\apply{T\times g}}
&U\times V\ar[r]^{f_2\times g_2}\ar[u]_{\pr'_U}\ar[d]^{\pr'_V}
&W\times Z\ar[u]_{\pr''_W}\ar[d]^{\pr''_Z}\\
Y \ar[r]^{g_1}\ar@/_1.8em/[rr]_{g_1g_2}& V\ar[r]^{g_2} & Z
}%
\end{xy}
\end{equation*}
commute. Thus, by uniqueness, it follows that
\m{(f_1f_2)\times (g_1g_2)} is equal to
\m{\apply{f_1\times g_1}\apply{f_2\times g_2}}.
\par
Hence, we have established that
\m{\mor{\cat\times\cat}{-_1\times -_2}{\cat}} is functorial in both
arguments, so it is a so\dash{}called \emph{bifunctor} into
\m{\cat}.
\item\label{item:product-functor}
The next example will also play an important role in
Subsection~\ref{subsect:monoids-to-monads} et seqq. If a category \m{\cat}
has binary products, and \m{T} is an object of \m{\cat}, then we may
certainly plug in the constant endo\dash{}functor \m{T}
(see~\eqref{item:constant-functor}) into the first coordinate of the
bifunctor \m{\times} given in~\eqref{item:product-bifunctor}. This
yields an endo\dash{}functor \m{\mor{\cat}{T\times -}{\cat}} mapping every
object \m{X} to the chosen product \m{T\times X} and morphisms
\m{\mor{X}{f}{Y}} to \m{\mor{T\times X\,}{T\times f}{\,T\times Y}
\defeq \mor{T\times X}{1_T\times f}{T\times Y}
=\mor{T\times X}{\tpl{\pr_T,\, \pr_X f}}{T\times Y}}. The latter is
the unique morphism \m{\mor{T\times X}{h}{T\times Y}} making the
diagram
\begin{equation*}
\begin{xy}
\xymatrix{%
& T\\
T\times X \ar@{-->}[r]^{h}\ar[d]_{\pr_X}\ar[ur]^{\pr_T}
& T\times Y\ar[d]^{\pr'_{Y}}\ar[u]_{\pr'_{T}}\\
X \ar[r]^{f}& Y
}%
\end{xy}
\end{equation*}
commute, in which \m{\mor{T\times X}{\pr_T}{T}} and
\m{\mor{T\times X}{\pr_X}{X}} are the projections of \m{T\times X},
and \m{\mor{T\times Y}{\pr'_T}{T}} and
\m{\mor{T\times Y}{\pr'_Y}{Y}} are the projections of \m{T\times Y}.
In a similar way, also a functor \m{-\times T} may be defined.
\par
A more subtle analysis of the situation makes clear, of course, that
it is not necessary to require that all binary products exist in
\m{\cat} in order to define the functor \m{T\times -}. It is
sufficient if for every \m{X} in \m{\cat} a product \m{T\times X}
exists, and making a specific choice for it, one can explicitly
define \m{T\times -} along the lines of
item~\eqref{item:product-bifunctor}.
\item The last example is also a bifunctor, \ie\ an assignment that
is functorial in both its input arguments: if \m{\cat} is any
category, the so\dash{}called \emph{hom\dash{}functor} is a
bifunctor from \m{\catop\times \cat} to the category of sets. For
every pair of objects \m{A,B} from \m{\cat}, the hom\dash{}functor
associates the set of morphisms \m{\cat\apply{A,B}}. Moreover, if
\m{C,D} are further objects of \m{\cat} and \m{\mor{A}{f}{C}} is a
morphism in \m{\catop} and \m{\mor{B}{g}{D}} is one in \m{\cat},
then
\m{\functionhead{\cat\apply{f,g}}{\cat\apply{A,B}}{\cat\apply{C,D}}}
is given by composition in \m{\cat}, \ie\
\m{\cat\apply{f,g}\apply{h}\defeq fhg} for any
\m{h\in\cat\apply{A,B}}. It is not difficult to check that this
assignment is indeed functorial. We remark that sometimes, in
particular if the category \m{\cat} is clear from the context,
\m{\Hom\apply{-,-}} is written instead of \m{\cat\apply{-,-}}.
\end{enumerate}
\end{example}
\par
Going one step further, we now also consider ``morphisms between
functors''. These are called \emph{natural transformations}.
\par
\begin{definition}\label{def:nat-trans}
Let \m{\cat} and \m{\catd} be categories and \m{\mor{\cat}{F,G}{\catd}} be
functors. A \emph{natural transformation} \m{\mor{F}{\eta}{G}} is a
\nbdd{\cat}indexed family of \nbdd{\catd}morphisms
\m{\apply{\mor{FX}{\eta_X}{GX}}_{X\in\cat}} such that for
all \m{X,Y} from \m{\cat} and all \nbdd{\cat}morphisms \m{\mor{X}{f}{Y}},
the following square
\begin{equation*}
\begin{xy}
\xymatrix{%
FX \ar[r]^{\eta_X}\ar[d]_{Ff}& GX\ar[d]^{Gf}\\
FY \ar[r]^{\eta_Y}& GY
}
\end{xy}
\end{equation*}
commutes, \ie \m{\eta_X Gf = Ff \eta_Y}.
\par
A natural transformation \m{\mor{F}{\eta}{G}} is called \emph{natural
equivalence} if for every fibre the morphism \m{\mor{FX}{\eta_X}{GX}} is
an isomorphism.
\end{definition}
\par
There are canonical ways of composing natural transformations with each
other and with functors. The details and the notation we shall apply later
for these compositions are contained in the following remark.
\begin{remark}\label{rem:nat-trafo-comp}
Let \m{\cat}, \m{\catd} and \m{\catlayout{E}} be categories,
\m{\mor{\cat}{F,G}{\catd}} be functors and \m{\mor{F}{\eta}{G}} be a
natural transformation.
\begin{enumerate}[(a)]
\item For any functor \m{\mor{\cat}{H}{\catd}} and a transformation
\m{\mor{G}{\epsilon}{H}}, we can define the morphism
\m{\apply{\eta\epsilon}_X\defeq \eta_X\epsilon_X} for any object
\m{X} in \m{\cat}. Then \m{\mor{F}{\eta\epsilon}{H}}, given by
\m{\apply{\mor{FX}{\apply{\eta\epsilon}_X}{HX}}_{X\in\cat}} is
again a natural transformation due to the commutativity of the
diagram
\begin{equation*}
\begin{xy}\xymatrix{%
FX \ar[r]^{\eta_X}
\ar[d]_{Ff}\ar@{-->}@/^1.8em/[rr]^{\apply{\eta\epsilon}_X}
& GX\ar[r]^{\epsilon_X}\ar[d]^{Gf}
& HX\ar[d]^{Hf}\\
FY\ar[r]^{\eta_Y}\ar@{-->}@/_1.8em/[rr]_{\apply{\eta\epsilon}_{Y}} &
GY\ar[r]^{\epsilon_Y} & HY\rlap{.}
}
\end{xy}
\end{equation*}
Let us note that \wrt\ this composition there also exists a neutral
element, namely the \emph{identical natural transformation}
\m{\mor{F}{1_F}{F}}, given as \m{\mor{FX}{1_{FX}}{FX}} for \m{X}
in \m{\cat}.
\item For any functor \m{\mor{\catd}{H}{\catlayout{E}}} we put
\m{\mor{HFX}{\apply{H\eta}_X\defeq H(\eta_X)}{HGX}} for all \m{X} in
\m{\cat}, thus obtaining a natural transformation
\m{\mor{HF}{H\eta}{HG}}. This follows since the functor \m{H} turns
the commutative square belonging to a \nbdd{\cat}morphism
\m{\mor{X}{f}{Y}} and the transformation \m{\eta} into the commuting
square
\begin{equation*}
\begin{xy}
\xymatrix{%
HFX\ar[r]^{H\eta_X} \ar[d]_{HFf}& HGX\ar[d]^{HGf}\\
HFY\ar[r]^{H\eta_Y}& HGY\rlap{.}
}
\end{xy}
\end{equation*}
\item For any functor \m{\mor{\catlayout{E}}{H}{\cat}} we put
\m{\mor{FHX}{\apply{\eta_H}_X\defeq \eta_{HX}}{GHX}} for \m{X} in
\m{\catlayout{E}}, yielding a natural transformation
\m{\mor{FH}{\eta_{H}}{GH}} since the diagram
\begin{equation*}
\begin{xy}
\xymatrix{%
FHX\ar[r]^{\eta_{HX}} \ar[d]_{FHf} & GHX\ar[d]^{GHf}\\
FHY\ar[r]^{\eta_{HY}} & GHY
}
\end{xy}
\end{equation*}
commutes for all \m{X,Y} in \m{\catlayout{E}} and
\m{f\in\catlayout{E}\apply{X,Y}}.\qedhere
\end{enumerate}
\end{remark}
\par
If we have a finite product category \m{\cat}, we can also use functors
and natural transformations to agree on some notation concerning the
terminal object and the morphisms into it.
\par
\begin{remark}\label{rem:notation-finite-prod-cats}
Assume that \m{\cat} is a finite product category. Since any terminal
object has the property of a product with no factors, we use the following
notation for the constant functor yielding a fixed terminal object \m{I}.
As \m{I} is the zeroth power of any object \m{X} from \m{\cat}, we write
\m{\mor{\cat}{-^0}{\cat}} for the constant endo\dash{}functor with value
\m{I=X^0}. We already know from
Example~\ref{ex:functors}\eqref{item:constant-functor} that this functor
maps any morphism \m{\mor{X}{f}{Y}} to \m{f^0 = 1_I = \excl_I}.
\par
Besides, the unique morphisms \m{\mor{X}{\excl_X}{I}} into the terminal
object can be grouped together in a natural transformation
\m{\mor{1_{\cat}}{!}{-^0}} as \m{\excl_X f^0 = \excl_X = f\excl_Y} holds
for every morphism \m{\mor{X}{f}{Y}}.
\par
Moreover, whenever we write \m{X\times Y} in a finite product category
\m{\cat}, we agree to mean by this the result of the bifunctor
\m{\mor{\cat\times\cat}{-_1\times -_2}{\cat}} given by one particular
(implicit or explicit) choice of the product (see
Example~\ref{ex:functors}\eqref{item:product-bifunctor}). This choice is
naturally accompanied by a choice of projections for each product.
However, instead of capturing these by two additional natural
transformations, we leave them implicit and use ad-hoc notation as needed.
\end{remark}
\par
Knowing now about functors and natural transformations, we can introduce
the notion of adjointness of functors. This is a very pervasive concept in
category theory, which can be motivated as a weak form of categorical
equivalence: one says that two functors \m{\mor{\cat}{F}{\catd}} and
\m{\mor{\catd}{G}{\cat}} constitute an equivalence of two categories
\m{\cat} and \m{\catd} if there exist natural transformations
\m{\mor{1_{\cat}}{\vheta}{GF}} and \m{\mor{FG}{\epsilon}{1_{\catd}}} that
are natural equivalences (\ie\ consist of isomorphisms). Adjointness of
functors \m{F} and \m{G} weakens this setting in such that two natural
transformations \m{\mor{1_{\cat}}{\vheta}{GF}} and
\m{\mor{FG}{\epsilon}{1_{\catd}}} must exist, but it is not required any
more that these are natural equivalences. However, one asks for two
conditions to be satisfied, which easily follow in case of a categorical
equivalence, but not conversely.
\par
\begin{definition}\label{def:adjunction}
Let \m{\cat}, \m{\catd} be categories and \m{\mor{\cat}{F}{\catd}},
\m{\mor{\catd}{G}{\cat}} be functors. One says that \m{F} is
\emph{left\dash{}adjoint} to \m{G} (and that \m{G} is
\emph{right\dash{}adjoint} to \m{F}), written as \m{F\ladjoint G}, if
there exist natural transformations \m{\mor{1_{\cat}}{\vheta}{GF}} (called
\emph{unit} of the adjunction) and \m{\mor{FG}{\epsilon}{1_{\catd}}}
(called \emph{co\dash{}unit} of the adjunction) such that for all objects
\m{X} from \m{\cat} and \m{Y} from \m{\catd} the following two axioms,
known as \emph{co\dash{}unit\dash{}unit equations}, hold:
\begin{align*}
1_{FX} &= F\vheta_X \epsilon_{FX} \\
1_{GY} &= \vheta_{GY}G\epsilon_{Y}.\qedhere
\end{align*}
\end{definition}
\par
Let us note that using Remark~\ref{rem:nat-trafo-comp}, the
co\dash{}unit\dash{}unit equations can be compactly stated as
\m{1_{F} = F\vheta \epsilon_{F}} and \m{1_{G} = \vheta_G G\epsilon}.
\par
The following relationship between adjointness of functors described by
unit and co\dash{}unit, and natural equivalence of hom\dash{}functors is
well\dash{}known (see \eg~\cite[19.3, 19.10, 19.11, 19.A]{cats}
and~\cite[9.4, 9.5, 9.6]{AwodeyCategoryTheory}, giving a few more details).
\par
\begin{proposition}\label{prop:char-adjunction}
For categories \m{\cat}, \m{\catd} and functors \m{\mor{\cat}{F}{\catd}}
and \m{\mor{\catd}{G}{\cat}} the following are equivalent:
\begin{enumerate}[(a)]
\item \m{F\ladjoint G}
\item There exists a natural equivalence between the hom\dash{}bifunctors
\m{\catd\apply{F,-}} and \m{\cat\apply{-,G}}.
\end{enumerate}
\par
More precisely, if \m{\mor{1_{\cat}}{\vheta}{GF}} and
\m{\mor{FG}{\epsilon}{1_{\catd}}} are the unit and co\dash{}unit of the
adjunction \m{F\ladjoint G}, then one defines the natural equivalence
\m{\mor{\catd\apply{F,-}}{\nu}{\cat\apply{-,G}}} by
\m{\nu_{X,Y}\apply{\mor{FX}{g}{Y}}\defeq \vheta_{X}Gg} for \m{X} in
\m{\cat}, \m{Y} in \m{\catd} and \m{g\in\catd\apply{FX,Y}}. Its inverse
\m{\nu^{-1}_{X,Y}} is given by
\m{\nu^{-1}_{X,Y}\apply{\mor{X}{f}{GY}}\defeq Ff \epsilon_Y} for \m{X} in
\m{\cat}, \m{Y} in \m{\catd} and \m{f\in\cat\apply{X,GY}}.
\par
Conversely, if the natural equivalence
\m{\mor{\catd\apply{F,-}}{\nu}{\cat\apply{-,G}}} is given, then one puts
\m{\vheta_X\defeq \nu_{X,FX}\apply{1_{FX}}} for \m{X} in \m{\cat} and
\m{\epsilon_Y\defeq \nu^{-1}_{GY,Y}\apply{1_{GY}}} for \m{Y} in \m{\catd}.
\end{proposition}
\par
\smallskip
Next, we define the concept of an \emph{algebra for an
endo\dash{}functor}, of a \emph{monad} and of an \emph{algebra for a
monad}, which has a richer structure than just an algebra for a functor.
Using duality (see Remark~\ref{rem:opp-cat}) these notions have duals,
known as \emph{coalgebra}, \emph{comonad} and \emph{coalgebra for a
comonad}.
\par
\begin{definition}\label{def:alg-coalg}
Let \m{\cat} be a category and \m{F\in\EndOp\cat} an endo\dash{}functor,
called \emph{signature functor}. Then an \emph{algebra} for the
endo\dash{}functor \m{F} (also called \emph{algebra of signature \m{F}} or
\emph{\nbdd{F}algebra}) is any pair \m{\apply{A,\mor{FA}{\aLpha}{A}}}
where \m{A} is an object of \m{\cat} and \m{\aLpha\in\cat\apply{FA,A}} is
a morphism.
\par
Dually, a \emph{coalgebra} for \m{F} (or \emph{\nbdd{F}coalgebra}) is a
pair, which is an algebra for \m{F} considered as an endo\dash{}functor of
\m{\catop}, \ie\ a pair \m{\apply{A,\mor{A}{\aLpha}{FA}}} where \m{A}
belongs to \m{\cat} and \m{\aLpha\in\cat\apply{A,FA}}.
\end{definition}
\par
To give an intuition in what sense this definition describes algebraic
structures, we present two examples:
\par
\begin{example}\label{ex:binary-alg}
Consider a category \m{\cat}, in which for any object \m{X} the product
\m{X\times X} exists, and fix one particular choice for this product as
\m{\Delta(X)\defeq X\times X} with projections
\m{\mor{\Delta(X)}{\pr_i^X}{X}} (\m{i\in\set{1,2}}). This setting can be
extended to an endo\dash{}functor if we define for any \m{\mor{X}{f}{Y}}
from \m{\cat} the morphism \m{\mor{X\times X}{\Delta(f)}{Y\times Y}} to be
\m{\Delta(f)\defeq f\times f = \tpl{\pr_1^X f, \pr_2^X f}} (cf.\
Example~\ref{ex:functors}\eqref{item:product-bifunctor}).
\par
Now an algebra of signature \m{\Delta} is a pair consisting of an object
\m{A} and a morphism \m{\mor{\Delta(A)=A\times A}{\aLpha}{A}}. This
morphism can be seen as a binary operation on \m{A}.
\par
More concretely, if \m{\cat=\Set}, then a \nbdd{\Delta}algebra is any
structure \m{\apply{A,f}}, where \m{\functionhead{f}{A\times A}{A}} is an
arbitrary binary operation on \m{A}. For example, it can be a semigroup,
or a loop or a trivial structure with a projection operation etc. However,
we do not know precisely what sort of structure it is: the concept of
\nbdd{\Delta}algebra is not powerful enough to encode information about
possible identities that may hold for the function \m{f}. It just encodes
that \m{f} is binary.\par
Similarly, if we let \m{\cat=\Top}, then a \nbdd{\Delta}algebra is just
any pair consisting of a topological space \m{\topSp{A}} together with a
continuous binary operation
\m{\functionhead{f}{\topSp{A}\times\topSp{A}}{\topSp{A}}}.
\end{example}
\par
Second, we give a concrete example in the category of sets, which already
prepares the central idea to be used in Subsection~\ref{subsect:currying}.
There, however, we will have a bit more structural information at our
disposal than just an algebra, namely monadicity which is discussed
subsequently.
\par
\begin{example}\label{ex:alg-coalg}
We consider \m{\cat=\Set} and the endo\dash{}functor \m{T\times -} for
some fixed set \m{T} (cf.\
Example~\ref{ex:functors}\eqref{item:product-functor}). An algebra for
\m{T\times -} is a simply a pair \m{\apply{A,\aLpha}}, where \m{A} is a
set and \m{\functionhead{\aLpha}{T\times A}{A}} is a mapping. Of course,
this encodes the same information as a structure with many unary
operations on \m{A}, one for each \m{t\in T}:
\m{\apply{A,\apply{\aLpha(t,-)}_{t\in T}}}.
\par
We can actually store the same amount of information also in a coalgebraic
structure. Yet, we need to use a different functor: instead of
\m{T\times -} we use the endo\dash{}functor \m{\Set\apply{T,-} = -^T}. It
maps any set \m{X} to the set of morphisms \m{\Set\apply{T,X}}, which is
nothing but the set of mappings \m{X^T} (or \nbdd{T}sequences in \m{X}).
A coalgebra for \m{\Set\apply{T,-}} is now a pair consisting of a set
\m{A} together with a map \m{\functionhead{\bEta}{A}{A^T}}, which
associates with every element \m{x\in A} a sequence \m{\psi(x)\in A^T}.
\par
If now a \nbdd{\apply{T\times -}}algebra \m{\apply{A,\aLpha}} as above is
given, then we may put, for instance,
\m{\bEta(x)\defeq \aLpha(-,x)\in A^T} and obtain a
\nbdd{\Set\apply{T,-}}coalgebra without losing any information.
Fortunately, we can even reverse this process: if a coalgebra
\m{\apply{A,\bEta}} for \m{\Set\apply{T,-}} is given, then we can define
\m{\apply{A,\aLpha}} by \m{\aLpha(t,x)\defeq \apply{\bEta(x)}(t)} and keep
all the information that was stored in the coalgebra also in the algebra.
\end{example}
\par
We saw in Example~\ref{ex:binary-alg} that only having an algebra or
coalgebra for a certain signature functor does not give us a lot of
structure to work with. To amend this we introduce now the notion of
\emph{monad} (and its dual), which will be used to define monadic algebras
(and comonadic coalgebras).
\par
\begin{definition}\label{def:monad}
\begin{enumerate}[(1)]
\item\label{item:monad}
A triple \m{\apply{T, \delta, \eta}}, in which \m{\mor{\cat}{T}{\cat}} is
an endo\dash{}functor, and \m{\mor{TT}{\delta}{T}} and
\m{\mor{1_{\cat}}{\eta}{T}} are natural transformations, is called a
\emph{monad} (originally called \emph{standard construction},
\cite{GodementTheorieDesFaisceaux},
later also \emph{triple}, see
\eg~\cite{EilenbergMoore_AdjointFunctorsTriples}) if the following two
diagrams commute\\
\begin{subequations}\label{diag:monad}
\begin{minipage}{0.49\linewidth}
\begin{align}\label{diag:monad-mult}
\begin{xy}\xymatrix@!C{%
T(T(TX))\ar[r]^{T(\delta_X)}\ar[d]_{\delta_{TX}}
&T(TX)\ar[d]^{\delta_X}\\
T(TX) \ar[r]^{\delta_X} & TX
}\end{xy}
\end{align}
\end{minipage}
\begin{minipage}{0.49\linewidth}
\begin{align}\label{diag:monad-neutr}
\begin{xy}\xymatrix@!C{%
TX \ar[r]^{\eta_{TX}}\ar[d]_{T\eta_X}\ar[dr]^{1_{TX}}
& TTX \ar[d]^{\delta_X}\\
TTX \ar[r]^{\delta_X} & TX
}\end{xy}
\end{align}
\end{minipage}
\end{subequations}
for every object \m{X} in \m{\cat}.
Using the composition notions from Remark~\ref{rem:nat-trafo-comp} these
can also be stated more compactly as \m{T(\delta)\delta = \delta_T \delta}
and \m{\eta_T\delta= 1_T =T(\eta)\delta}.
\item\label{item:comonad}
The dual notion is that of a \emph{comonad}, \ie\ a triple
\m{\apply{T,\delta,\eta}}, where \m{\mor{\cat}{T}{\cat}} is an
endo\dash{}functor, and \m{\mor{T}{\delta}{TT}} and \m{\mor{T}{\eta}{1_T}}
are natural transformations satisfying that the diagrams\\
\begin{subequations}\label{diag:comonad}
\begin{minipage}{0.49\linewidth}
\begin{align}\label{diag:comonad-mult}
\begin{xy}\xymatrix@!C{%
T(T(TX))
&T(TX)\ar[l]_{T(\delta_X)}\\
T(TX) \ar[u]^{\delta_{TX}}
& TX \ar[l]_{\delta_X}\ar[u]_{\delta_X}
}\end{xy}
\end{align}
\end{minipage}
\begin{minipage}{0.49\linewidth}
\begin{align}\label{diag:comonad-neutr}
\begin{xy}\xymatrix@!C{%
TX & TTX \ar[l]_{\eta_{TX}}\\
TTX \ar[u]^{T\eta_X} & TX\ar[l]_{\delta_X}\ar[u]_{\delta_X}
\ar[ul]_{1_{TX}}
}\end{xy}
\end{align}
\end{minipage}
\end{subequations}
commute for every \m{X} from \m{\cat}, \ie\
\m{\delta T(\delta) = \delta \delta_T} and
\m{\delta\eta_T = 1_T = \delta T(\eta)}.\qedhere
\end{enumerate}
\end{definition}
\par
Monads are used to encode extra structure about algebras for
endo\dash{}functors, for instance, identities that hold between operations
of algebras in the sense of universal algebra. All such structures can
indeed be interpreted as algebras for specific endo\dash{}functors. The
mentioned extra information in so\dash{}called monadic algebras is
expressed in the additional commuting diagrams in the following definition:
\par
\begin{definition}\label{def:monadic-algebra}
Let \m{\cat} be a category and \m{\mor{\cat}{T}{\cat}} be an
endo\dash{}functor.
\begin{enumerate}[(1)]
\item\label{item:monadic-alg}
If \m{\apply{T,\delta,\eta}} is a monad, then a \nbdd{T}algebra
\m{\apply{A,\mor{TA}{\aLpha}{A}}} is said to be
\emph{monadic \wrt\ \m{\apply{T,\delta,\eta}}} (or a
\emph{\nbdd{T}algebra for the monad \apply{T,\delta, \eta}}) if the
following two diagrams\\
\begin{subequations}\label{diag:monadic-alg}
\begin{minipage}{0.49\linewidth}
\begin{align}\label{diag:monadic-alg-mult}
\begin{xy}\xymatrix@!C{%
TTX\ar[r]^{T\aLpha} \ar[d]_{\delta_X}& TX\ar[d]^{\aLpha} \\
TX \ar[r]^{\aLpha} & X
}\end{xy}
\end{align}
\end{minipage}
\begin{minipage}{0.49\linewidth}
\begin{align}\label{diag:monadic-alg-neutr}
\begin{xy}\xymatrix@!C{%
X \ar[r]^{\eta_X}\ar[rd]_{1_X}& TX \ar[d]^{\aLpha}\\
& X
}\end{xy}
\end{align}
\end{minipage}
\end{subequations}
commute for every \m{X} in \m{\cat}.
\item\label{item:comonadic-coalg}
If \m{\apply{T,\delta,\eta}} is a comonad, then a \nbdd{T}coalgebra
\m{\apply{A,\mor{TA}{\aLpha}{A}}} is said to be
\emph{comonadic \wrt\ \m{\apply{T,\delta,\eta}}} (or a
\emph{\nbdd{T}coalgebra for the comonad \apply{T,\delta, \eta}}) if
the following two diagrams\\
\begin{subequations}\label{diag:comonadic-coalg}
\begin{minipage}{0.49\linewidth}
\begin{align}\label{diag:comonadic-coalg-mult}
\begin{xy}\xymatrix@!C{%
TTX & TX\ar[l]_{T\aLpha} \\
TX \ar[u]^{\delta_X} & X\ar[l]_{\aLpha}\ar[u]_{\aLpha}
}\end{xy}
\end{align}
\end{minipage}
\begin{minipage}{0.49\linewidth}
\begin{align}\label{diag:comonadic-coalg-neutr}
\begin{xy}\xymatrix@!C{%
X & TX \ar[l]_{\eta_X}\\
& X\ar[lu]^{1_X}\ar[u]_{\aLpha}
}\end{xy}
\end{align}
\end{minipage}
\end{subequations}
commute for every \m{X} in \m{\cat}.\qedhere
\end{enumerate}
\end{definition}
\par
%\begin{itemize}
%\item category, notation of \m{1_{X}}, composition without symbol
%\item terminal objects, unique morphisms \m{\excl_{X}}
%\item monomorphisms, epimorphisms
%\item products, tupling notation, equivalence equality of arrows into a product and equalities of arrows composed with projections, i.e.\
% for \m{\mor{A}{f,g}{\prod_{i \in I} P_i}} the equality \m{f=g} is equivalent to \m{f p_i = g p_i} for all \m{i \in I}.
% \item product categories, bifunctors and transformations needed, maybe
% motivating remark \m{X\times (Y\times Z) \neq (X\times Y)\times
% Z\neq X\times Y\times Z}.
%\item functor, contravariant composition notation, i.e.\ \m{FG(X)} means \m{F(G(X))} in contrast to the composition notation that is used for everything else (this is a bit inconsistent)
%\item natural transformation, definition (morphism between functors), characteristic diagram, possibilities to compose natural transformations with each other and with functors on both sides, natural equivalences = natural isomorphisms = natural transformation consisting of only isomorphisms.
% \item algebras and coalgebras, definition and maybe motivating example (e.g.\ a monoid as a functorial algebra)
% \item monads and comonads, defining diagrams, motivation, duality of the concepts
% \item (co)monadic (co)algebras
%\item subcategories and full subcategories
% \item adjoint functors, definition via hom\dash{}set\dash{}adjunction (natural equivalence of hom\dash{}bifunctors), characterisation via unit-co\dash{}unit equations and via existence of all universal solutions (freeness property), dually cofreeness property.
%\end{itemize}
\subsection{Classical dynamical systems theory}%
\label{subsect:class-dyn-sys}
A central problem studied in classical dynamical systems theory is the
following: given a set \m{T} (whose elements are to be interpreted as
points in \emph{time}) a set \m{X}, the \emph{state} (or \emph{phase})
\emph{space}, and an indexed family \m{\apply{\phi_t}_{t\in T}} of
mappings from \m{X} to \m{X}, called the \emph{evolution rule} of the
dynamical system, one is interested in the time behaviour of states
\m{x \in X} under the evolution rule.
\par
The most important cases for the time
set \m{T} are the integers, reals, and their subsets of non\dash{}negative
numbers. This implies that one also has an addition structure on the time
space, which usually at least satisfies the axioms of a \emph{monoid},
\ie\ an associative binary operation with a (two\dash{}sided) neutral
element. Often also the state space carries some extra structure such as
a topology, a uniformity, a metric, a differentiable structure, a
\nbd{\m{\sigma}}algebra, a measure etc. The
functions describing the evolution rule are then required to be
structure preserving w.r.t.\ \m{X}, i.e.\ continuous (if \m{X} is a
topological, uniform or metric space, e.g.\ a subspace of \m{\R^n}),
differentiable (if \m{X} is a geometric manifold), measurable (if \m{X} is
a measurable space), measure preserving (if \m{X} is a measure space, in
particular a probability space) etc. Accordingly, there is a large variety
of literature studying different types of dynamical systems depending on
the setting that is assumed for \m{X} and \m{T}.
\par
It is the aim of this paper to present a unifying framework that extends
the foundations of the classical theory. The initial step towards this
goal is the following simple observation: clearly, the evolution rule can
also be specified more compactly by just one map
\[\function{\aLpha}{T\times X}{X}{(t,x)}{
\phi\apply{t,x}\defeq \phi_t(x).}\]
This function is then usually assumed to fulfil the compatibility
conditions from above concerning structure that \m{T\times X} inherits
from \m{T} and \m{X} by a canonical product construction in the respective
settings. In general, the constraint that \m{\aLpha} has to be structure
preserving is a stronger condition than just requiring it for the
individual mappings \m{\phi_t}, \m{t\in T}.
However, in special cases both assumptions can be equivalent, as
mentioned, for instance, for the discrete time case of measurable dynamical
systems on p.~536 of~\cite{ArnoldRandomDS}.
\par
This can be considered as a motivation to study the more restrictive form
of an evolution rule given by a structure preserving map \m{\phi} instead
of an indexed family \m{\apply{\phi_t}_{t\in T}}. The following paragraph
demonstrates that we thereby do not lose an important class of examples
from where the notion of dynamical system originates.
\par\smallskip
Simple, and at the same time, prototypical representatives of
so\dash{}called \emph{discrete time} dynamical systems arise
in the following way: one starts with a topological space \m{X} and any
continuous function \m{\functionhead{f}{X}{X}}. Often, \m{X} is a subspace
of \m{\R^n} for some \m{n\in\N\setminus\set{0}} with the usual topology
inherited
from the Euclidean metric. The states are the points of the topological
space \m{X}. The evolution rule of the dynamical system is given by
iterating the function \m{f}. That is, the time space is the set of
natural numbers, \m{\N}, which clearly can be equipped with a monoid
structure \m{\gapply{\N; +, 0}}. In Definition~\ref{def:top-dyn-sys}, we
will understand this monoid more generally as a topological monoid by
considering the set of natural numbers as the carrier of a discrete
topological space, hence the name \emph{discrete time dynamical system}.
The dynamics is then given by
\[\function{\aLpha}{\N\times X}{X}{(n,x)}{f^n(x),}\]
where \m{f^0\defeq \id_X} is the identical mapping and
\m{f^{n+1}\defeq f\circ f^n} for \m{n\in\N}. This evolution rule fulfils
the properties of a dynamical system as described in the following
paragraphs. \par
At the same time, using the axioms below, one can see that
every discrete time dynamical system
\m{\functionhead{\aLpha}{\N\times X}{X}}
over a topological space \m{X} is given by iteration of a continuous
self-map, namely \m{\functionhead{f\defeq \phi(1,\cdot)}{X}{X}}.
This also explains why one frequently encounters definitions of dynamical
systems just as a pair of a space \m{X} and a structurally compatible
self\dash{}mapping \m{\functionhead{f}{X}{X}}, e.g.\ a topological space
and a continuous map, or a measurable space and a measurable map etc.
These kinds of definitions are subsumed by the discrete cases considered
here.
\par\smallskip
However, existing variants of dynamical systems do not only differ in the
type of time space used (discrete vs.\ continuous time), also in the sort
of (state) space (topological, measurable, etc.) or mappings (continuous,
measurable etc.). Therefore, one of the aims of this paper is to give a
definition of dynamical system (see Definition~\ref{def:Cdyn-sys}) that
encompasses many of
the competing notions that can be found throughout the literature. This is
possible using the language of category theory. In this formulation we
shall then see that dynamical systems are in fact a special instance of a
well\dash{}known concept in algebra and theoretical computer science,
namely that of a monadic algebra.
\par
The following informal definition of a dynamical system seems to be the
core of all the different formulations that one encounters. Given a
monoid \m{\alg[+,0]{T}} and a mapping
\m{\functionhead{\aLpha}{T\times X}{X}}, we say that
\m{\apply{\alg{T},\aLpha}} is a dynamical system provided the following
compatibility conditions hold and all involved mappings are structure
preserving w.r.t.\ the framework assumed for \m{X} and \m{T}:
\begin{enumerate}[(1)]
\item\label{eq:monoid-action-neutral}
For all \m{x \in X} we have \m{\aLpha(0,x)=x}.\hfill{(initial
condition)}
\item\label{eq:monoid-action-plus}
For all \m{x \in X} and all \m{s,t \in T}, it is
\m{\aLpha(s,\aLpha(t,x)) = \aLpha(s+t,x)}.%
\hfill{}(semigroup\\\mbox{}\hfill{}property)
\end{enumerate}
We remark that in case \m{X} and \m{T} are just sets, \ie\ no additional
structure needs to be preserved,
conditions~\eqref{eq:monoid-action-neutral}
and~\eqref{eq:monoid-action-plus} express that
\m{\functionhead{\aLpha}{T\times X}{X}} is a so\dash{}called \emph{monoid
action} of \m{\alg{T}} on \m{X}.
\par
In the next step we are going to put this into a formal definition for the
setting of topological spaces. On the one hand, this will be the basis for
a straightforward generalisation to arbitrary abstract categories. On the
other hand, the case of dynamical systems in a topological environment will
receive the highest level of emphasis among all types of dynamical systems
considered in this paper. After that we collect further variants from the
literature to outline the scope of our general modelling: we either use
them, with marginal modifications, as examples, or we discuss why they are
not fitting in our framework. First, we will briefly focus on special
cases such as dynamical systems in metric spaces. Subsequently, we
introduce measurable dynamical systems and discuss measure preserving
systems. Then we consider nonautonomous dynamical systems and their
continuous and measurable variants generalising, for example, skew product
flows.
\par
\smallskip
We recall that for a topological space \m{T}, a monoid
\m{\gapply{T;\, +,0}} is called \emph{topological monoid} if the
addition operation \m{\functionhead{+}{T\times T}{T}} is continuous \wrt\
the product topology. The constant \m{\functionhead{0}{T^0}{T}} is
automatically continuous \wrt\ the unique topology on the
one\dash{}element (terminal) topological space.\par
\begin{definition}\label{def:top-dyn-sys}
Let \m{T, X} be topological spaces. A \emph{topological dynamical system
over a monoid} is a triple
\m{\apply{\alg[+,0]{T},X,\aLpha\colon T \times X \to X}} where
\begin{enumerate}[(1)]
\item \m{\alg{T}} is a \emph{topological monoid},
\item \m{\aLpha\colon T \times X \to X} is a \emph{topological monoid
action}, \ie\ it is continuous \wrt\ the product topology and
satisfies the equalities~\eqref{eq:monoid-action-neutral}
and~\eqref{eq:monoid-action-plus} from above.\qedhere
\end{enumerate}
\end{definition}\par
As stated here our definition of topological dynamical system is a slight
generalisation of the same concept defined by E.~Glasner
in Section~1 of~\cite{GlasnerEnvelopingSemigroupsInTopologicalDynamics}.
There, Glasner studies the special case of our definition where the state
space is compact Hausdorff and the continuously acting topological monoid
is actually a topological group. Similarly,
in~\cite[Section~1(i)]{NerurkarErgodicContinuousSkewProductActions} the
notion of topological dynamical system is defined as a locally compact
separable topological group acting continuously (on the right) on a
compact metric space.\par
Our basic definition of topological dynamical system over a monoid
subsumes both existing notions, and it will be the starting point for
modelling and therefore generalising dynamical systems in any abstract
category in Section~\ref{sect:dyn-sys-abstr-cat}. \par
Of course, the previous definition can also be given in settings that
can be interpreted as prominent full subcategories of the category of
topological spaces, such as, for instance, Hausdorff topological
spaces, compact Hausdorff spaces, metrisable spaces etc.
Then one requires that all involved spaces, namely \m{T} and \m{X}, belong
to this subcategory and that all morphisms are continuous w.r.t.\ the
topologies on the spaces that are induced by the interpretation. In this
sense, we can, for example, define the notions of \emph{metric dynamical
system}, \emph{(compact) Hausdorff topological dynamical system} etc.\ in
complete analogy to Definition~\ref{def:top-dyn-sys}.\par
\smallskip
Another variant of dynamical system, which comes up via iterating
measurable maps in the same way as explained earlier for continuous maps,
is a \emph{measurable dynamical system},
see e.g.~\cite[p.~536]{ArnoldRandomDS}. Comparing the following
definition, which we take from the mentioned monograph, with
Definition~\ref{def:top-dyn-sys}, we have essentially replaced
the notion of topological space by measurable space and that of continuity
by measurability.
In particular, we call a monoid \m{\gapply{T;\,+,0}} on a
measurable space \m{T} a \emph{measurable monoid} if addition
\m{\functionhead{+}{T\times T}{T}} is measurable \wrt\ the
product \nbd{\m{\sigma}}algebra (generated by all binary
\name{Cartesian} products of measurable sets from the
\nbd{\m{\sigma}}algebra on \m{T}). The constant
\m{\functionhead{0}{T^0}{T}} is automatically measurable \wrt\ the
unique full \nbd{\m{\sigma}}algebra on the one\dash{}element
(terminal) measurable space.
\par
\begin{definition}\label{def:measrbl-dyn-sys}
Let \m{T, X} be measurable spaces. A \emph{measurable
dynamical system over a monoid} is a triple
\m{\apply{\alg[+,0]{T},X,\aLpha\colon T \times X \to X}} where
\begin{enumerate}[(1)]
\item \m{\alg{T}} is a \emph{measurable monoid},
\item \m{\aLpha\colon T \times X \to X} is a
\emph{measurable monoid action}, i.e.\ it is measurable w.r.t.\
the product \nbd{\m{\sigma}}algebra and satisfies the
equalities~\eqref{eq:monoid-action-neutral}
and~\eqref{eq:monoid-action-plus} from above.\qedhere
\end{enumerate}%
\end{definition}\par
We mention that again the prototype of this definition, to be found on
p.~536 of~\cite{ArnoldRandomDS}, is not as general as our version. Arnold
only defines these dynamical systems for monoids \m{\alg{T}} belonging to
the set \m{\set{\R, \R_{\geq 0}, \R_{\leq 0}, \Z, \N, \Z_{\leq 0}}}, each
to be understood with the usual addition operation as monoid operation and
zero as the neutral element. Since he just considers these special cases,
he does not mention the condition for \m{\alg{T}} to be a measurable
monoid. This is a requirement we have added to the definition in order to
get a homogeneous general setting. Moreover, it is implicitly fulfilled
by all the time monoids \m{\alg{T}} listed as examples
in~\cite{ArnoldRandomDS} (w.r.t.\ the
Borel \nbd{\m{\sigma}}algebra on \m{T} given by the standard metric
topology on the uncountable monoids and the discrete topology on the
countable monoids, respectively). This observation follows from
continuity of the monoid operations and the fact that the Borel
\nbd{\m{\sigma}}algebra of the product of two topological Hausdorff
spaces, one of which is second\dash{}countable, \ie\ has a countable
base, equals the product \nbd{\m{\sigma}}algebra of the Borel
\nbd{\m{\sigma}}algebras given by the individual spaces
(cf.~\cite[Lemma~6.4.2(i), p.~525]{BogachevMeasureTheory}).\par
In~\cite[p.~537]{ArnoldRandomDS} the yet stronger notion of
\emph{measure preserving dynamical system} (or \emph{metric dynamical
system}, a historical term that we wish to avoid for clarity) is defined.
The definition relies upon the concept of a measure
preserving map, which was introduced on
page~\pageref{page:measure-preserving-map}. We recall that a
self\dash{}map \m{\functionhead{f}{X}{X}} of a measure space \m{X}
carrying a measure \m{\mu} is measure preserving if
\m{\mu\circ f^{-1} = \mu}.
\par
\begin{definition}\label{def:measure-presDS}
Suppose that \m{\alg[+, 0]{T}} is a measurable monoid and \m{\measrSp{X}}
is a measure space %\todo{Why does Arnold require probability spaces here?}
with measure \m{\mu} and underlying measurable space \m{X}. A measurable
dynamical system
\m{\apply{\alg{T}, X, \functionhead{\aLpha}{T\times X}{X}}}
is called \emph{measure preserving} if the self-map
\m{\functionhead{\aLpha(t,\cdot)}{\measrSp{X}}{\measrSp{X}}} is measure
preserving for every point in time \m{t\in T}.
\end{definition}
Unfortunately, this definition is not suitable to be modelled within just
one category: the requirement on the self\dash{}mappings
\m{\functionhead{\phi(t,\cdot)}{\measrSp{X}}{\measrSp{X}}} to be measure
preserving suggests to choose the category of measure spaces together with
measure preserving mappings as morphisms. For a categorical modelling it
would be desirable if not only the individual mappings
\m{\apply{\phi\apply{t,\cdot}}_{t\in T}} were measure preserving, but if
the evolution rule \m{\functionhead{\phi}{T\times X}{X}} were measure
preserving as a whole \wrt\ the product measure on \m{T\times X} given
by the measure \m{\mu} on \m{X} and some measure \m{m} on \m{T}. Solving
for simple cases (\eg\ \m{\alg{T}} being the reals with addition, and
\m{\measrSp{X}} being the reals with \name{Lebesgue} measure) the question
if such a measure \m{m} exists at all, shows that it will often be
uniquely determined by \m{\mu} if it exists. So there is not much choice
left for \m{\alg{T}} once \m{\measrSp{X}} is fixed. On the other hand,
for \m{\alg{T}} being in accordance with category chosen for
\m{\measrSp{X}}, the measure on \m{T} should also be such that \m{\alg{T}}
is a measure preserving monoid. This means that the addition of
\m{\alg{T}} is measure preserving and,
moreover that \m{\functionhead{0}{T^0}{T}} is measure preserving \wrt\ the
unique one\dash{}element measure space on \m{T^0}. This is equivalent to
saying that the measure \m{m} on \m{T} is the \name{Dirac} measure
centred in the point \m{0}. This is a rather strong condition, prescribing
a possibly different measure space on \m{T} than the requirement coming
from \m{\aLpha}.\par
In view of these arguments it seems that a reasonable categorical
modelling of measure preserving dynamical systems should be done with the
option to choose the time space and the state space from different
categories. As this contradicts our original intention, we will not
consider measure preserving dynamical systems further in this paper.
\par\smallskip
\begin{comment}
\todo[inline,caption={},color=yellow!20]{%
This definition raises the following problems:
\begin{enumerate}[1))]
\item To become a categorical notion, we need the objects (and the
mappings) to be homogeneous. This homogeneity is not given here since only
\m{\measrSp{X}} is a measure (or probability) space. This first question
is, what should be the appropriate measure on the respective time spaces;
Lebesgue measure on \m{T=\R}?
\item Related to the first question is the problem: is the addition
operation on \m{T} measure preserving w.r.t.\ the product measure on
\m{T\times T}.
\item More importantly, is \m{\phi} as a whole measure
preserving? The answer is probably no, in general. Is it maybe true in the
discrete cases \m{\mathbf{T}\in\set{\N,\Z}}.
\item Is there a measure \m{\mu} on \m{T\times X} (not necessarily, but
preferably the product measure) such that \m{\phi(t,\cdot)} measure
preserving for all \m{t\in T} is equivalent to \m{\phi} being measure
preserving.
\end{enumerate}
Moreover, in the definition of \textbf{ergodic dynamical system} all the
mappings \m{\apply{\phi(t,\cdot)}_{t\in T}} are required to be ergodic, a
property that seems to be definable only for self-mappings. Is there a
characterisation of ergodicity which can be extended to \m{\phi}?\par
If the answer to the third (or the second) question is negative, we need
to abandon the notion of measure preserving dynamical system. If the
answer to the ergodicity question is ``no'', then the same is true for
ergodic dynamical systems.}
\end{comment}
A different sort of dynamical system arises when studying dynamical
behaviour of a system under an external influence, which itself is
modelled by a dynamical system. This kind of constellation entails a
so\dash{}called \emph{skew product}; its study is subject to the field of
nonautonomous dynamics.\par
In this context we refer to the
article~\cite{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts},
where the concepts of \emph{nonautonomous dynamical system (NDS)} and
\emph{continuous skew product flow} are defined. While the notion of
continuous skew product flow is suitable for categorical modelling
(cf.~Subsection~\ref{subsect:control-sys}), nonautonomous dynamical systems as
defined
in~\cite{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts}, do
not fit into an easy generalisation using just one category, unless they
essentially form a special case of a continuous skew product flow with a
discrete driving system. This is so because the driving system of an
NDS as in~\cite[Definition~2.1%
]{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts}
simply consists of sets and mappings without any topological structure,
whereas the second part of an NDS is assumed to satisfy continuity
requirements w.r.t.\ a metric. With the following definition we remove this
asymmetry
from~\cite[Definition~2.1%
]{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts} and emphasise
its purely algebraic, non\dash{}topological aspect. \par
\begin{definition}\label{def:setNDS}
For monoids \m{\alg{S}} and \m{\alg{T}}, such that
\m{\gapply{S; +, 0}=\alg{S}\leq \alg{T}} is a submonoid, and sets \m{X}
and \m{Y}, we call a pair \m{\apply{\theta,\phi}} of mappings
\m{\functionhead{\theta}{T\times X}{X}} and
\m{\functionhead{\phi}{S\times X\times Y}{Y}} a
\emph{nonautonomous dynamical system with times \m{\alg{S}\leq \alg{T}} on
\m{Y} with base \m{X}} if
\begin{enumerate}[(1)]
\item \m{\apply{\alg{T}, X, \theta}} is a (non\dash{}topological)
dynamical system over the monoid \m{\alg{T}} (\ie\ \m{\theta} is a
left\dash{}monoid action of \m{\alg{T}} on \m{X}), called
\emph{driving system},
\item \m{\phi} is a \emph{cocycle over \m{\theta}}, that is,
the following two equations, known as
\emph{cocycle property},
\begin{align}
\phi(0, x, y) &= y,\\
\phi(t+s,x,y) &= \phi(t, \theta(s,x), \phi(s, x, y))
\end{align}
hold for all \m{s,t \in S}, \m{x\in X} and \m{y\in Y}. \qedhere
\end{enumerate}
\end{definition}\par
It is not only with respect to continuity of the cocycle, where our
Definition~\ref{def:setNDS} slightly differs from the one given
in~\cite{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts}. Also
\wrt\ to the time spaces, we are marginally more general here than what
was written
in~\cite{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts}.
The only time monoids \m{\alg{T}} considered there are explicitly \m{\R}
(continuous time) and \m{\Z} (discrete time). Furthermore, the submonoids
\m{\alg{S}} were always chosen as the non\dash{}negative points in time,
i.e.\ \m{\R_{\geq 0}} and \m{\N}, respectively. Since we assume an
arbitrary monoid \m{\alg{T}} in our definition, which does not need to
have a compatible order relation, we can in general not speak of
``non\dash{}negative'' points in time. Hence, we replace the role of this
special submonoid by allowing any submonoid \m{\alg{S}}.
\par
The following is the companion definition to~\ref{def:setNDS}, focussing
on the continuous aspect of nonautonomous dynamics and extending
Definition~2.6
in~\cite{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts}
to general topological monoid actions.\par
\begin{definition}\label{def:ContSPF}
Suppose \m{\alg[+, 0]{S}} and \m{\alg{T}} are topological monoids,
\m{\alg{S}\leq \alg{T}} being a submonoid, and \m{X} and \m{Y} be
topological spaces. A pair \m{\apply{\theta,\phi}} of mappings
\m{\functionhead{\theta}{T\times X}{X}} and
\m{\functionhead{\phi}{S\times X\times Y}{Y}} is called
\emph{continuous skew product system\footnote{We have replaced the word
``flow'' by ``system'' since ``flow'' explicitly refers to \m{\alg{T}}
being the reals with addition, and we allow arbitrary topological
monoids, instead.} with times \m{\alg{S}\leq \alg{T}} on
\m{Y} with base \m{X}} if
\begin{enumerate}[(1)]
\item \m{\apply{\alg{T}, X, \theta}} is a topological dynamical system
over the monoid \m{\alg{T}} (as in Definition~\ref{def:top-dyn-sys}),
called \emph{driving system},
\item \m{\phi} is a \emph{continuous cocycle over \m{\theta}}, that is,
\m{\phi} is continuous and fulfils the cocycle property as introduced
in Definition~\ref{def:setNDS}.\qedhere
\end{enumerate}
\end{definition}\par
Comparing again
to~\cite{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts},
we have generalised the role of a continuous time monoid
(\m{\gapply{\R; +, 0}}) and its submonoid of non\dash{}negative time
points \m{\gapply{\R_{\geq 0}; +, 0}} and that of a discrete time monoid
\m{\gapply{\Z; +, 0}} with the submonoid \m{\gapply{\N; +,0}},
respectively, to any topological time monoid \m{\alg{T}} with an arbitrary
submonoid \m{\alg{S}}. Additionally, all spaces in Definition~2.6
of~\cite{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts} were
assumed to be metric spaces.
However, since the notion of continuity is a
purely topological concept, and we have widened the time monoid to allow
arbitrary continuous monoids, and groups in particular, it seems natural
to formulate the whole definition within the setting of topological
spaces. In this way we make sure not to lose interesting topological
groups or monoids which are not metrisable. An example would be, for
instance, the topological monoid \m{\alg{T}\defeq \gapply{\R; +, 0}}
consisting of the real line with the usual addition operation,
carrying not the standard metric topology, but the Sorgenfrey topology,
which fails to be metrisable. This structure is famous in topology and
often used as a counterexample. At the same time, this choice for
\m{\alg{T}} can serve as
a motivation for not restricting our Definitions~\ref{def:top-dyn-sys}
and~\ref{def:ContSPF} to topological groups. It is an example for a
topological monoid, which is not a topological group, since the inverse
operation is not continuous (see \eg~\cite[Example~3,
p.~799]{NyikosMetrizabilityFrechetUrysohnPropTopGrp}).
%\todo[size=\footnotesize]{%
% Bug Martin to come up with more interesting examples.}
\par\smallskip
We continue to comment a little bit more on the notion of
\emph{nonautonomous dynamical system} as stated
in~\cite{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts}.
This concept is a weakening of a special case of continuous skew product
flows where the base \m{X} is a discrete space, \ie\ essentially a set.
Then the condition that \m{\phi} is continuous can be expressed
equivalently\footnote{This follows because \m{S\times X\times Y} then
equals the copower \m{\coprod_{x\in X} S\times Y}, and \m{\phi} is the
cotupling of all the continuous maps \m{\apply{\phi(\cdot, x,
\cdot)}_{x\in X}}.} by the fact that the mappings
\m{\functionhead{\phi(\cdot, x, \cdot)}{S\times Y}{Y}} are continuous for
all \m{x\in X}, which is the formulation used in
Definition~2.1
of~\cite{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts}.
Moreover, it follows from Definition~\ref{def:ContSPF} that the action
\m{\theta} is continuous. In case that \m{X} is discrete, this is again
equivalent to
\m{\functionhead{\theta(\cdot,x)}{T}{X}}, \m{t\mapsto\theta\apply{t, x}}
being continuous for every point \m{x\in X}. This is the part of our
definition that is dropped
in~\cite[%
Definition~2.1]{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts},
making it weaker, \ie\ more general than~\ref{def:ContSPF} for discrete
base \m{X}. Still it is less general than our notion of nonautonomous
dynamical system (Definition~\ref{def:setNDS}), which simply requires
sets and no topology at all. At the same time, mixing topological spaces
and just sets in Definition~2.1
of~\cite{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts} makes
their construct more inhomogeneous. Similarly as for measure preserving
dynamical systems, it is this inhomogeneity between
continuous actions and simply group actions on a set, which renders Berger
and Siegmund's definition unfit for a generalisation using just one
category as we intend it in the following section. \par\medskip
%----------this cannot be said since we need to require that the set
% ---------\m{X} in BS03, Defintion~2.1, understood as a discrete space
% ---------has a continuous drive \m{\theta}. This is not the content of
% ---------the following paragraph.
%Summing up, we can say that nonautonomous dynamical systems as defined
%in~\cite{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts}, modulo
%the difference of topological vs.\ metric space and the special choices
%for \m{\alg{S}} and \m{\alg{T}}, correspond precisely to continuous skew
%product flows with discrete base and continuous driving system.
A third important notion in nonautonomous dynamics is that of \emph{random
dynamical system (RDS)}. A definition can, for instance, be found
in~\cite[Definition~2.3%
]{BergerSiegmundOnTheGapBetweenRDSAndContinuousSkewProducts} and
in~\cite[Definition~1.1.1]{ArnoldRandomDS}. Rephrasing Arnold's definition
in our language, an RDS is an NDS \m{\apply{\theta,\phi}}, where \m{\phi}
is measurable, and the driving system \m{\theta} is measure preserving
\wrt\ a probability space on the base space \m{X} as
in Definition~\ref{def:measure-presDS}. Berger and Siegmund's definition
additionally requires that \m{\theta} be ergodic.
Due to the concerns in connection with modelling measure preserving
dynamical systems, we will not consider RDS in this article.\par
However, relaxing the conditions on the driving system, we can introduce
the following notion of \emph{measurable nonautonomous dynamical system}.
\begin{definition}\label{def:measrblNDS}
Given measurable monoids \m{\alg{S}} and \m{\alg{T}} such that
\m{\alg{S}\leq \alg{T}} is a submonoid, and measurable spaces
\m{X}, \m{Y}, a pair \m{\apply{\theta,\phi}} of mappings
\m{\functionhead{\theta}{T\times X}{X}} and
\m{\functionhead{\phi}{S\times X\times Y}{Y}} is called
\emph{measurable nonautonomous dynamical system with times
\m{\alg{S}\leq \alg{T}} on \m{Y} with base \m{X}} if
\begin{enumerate}[(1)]
\item \m{\apply{\alg{T}, X, \theta}} is a measurable dynamical system
over the monoid \m{\alg{T}} (as in Definition~\ref{def:measrbl-dyn-sys}),
called \emph{driving system},
\item \m{\phi} is a \emph{measurable cocycle over \m{\theta}}, that is,
\m{\phi} is measurable and fulfils the cocycle property as introduced
in Definition~\ref{def:setNDS}.\qedhere
\end{enumerate}
\end{definition}
\par\smallskip
In the subsequent section we will now see how to understand the notions
presented so far from an abstract, categorical point of view.
\par
%\todo[inline]{%
% Why does Arnold require probability spaces for measure preserving
% DS, and not just measure spaces?
% (see Definition~\ref{def:measure-presDS})}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%% Core Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Dynamical Systems in Abstract Categories}%
\label{sect:dyn-sys-abstr-cat}
To model dynamical systems as coalgebras in abstract categories we are
going to pursue the following strategy. We will move all the additional
conditions that mappings involved in the definition of a dynamical system
have to satisfy (e.g.\ continuity) into the definition of a suitably
chosen category \m{\cat}. For the examples we will be primarily interested
in within this paper, this will mostly be the categories \m{\Top},
\m{\Mea} and \m{\Set} as introduced in
Example~\ref{ex:cats}\eqref{item:Set}--\eqref{item:Mea}.
\par
Then we are going to explore what the two
conditions~\eqref{eq:monoid-action-neutral}
and~\eqref{eq:monoid-action-plus} mentioned at the beginning of
Subsection~\ref{subsect:class-dyn-sys} (see
page~\pageref{eq:monoid-action-neutral}) mean in our abstract context. To
this end we will first define straightforward generalisations of monoids
and monoid actions in abstract categories.
This will allow us to state a very general definition of dynamical system,
which will comprise different variations of dynamical systems found in the
literature.
Further, we will generalise
the definition of nonautonomous dynamical system and show that on the
abstract level these can be understood as a special instance of our
general category theoretic formulation of dynamical system.
\par\smallskip
In our definitions and results we will need certain requirements on the
given category \m{\cat}. For convenience we will most frequently suppose
that \m{\cat} is a finite product category (cf.\
Definition~\ref{def:product-category}). Regarding this assumption, we will
always consider a particular product construction to be fixed in advance
as explained in Remark~\ref{rem:notation-finite-prod-cats}. Moreover, in
some cases we are going to need that certain projection morphisms are
epimorphisms. This is not a condition that we can require to hold
universally as this would exclude our main test cases: clearly, in
\m{\Set}, \m{\Top}, \m{\Mea} projections onto a non\dash{}empty factor
of a product containing an empty factor fail to be epimorphisms (because
the product has an empty carrier set and the map underlying the projection
morphism is not surjective). Nevertheless, in the mentioned categories,
having an empty factor in a product is basically the only case, when
projections fail to be epi. Thus the assumption that some projections are
epimorphisms is indeed a very mild condition.
\par
As topological spaces, measurable spaces etc.\ are, in the context of this
section, just objects of some abstract category, we will denote them
here with standard, non\dash{}boldface symbols as in
Subsection~\ref{subsect:category-prelims}.
\par
\subsection{Monoids and monoid actions in abstract categories}%
\label{subsect:mon-act-abstr-cat}
The purpose of this subsection is to lift the notions of monoid and monoid
action to any abstract category.
\par
\begin{definition}\label{def:Cmonoid}
Let \m{\cat} be a finite product category, \m{T} be an object of \m{\cat},
and \m{\mor{T\times T}{+}{T}} and \m{\mor{T^0}{e}{T}} be morphisms.
\begin{enumerate}[(1)]
\item We call the triple \m{\apply{T,+,e}} a \emph{\nbd{\m{\cat}}monoid setting}.
\item A \nbd{\m{\cat}}monoid setting \m{\apply{T,+,e}} is called a \emph{\nbd{\m{\cat}}monoid} if the following three diagrams commute:
\begin{subequations}\label{eq:Cmonoid}
\begin{equation}\label{eq:Cmonoid-left}
\begin{xy}
\xymatrix{%
T \ar@{.>}@/^1.8em/[rr]^{\tpl{\excl_T e,1_T}}\ar[rrd]_{1_T} & \cong T^0 \times T \ar[r]^-{e \times T} & T\times T \ar[d]^{+}\\
& &T
}%
\end{xy}
\end{equation}
\begin{equation}\label{eq:Cmonoid-right}
\begin{xy}
\xymatrix{%
T \ar@{.>}@/^1.8em/[rr]^{\tpl{1_T,\excl_T e}}\ar[rrd]_{1_T}&\cong T \times T^0 \ar[r]^-{T \times e} & T\times T \ar[d]^{+}\\
&& T
}%
\end{xy}
\end{equation}
\begin{equation}\label{eq:Cmonoid-ass}
\begin{xy}
\xymatrix@!C{%
**[l] (T\times T ) \times T \ar[r]^-{+ \times T} & T\times T \ar[rd]^{+}&\\
&&T.\\
**[l] T\times (T \times T) \ar[r]^-{T \times +} \ar[uu]^{\cong (a_{12})}& T\times T \ar[ru]_{+}&\\
}%
\end{xy}
\end{equation}
\end{subequations}
\end{enumerate}
The dotted arrows have just been added to make the morphism explicit and
add nothing to the commutativity condition. The isomorphism \m{a_{12}}
will be defined in the proof of Lemma~\ref{lem:nat-trans-delta-eta}.
\end{definition}
\par
To model nonautonomous dynamics we need to generalise the concept of
submonoid. The category theoretical answer to this task is, of course, to
use embeddings which are a certain kind of monic (homo)morphisms. However,
category theory does not give a satisfactory one-and-only answer to the
question what an embedding should be. There are various notions of
embedding occurring in specific categories, and most of them represent a
category theoretic concept, in fact a certain type of monomorphism.
However, not all of these specific concepts can be modelled by the same
kind of monomorphism; sometimes just monomorphisms are the right choice
(e.g.\ in the categories of sets, semigroups or rings, respectively),
sometimes additional properties like extremality, strongness or
regularity of the monomorphism (e.g.\ in the categories of
topological, Hausdorff or metric spaces, respectively, cp.~Examples~7.58
on p.~116 of~\cite{cats}) need to be assumed (cf.~the introductory paragraphs to the subsections ``Regular and extremal
monomorphisms'' on p.~114, ``Subobjects'' on p.~122 and
``Embeddings'' on p.~133 of~\cite{cats}, respectively;
see Remark~7.7.6(2) on p.~121 of the same monograph for a list of
different kinds of monomorphisms used in different prominent categories).
So each category comes with its own natural concept of embedding, which is
why we do not define this term in abstract categories apart from requiring
that it must be a monomorphism. We emphasise however, that in all of our
applications we are considering concrete categories (over the category
of sets), where we may use the embedding concept defined as an
initial monomorphism (cp.~\cite[Definition~8.6, p.~134]{cats}; see
also~Examples~8.8 there, for a list of appropriate embedding notions in
familiar categories).\par
\begin{definition}\label{def:mon-hom-emb}
Suppose that \m{\alg[+^{\alg{S}}, e^{\alg{S}}]{S}} and
\m{\alg[+^{\alg{T}}, e^{\alg{T}}]{T}} are \nbd{\m{\cat}}monoid settings in
a finite product category \m{\cat}. We call a morphism \m{\mor{S}{h}{T}}
\begin{enumerate}[(1)]
\item a \emph{homomorphism} between the \nbd{\m{\cat}}monoid settings if
the following two diagrams commute:\\
\begin{subequations}\label{diag:hom-mon-sett}
\begin{minipage}{0.49\linewidth}
\begin{align}\label{diag:hom-mon-plus}
\begin{xy}\xymatrix@!C{%
T\times T\ar[r]^{+^{\alg{T}}}& T\\
S\times S\ar[r]^{+^{\alg{S}}}
\ar[u]^{h\times h}&S\ar[u]_{h}
}\end{xy}
\end{align}
\end{minipage}
\begin{minipage}{0.49\linewidth}
\begin{align}\label{diag:hom-mon-neutr}
\begin{xy}\xymatrix@!C{%
T^0\ar[r]^{e^{\alg{T}}}& T\\
S^0\ar[r]^{e^{\alg{S}}}\ar[u]^{h^0= \excl_{S^0}}& S\ar[u]_{h}
}\end{xy}
\end{align}
\end{minipage}
\end{subequations}
\item an \emph{embedding} if it is a homomorphism and an embedding in
\m{\cat}. We denote this by
\m{\alg{S}\stackrel{h}{\hookrightarrow}\alg{T}} or simply
\m{\alg{S}\hookrightarrow\alg{T}} if the particular embedding morphism
is not interesting or is merely given by an existence condition. We
then say that \m{\alg{S}} \emph{embeds as a submonoid setting} into
\m{\alg{T}}.\qedhere
\end{enumerate}
\end{definition}
\par
Having dealt with the generalisation of monoids in abstract categories, we
can now turn towards their actions.\par
\begin{definition}\label{def:Cmon-act}
Let \m{\cat} be a finite product category and
\m{\apply{T,+,e}} be a \nbd{\m{\cat}}monoid. Furthermore, let \m{X} be
an object in \m{\cat} and \m{\mor{T\times X}{\aLpha}{X}} be a morphism. We
call the pair \m{\apply{X,\mor{T\times X}{\aLpha}{X}}} a
\emph{\nbd{\m{\cat}}monoid action} (of \m{\apply{T,+,e}} on \m{X}) if the
following two diagrams commute
\begin{subequations}\label{eq:Cmon-act}
\begin{equation}\label{eq:Cmon-act-neutral}
\begin{xy}
\xymatrix{%
X\ar@{.>}@/^1.8em/[rr]^{\tpl{\excl_{X} e,1_{X}}}\ar[rrd]_{1_{X}}&\cong T^0 \times X \ar[r]^-{e \times X} & T\times X \ar[d]^{\aLpha}\\
&& X
}%
\end{xy}
\end{equation}
\begin{equation}\label{eq:Cmon-act-plus}
\begin{xy}
\xymatrix@!C{%
**[l] (T\times T ) \times X \ar[r]^-{+ \times X} & T\times X \ar[rd]^{\aLpha}&\\
&&X.\\
**[l] T\times (T \times X) \ar[r]^-{T \times \aLpha} \ar[uu]^{\cong(a_{15})}& T\times X \ar[ru]_{\aLpha}&\\
}%
\end{xy}
\end{equation}
\end{subequations}
Again the dotted arrow has been added for making the morphism explicit,
and the canonical isomorphism \m{a_{15}} will properly be defined in the
proof of Lemma~\ref{lem:nat-trans-delta-eta}.
\end{definition}
\par
\subsection{Abstract dynamical systems}\label{subsect:abstr-dyn-sys}
We will define abstract dynamical systems as a straightforward
generalisation of Definition~\ref{def:top-dyn-sys} using the notions of
\nbd{\m{\cat}}monoid and \nbd{\m{\cat}}monoid action from above.\par
In Section~\ref{sect:dyn-sys-alg-coalg} we are going to establish a
characterisation of such general dynamical systems as certain monadic
algebras for the endo\dash{}functor \m{T \times -} exploiting that
products of the time space with every object in the considered category
exist.
\par
\begin{definition}\label{def:Cdyn-sys}
A \emph{dynamical system on a finite product category \m{\cat}} is a
triple \m{\apply{\apply{T,+,e}, X, \mor{T\times X}{\aLpha}{X}}}, where
\m{X \in \cat} is an object, \m{\apply{T,+,e}} is a \nbd{\m{\cat}}monoid
and \m{\apply{X,\mor{T\times X}{\aLpha}{X}}} is a \nbd{\m{\cat}}monoid
action of \m{\apply{T,+,e}} on \m{X}.
\par
To add some interpretative terminology to this definition, the object
\m{X} will occasionally be called \emph{state space}, \m{T}
\emph{time space}, \m{\apply{T,+,e}} \emph{time structure} and the pair
\m{\apply{X,\mor{T\times X}{\aLpha}{X}}} or simply
\m{\mor{T\times X}{\aLpha}{X}} \emph{transition structure} of the
dynamical system.
\end{definition}\par
The following result makes sure that this is indeed a generalisation of
the notions developed in Subsection~\ref{subsect:class-dyn-sys}.
\begin{corollary}\label{cor:Top-dyn-sys=class-dyn-sys}
The notions of \emPh{topological dynamical system over a monoid} (as in
Definition~\ref{def:top-dyn-sys}) and \emPh{dynamical system on \m{\Top}}
(as in Definition~\ref{def:Cdyn-sys}) coincide.\par
Likewise, the concepts of \emPh{measurable dynamical system over a monoid}
(as in Definition~\ref{def:measrbl-dyn-sys}) and of \emPh{dynamical system
on} the category of measurable spaces \m{\Mea} (as in
Definition~\ref{def:Cdyn-sys}) are the same.
\end{corollary}\par
Of course, in the same way we can use the categories \m{\Metric} of metric
spaces or \m{\Uniform} of uniform spaces, each with continuous mappings as
morphisms, instead of \m{\Top} to study metric dynamics or uniform
dynamics, respectively. With regard to basic aspects this is essentially
the same as equipping the space with its underlying topology and
forgetting about the metric or uniform structure, \ie\ studying dynamical
systems on the full subcategories \m{\Met} and \m{\Unif} of \m{\Top},
given by metrisable and uniformisable spaces, respectively.
\par
%To illustrate a bit the range of Definition~\ref{def:Cdyn-sys}, we give the
%following example of dynamical systems on the category of unary algebras,
%i.e.\ algebras in the sense of universal algebra, having only unary
%fundamental operations, together with their homomorphisms as morphisms.
%
%\begin{example}
%\todo[inline]{give this example}
%\m{\aLpha} being a ds over an algebra \m{\alg[f^A]{A}}, where \m{f} is
%unary, is exactly the same as saying that the pair \m{(f^T,f^A)} is a
%homomorphism of the monoid action \m{(A,\aLpha)} on itself.\par
%We use here \m{f^{T\times T} = f^T\times f^T} and \m{f^{T\times X} =
%f^T\times f^X} as usual for products.\par
%Can this be extended to \nbd{\m{n}}ary operation symbols \m{f} yielding a
%homomorphism from \m{(A,\aLpha)^n} to \m{(A,\aLpha)}?
%\end{example}
%\par
One advantage of our abstract view on dynamical systems is that we now have a
very simple way to translate a given system into others (in possibly different
categories). Indeed, whenever we have a finite product
preserving\footnote{%
This means for a functor \m{\mor{\cat}{F}{\catd}} that whenever \m{P} is a
product of \m{X} and \m{Y} in \m{\cat} with
projections \m{\pr_X} and \m{\pr_Y}, then \m{F\apply{P}} together with
\m{F\apply{\pr_X}} and \m{F\apply{\pr_Y}} is a product of \m{F\apply{X}}
and \m{F\apply{Y}} in \m{\catd}, and that \m{F\apply{I}} is a terminal
object in \m{\catd} whenever \m{I} is one in \m{\cat}.
}
functor between two categories and a dynamical system on one of them, we
also get one on the other category.\par
\begin{remark}
For a finite product category \m{\cat}, a finite product preserving
functor \m{\mor{\cat}{F}{\catd}} into some category \m{\catd} every dynamical system
\[\apply{\apply{T,+,e}, X, \mor{T\times X}{\aLpha}{X}}\]
on \m{\cat} gives rise to a dynamical system
\[\apply{\apply{FT,F+,Fe}, FX, \mor{FT\times FX}{F\aLpha}{FX}}\]
on \m{\catd}.
\end{remark}
\begin{proof}
It is clear that the functor \m{F} transforms the defining commutative
diagrams for the dynamical system
\m{\apply{\apply{T,+,e}, X, \mor{T\times X}{\aLpha}{X}}} into commutative
diagrams in the category \m{\catd}. Since it preserves finite products,
the resulting diagrams also have the correct form to describe a dynamical
system on \m{\catd}. We remark that these diagrams can be adjusted to use
any other product bifunctor on \m{\catd} via the natural isomorphisms
between different products of the same factors. This can be necessary if
one has agreed on a particular product construction in \m{\catd}
beforehand.
%\todo{Do we need strict product preserving functors here?}
\end{proof}
\subsection{Nonautonomous dynamics}\label{subsect:control-sys}
Here we shall give an example how the notion of skew product
system can also be lifted to our abstract setting. In fact, continuous skew
product systems as defined in~\ref{def:ContSPF} have a straightforward
generalisation in abstract categories, called \emph{abstract NDS}, and
Definition~\ref{def:ContSPF} is the specialisation of the general concept
for the category of topological spaces. Subsequently, we will see that for
coinciding time monoids, abstract NDS are in turn a
special instance of our abstract dynamical systems as given in
Definition~\ref{def:Cdyn-sys}, namely in the case where the state space
is a product of two spaces. This is a purely algebraic fact being
true in the abstract categorical setting, no matter what category we
choose.
\par\smallskip
The defining equations for continuous skew product systems clearly
translate into commutative diagrams as we can see in the following
definition.
\begin{definition}\label{def:CSPF}
Suppose \m{\alg[+, e]{S}} and \m{\alg{T}} are \nbd{\m{\cat}}monoids
in a finite product category \m{\cat} such that \m{\alg{S}} embeds as a
submonoid into \m{\alg{T}}. Let \m{X} and \m{Y} be objects in \m{\cat} and
\m{\mor{T\times X}{\theta}{X}} and
\m{\mor{S\times X\times Y}{\phi}{Y}} be morphisms. The pair
\m{\apply{\theta,\phi}} of morphisms is called
\emph{abstract nonautonomous dynamical system (abstract NDS) in \m{\cat}
with times \m{\alg{S}\hookrightarrow \alg{T}} on \m{Y} with base \m{X}} if
\begin{enumerate}[(1)]
\item \m{\apply{\alg{T}, X, \theta}} is a dynamical system on
\m{\cat} over the monoid \m{\alg{T}} (as in Definition~\ref{def:Cdyn-sys}),
called \emph{driving system},
\item \m{\phi} is an \emph{abstract cocycle over \m{\theta}}, that is,
the following two diagrams, called \emph{abstract cocycle property},
\begin{subequations}\label{eq:cocycle-property}
\begin{equation}\label{eq:control-act-neutral}
\begin{xy}
\xymatrix{%
X\times Y\ar@{.>}@/^1.8em/[rrr]^{\tpl{\excl_{X\times Y}
e,1_{X\times Y}}}\ar[rrrd]_{\pr'_{Y}}&\cong S^0 \times \apply{X\times Y}
\ar[rr]^-{e \times \apply{X\times Y}} && S\times \apply{X\times Y} \ar[d]^{\phi}\\
&&& Y
}%
\end{xy}
\end{equation}
\begin{equation}\label{eq:cocyle-prop}
\begin{xy}
\xymatrix@!C{%
**[l] (S\times S ) \times \apply{X \times Y}
\ar[r]^-{+\times \apply{X\times Y}} &
S\times \apply{X\times Y} \ar[rd]^{\phi}&\\
&& Y\\
**[l] S\times (S \times \apply{X\times Y})
\ar[r]^-{S \times \tpl{\tpl{\pr_S,\pr_X}\theta,\phi}}
\ar[uu]^{\cong}& S\times \apply{X\times Y}
\ar[ru]_{\phi}&\\
}%
\end{xy}
\end{equation}
%\begin{align}
%\phi(0, x, y) &= y,\\
%\phi(t+s,x,y) &= \phi(t, \theta(s,x), \phi(s, x, y))
%\end{align}
\end{subequations}
commute. Here \m{\pr_S} and \m{\pr_X} denote the first and second
projection morphism of the product \m{S\times \apply{X\times Y}}, and
\m{\pr'_X} and \m{\pr'_Y} are the projections belonging to \m{X\times Y}.
\qedhere
\end{enumerate}
\end{definition}\par
Evidently, we have the following corollary, which shows that our
definition is sound, i.e.\ that it indeed entails the special case of
continuous skew product system we started from.
\begin{corollary}\label{cor:CSPF-on-Top}
Every continuous skew product system on a topological space with times
\m{\alg{S}\leq \alg{T}} (as in Definition~\ref{def:ContSPF}) is an
abstract NDS on \m{\Top} with times \m{\alg{S}\hookrightarrow\alg{T}} (as
in Definition~\ref{def:CSPF}).\par
Furthermore, every abstract NDS on \m{\Top} with times
\m{\alg{S}\stackrel{\epsilon}{\hookrightarrow}\alg{T}} is a continuous
skew product system with times \m{\epsilon\apply{\alg{S}}\leq \alg{T}},
where \m{\epsilon\apply{\alg{S}}} denotes the image of the topological
monoid \m{\alg{S}} under the embedding \m{\epsilon}, which is isomorphic
to \m{\alg{S}}.
\end{corollary}
\par
Similarly, interpreting Definition~\ref{def:CSPF} in the category of
sets, we obtain nonautonomous dynamical systems.\par
\begin{corollary}\label{cor:CSPF-on-Set}
Every nonautonomous dynamical system on a set with times
\m{\alg{S}\ovflhbx{0.625pt}\leq\ovflhbx{0.626pt} \alg{T}} (as in
Definition~\ref{def:setNDS}) is an abstract
NDS on \m{\Set} with times \m{\alg{S}\hookrightarrow\alg{T}} (as
in Definition~\ref{def:CSPF}).\par
Furthermore, every abstract NDS on \m{\Set} with times
\m{\alg{S}\stackrel{\epsilon}{\hookrightarrow}\alg{T}} is a nonautonomous
dynamical system with times \m{\epsilon\apply{\alg{S}}\leq \alg{T}},
where \m{\epsilon\apply{\alg{S}}} denotes the image of the
monoid \m{\alg{S}} under the embedding \m{\epsilon}, which is isomorphic
to \m{\alg{S}}.
\end{corollary}
\par
Likewise, abstract NDS on \m{\Mea} correspond to measurable NDS
as in Definition~\ref{def:measrblNDS}. An explicit corollary is omitted
for brevity.
\par
Next we prove that for two equal time monoids abstract NDS can be
understood as a special kind of abstract dynamical system. This fact has
been known for concrete cases of dynamical systems, \eg\ continuous
flows (topological dynamical systems as in
Definition~\ref{def:top-dyn-sys} where time is given by the real numbers
with addition) arising as solutions of nonautonomous ordinary differential
equations, \cf~Chapter~IV of~\cite{Sell71TopDynODE}, especially IV.A,
IV.F and Theorem~IV.11.
Our lemma shows that this
result only depends on the algebraic structure behind dynamical
systems, not on the analytic or measure theoretic framework in which it
is placed.
\par
Since nonautonomous dynamics does not lie in the
main focus of this article, we keep the proof sketchy and leave some
details for the reader to work out.
\par
\begin{lemma}\label{lem:cocycle-char-control}
Let \m{X}, \m{Y} belong to a finite product category \m{\cat}, let
\m{\alg[+, e]{T}} be a \nbd{\m{\cat}}monoid setting and
\m{\mor{T\times \apply{X\times Y}}{\Phi}{X\times Y}},
\m{\mor{T\times X}{\theta}{X}} be morphisms in \m{\cat}
satisfying the condition\footnote{As in Definition~\ref{def:CSPF},
\m{\pr'_X} and \m{\pr'_Y} denote the projection morphisms belonging to the
product \m{X\times Y}.}
\m{\Phi \pr'_X= \tpl{\pr_T,\pr_X} \theta}, i.e.\ the \nbd{\m{X}}component
of \m{\Phi} does not depend on \m{Y} and is given by \m{\theta}.
Furthermore, we require that the morphisms\footnote{%
Here \m{\pr_{T_1}}, \m{\pr_{T_2}} and \m{\pr_X} denote the projection
morphisms of \m{T\times\apply{T\times\apply{X\times Y}}} onto the first
factor \m{T}, onto the second factor \m{T} and on the \m{X} component of
the product.
}
\m{\mor{T\times \apply{T \times \apply{X\times Y}}}{%
\tpl{\pr_{T_1}, \tpl{\pr_{T_2},\pr_{X}}}}{%
T\times\apply{T \times X}}}
and \m{\mor{X\times Y}{\pr'_X}{X}} be epi.
Then the following statements are equivalent:
\begin{enumerate}[(a)]
\item The triple
\m{\apply{\alg{T}, X\times Y,
\mor{T\times \apply{X\times Y}}{\Phi}{X\times Y}}}
is a dynamical system on \m{\cat}.
\item The pair \m{\apply{\theta, \Phi\pr'_Y}} is an abstract NDS
in \m{\cat} with times \m{\alg{S} = \alg{T}} on \m{Y} with base
\m{X}.
\end{enumerate}
\end{lemma}
\begin{proof}
The argument is based on transforming the defining condition for the
dynamical system
\m{\apply{\apply{T,+,e},X\times Y,
\mor{T\times \apply{X\times Y}}{\Phi}{X\times Y}}}.
According to Definition~\ref{def:Cdyn-sys}, the notion of dynamical system
is built upon \m{\apply{T,+,e}} being a \nbd{\m{\cat}}monoid and
\m{\apply{X\times Y, \mor{T\times \apply{X\times Y}}{\Phi}{X\times Y}}}
being a \nbd{\m{\cat}}monoid action. The latter fact is a conjunction of
two commuting diagrams, \eqref{eq:Cmon-act-neutral}
and~\eqref{eq:Cmon-act-plus}. These have the form
\begin{equation*}
\begin{xy}
\xymatrix{%
X\times Y\ar@{.>}@/^1.8em/[rrr]^{\tpl{\excl_{X\times Y}
e,1_{X\times Y}}}\ar[rrrd]_{1_{X\times Y}}&\cong T^0
\times \apply{X\times Y} \ar[rr]^-{e \times \apply{X\times
Y}} && T\times \apply{X\times Y} \ar[d]^{\Phi}\\
&&& X\times Y
}%
\end{xy}
\end{equation*}
and
\begin{equation*}
\begin{xy}
\xymatrix@!C{%
**[l] (T\times T ) \times \apply{X \times Y}
\ar[r]^-{+ \times \apply{X\times Y}} &
T\times \apply{X\times Y} \ar[rd]^{\Phi}&\\
&& X\times Y.\\
**[l] T\times (T \times \apply{X\times Y})
\ar[r]^-{T \times \Phi}
\ar[uu]^{\cong}& T\times \apply{X\times Y}
\ar[ru]_{\Phi}&\\
}%
\end{xy}
\end{equation*}
\par
Both diagrams express that two certain morphisms \m{f,g}, starting in the
same object \m{Z} (either \m{X\times Y} or
\m{T\times \apply{T\times \apply{X\times Y}}}) and ending in the product
\m{X\times Y}, are identical. By definition of the product this is
equivalent to the fact that the equalities
\m{f\pr'_X = g\pr'_X} and \m{f\pr'_Y = g\pr'_Y} hold. This means that we
can equivalently replace each of the two diagrams by a conjunction of two
commutative diagrams.
\par
Taking into account the assumption that
\m{\Phi \pr'_X= \tpl{\pr_T,\pr_X} \theta}, we get
\[T \times \tpl{\tpl{\pr_T,\pr_X}\theta,\Phi\pr'_{Y}}
= T \times \tpl{\Phi\pr'_{X},\Phi\pr'_{Y}}
= T \times \Phi,\]
and thus we see that the two diagrams arising from composition with
\m{\pr'_Y} are precisely the ones occurring in
Definition~\ref{def:CSPF}. The other two ones, coming from
composition with \m{\pr'_X}, are equivalent to the two defining diagrams
of the dynamical system
\m{\apply{\apply{T,+,e}, X, \mor{T\times X}{\theta}{X}}}.
This can be seen from a short calculation using again the assumption
\m{\Phi \pr'_X= \tpl{\pr_T,\pr_X} \theta}.
\begin{comment}
This can be seen from a short calculation using again the condition
\m{\Phi \pr'_X= \tpl{\pr_T,\pr_X} \theta} and the assumption that the two
projection morphisms mentioned in the statement of the lemma are epi. For
further details we refer to~\cite{}.
\end{comment}
\par
We show this exemplarily for the second diagram. Denoting the canonical
isomorphism between \m{T\times \apply{T\times \apply{X\times Y}}} and
\m{\apply{T\times T}\times \apply{X\times Y}} by \m{a}, the equality of
interest is
\[a \apply{+\times \apply{X\times Y}} \Phi\pr'_X
=\apply{T\times \Phi} \Phi\pr'_X.\]
Using the projection morphisms \m{\pr_{T_1}}, \m{\pr_{T_2}}, \m{\pr_{X}}
and \m{\pr_{Y}} belonging to the product
\m{T\times (T \times \apply{X\times Y})} in the order of the factors
read from left to right, one can rewrite the left\dash{}hand side as
\begin{align*}
a \apply{+\times \apply{X\times Y}} \Phi\pr'_X
&=a \tpl{\tpl{\pr_{T_1},\pr_{T_2}}+,\pr_X,\pr_Y} \Phi\pr'_X\\
&=a \tpl{\tpl{\pr_{T_1},\pr_{T_2}}+,\pr_X,\pr_Y}\tpl{\pr_T,\pr_X} \theta\\
&=a \tpl{\tpl{\pr_{T_1},\pr_{T_2}}+,\pr_X} \theta \\
&=\tpl{\pr_{T_1},\tpl{\pr_{T_2},\pr_{X}}}b \apply{+\times X} \theta,
\end{align*}
where \m{\tpl{\pr_{T_1},\tpl{\pr_{T_2},\pr_{X}}}} is the projection on
\m{T\times \apply{T\times X}} and \m{b} is the isomorphism in
diagram~\eqref{eq:Cmon-act-plus} belonging to \m{\theta}. Similarly, we
have for the other side
\begin{align*}
\apply{T\times \Phi} \Phi\pr'_X
&= \tpl{\pr_{T_1},\tpl{\pr_{T_2},\tpl{\pr_X,\pr_Y}}\Phi}\Phi\pr'_X\\
&= \tpl{\pr_{T_1},\tpl{\pr_{T_2},\tpl{\pr_X,\pr_Y}}\Phi}\tpl{\pr_T,\pr_X}
\theta\\
&= \tpl{\pr_{T_1},\tpl{\pr_{T_2},\tpl{\pr_X,\pr_Y}}\Phi\pr'_X}\theta\\
&= \tpl{\pr_{T_1},\tpl{\pr_{T_2},\tpl{\pr_X,\pr_Y}}\tpl{\pr_T,\pr_X}
\theta}\theta\\
&= \tpl{\pr_{T_1},\tpl{\pr_{T_2},\pr_X}\theta}\theta\\
&= \tpl{\pr_{T_1},\tpl{\pr_{T_2},\pr_{X}}}\apply{T\times \theta}\theta.
\end{align*}
Hence, if \m{\apply{\apply{T,+,e}, X, \mor{T\times X}{\theta}{X}}} is a
dynamical system, then the desired equality follows. Since
\m{\tpl{\pr_{T_1},\tpl{\pr_{T_2},\pr_{X}}}} is an epimorphism, also the
converse implication holds.
\end{proof}
\section{Dynamical Systems as Algebras and Coalgebras}%
\label{sect:dyn-sys-alg-coalg}
\subsection{From monoids to monads}%
\label{subsect:monoids-to-monads}
Here we are going to explore the connection of \nbd{\m{\cat}}monoids and
their actions to monads and monadic algebras. For this we need to assume
that for some object \m{T} from \m{\cat} all products \m{T\times X} exist
for \m{X} in \m{\cat}. This allows us to define the
endo\dash{}functor \m{T\times -} on \m{\cat}. Of course in finite product
categories, this assumption is certainly valid.
\par
The main and only result of this subsection is a lemma connecting the
commutativity conditions from the definitions of a \nbd{\m{\cat}}monoid
and a \nbd{\m{\cat}}monoid action with certain commutative diagrams for
two derived natural transformations. In the next subsection we shall use
this lemma to translate abstract \nbd{\m{\cat}}monoids into monads and
\nbd{\m{\cat}}monoid actions into monadic algebras for the monad
associated with the \nbd{\m{\cat}}monoid.
\par
\begin{lemma}\label{lem:nat-trans-delta-eta}
Suppose \m{\cat} is a finite product category with the endo\dash{}functor
\m{T\times -} for some object \m{T} and let
%Let \m{\cat} be a finite product category with the endo\dash{}functor
%\m{T\times -} for some object \m{T} and let
\m{\apply{T,+,e}} be a \nbd{\m{\cat}}monoid setting. For every object
\m{X} from \m{\cat} let the morphisms \m{\eta_{X}} and \m{\delta_{X}} be
defined by the commutativity of the following diagrams
\[\begin{xy}\xymatrix{ X \ar@{-->}@/^1.5em/[rr]^-{\eqdef \eta_{X} = \tpl{\excl_{X}e, 1_{X}}} &\cong T^0 \times X \ar[r]_-{e \times X} & T\times X} \end{xy}\]
and
\[\begin{xy}\xymatrix{%
& T\times (T \times X)\ar[rrd]^-{a_2} \ar[ld]_-{a_1}\ar[dd]^{\exists ! a_7}_{\stackrel{\tpl{a_1,a_2a_3}=}{T \times a_3}}\ar@{-->}@/^2.5em/[dddd]^(0.36){\eqdef\delta_{X}=\tpl{a_7+,a_2a_4}}\\
T &&&T \times X \ar[ldd]_{a_3}\ar[ddd]^{a_4}\\
&T\times T \ar[lu]_{a_5} \ar[rd]^(0.65){a_6} \ar[ldd]_{+}\\
&&T\\
T&T \times X \ar[l]_{a_3} \ar[rr]^{a_4}&&X
} \end{xy}\]
(where the morphisms \m{a_i}, \m{i \neq 7}, are projection morphisms of the respective products). Then
\begin{enumerate}[(a)]
\item\label{item:def-delta-eta} \m{\mor{1_{\cat}}{\eta}{T \times -}} and \m{\mor{T\times (T\times -)}{\delta}{T\times -}} are natural transformations.
\item\label{item:etaTxXdeltaX-eq} For an object \m{X\in \cat} and the projection morphism \m{\mor{T \times X}{a_3}{T}}, the conditions \m{a_3\tpl{\excl_T e,1_T}+ = a_3 \cong (e \times T) + = a_3} and \m{\eta_{T\times X} \delta_{X} = 1_{T\times X}} are equivalent.
\item\label{item:etaTxXdeltaX-1} If \m{\apply{T,+,e}} satisfies condition~\eqref{eq:Cmonoid-left}, then the diagrams
\begin{equation}\label{eq:Tmon-left}
\begin{xy}\xymatrix{T \times X \ar[r]^-{ \eta_{T \times X}} \ar[dr]_{1_{T \times X}}& T \times (T \times X)\ar[d]^{\delta_{X}}\\&T \times X}
\end{xy}
\end{equation}
commute for all \m{X\in \cat}. If the projection morphism \m{\mor{T \times X}{a_3}{T}} is epi for one \m{X \in \cat}, then the converse implication is true, as well.
\item\label{item:TxetaXdeltaX-eq} For an object \m{X\in \cat} and the projection morphism \m{\mor{T \times X}{a_3}{T}}, the conditions \m{a_3\tpl{1_T,\excl_T e}+ = a_3 \cong (T \times e) + = a_3} and \m{(T\times \eta_{X} )\delta_{X} = 1_{T\times X}} are equivalent.
\item\label{item:TxetaXdeltaX-1} If \m{\apply{T,+,e}} satisfies condition~\eqref{eq:Cmonoid-right}, then the diagrams
\begin{equation}\label{eq:Tmon-right}
\begin{xy}\xymatrix{T \times X \ar[r]^-{T \times \eta_{X}} \ar[dr]_{1_{T \times X}}& T \times (T \times X)\ar[d]^{\delta_{X}}\\&T \times X}\end{xy}
\end{equation}
commute for all \m{X\in \cat}. If the projection morphism \m{\mor{T \times X}{a_3}{T}} is epi for one \m{X \in \cat}, then the converse implication is true, as well.
\item\label{item:deltaTxXdeltaX-TxdeltaXdeltaX} For an object \m{X\in \cat} and the isomorphism \m{\mor{T \times (T\times T)}{a_{12}}{(T\times T) \times T}} the following equalities hold
\begin{align}
\delta_{T\times X}a_7+ &= (T \times a_7) a_{12} (+ \times T) + \label{eq:deltaTxXa7+}\\
(T \times \delta_{X}) a_7+ &= (T \times a_7)(T \times +)+\label{eq:TxdeltaXa7+}.
\end{align}
Furthermore, the equality \m{\delta_{T \times X} \delta_{X} = (T\times \delta_{X}) \delta_{X}} is equivalent to
\begin{equation*}
\delta_{T\times X}a_7+ =(T \times \delta_{X}) a_7+
\end{equation*}
and consequently to \m{(T \times a_7) a_{12} (+ \times T) + = (T \times a_7)(T \times +)+}.
\item\label{item:Tmon-ass} If \m{\apply{T,+,e}} satisfies condition~\eqref{eq:Cmonoid-ass}, then the diagrams
\begin{equation}\label{eq:Tmon-ass}
\begin{xy}\xymatrix@!C{T\times(T\times (T \times X)) \ar[r]^-{\delta_{T\times X}}\ar[d]_{T \times \delta_{X}}& T\times (T \times X) \ar[d]^{\delta_{X}} \\ T \times (T \times X) \ar[r]_{\delta_{X}} & T \times X}
\end{xy}
\end{equation}
commute for all \m{X\in \cat}. If
\m{\mor{T\times(T\times (T \times X))}{T \times a_7}{T\times (T\times T)}}
is an epimorphism for one \m{X \in \cat}, then the converse implication is
true, as well.
\item\label{item:Cmon-Tmon} If \m{\apply{T,+,e}} is a
\nbd{\m{\cat}}monoid, then \m{(T\times -, \delta, \eta)} is a monad. If
the projection morphisms \m{\mor{T \times X}{a_3}{T}} and
\m{\mor{T\times(T\times (T \times Y))}{T \times a_7}{T\times (T\times T)}}
are epi for some objects \m{X,Y \in \cat}, then the converse also holds.
\item\label{item:Cmon-act-Tmon-alg} Let an object \m{X \in \cat} and
a morphism \m{\mor{T \times X}{\aLpha}{X}} be given. For the
isomorphism
\m{\mor{T \times (T\times X)}{a_{15}}{(T\times T) \times X}}
from condition~\eqref{eq:Cmon-act-plus}
the following equality holds
\[a_{15} (+ \times X) = \delta_{X},\]
whence diagram~\eqref{eq:Cmon-act-plus} commutes if and only if
\begin{subequations}\label{eq:Tmon-alg}
\begin{equation}\label{eq:Tmon-alg-delta}
\begin{xy}
\xymatrix@!C{%
T \times (T \times X)\ar[r]^-{T \times \aLpha} \ar[d]_{\delta_{X}}& T \times X \ar[d]^{\aLpha}\\
T \times X \ar[r]_{\aLpha}& X
}
\end{xy}
\end{equation}
commutes, and diagram~\eqref{eq:Cmon-act-neutral} commutes if and
only if
\begin{equation}\label{eq:Tmon-alg-eta}
\begin{xy}
\xymatrix@!C{%
X\ar[r]^{\eta_{X}}\ar[rd]_{1_{X}} & T \times X\ar[d]^{\aLpha} \\
& X
}
\end{xy}
\end{equation}
\end{subequations}
commutes.
\end{enumerate}
\end{lemma}
\begin{proof} We start the proof with reminding the reader how the functor
\m{T\times -} operates on morphisms \m{\mor{X}{f}{Y}}, where \m{X,Y}
are arbitrary objects of \m{\cat}. The morphism
\m{\mor{T \times X}{T \times f}{T \times Y}} is uniquely determined by the
commutativity of the following diagram (see also
Example~\ref{ex:functors}\eqref{item:product-functor})
\begin{equation}\label{diag:Txf}\begin{xy}\xymatrix{%
& T\\
T \times X \ar@{-->}[r]^-{T \times f}\ar[ru]^-{a_3} \ar[d]_{a_4}& T \times Y \ar[u]_{b_3} \ar[d]^-{b_4}\\
X \ar[r]_{f} &Y,
}\end{xy}\end{equation}
where the morphisms \m{a_3,a_4,b_3,b_4} are projection morphisms belonging to the products \m{T \times X} and \m{T \times Y}.
\begin{enumerate}[(a)]
\item To show that \m{\eta} and \m{\delta} are natural transformations, we fix objects \m{X,Y \in \cat} and a morphism \m{\mor{X}{f}{Y}} between them.
It has to be shown that
\[f \eta_{Y} = \eta_x T \times f \qquad \text{and}\qquad T \times (T \times f) \delta_{Y} = \delta_{X} T \times f.\]
For the first equality let us mention that the commutativity of the following diagram is equivalent to the definition of \m{\eta_{X}}
\begin{equation}\label{diag:etaX}
\begin{xy}
\xymatrix{%
& X\\
X \ar@{-->}[r]^-{\eta_{X}}\ar[ru]^-{1_{X}} \ar[d]_{\excl_{X}}& T \times X \ar[u]_{a_4} \ar[d]^-{a_3}\\
T^0 \ar[r]_{e} &T,
}
\end{xy}
\end{equation}
since \m{T\times X} is a product with projections \m{a_{3}} and
\m{a_{4}}. The proof of the desired equality is contained in the
commutativity of the following diagram:
\[\begin{xy}\xymatrix{%
&&&&X\ar[dddd]^{f}\\
X\ar[dd]_{f}\ar[rd]^{\excl_{X}}\ar[rrrru]^-{1_{X}}\ar[rrr]^{\eta_{X}} &&&T \times X \ar[ru]_-{a_4}\ar[dd]^{T \times f}\ar[dl]^{a_3}\\
& T^0 \ar[r]^{e} &T\\
Y\ar[ru]_{\excl_{Y}}\ar[rrrrd]^-{1_{Y}}\ar[rrr]^-{\eta_{Y}} &&&T \times Y \ar[rd]^-{b_4}\ar[ul]_{b_3}\\
&&&&Y,\\
}\end{xy}\]
where the triangle on the left commutes by the definition of the
terminal object \m{T^0}, the central quadrangles and the triangles
on top and bottom commute by the definition of \m{\eta}
(cf.~\eqref{diag:etaX}), and the triangle and the quadrangle on
the right commute by the definition of \m{T \times f}
(cf.~\eqref{diag:Txf}).
\par
\enlargethispage{\baselineskip}
From this it follows that
\begin{align*}
f\eta_{Y}b_3
&= f \excl_{Y}e = \excl_{X} e = \eta_{X} a_3 = \eta_{X} (T \times f) b_3\\
f\eta_{Y}b_4
&= f 1_{Y} = 1_{X} f = \eta_{X} a_4 f =\eta_{X} (T\times f) b_4,
\end{align*}
and the conjunction of these two equalities is equivalent to \m{f
\eta_{Y} = \eta_{X} T \times f} since \m{T \times Y} together
with \m{b_{3}}, \m{b_{4}} is a product.\par
The proof of the remaining equality, \m{T \times (T \times f) \delta_{Y} = \delta_{X} T \times f}, is a bit more technical but uses the same ideas
as just presented. First we link the defining diagrams for \m{\delta_{X}} and \m{\delta_{Y}} in the following scheme:
\begin{equation*}
\begin{xy}\xymatrix{%
& T\times (T \times X)\ar[rrdd]^-{a_2} \ar[ld]_-{a_1}\ar[dd]^(0.45){a_7}\ar@/^2.5em/[dddd]^(0.36){\delta_{X}}\ar[rrrr]^{T \times (T \times f)}&&&%
& T\times (T \times Y)\ar[rrdd]^-{b_2} \ar[ld]_-{b_1}\ar[dd]^{b_7}\ar@/^2.5em/[dddd]^(0.36){\delta_{Y}}&&&\\
T \ar[rrrr]_(0.75){1_T}&&&&%
T &&&&\\
&T\times T\ar@/_1.5ex/[rrrr]_(0.7){1_{T \times T}} \ar[lu]_{a_5} \ar[rd]^(0.65){a_6} \ar[lddd]_{+}&&T \times X \ar[ld]_{a_3}\ar[ddd]^{a_4} \ar'[rr]^(0.5){T \times f}[rrrr]&%
&T\times T \ar[lu]_{a_5} \ar[rd]^(0.65){a_6} \ar[lddd]_{+}&&T \times Y \ar[ld]_{b_3}\ar[ddd]^{b_4}&\\
&&T\ar[rrrr]^{1_T}&&%
&&T&&\\
&T \times X \ar[ld]_{a_3} \ar[rrd]^{a_4}\ar[rrrr]^(0.3){T \times f}&&&%
&T \times Y \ar[ld]_{b_3} \ar[rrd]^{b_4}&&&\\
T\ar@/_1.5ex/[rrrr]^{1_T}&&&X\ar@/_1.5ex/[rrrr]^{f}&%
T&&&Y.&
}\end{xy}\acceptoverfulbox{-3cm}
\end{equation*}
Again, as \m{T \times Y} is a product with projections
\m{b_{3}}, \m{b_{4}}, the desired equality is equivalent to the
conjunction of
\[T \times (T \times f) \delta_{Y}b_3 = \delta_{X} (T \times f)b_3
\quad\text{and}\quad
T \times (T \times f) \delta_{Y}b_4 = \delta_{X} (T \times f)b_4.\]
First, note that
\begin{align*}
a_7 1_{T \times T} a_5 &= a_7 a_5 1_T
\bydef{a_7} a_1 1_T
\bydef{T \times (T \times f)} T \times (T \times f) b_1
\bydef{b_7} T \times (T \times f) b_7 a_5
\intertext{and}
a_7 1_{T \times T} a_6
&=a_7 a_6 1_T \bydef{a_7} a_2 a _3 1_T
\bydef{T \times f} a_2(T \times f) b_3
\bydef{T \times (T \times f)} T \times (T \times f) b_2 b_3\\
&\bydef[]{b_7} T \times (T \times f) b_7 a_6,
\end{align*}
whence \m{a_7 1_{T \times T} = T \times (T \times f) b_7} follows
due to \m{T \times T} being a product with projections
\m{a_{5}}, \m{a_{6}}. Using this one obtains
\begin{align*}
\delta_{X}(T \times f)b_3\quad
&\bydef[]{T \times f} \delta_{X} a_3 1_T
\bydef{\delta_{X}} a_7 + 1_T
= a_7 1_{T \times T} +
\vs T \times (T \times f) b_7 + \\
&\bydef[]{\delta_{Y}} T \times (T \times f) \delta_{Y} b_3.
\end{align*}
Likewise, one can show
\begin{align*}
\delta_{X}(T \times f)b_4\quad
&\bydef[]{T \times f} \delta_{X} a_4 f
\bydef{\delta_{X}} a_2 a_4 f
\bydef{T \times f} a_2 (T \times f) b_4\\
&\bydef[]{T \times (T \times f)} T \times (T \times f) b_2 b_4
\bydef{\delta_{Y}} T \times (T \times f) \delta_{Y} b_4,
\end{align*}
finishing the proof of this item.
\item We fix an object \m{X} of \m{\cat} and start to demonstrate a
number of auxiliary equalities that are needed for our equivalence.
The following diagram derived from diagram~\eqref{diag:etaX} will
be useful
\[\begin{xy}\xymatrix@!C{%
& T \times X\\
T \times X \ar[r]^-{\eta_{T \times X}}\ar[ru]^-{1_{T\times X}} \ar[d]_{\excl_{T \times X}}& T\times (T \times X) \ar[u]_{a_2} \ar[d]^-{a_1}\\
T^0 \ar[r]_{e} &T,
}\end{xy}\]
since it expresses the definition of \m{\eta_{T \times X}}.
First, it is
\[\eta_{T \times X}\delta_{X} a_4
\bydef{\delta_{X}} \eta_{T \times X}a_2a_4
\bydef{\eta_{T \times X}} 1_{T \times X} a_4 = a_4.\]
Second, we have
\begin{align*}
\eta_{T \times X} a_7 a_5\
&\bydef[]{a_7} \eta_{T \times X} a_1
\bydef{\eta_{T\times X}} \excl_{T \times X}e
= a_3\excl_Te = a_3 \tpl{\excl_Te,1_T} a_5
\intertext{and}
\eta_{T \times X} a_7 a_6\
&\bydef[]{a_7} \eta_{T \times X} a_2 a_3
\bydef{\eta_{T \times X}} 1_{T \times X}a_3
= a_3 1_T = a_3\tpl{\excl_Te,1_T}a_6,
\end{align*}
whence we obtain \m{\eta_{T \times X} a_7 = a_3\tpl{\excl_Te,1_T}}
as \m{T \times T} is a product with projections \m{a_{5}} and
\m{a_{6}}. Consequently, we get
\m{
\eta_{T \times X}\delta_{X} a_3 \bydef{\delta_{X}} \eta_{T \times
X} a_7 + \vs a_3\tpl{\excl_Te,1_T} +}.
Since \m{T \times X} with \m{a_{3}} and \m{a_{4}} is a product,
the equality \m{\eta_{T \times X}\delta_{X} = 1_{T \times X}} is
equivalent to the conjunction of
\m{\eta_{T \times X}\delta_{X} a_3 = a_3} and
\m{\eta_{T \times X}\delta_{X} a_4 = a_4},
the latter of which is generally true by what has been shown
above. Hence the equality
\m{\eta_{T \times X}\delta_{X} = 1_{T\times X}}
holds if and only if
\m{a_3\tpl{\excl_Te,1_T} +
\vs \eta_{T \times X}\delta_{X} a_3 = a_3}.
\item For any \m{X} in \m{\cat}, condition~\eqref{eq:Cmonoid-left}
implies, by composition from the left with the respective
projection morphism \m{\mor{T \times X}{a_3}{T}}, that
\m{a_3\tpl{\excl_T e,1_T}+=a_3}. This is, by
item~\eqref{item:etaTxXdeltaX-eq}, equivalent to the commutativity
of diagram~\eqref{eq:Tmon-left}.\par
If, conversely, diagram~\eqref{eq:Tmon-left} commutes for all \m{X}
in \m{\cat}, this means that the equality
\m{a_3\tpl{\excl_T e,1_T}+ = a_3} holds for every object \m{X} of
\m{\cat}. If \m{a_3} can be cancelled from the left in this
equality for at least one object \m{X} of \m{\cat} (e.g.\ if
\m{a_3} is epi), then obviously condition~\eqref{eq:Cmonoid-left},
\ie\ \m{\tpl{\excl_T e,1_T}+ = 1_{T}}, follows.
\item This proof is similar to that of item~\eqref{item:etaTxXdeltaX-eq}.
We fix an object \m{X \in \cat} and start to show some equalities
that are needed for the statement.
The following diagram expressing the definition of
\m{T \times \eta_{X}} can be obtained from~\eqref{diag:Txf}:
\[\begin{xy}\xymatrix@!C{%
& T\\
T \times X \ar[r]^-{T \times \eta_{X}}\ar[ru]^-{a_3} \ar[d]_{a_4}& T \times (T \times X) \ar[u]_{a_1} \ar[d]^-{a_2}\\
X \ar[r]_{\eta_{X}} &T \times X.
}\end{xy}\]
First, it is
\begin{align*}
(T \times \eta_{X})\delta_{X} a_4\
&\bydef[]{\delta_{X}} (T \times \eta_{X})a_2a_4
\bydef{T \times \eta_{X}} a_4 \eta_{X} a_4
\bydef{\eta_{X}} a_4 1_{X} =a_4.
\intertext{Second, we have}
(T \times \eta_{X})a_7a_5\
&\bydef[]{a_7} (T \times \eta_{X}) a_1
\bydef{T \times \eta_{X}} a_3
= a_3 1_T = a_3 \tpl{1_T,\excl_T e}a_5
\intertext{and}
(T \times \eta_{X})a_7a_6\
&\bydef[]{a_7} (T \times \eta_{X}) a_2 a_3
\bydef{T \times \eta_{X}} a_4 \eta_{X} a_3
\bydef{\eta_{X}} a_4 \excl_{X} e
= \excl_{T \times X} e\\
&= a_3 \excl_T e = a_3 \tpl{1_T,\excl_T e}a_6,
\end{align*}
whence we obtain
\m{(T \times \eta_{X})a_7= a_3 \tpl{1_T,\excl_T e}}
as \m{T \times T} is a product with projections \m{a_{5}} and
\m{a_{6}}. Consequently, we get
\[(T \times \eta_{X})\delta_{X} a_3
\bydef{\delta_{X}} (T \times \eta_{X})a_7 +
\vs a_3 \tpl{1_T,\excl_T e} +.\]
Since \m{T \times X} with \m{a_{3}}, \m{a_{4}} is a product,
the equality \m{(T \times \eta_{X})\delta_{X} = 1_{T \times X}} is
equivalent to the conjunction of
\m{(T \times \eta_{X})\delta_{X} a_3 = a_3}
and \m{(T \times \eta_{X})\delta_{X} a_4 = a_4},
the latter of which is generally true by what has been shown
above. Therefore, the condition
\m{(T \times \eta_{X})\delta_{X} = 1_{T \times X}} is satisfied
if and only if the equality
\m{a_3 \tpl{1_T,\excl_T e} + \vs (T \times\eta_{X})\delta_{X} a_3
= a_3}
holds.
\item This proof is similar to that of item~\eqref{item:etaTxXdeltaX-1}.
For any \m{X} in \m{\cat}, condition~\eqref{eq:Cmonoid-right}
implies, by composition from the left with the respective
projection morphism \m{\mor{T \times X}{a_3}{T}}, the equality
\m{a_3\tpl{1_T,\excl_T e} + =a_3}. The latter is, by
item~\eqref{item:TxetaXdeltaX-eq}, equivalent to the commutativity
of diagram~\eqref{eq:Tmon-right}.\par
If, conversely, diagram~\eqref{eq:Tmon-right} commutes for all
\m{X} in \m{\cat}, this means that the equality
\m{a_3 \tpl{1_T,\excl_T e} + = a_3} holds for every object
\m{X} of \m{\cat}. If \m{a_3} can be cancelled from the left in
this equality for at least one object \m{X} of \m{\cat} (e.g.\ if
\m{a_3} is epi), then obviously
condition~\eqref{eq:Cmonoid-right}, \ie\
\m{\tpl{1_T,\excl_T e} + = 1_{T}}, follows.
\item Again we consider a fixed object \m{X} from \m{\cat}. For this
part we will need the defining diagrams for
\m{T \times \delta_{X}}, \m{T \times a_7}, \m{+ \times T},
\m{\delta_{T \times X}} and the not yet specified
canonical isomorphism \m{a_{12}} from
diagram~\eqref{eq:Cmonoid-ass}:
\[
\begin{xy}\xymatrix@!C{%
& T\\
T \times (T \times (T \times X)) \ar[r]^-{T \times \delta_{X}}\ar[ru]^-{a_1'} \ar[d]_{a_2'}& T \times (T \times X) \ar[u]_{a_1} \ar[d]^-{a_2}\\
T\times (T \times X) \ar[r]_{\delta_{X}} &T \times X,
}\end{xy}\quad%
\begin{xy}\xymatrix{%
& T\\
T \times (T \times (T \times X)) \ar[r]^-{T \times a_7}\ar[ru]^-{a_1'} \ar[d]_{a_2'}& T \times (T \times T) \ar[u]_{a_8} \ar[d]^-{a_9}\\
T\times (T \times X) \ar[r]_{a_7} &T \times T,
}\end{xy}\acceptoverfulbox{-2cm}\]
\[\begin{xy}\xymatrix{%
& T \times (T\times (T \times X))\ar[rrd]^-{a_2'} \ar[ld]_-{a_1'}\ar[dd]^{a_7'}_{T \times a_1=}\ar@/^2.5em/[dddd]^(0.36){\delta_{T \times X}}\\
T &&&T \times (T \times X) \ar[ldd]_{a_1}\ar[ddd]^{a_2}\\
&T\times T \ar[lu]_{a_5} \ar[rd]^(0.65){a_6} \ar[ldd]_{+}\\
&&T\\
T&T \times (T \times X) \ar[l]_{a_1} \ar[rr]^{a_2}&&T \times X,
}\end{xy}
\]
\[\begin{xy}\xymatrix@!C{%
&T\times (T \times T) \ar[r]^{a_9}\ar[dl]_{T \times a_5}\ar@{-->}[d]_{a_{12}}^{=\tpl{T \times a_5, a_9a_6}}& T \times T\ar[d]^{a_6}\\
T\times T &\ar[l]^-{a_{10}}(T\times T)\times T\ar[r]_-{a_{11}}&T,\\
T\times T\ar[d]_{+} & \ar[l]_-{a_{10}}(T \times T)\times T \ar[d]^{+\times T}\ar[r]^-{a_{11}}& T\\
T &\ar[l]^{a_5} T\times T. \ar[ru]_{a_6}
}\end{xy}\]
Now we show equalities~\eqref{eq:deltaTxXa7+}
and~\eqref{eq:TxdeltaXa7+}. To this end we note that
\begin{multline*}
\delta_{T \times X}a_7 a_5 \bydef{a_7} \delta_{T \times X}a_1
\bydef{\delta_{T \times X}} a_7' +
\bydef{a_7'} (T \times a_1) + \bydef{a_7} T \times (a_7a_5)+ \\
= (T \times a_7)(T \times a_5)+
\bydef{a_{12}}(T \times a_7)a_{12}a_{10}+
\bydef{+ \times T} (T \times a_7)a_{12}(+\times T)a_5
\end{multline*}
and
\begin{align*}
\delta_{T \times X}a_7 a_6
\bydef{a_7} \delta_{T \times X} a_2 a_3 \quad
&\bydef[]{\delta_{T \times X}} a_2' a_2 a_3
\bydef{a_7} a_2' a_7 a_6
\bydef{T \times a_7} (T \times a_7)a_9 a_6\\
&\bydef[]{a_{12}} (T\times a_7) a_{12} a_{11}
\bydef{+ \times T} (T\times a_7)a_{12}(+\times T) a_6,
\end{align*}
whence we obtain that
\m{\delta_{T \times X} a_7 = (T \times a_7) a_{12}(+\times T)}
as \m{T \times T} is a product with projections \m{a_{5}} and
\m{a_{6}}. Composition with \m{+} on the right\dash{}hand side
then yields equality~\eqref{eq:deltaTxXa7+}.
\par
Equality~\eqref{eq:TxdeltaXa7+} follows from
\[(T \times \delta_{X}) a_7
\bydef{a_7} (T \times \delta_{X}) (T \times a_3)
= T\times (\delta_{X} a_3)
\bydef{\delta_{X}} T \times (a_7 +)
= (T\times a_7) (T\times +)\]
by composition with \m{+} on the right\dash{}hand side.\par
Note that
\begin{align*}
\delta_{T \times X}\delta_{X} a_4
\bydef{\delta_{X}} \delta_{T\times X}a_2a_4
\bydef{\delta_{T \times X}} a_2' a_2 a_4
\bydef{\delta_{X}} a_2'\delta_{X} a_4 \quad
&\bydef[]{T \times \delta_{X}} (T \times \delta_{X})a_2 a_4 \\
&\bydef[]{\delta_{X}} (T \times \delta_{X}) \delta_{X} a_4.
\end{align*}
This implies, as \m{T \times X} with \m{a_{3}}, \m{a_{4}} is a
product, that
\m{\delta_{T\times X} \delta_{X} = (T\times\delta_{X}) \delta_{X}}
is equivalent to
\m{\delta_{T\times X} \delta_{X} a_3
= (T \times \delta_{X}) \delta_{X} a_3}.
Since \m{\delta_{X} a_3 = a_7 +} holds by definition of
\m{\delta_{X}}, the previous equality is equivalent to
\m{\delta_{T \times X} a_7 + = (T\times \delta_{X}) a_7 +}.
Combining this with equalities~\eqref{eq:deltaTxXa7+}
and~\eqref{eq:TxdeltaXa7+} finishes the proof of this item.
\item If diagram~\eqref{eq:Cmonoid-ass} commutes, then for every
\m{X} in \m{\cat}, one obtains, by composition with \m{T\times a_7}
from the left\dash{}hand side, the equality
\[ (T\times a_7)a_{12} (+ \times T)+
= (T \times a_7) (T \times +)+,\]
which, by the previous item, is equivalent to commutativity of
diagram~\eqref{eq:Tmon-ass}.
\par
If, conversely, diagram~\eqref{eq:Tmon-ass} commutes for all
\m{X} in \m{\cat} and for some object \m{X} of \m{\cat} the
morphism \m{T \times a_7} is cancellable in the equation
\begin{equation*}
(T\times a_7)a_{12} (+ \times T)+ = (T \times a_7) (T \times +)+,
\end{equation*}
then also the converse implication is true. This is, for instance,
the case if \m{T \times a_7} is an epimorphism.
\item If \m{(T,+,e)} is a \nbd{\m{\cat}}monoid, then the three
diagrams~\eqref{eq:Cmonoid} commute. Using the
items~\eqref{item:etaTxXdeltaX-1}, \eqref{item:TxetaXdeltaX-1}
and~\eqref{item:Tmon-ass} above, one obtains from this that for
any object \m{X} in \m{\cat} the diagrams~\eqref{eq:Tmon-left},
\eqref{eq:Tmon-right} and~\eqref{eq:Tmon-ass} commute,
equivalently that \m{(T \times -, \delta, \eta)} is a monad.
\par
The additional assumptions on the morphisms in this item ensure
that the implications stated in items~\eqref{item:etaTxXdeltaX-1},
\eqref{item:TxetaXdeltaX-1} and~\eqref{item:Tmon-ass} are actually
logical equivalences. Hence, the shown implication can be reversed
and one obtains that \m{(T,+,e)} is a \nbd{\m{\cat}}monoid.
\item We fix an object \m{X} of \m{\cat} and a morphism
\m{\mor{T \times X}{\aLpha}{X}}. For this part we need the
defining diagrams for the morphism \m{+ \times X} and the
isomorphism \m{a_{15}} from diagram~\eqref{eq:Cmon-act-plus}:
\[\begin{xy}\xymatrix@!C{%
&T\times (T \times X) \ar[r]^{a_2}\ar[dl]_{a_7}\ar@{-->}[d]_{a_{15}}^{=\tpl{a_7, a_2a_4}}& T \times X\ar[d]^{a_4}\\
T\times T &\ar[l]^-{a_{13}}(T\times T)\times X\ar[r]_-{a_{14}}&X,\\
T\times T\ar[d]_{+} & \ar[l]_-{a_{13}}(T \times T)\times X \ar[d]^{+\times X}\ar[r]^-{a_{14}}& X\\
T &\ar[l]^{a_3} T\times X. \ar[ru]_{a_4}
}\end{xy}\]
First we infer from the equalities
\begin{align*}
a_{15}(+ \times X)a_3 \quad
&\bydef[]{+\times X} a_{15}a_{13}+
\bydef{a_{15}} a_7 + \bydef{\delta_{X}}\delta_{X} a_3
\intertext{and}
a_{15}(+ \times X)a_4 \quad
&\bydef[]{+\times X} a_{15}a_{14}
\bydef{a_{15}} a_2 a_4 \bydef{\delta_{X}}\delta_{X} a_4
\end{align*}
that \m{a_{15}(+\times X) = \delta_{X}}. With this condition
diagram~\eqref{eq:Cmon-act-plus} becomes
\begin{equation*}
\begin{xy}
\xymatrix@!C{%
**[l] (T\times T ) \times X \ar[r]^-{+ \times X}
& T\times X \ar[rd]^{\aLpha}&\\
&&X,\\
**[l] T\times (T \times X) \ar[uur]^{\delta_{X}}
\ar[r]^-{T \times \aLpha}
\ar[uu]^{\cong(a_{15})}
& T\times X \ar[ru]_{\aLpha}&
}%
\end{xy}
\end{equation*}
and since the upper triangle commutes, \eqref{eq:Cmon-act-plus}
commutes if and only if~\eqref{eq:Tmon-alg-delta} commutes.
Furthermore, by definition of \m{\eta}, the
diagrams~\eqref{eq:Cmon-act-neutral} and~\eqref{eq:Tmon-alg-eta}
are identical.\qedhere
\end{enumerate}
\end{proof}
The previous lemma enables us to characterise abstract dynamical systems
in terms of monadic algebras for the endo\dash{}functor \m{T \times -} on
\m{\cat}.
\subsection{From abstract dynamical systems to monadic algebras}%
\label{subsect:abs-dyn-sys-to-mon-algs}
Here we finally relate our definition of abstract dynamical system on
finite product categories to the well\dash{}known algebraic concept of
monadic algebra.
\par
\begin{proposition}\label{prop:char-Cdyn-sys-Tmon-alg}
Let \m{\cat} be a finite product category and \m{T} one of its objects.
Suppose \m{\apply{T,+,e}} is a \nbd{\m{\cat}}monoid setting and
\m{\mor{1_{\cat}}{\eta}{T \times -}} and
\m{\mor{T\times\ovflhbx{1.32pt}(T\times\ovflhbx{1.32pt}-)}{%
\delta}{T\times -}}
are the associated natural transformations as in
Lemma~\ref{lem:nat-trans-delta-eta}\eqref{item:def-delta-eta}.
Furthermore, let \m{X} be an object of \m{\cat} with a morphism
\m{\mor{T \times X}{\aLpha}{X}}. Provided that
\[\apply{\apply{T,+,e}, X, \mor{T\times X}{\aLpha}{X}}\]
is a \emPh{dynamical system on \m{\cat}} then
\m{(T\times -, \delta, \eta)} is a \emPh{monad} and
\m{\apply{X,\mor{T\times X}{\aLpha}{X}}} is a
\emPh{monadic \nbdd{\apply{T\times -}}algebra} for this monad.
\par
If, for certain objects \m{Y,Z} of \m{\cat}, the morphism
\m{\mor{T \times Z}{a_3}{T}} and the morphism
\m{\mor{T\times(T\times (T \times Y))}{T\times a_7}{T\times (T\times T)}}
mentioned in Lemma~\ref{lem:nat-trans-delta-eta}\eqref{item:Cmon-Tmon} are
epi, then also the converse implication holds.
\end{proposition}
\begin{proof}
If \m{(\apply{T,+,e}, X, \mor{T\times X}{\aLpha}{X})} is a dynamical
system on \m{\cat}, then \m{(T,+,e)} is a \nbd{\m{\cat}}monoid, so by
Lemma~\ref{lem:nat-trans-delta-eta}\eqref{item:Cmon-Tmon},
\m{(T\times -,\delta, \eta)} is a monad. Furthermore, \m{(X,\aLpha)} is a
\nbd{\m{\cat}}monoid action, so diagrams~\eqref{eq:Cmon-act-neutral}
and~\eqref{eq:Cmon-act-plus} commute, which, by
Lemma~\ref{lem:nat-trans-delta-eta}\eqref{item:Cmon-act-Tmon-alg}, is
equivalent to the commutativity of diagrams~\eqref{eq:Tmon-alg-eta}
and~\eqref{eq:Tmon-alg-delta}. This, however, means that \m{(X,\aLpha)} is
a monadic \nbdd{\apply{T \times -}}algebra w.r.t.~the monad
\m{(T\times -,\delta, \eta)}.\par
Under the additional assumptions, the implication in
Lemma~\ref{lem:nat-trans-delta-eta}\eqref{item:Cmon-Tmon} can be reversed,
which shows the second part of the proposition.
\end{proof}
A much more concise formulation of this result is achieved if one starts
with a monoid instead of a monoid setting as in the following corollary:
\begin{corollary}\label{cor:char-Cdyn-sys-Tmon-alg}
Let \m{\cat} be a finite product category and \m{T}, \m{X} be objects of
\m{\cat} with a morphism \m{\mor{T\times X}{\aLpha}{X}}. Furthermore, let
\m{\apply{T,+,e}} be a \nbdd{\cat}monoid and
\m{(T\times -, \delta, \eta)} the associated monad as in
Lemma~\ref{lem:nat-trans-delta-eta}\eqref{item:Cmon-Tmon}. Then
\newline
\begin{minipage}[]{142.7pt}%{0.45\textwidth}
\m{\displaystyle\apply{\apply{T,+,e}, X, \mor{T\times X}{\aLpha}{X}}}\\
is a \emPh{dynamical system on \m{\cat}}
\end{minipage}
\hfill
if and only if%
\hfill
\begin{minipage}[]{153.1pt}%{0.45\textwidth}
\m{\displaystyle\apply{X,\mor{T\times X}{\aLpha}{X}}}\\
is a \emPh{monadic \nbdd{\apply{T\times-}}algebra}\\
for \m{(T\times -, \delta, \eta)}.
\end{minipage}
\end{corollary}
\begin{proof}
Note that the additional assumptions in
Proposition~\ref{prop:char-Cdyn-sys-Tmon-alg} have only been needed to
show that \m{(T,+,e)} is a \nbdd{\cat}monoid provided that
\m{(T \times -, \delta, \eta)} is a monad. As the conclusion of this
implication is already contained in the assumptions of the corollary, the
same proof as for the proposition works, just using the part involving
Lemma~\ref{lem:nat-trans-delta-eta}\eqref{item:Cmon-act-Tmon-alg}.
\end{proof}
\par
It is now easy to see that the connection exhibited in the previous
corollary can be formalised as an isomorphism between categories.
\par
\begin{remark}\label{rem:eq-categories-of-dyn-sys}
For a finite product category \m{\cat}, any two objects \m{T}, \m{X}, a
morphism \m{\mor{T \times X}{\aLpha}{X}} and a \nbdd{\cat}monoid
\m{\apply{T,+,e}} with associated monad \m{(T\times -, \delta, \eta)} as
in Lemma~\ref{lem:nat-trans-delta-eta}\eqref{item:Cmon-Tmon}, mapping
\[\apply{\apply{T,+,e}, X, \mor{T\times X}{\aLpha}{X}}
\mapsto
\apply{X,\mor{T\times X}{\aLpha}{X}}\]
induces a categorical equivalence (even an isomorphism) between the
category of abstract dynamical systems on \m{\cat} w.r.t.\ the
\nbdd{\cat}monoid \m{\apply{T,+,e}} and that of monadic
\nbdd{\apply{T\times-}}algebras for the
associated monad \m{\apply{T\times -, \delta, \eta}}. This is so because
the condition for a morphism \m{\mor{X}{h}{Y}} of \m{\cat} to be a
morphism of dynamical systems
\m{\apply{\apply{T,+,e}, X, \mor{T\times X}{\aLpha}{X}}}
and \m{\apply{\apply{T,+,e}, Y, \mor{T\times Y}{\bEta}{Y}}} is precisely
the same as for being a morphism of \nbdd{\apply{T\times-}}algebras, namely
that the diagram
\[\begin{xy}\xymatrix{T \times X \ar[r]^{ T \times h} \ar[d]_{\aLpha}
& T \times Y\ar[d]^{\bEta}\\ X\ar[r]^{h} &Y}
\end{xy}\]
commutes. Therefore, the assignment above extends to a functor that maps
morphisms identically and has the obvious inverse functor.
\end{remark}
\par
In particular, if we combine the latter observation with
Corollary~\ref{cor:Top-dyn-sys=class-dyn-sys}, we obtain that the category
of topological dynamical systems over a fixed topological monoid
\m{\alg[+,0]{T}}, which are the dynamical systems on \m{\Top} for this
particular \nbd{\m{\Top}}monoid, is isomorphic to the category of
\nbdd{\apply{T\times-}}algebras for the associated monad
\m{\apply{T\times -, \delta, \eta}} as given in
Lemma~\ref{lem:nat-trans-delta-eta}\eqref{item:Cmon-Tmon}.\par
In this context the canonically given notion of isomorphism in the
category of \nbdd{\apply{T\times-}}algebras translates to the
well\dash{}known concept of \emph{topological conjugacy} from the world of
dynamical systems.
\par
For example, in Section~2.3.2 of~\cite{BergerChaosAndChance} a
prototypical example of a chaotic dynamical system is studied. It is a
discrete time system as introduced at the beginning of
Subsection~\ref{subsect:class-dyn-sys}, induced by iterating the logistic
map on a certain Cantor set \m{\Lambda} within the real unit interval,
viewed as a topological subspace \m{X} of the real numbers with the
topology being given by the absolute value metric. In Theorem~2.20,
Berger examines the topological dynamical system over the discrete
topological monoid \m{\gapply{\N;\,+, 0}} given by
\m{\functionhead{\aLpha}{\N\times X}{X}}, where
\m{\aLpha(n,x)\defeq f^n(x)}, and \m{\functionhead{f}{X}{X}} is defined by
\m{f(x)\defeq\mu x(1-x)} for \m{x\in X} and the special choice
\m{\mu\defeq 3.839}. The space \m{X} is partitioned into two disjoint
parts and each state \m{x\in X} is mapped to an \nbd{\m{\omega}}sequence
\m{h(x)\in 2^\omega} of indices zero and one, indicating which of the two
parts the respective \nbd{\m{n}}th iterate \m{\aLpha(n,x)=f^n(x)} belongs
to. Thereby, Berger establishes that the particular discrete time dynamical
system is isomorphic to a so\dash{}called \emph{subshift of finite type}.
The latter one is readily seen to fulfil the criteria of a chaotic system.
\par
The condition that needs to be shown in the proof of the mentioned theorem
is precisely that the two associated monadic algebras are isomorphic: the
mapping \m{h} has to be a homeomorphism (an isomorphism in the category
\m{\Top}) satisfying the condition that for every \m{x\in X} shifting the
sequence assigned to \m{x} to the left yields the sequence assigned to
\m{f(x)}.
\par
In a similar way, other category theoretic concepts and constructions,
\eg\ existing limits for monadic algebras, can be shifted both ways
between the algebraic world of \nbdd{\apply{T\times-}}algebras and the
analytic world of dynamical systems.
\par
\begin{comment}
\todo[inline]{Discuss the connection of subshifts of finite type with
B\"uchi recognisable languages!}
\end{comment}
\subsection{Connections to coalgebras}\label{subsect:currying}
The aim of this part is to establish a link between abstract dynamical
systems that have now been understood as monadic algebras for
the endo\dash{}functor \m{T \times -} and coalgebras for another signature
functor. It will turn out that these coalgebras will also carry
a comonadic structure in a natural way.\par
The motivation for the rest of this section comes from regarding
Corollary~\ref{cor:char-Cdyn-sys-Tmon-alg} in the special case of
\m{\cat = \Set} and at first forgetting about monadicity conditions. What
remains is an algebra \m{\apply{X, \aLpha\colon T\times X \to X}} of
signature\footnote{Readers familiar with the modelling of classical
universal algebras as functorial algebras are invited to view this as a
unary universal algebra with one unary operation for each point \m{t \in
T} in time, assigning to each state \m{x \in X} its evolved state
\m{\aLpha(t,x)} at the point \m{t}.} \m{T} on the state space \m{X}. There
is an easy construction (recall Example~\ref{ex:alg-coalg}),
well\dash{}known from computer science as \emph{currying}, that transforms
every mapping \m{\aLpha\colon T\times X \to X} into a mapping
\m{\bEta\colon X \to X^T}, where \m{X^T} denotes the set of all mappings
from \m{T} to \m{X}. The morphism \m{\bEta} sends every state \m{x \in X}
to the mapping \m{\bEta(x)\colon T \to X} assigning to all time points
\m{t \in T} the evolved state \m{\aLpha(t,x)} derived from \m{x}.
Evidently, the mapping \m{\bEta} suffices to encode all the information
about state transitions that is contained in \m{\aLpha}, i.e.\ the
currying operation can be reversed by assigning to every pair
\m{(t,x)\in T \times X} the state \m{\bEta(x)(t)}, thus re\dash{}obtaining
\m{\aLpha} from \m{\bEta}.
\par
Consequently, in \m{\Set} there is a one-to-one correspondence between
mappings of the form \m{\aLpha\colon T\times X \to X} and \m{\bEta\colon X
\to X^T} or, in other words, between algebras \m{\apply{X, \aLpha\colon
T\times X \to X}} and coalgebras \m{\apply{X, \bEta\colon X \to X^T}} for
the hom\dash{}functor \m{-^T = \Hom(T,-)}.
\par
This encourages the question,
how the latter phenomenon can be generalised to arbitrary abstract
categories. To this end
the first problem that has to be solved is that in the case of \m{\Set},
the hom\dash{}functor \m{-^T} turns out to be an endo\dash{}functor, and
that in fact the category \m{\Set} and its subcategories are basically the
only cases when this happens (as hom\dash{}sets always have to be sets).
Our search for an appropriate replacement (or definition) of the object
\m{X^T} leads us back to the original idea of currying. In fact the
one-to-one correspondence between mappings as described above in the case
of dynamical systems on \m{\Set} is a bit more general: every mapping
\m{\aLpha\colon T \times X \to Y} in \m{\Set} can be translated into a
mapping \m{\bEta\colon X \to Y^T} and vice versa. However, this is the
defining property of an adjunction between the endo\dash{}functors \m{T
\times -} and \m{-^T}. It turns out that this is the right point of view
for a generalisation to arbitrary categories, which as a side effect
ensures that algebras for \m{T \times -} and coalgebras for the other
functor are uniquely related.\par
In every finite product category \m{\cat} any object \m{T} gives rise to
an endo\dash{}functor \m{T\times -} on \m{\cat}. We say that \m{\cat}
\emph{has exponential objects w.r.t.\ \m{T}} if the endo\dash{}functor
\m{\mor{\cat}{T \times -}{\cat}} has a right adjoint, called
\m{\mor{\cat}{-^T}{\cat}}.
Moreover, \m{\cat} \emph{has exponential objects}, if it has exponential
objects \wrt\ to any object \m{T} of \m{\cat}. Such categories having
all finite products and exponentials are also called
\emph{Cartesian closed}.
\par
These notions enable us to study the connections between dynamical systems
as monadic algebras and a possible formalisation as coalgebras on the more
general level of adjoint functors. In fact, this discussion can be
done independently of the particular functor \m{T \times -} and a possible
adjoint \m{-^T}. We will continue with this approach in
Subsection~\ref{subsect:(co)mon-(co)alg-adj}.
\par
Since adjoint functors (if they exist at all) are unique up to isomorphism
this method also yields a reasonable definition of the object \m{X^T} for
our algebras: \m{X^T} is \emph{whatever the adjoint functor returns}, not
necessarily the set \m{\Hom(T,X)} equipped with some structure. However,
if \m{\cat} is a construct (having a faithful forgetful functor \m{U} to
\m{\Set}), then it is usually a good idea to start with \m{\Hom(T,X)} and
to try to find some object \m{X^T} satisfying \m{U(X^T) = \Hom(T,X)}
(cf.~\cite[Chapter~27]{cats}). For example in the category \m{\Top} the set
\m{\Hom(T,X)} equipped with the compact open topology serves as an
exponential object provided that the time space \m{T} is locally compact
Hausdorff. Since topological spaces are a central example of this paper,
we give detailed account of this in the following subsection.
\par
\subsection{\texorpdfstring{Exponential objects in \m{\protect\Top} for
locally compact Hausdorff spaces}{Exponential objects in Top for locally
compact Hausdorff spaces}}%
\label{subsect:exp-obj-for-TopLocComp}
In this subsection it will be proven that the category \m{\Top} has
exponential objects with respect to locally compact Hausdorff spaces. In
the first instance, we address some notational issues. The main result of
this subsection is revealed in the third statement of the subsequent
proposition.
\par
\begin{definition}\label{def:compact-open-topology}
For topological spaces \m{\bx=\apply{X,\rho}} and \m{\by=\apply{Y,\sigma}},
a compact set \m{K \in \comp{\bx}} and \m{U \in \sigma} we let
\m{\cosb{K}{U} \defeq \lset{ f \in\cont{\bx}{\by}}{f\fapply{K}\subs U}}.
Then we define \m{\cotop{\bx}{\by}} to be the
\emph{compact\dash{}open topology}
on \m{\cont{\bx}{\by}}, \ie\ the topology generated by the subbase
\m{\lset{\cosb{K}{U}}{K \in\comp{\bx}, U \in\sigma}}. More\-over,
we put \m{\by^{\bx} \defeq \apply{\cont{\bx}{\by},\cotop{\bx}{\by}}}.
\end{definition}
\par
Note that the set \m{\cont{\bx}{\by}} was called \m{\Top\apply{\bx,\by}}
in the general category theoretic setting introduced in
Subsection~\ref{subsect:category-prelims}.
\par
As we will see in the next proposition, the category of locally compact
Hausdorff spaces has exponential objects.
\par
\begin{proposition}\label{prop:exponentials-for-locally-comp-T}
Let \m{\bt = \apply{T,\tau} \in \Top}.
\begin{enumerate}[(a)]
\item The assignment \m{\functionhead{-^{\bt}}{\Top}{\Top}\colon}
\m{\bx \mapsto \bx^{\bt}} defines a functor, operating on
morphisms \m{\mor{\bx}{f}{\by}} via
\m{\mor{\bx^{\bt}}{f^{\bt}}{\by^{\bt}}\colon g\mapsto f\circ g}.
\item The family of morphisms given by
\[\begin{array}{llll}
\Phi^{\bt}_{\bx,\by} \colon
& \Top(\bt \times \bx ,\by ) & \to
& \Top(\bx, \by^{\bt})\\
& \mor{\bt\times\bx}{f}{\by} & \mapsto
& \mor{\bx}{\Phi^{\bt}_{\bx,\by}\apply{f}}{\by^{\bt}}\colon
[x \mapsto [t \mapsto f(t,x)]],
% \apply{\bx ,[x \mapsto [t \mapsto f(t,x)]],\by^{\bt}},
\end{array}\]
constitutes a natural transformation.
\item If \m{\bt} is locally compact Hausdorff, then
\m{\functionhead{\Phi^{\bt}}{%
\Top\apply{\bt\times-_{1},-_{2}}}{%
\Top\apply{-_{1}, -_{2}^{\bt}}}}
is a natural equivalence.
\end{enumerate}
\end{proposition}
\begin{proof}
\begin{enumerate}[(a)]
\item Functoriality of \m{-^{\bt}} is clear. For a continuous map
\m{\functionhead{f}{\bx}{\by}} between spaces
\m{\bx=\apply{X,\rho}} and \m{\by=\apply{Y,\sigma}}, the resulting
map \m{\functionhead{f^{\bt}}{\bx^{\bt}}{\by^{\bt}}} is indeed
continuous in every point \m{g\in \cont{\bt}{\bx}}. Namely, for every
basic open neighbourhood \m{\cosb{K}{U}} of
\m{f^{\bt}\apply{g}=f\circ g}, \ie\ \m{K\in \comp{\bt}} and
\m{U\in\sigma} such that \m{f\circ g\fapply{K}\subs U}, the set
\m{\cosb{K}{f^{-1}\fapply{U}}} is an open neighbourhood of \m{g},
and every \m{h\in\cosb{K}{f^{-1}\fapply{U}}} satisfies
\m{h\fapply{K}\subs f^{-1}\fapply{U}}, so
\m{f\circ h\fapply{K}\subs f\fapply{f^{-1}\fapply{U}}\subs U}.
This means \m{f^{\bt}\apply{h} = f\circ h \in \cosb{K}{U}}.
\item Let \m{\bx =\apply{X,\rho}} and \m{\by=\apply{Y,\sigma}} be
topological spaces, \m{f \in \cont{\bt \times \bx}{\by}}. Obviously,
for each \m{x \in X} it is \m{[t\mapsto f(t,x)]\in\cont{\bt}{\by}}.
In order to prove that the mapping
\m{[x \mapsto [t \mapsto f \apply{t,x}]]}
belongs to \m{\cont{\bx}{\by^{\bt}}}, consider \m{x \in X},
\m{K \subseteq T} compact w.r.t.\ \m{\tau}, \m{U \in \sigma} such
that \m{[t \mapsto f(t,x)]\in\cosb{K}{U}}. By continuity of \m{f},
for
\begin{align*}
\mathcal{V} \defeq
\bigcup_{t \in K} \lset{V\in\neigh{t}{\bt}}{%
\exists W\in\neigh{x}{\bx}\colon
f\fapply{V\times W}\subseteq U}
\end{align*}
we have
\m{K \subseteq \bigcup_{V \in \mathcal{V}}\interior[{\bt}]{V}}. Since
\m{K} is compact, there exist \m{V_{1},\dotsc,V_{n}\in\mathcal{V}}
such that \m{K \subseteq \bigcup_{i=1}^{n} \interior[{\bt}]{V_{i}}}.
For each \m{i \in \set{1,\dotsc,n}}, we can find some neighbourhood
\m{W_{i} \in \neigh{x}{\by}} with the property
\m{f\fapply{V_{i}\times W_{i}} \subseteq U}.
Define \m{V \ovflhbx{0.92236pt}\defeq \bigcup_{i=1}^{n} V_{i}},
\m{W \defeq \bigcap_{i=1}^{n} W_{i}}. Then it follows
\m{W \in \neigh{x}{\bx}} and
\m{f\fapply{K\times W} \subseteq f\fapply{V\times W} \subseteq U}.
So we have \m{[t \mapsto f (t,x)]\in\cosb{K}{U}} for all \m{x \in W}.
Moreover, it is easy to see that the naturality of the
transformation
\m{\functionhead{\Phi^{\bt}}{\Top(\bt\times -_{1} ,-_2)}{%
\Top(-_1, {-_2}^{\bt})}} is satisfied.
%
% Reason for naturality
% ---------------------
%% \par
%% \paragraph{Reason:}
%% \ovflhbx{1.45pt}For topological spaces \m{\bx, \by, \topSp{U},
%% \topSp{V}} and morphisms \m{\mor{\topSp{U}}{f}{\bx}} and
%% \m{\mor{\by}{g}{\topSp{V}}} and some argument
%% \m{\mor{\bt\times \bx}{h}{\by}} we have for all \m{u\in U} and
%% \m{t\in T} that
%% \begin{align*}
%% \Phi_{\topSp{U},\topSp{V}}\apply{g\circ h\circ \bt\times f} (u) (t)
%% &= g\circ h\circ \bt\times f \apply{t,u} = g\circ h\apply{t, f(u)}.
%% \end{align*}
%% On the other side we have
%% \begin{align*}
%% g^{\bt}\apply{\Phi_{\bx,\by}(h)\apply{f(u)}}(t)
%% &=g\apply{\Phi_{\bx,\by}(h)\apply{f(u)} (t)}
%% =g\apply{h\apply{t,f(u)}}.
%% \end{align*}
%% This implies
%% \m{g^{\bt}\circ \Phi_{\bx,\by}(h) \circ f
%% = \Phi_{\topSp{U},\topSp{V}}\apply{g\circ h\circ \bt\times f}},
%% or slightly differently expressed,
%% \m{\Phi_{\topSp{U},\topSp{V}}\circ \Top(\bt\times f, g) (h)
%% = \Top(f,g^{\bt})\circ\Phi_{\bx,\by}(h)}. This is the naturality
%% condition.
%% \end{comment}
%
\item Let \m{\bx = \apply{X, \rho}, \by = \apply{Y, \sigma} \in \Top}.
It is easy to see that \m{\Phi^{\bt}_{\bx,\by}} is injective. Hence
it is left to prove that it is surjective. Let
\m{g \in \Top\apply{\bx, \by^{\bt}}}. Define the mapping
\[\function{f}{T \times X}{Y}{(t,x)}{g(x)(t).}\]
Let us show that \m{f} is continuous. To this end, let
\m{(t,x) \in T \times X} and \m{W \in \sigma}
such that \m{f(t,x) \in W}. Since \m{T} is locally compact
Hausdorff, there exists a compact neighbourhood
\m{K} of \m{t} such that
\m{f\fapply{K\times\set{x}} = g(x)\fapply{K} \subseteq W}.
Yet now, due to the continuity of \m{g}, there exists a
neighbourhood \m{U} of \m{x} such that
\m{g\fapply{U} \subseteq \cosb{K}{W}}.
Thus, \m{f\fapply{K \times U} \subseteq W}, that
is, \m{f} is continuous.
Evidently, \m{\Phi^{\bt}_{\bx,\by}(f) = g}, so we are done. \qedhere
\end{enumerate}
\end{proof}
\par
In the theory of dynamical systems, state spaces are often chosen as
metric spaces. This motivates the search for those topological spaces
\m{\bt} for which the space \m{\bx^{\bt}} is metrisable whenever \m{\bx}
is metrisable.
\par
We recall that a topological space is \nbdd{\sigma}compact if it has a
countable exhaustion by compact subsets (cf.\
Definition~\ref{def:sigma-compact}). Note, furthermore, that
\nbdd{\sigma}compact \name{Hausdorff} spaces are necessarily locally
compact (see Lemma~\ref{lem:char-sigma-compact}).
% Hausdorff needed due to strong version of local compactness involving a
% whole neighbourhood base
The following proposition now answers the previously stated question.
\par
\begin{proposition}\label{prop:metrisability-X-to-T}
% It is not needed that T is Hausdorff.
If \m{\bt} is a \nbd{\m{\sigma}}compact topological space and \m{\bx} a
metrisable topological space, then \m{\bx^{\bt}} is metrisable, too.
\end{proposition}
\begin{comment}
\begin{remark}
In~\cite[43G.1., p.~289]{WillardGeneralTopologyReprint} the space
\m{\continuous{\bt}=\cont{\bt}{\R}}, equipped with the
compact\dash{}open topology is considered, \ie\
\m{\continuous{\bt}=\R^{\bt}}. The task there is to prove that
\m{\R^{\bt}} is metrisable whenever \m{\bt} is completely regular
\name{Hausdorff} and \emph{hemicompact}, where hemicompactness means the
existence of a sequence \m{\apply{K_n}_{n\in\N}} in \m{\comp{\bt}^{\N}}
such that for every \m{K\in\comp{\bt}} there exists some \m{n\in\N} for
which \m{K\subs K_n}. This assumption is strictly weaker than, \ie\
follows from but does not imply, \nbdd{\sigma}compactness in the sense
that \m{\bt=\bigcup_{n\in\N} K_n} for some sequence
\m{\apply{K_{n}}_{n\in\N}\in\comp{\bt}^{\N}}
(see~\cite[17I.1., p.~126]{WillardGeneralTopologyReprint}). Certainly, our
definition of \nbdd{\sigma}compactness (cf.\
Definition~\ref{def:sigma-compact}) implies Willard's weaker notion of
\nbdd{\sigma}compactness, and thus also hemicompactness (according
to~\cite[43G.1., p.~289]{WillardGeneralTopologyReprint}).
\par
On the other hand, we do not require the \name{Hausdorff} property for
\m{\bt}, and Martin confirms that due to our stronger notion of compact
exhaustion, where we require \m{K_n\subs \interior[\bt]{K_{n+1}}} for
every \m{n\in\N}, we really do not need the \m{\mathrm{T}_{2}} separation
axiom.
\par
It is easy to see that the topology defined by the metric is contained in
the compact\dash{}open topology. For the converse inclusion, it suffices
to consider subbasic open sets \m{\cosb{K}{U}}, where \m{K\in\comp{\bt}}
and \m{U} is open in \m{\bx}, and to prove that these sets are open in the
metric topology, \ie\ that any of its points is an interior point. Due to
the stronger exhaustion axiom, one does not need the \name{Hausdorff}
property for this.
\end{remark}
\end{comment}
\begin{proof}
Let \m{\apply{K_n}_{n \in \N}} be a countable exhaustion of \m{\bt} by compact subsets, and let \m{d} be
a metric generating the topology of \m{\bx}. Then it is not difficult to see that
\[
\begin{array}{llll}
d^* \colon & \cont{\bt}{\bx}^2 & \to & \R, \\
& (f,g) & \mapsto & \sum_{n=0}^{\infty} \frac{1}{2^n} \min \set{\sup_{x \in K_n} d(f(x),g(x)),1}.
\end{array}
\]
is a metric on \m{\cont{\bt}{\bx}} that generates \m{\cotop{\bt}{\bx}}
(cp.\ also~\cite[43G.1., p.~289]{WillardGeneralTopologyReprint}).
\end{proof}
Many well\dash{}known topological spaces are \nbdd{\sigma}compact, such
as all finite powers of \m{\N}, \m{\Z} and \m{\R}. However, as it turns
out, a slight generalization of metrisable spaces allows us to use a
notably larger class of time spaces. Namely, if \m{\bx} is uniformisable,
we shall see that \m{\bt} may indeed be an arbitrary topological space.
\par
Obviously, the notion of uniform space generalises that of metric space.
Namely, with every metric space \m{\apply{X,d}}, we associate a uniformity
\m{\Theta} on \m{X} generated by the entourages
\m{U_{\epsilon}\defeq \lset{\apply{x,y}\in X^2}{d(x,y)\leq \epsilon}},
\m{\epsilon \in \R_{>0}}.\par
To give an example of uniform spaces that properly generalise metric
spaces, let \m{\bx} be a topological space and consider the space
\m{\continuous{\bx}\defeq\cont{\bx}{\R}} of continuous real\dash{}valued
functions on \m{\bx}, equipped with the topology
of compact convergence. That is, convergence in \m{\continuous{\bx}}
means uniform convergence on every compact subset of \m{\bx}. The
topology underlying this notion of convergence is given by the base
\m{\lset{\ccbs{f}{K}{\epsilon}}{%
f\in \continuous{\bx}, K\in\comp{\bx}, \epsilon \in \R_{>0}}},
where
\begin{equation*}
\ccbs{f}{K}{\epsilon}\defeq
\lset{g\in \continuous{\bx}}{%
\sup_{x\in K} \abs{f(x)-g(x)}< \epsilon}.
\end{equation*}
For completeness we mention that one can show
that this topology coincides with the compact\dash{}open
topology on \m{\continuous{\bx}}. This is in fact an instance of a
general non\dash{}trivial observation, depending only on
uniformisability of the image space \m{\R}
(cf.~\cite[Theorem~43.7, p.~284]{WillardGeneralTopologyReprint}).
% Satz~14.13 in [von Querenburg'79]
\par
It is, furthermore, easy to see that the topology of compact
convergence on \m{\continuous{\bx}} is induced by\footnote{see also the
definition on page~\pageref{page:top-of-uniform-space}}
the uniform structure generated by the uniformity base
\m{\lset{\Theta_{K,\epsilon}}{K\in\comp{\bx},
\epsilon\in\R_{>0}}} where
\begin{equation*}
\Theta_{K,\epsilon}\defeq
\lset{\apply{f,g}\in \apply{\continuous{\bx}}^2}{%
\sup_{x\in K} \abs{f(x)-g(x)}<\epsilon}.
\end{equation*}
\par
However, it does not follow in general that the induced topology or the
uniform structure, respectively, is metrisable. Namely, if \m{\bx} is a
locally compact Hausdorff space, it is well\dash{}known that
metrisability of \m{\continuous{\bx}} is equivalent to
\nbdd{\sigma}compactness of \m{\bx}
(cf.~\cite[Theorem~8]{ArensTopologyForSpacesOfTransformations} for more
details). %
% + \sigma-compactness of X always easily implies metrisability of C(X)
% + The converse is non-trivial:
% R. Arens: A Topology for Spaces of Transformations, Ann. of Math.
% 47(1946), 480-495
% Theorem 8: If $C(A,B)$ is first-countable and if for all points
% $x,y\in A$ there exists a function $f\in C(A)$ with
% $f(x)\neq f(y)$, then $A$ is hemicompact.
% [see also
% http://mathoverflow.net/questions/89906/metrizable-implies-hemicompact]
% ----------------------------------------
% If C(A,B) is metrisable, then it is first-countable (has a countable
% neighbourhood base), so we get that it is hemi-compact. In our case
% this also implies \sigma-compactness.
%
Thus, choosing for \m{\bx} any locally compact Hausdorff
space which is not \nbd{\m{\sigma}}compact, we obtain that
\m{\continuous{\bx}} is
a space with a uniform structure that cannot be given by a metric. For
instance, we may take for \m{\bx} the subspace of a Tychonoff cube
\m{\fapply{0,1}^I} with an uncountable index set \m{I} that results from
deleting an arbitrary single point from \m{\fapply{0,1}^I}.
\par
Such function spaces \m{\continuous{\bx}} as state spaces promise a wide
variety of dynamic behaviour, much more than just \m{\R^n}, which
corresponds to the case, when \m{\bx} is discrete and finite (in
particular compact). It goes beyond the scope of this article to study
them in more detail, but in~\cite{%
BehKerkhoffSchneiderSiegmundChaoticGroupActionsOnHausdorffSpaces}, we
examine topological dynamical systems on function spaces
over topological groups more closely. In particular, we study and
characterise faithful strongly chaotic continuous actions of locally
compact Hausdorff topological groups on such spaces.
\par\smallskip
Even though function spaces \m{\continuous{\bx}} sometimes lack
metrisability and
thus Proposition~\ref{prop:metrisability-X-to-T} fails to be applicable,
these spaces are certainly uniformisable as said before. Hence, one may
instead rely on the following well\dash{}known variant of
Proposition~\ref{prop:metrisability-X-to-T}, which, as a
side\dash{}effect, allows us to drop the assumption of
\nbdd{\sigma}compactness \wrt\ the time space \m{\bt}. For a proof of this
fact we refer to~\cite[Theorem~43.7]{WillardGeneralTopologyReprint}.
\par
\begin{proposition}\label{prop:uniformisability-X-to-T}
If \m{\bt} is a topological space and \m{\bx} a uniformisable space, then
\m{\bx^{\bt}} is uniformisable.
\end{proposition}
\par
According to Proposition~\ref{prop:metrisability-X-to-T}, if \m{\bx} is a
metrisable space and the time space \m{\bt} is \nbd{\m{\sigma}}compact,
then also \m{\bx^{\bt}} is metrisable, \ie\ the compact\dash{}open
topology on \m{\bx^{\bt}} is induced by some metric. Such a metric in a
natural way defines a uniform structure \m{\Theta} on \m{\bx^{\bt}}
(\vsup), which is indeed the same as the uniform structure constructed by
Proposition~\ref{prop:uniformisability-X-to-T} applied to \m{\bt} and
the uniform space on \m{X} derived from the metric on \m{X}.\par
\smallskip
With the previous result we have established the existence of exponential
objects \wrt\ any time space in the full subcategory \m{\Unif} of
uniformisable spaces. With Proposition~\ref{prop:metrisability-X-to-T}
we have done the same for the subcategory \m{\Met} of metrisable spaces and
\nbd{\m{\sigma}}compact times spaces. % the assumption of sigma-compactness
% for metric spaces is not redundant.
Furthermore, Proposition~\ref{prop:exponentials-for-locally-comp-T} solves
this question for the category of locally compact Hausdorff spaces in
general and for the category of topological spaces \wrt\ locally compact
Hausdorff time spaces.\par
Thus, in many familiar situations, one can ensure that the functor taking
products with the time space \m{\bt} has a right adjoint
endo\dash{}functor \m{-^{\bt}}. It is on the level of adjoint
endo\dash{}functors that we will now explore, how to understand
dynamical systems in abstract categories in a different manner than as
monadic algebras.
\par
\subsection{(Co)Monadic (co)algebras and adjoint functors}%
\label{subsect:(co)mon-(co)alg-adj}
In this part we will show that monadic algebras correspond closely to
comonadic coalgebras if the respective signature functors are adjoint.
Since under fairly weak assumptions on the considered category \m{\cat},
general dynamical systems have been modelled as monadic algebras for the
signature functor \m{T \times -} (cf.
Corollary~\ref{cor:char-Cdyn-sys-Tmon-alg}), this result will in
particular apply to an adjoint functor \m{-^T} on \m{\cat} provided it
exists. However, our treatment of this topic allows the functors \m{T
\times -} and \m{-^T} to be replaced by any other adjoint pair of
endo\dash{}functors \m{F \ladjoint G}.
\par
Our first aim is to show how a monad \m{(F,\delta,\eta)} for an
endo\dash{}functor \m{F \in \EndOp \cat} can be transformed into a comonad
\m{(G,\tilde{\delta},\tilde{\eta})} for a right adjoint endo\dash{}functor
\m{G \in \EndOp \cat}. We will put the technical part of the construction
into the following lemma:
\par
\begin{lemma}\label{lem:Fmon-def-Gcomon}
Let \m{\cat} be a category and \m{F,G \in \EndOp \cat} be two adjoint
endo\dash{}functors (\m{F \ladjoint G}). We denote the corresponding
natural equivalence between the hom\dash{}sets by
\m{\mor{\Hom(F,-)}{\pHi}{\Hom(-,G)}}, the unit by
\m{\mor{1_{\cat}}{\vheta}{\!GF}} and the co\dash{}unit by
\m{\mor{FG}{\epsilon}{\!1_{\cat}}}.\par
Furthermore, let two natural transformations \m{\mor{FF}{\delta}{F}} and
\m{\mor{1_{\cat}}{\eta}{F}}, and an arbitrary object \m{X \in \cat} be
given.
\par
For every object \m{Y \in \cat} we define the following morphisms:
\begin{align*}
\mor{FFGY}{\zeta_{Y} \defeq \delta_{GY}\epsilon_{Y}}{Y} &&
\mor{GY}{\tilde{\delta}_{Y} \defeq \pHi_{GY,GY}(\mu_{Y})}{GGY} \\
\mor{FGY}{\mu_{Y} \defeq \pHi_{FGY,Y}(\zeta_{Y})}{GY} &&
\mor{GY}{\tilde{\eta}_{Y} \defeq \eta_{GY}\epsilon_{Y}}{Y}.
\end{align*}
Then the following assertions are true:
\begin{enumerate}[(a)]
\item \m{\mor{FFG}{\zeta}{1_{\cat}}}, \m{\mor{FG}{\mu}{G}},
\m{\mor{G}{\tilde{\delta}}{GG}} and
\m{\mor{G}{\tilde{\eta}}{1_{\cat}}} are natural transformations.
\item\label{item:tdelta-Gteta} $\begin{aligned}[t]
\tilde{\delta}_{X}G\tilde{\eta}_{X}
&= \pHi_{GX,X}(\eta_{FGX}\delta_{GX}\epsilon_{X})
= \pHi_{GX,X}(\eta_{FGX}\zeta_{X}) & \text{ and } \\
\eta_{FX}\delta_{X} &= F\vheta_{X}\eta_{FGFX}\zeta_{FX}.
\end{aligned}$
\item\label{item:tdelta-tetaG}$\begin{aligned}[t]
\tilde{\delta}_{X}\tilde{\eta}_{GX}
&= \pHi_{GX,X}(F\eta_{GX}\delta_{GX}\epsilon_{X})
= \pHi_{GX,X}(F\eta_{GX}\zeta_{X}) & \text{ and }\\
F\eta_{X}\delta_{X} &= F\vheta_{X}F\eta_{GFX}\zeta_{FX}.
\end{aligned}$
\item\label{item:tdelta-Gtdelta-tdelta-tdeltaG} $\begin{aligned}[t]
\tilde{\delta}_{X} G \tdelta_{X}
&=\pHi_{GX,G^2X}(\pHi_{FGX,GX}(\pHi_{F^2GX,X}(\delta_{FGX}\zeta_{X})))
& F\delta_{X} \delta_{X} &= F^3\vheta_{X} F\delta_{GFX}\zeta_{FX}\\
\tdelta_{X}\tdelta_{GX}
&=\pHi_{GX,G^2X}(\pHi_{FGX,GX}(\pHi_{F^2GX,X}(F\delta_{GX} \zeta_{X})))
&\delta_{FX}\delta_{X}
&= F^3\vheta_{X}\delta_{FGFX}\zeta_{FX}.
\end{aligned}$
\end{enumerate}
\end{lemma}
\begin{proof}
Before we start with the actual proof we remind the reader about some
basic facts regarding adjunctions \m{F \ladjoint G}: for all objects
\m{X,Y\in \cat} and every morphism \m{\mor{FX}{g}{Y}} the following
equations hold:
\begin{align}
1_{FX} &= F\vheta_{X} \epsilon_{FX} \label{eq:adj-F}\\
1_{GY} &= \vheta_{GY}G\epsilon_{Y} \label{eq:adj-G}\\
\vheta_{X} Gg &= \pHi_{X,Y}(g) \label{eq:adj-phi}\\
F\pHi_{X,Y}(g)\epsilon_{Y} &= g \label{eq:adj-phi-inv}
\end{align}
Equations~\ref{eq:adj-F} and \ref{eq:adj-G} characterise adjunctions and
are known as co\dash{}unit\dash{}unit equations
(cf.~Definition~\ref{def:adjunction}). The other two relate the
natural equivalences \m{\pHi} and \m{\pHi^{-1}} to the unit and
co\dash{}unit, respectively (see also
Proposition~\ref{prop:char-adjunction}).
\par
In the course of the proof we are going to need the characterising
commutative diagrams for each of the involved natural transformations. We
will refer to them using the names of the respective transformations if we
apply the commutativity condition for some morphism in a calculation.
Such an application is indicated by underlining the corresponding part of
the formula which has to be replaced.
\par
For objects \m{X,Y \in \cat} and any morphism \m{\mor{X}{h}{Y}} the
following diagrams commute:\par
\noindent%
\begin{subequations}\label{diag:nat-trans}
\begin{minipage}{0.3\linewidth}
\begin{align}\tag{\ref{diag:nat-trans}\m{\eta}}%
\label{diag:trans-eta}
\begin{xy}\xymatrix@!C{%
FX\ar[r]^{Fh}& FY\\
X\ar[r]^{h}\ar[u]^{\eta_{X}}&Y\ar[u]_{\eta_{Y}}
}\end{xy}
\end{align}
\end{minipage}
\begin{minipage}{0.3\linewidth}
\begin{align}\tag{\ref{diag:nat-trans}\m{\delta}}%
\label{diag:trans-delta}
\begin{xy}\xymatrix@!C{%
FFX\ar[r]^{FFh}\ar[d]_{\delta_{X}}& FFY\ar[d]^{\delta_{Y}}\\
FX\ar[r]^{Fh}&FY
}\end{xy}
\end{align}
\end{minipage}
\begin{minipage}{0.3\linewidth}
\begin{align}\tag{\ref{diag:nat-trans}\m{\zeta}}%
\label{diag:trans-zeta}
\begin{xy}\xymatrix@!C{%
FFGX\ar[r]^{FFGh}\ar[d]_{\zeta_{X}}& FFGY\ar[d]^{\zeta_{Y}}\\
X\ar[r]^{h}&Y
}\end{xy}
\end{align}
\end{minipage}\\
\begin{minipage}{0.3\linewidth}
\begin{align}\tag{\ref{diag:nat-trans}\m{\epsilon}}%
\label{diag:trans-epsilon}
\begin{xy}\xymatrix@!C{%
FGX\ar[r]^{FGh}\ar[d]_{\epsilon_{X}}& FGY\ar[d]^{\epsilon_{Y}}\\
X\ar[r]^{h}&Y
}\end{xy}
\end{align}
\end{minipage}
\begin{minipage}{0.3\linewidth}
\begin{align}\tag{\ref{diag:nat-trans}\m{\vheta}}%
\label{diag:trans-vheta}
\begin{xy}\xymatrix@!C{%
GFX\ar[r]^{GFh}& GFY\\
X\ar[r]^{h}\ar[u]^{\vheta_{X}}&Y\ar[u]_{\vheta_{Y}}
}\end{xy}
\end{align}
\end{minipage}
\begin{minipage}{0.3\linewidth}
\begin{align}\tag{\ref{diag:nat-trans}\m{\mu}}%
\label{diag:trans-mu}
\begin{xy}\xymatrix@!C{%
FGX\ar[r]^{FGh}\ar[d]_{\mu_{X}}& FGY\ar[d]^{\mu_{Y}}\\
GX\ar[r]^{Gh}&GY
}\end{xy}
\end{align}
\end{minipage}
\end{subequations}
\par
\begin{enumerate}[(a)]
\item Taking into account the co\dash{}unit\dash{}unit equations it is
easy to see that the defined families of morphisms are each obtained
using compositions of natural transformations with functors and with
each other (cf.\ Remark~\ref{rem:nat-trafo-comp}). Indeed, we have
\begin{align*}
\zeta &= \delta_G \epsilon, & \tdelta &= \vheta_{G} G\mu, \\
\mu &= \vheta_{FG} G\zeta, & \teta &= \eta_G \epsilon. \\
\end{align*}
As such compositions yield again natural transformations this item
is proven.
\item First we note that
\begin{align*}
\pHi&_{FGX,X}(\zeta_{X})\teta_{X}
\stackrel{\eqref{eq:adj-phi}}{=} \vheta_{FGX}G\zeta_{X} \teta_{X}
\bydef{\teta_{X}} \vheta_{FGX}\hl{G\zeta_{X}\eta_{GX}}\epsilon_{X}\\
&\bynt[]{eta}\vheta_{FGX}\eta_{GFFGX}\hl{FG\zeta_{X}\epsilon_{X}}
\bynt{epsilon}\hl{\vheta_{FGX}\eta_{GFFGX}}\epsilon_{FFGX}\zeta_{X}\\
&\bynt[]{eta}\eta_{FGX}\hl{F\vheta_{FGX}\epsilon_{FFGX}}\zeta_{X}
\stackrel{\eqref{eq:adj-F}}{=} \eta_{FGX}1_{FFGX}\zeta_{X}
= \eta_{FGX}\zeta_{X}.
\end{align*}
Then, by definition,
\begin{align*}
\tdelta_{X}G\teta_{X}
&= \pHi_{GX,GX}(\pHi(FGX,X)(\zeta_{X}))G\teta_{X}
\stackrel{\eqref{eq:adj-phi}}{=}
\vheta_{GX}G(\pHi_{FGX,X}(\zeta_{X})\teta_{X})\\
&\vs[] \vheta_{GX} G(\eta_{FGX}\zeta_{X})
\stackrel{\eqref{eq:adj-phi}}{=} \pHi_{GX,X}(\eta_{FGX}\zeta_{X})
\bydef{\zeta_{X}} \pHi_{GX,X}(\eta_{FGX}\delta_{GX}\epsilon_{X}).
\end{align*}
The other equality holds because
\begin{multline*}
\eta_{FX}\delta_{X} = \eta_{FX}\delta_{X}\hl{1_{FX}}
\stackrel{\eqref{eq:adj-F}}{=}
\eta_{FX}\hl{\delta_{X}F\vheta_{X}} \epsilon_{FX}
\bynt{delta} \eta_{FX}FF\vheta_{X}\delta_{GFX}\epsilon_{FX}\\
\bydef{\zeta_{FX}} \eta_{FX}FF\vheta_{X}\zeta_{FX}.
\end{multline*}
\item A long calculation
\begin{align*}
\tdelta&_{X}\teta_{GX}
\bydef{\tdelta_{X}} \pHi_{GX,GX}(\mu_{X})\teta_{GX}
\stackrel{\eqref{eq:adj-phi}}{=}\vheta_{GX}G\mu_{X}\teta_{GX}
\bydef{\teta_{GX}} \vheta_{GX}\hl{G\mu_{X}\eta_{GGX}}\epsilon_{GX}\\
&\bynt[]{eta}\vheta_{GX} \eta_{GFGX}\hl{FG\mu_{X}\epsilon_{GX}}
\bynt{epsilon} \hl{\vheta_{GX}\eta_{GFGX}}\epsilon_{FGX}\mu_{X}
\bynt{eta} \eta_{GX}\hl{F\vheta_{GX}\epsilon_{FGX}}\mu_{X} \\
&\stackrel[]{\eqref{eq:adj-F}}{=} \eta_{GX}1_{FGX}\mu_{X}
\bydef{\mu_{X}} \eta_{GX}\pHi_{FGX,X}(\zeta_{X})
\stackrel{\eqref{eq:adj-phi}}{=}
\hl{\eta_{GX}\vheta_{FGX}}G\zeta_{X}\\
&\bynt[]{vheta} \vheta_{GX}GF\eta_{GX}G\zeta_{X}
= \vheta_{GX}G(F\eta_{GX}\zeta_{X})
\stackrel{\eqref{eq:adj-phi}}{=} \pHi_{GX,X}(F\eta_{GX}\zeta_{X})\\
&\bydef[]{\zeta_{X}} \pHi_{GX,X}(F\eta_{GX}\delta_{GX}\epsilon_{X})
\end{align*}
shows the first equality. The second one can be seen from
\begin{align*}
F\eta_{X}\delta_{X}
&= F\eta_{X}\delta_{X}\hl{1_{FX}}
\stackrel{\eqref{eq:adj-F}}{=}
F\eta_{X}\hl{\delta_{X}F\vheta_{X}}\epsilon_{FX}
\bynt{delta} F\eta_{X}FF\vheta_{X}\delta_{GFX}\epsilon_{FX}\\
&\bydef[]{\zeta_{FX}} F(\hl{\eta_{X}F\vheta_{X}})\zeta_{FX}
\bynt{eta} F(\vheta_{X}\eta_{GFX})\zeta_{FX}
= F\vheta_{X}F\eta_{GFX}\zeta_{FX}.
\end{align*}
\item We start by showing
\m{\tilde{\delta}_{X} G \tdelta_{X}
= \pHi_{GX,G^2X}(\pHi_{FGX,GX}(\pHi_{F^2GX,X}(%
\delta_{FGX}\zeta_{X})))}.
This equality follows from
\begin{align*}
\tdelta_{X}G\tdelta_{X}\
&\bydef[]{\tdelta_{X}} \pHi_{GX,GX}(\mu_{X})G\tdelta_{X}
\stackrel{\eqref{eq:adj-phi}}{=} \vheta_{GX}G\mu_{X}G\tdelta_{X}
= \vheta_{GX}G(\mu_{X}\tdelta_{X}) \\
&\stackrel[]{\eqref{eq:adj-phi}}{=}
\pHi_{GX,G^2X}(\mu_{X}\tdelta_{X}),
\end{align*}
together with
\begin{align*}
\mu_{X}\tdelta_{X}\
&\bydef[]{\mu_{X}} \pHi_{FGX,X}(\zeta_{X})\tdelta_{X}
\stackrel{\eqref{eq:adj-phi}}{=} \vheta_{FGX}G\zeta_{X}\tdelta_{X}
\bydef{\tdelta_{X}} \vheta_{FGX}G\zeta_{X}\pHi_{GX,GX}(\mu_{X})\\
&\stackrel[]{\eqref{eq:adj-phi}}{=}
\vheta_{FGX}\hl{G\zeta_{X}\vheta_{GX}}G\mu_{X}
\bynt{vheta} \hl{\vheta_{FGX}\vheta_{GFFGX}}GFG\zeta_{X}G\mu_{X}\\
&\bynt[]{vheta} \vheta_{FGX}\hl{GF\vheta_{FGX}GFG\zeta_{X}G\mu_{X}}
= \vheta_{FGX}G(F\vheta_{FGX}FG\zeta_{X}\mu_{X})\\
&\stackrel[]{\eqref{eq:adj-phi}}{=}
\pHi_{FGX,GX}(F\vheta_{FGX}FG\zeta_{X}\mu_{X}),
\end{align*}
\begin{align*}
F&\vheta_{FGX}\hl{FG\zeta_{X}\mu_{X}}
\bynt{mu} F\vheta_{FGX}\mu_{FFGX}G\zeta_{X}\\
&\bydef[]{\mu_{FFGX}}
F\vheta_{FGX}\pHi_{FGFFGX,FFGX}(\zeta_{FFGX})G\zeta_{X}\\
&\stackrel[]{\eqref{eq:adj-phi}}{=}
\hl{F\vheta_{FGX}\vheta_{FGFFGX}}G\zeta_{FFGX}G\zeta_{X}
\bynt{vheta} \vheta_{FFGX}
\hl{GFF\vheta_{FGX}G\zeta_{FFGX}G\zeta_{X}}\\
&= \vheta_{FFGX} G(FF\vheta_{FGX}\zeta_{FFGX}\zeta_{X})
\stackrel{\eqref{eq:adj-phi}}{=}
\pHi_{FFGX,X}(FF\vheta_{FGX}\zeta_{FFGX}\zeta_{X})
\end{align*}
and
\begin{align*}
F^2&\vheta_{FGX}\hl{\zeta_{F^2GX}\zeta_{X}}
\bynt{zeta} \hl{F^2\vheta_{FGX}F^2G\zeta_{X}}\zeta_{X}
= F^2(\vheta_{FGX}G\zeta_{X})\zeta_{X}\\
&\bydef[]{\zeta_{X}}
\hl{F^2(\vheta_{FGX}G\zeta_{X})\delta_{GX}}\epsilon_{X}\\
&\bynt[]{delta} \delta_{FGX}F(\vheta_{FGX}G\zeta_{X})\epsilon_{X}
= \delta_{FGX}F\vheta_{FGX}\hl{FG\zeta_{X}\epsilon_{X}}\\
&\bynt[]{epsilon}
\delta_{FGX}\hl{F\vheta_{FGX}\epsilon_{FFGX}}\zeta_{X}
\stackrel{\eqref{eq:adj-F}}{=} \delta_{FGX}1_{FFGX}\zeta_{X}
= \delta_{FGX}\zeta_{X}.
\end{align*}
We continue with the equality
\m{\tdelta_{X}\tdelta_{GX}
= \pHi_{GX,G^2X}(\pHi_{FGX,GX}(\pHi_{F^2GX,X}(%
F\delta_{GX}\zeta_{X})))},
following from
\begin{align*}
\tdelta_{X}\tdelta_{GX}\
&\bydef[]{\tdelta} \pHi_{GX,GX}(\mu_{X})\pHi_{G^2X,G^2X}(\mu_{GX})
\stackrel{\eqref{eq:adj-phi}}{=}
\hl{\apply{\vheta_{GX}G\mu_{X}}\vheta_{G^2X}}G\mu_{GX}\\
&\bynt[]{vheta}
\vheta_{GX}\hl{G\hl{F\apply{\vheta_{GX}G\mu_{X}}}G\mu_{GX}}
= \vheta_{GX}G\apply{F\vheta_{GX}FG\mu_{X}\mu_{GX}}\\
&\stackrel[]{\eqref{eq:adj-phi}}{=}
\pHi_{GX,G^2X}\apply{F\vheta_{GX}FG\mu_{X}\mu_{GX}},
\end{align*}
\begin{align*}
F\vheta_{GX}\hl{FG\mu_{X}\mu_{GX}}
&\bynt[]{mu} F\vheta_{GX}\mu_{FGX}G\mu_{X}
\bydef{\mu_{FGX}}F\vheta_{GX}\pHi_{FGFGX,FGX}(\zeta_{FGX})G\mu_{X}\\
&\stackrel[]{\eqref{eq:adj-phi}}{=}
\hl{F\vheta_{GX}\vheta_{FGFGX}}G\zeta_{FGX}G\mu_{X}
\bynt{vheta} \vheta_{FGX}\hl{GFF\vheta_{GX}G\zeta_{FGX}G\mu_{X}}\\
&= \vheta_{FGX}G\apply{F^2\vheta_{GX}\zeta_{FGX}\mu_{X}}
\stackrel{\eqref{eq:adj-phi}}{=}
\pHi_{FGX,GX}\apply{F^2\vheta_{GX}\zeta_{FGX}\mu_{X}}
\end{align*}
and
\begin{align*}
F^2&\vheta_{GX}\hl{\zeta_{FGX}\mu_{X}}
\bynt{zeta} \hl{F^2\vheta_{GX}F^2G\mu_{X}}\zeta_{GX}
= F^2\apply{\vheta_{GX}G\mu_{X}}\zeta_{GX}\\
&\bydef[]{\zeta_{GX}}
\hl{F^2\apply{\vheta_{GX}G\mu_{X}}\delta_{G^2X}}\epsilon_{GX}
\bynt{delta} \delta_{GX}F\apply{\vheta_{GX}G\mu_{X}}\epsilon_{GX}\\
&=\delta_{GX}F\vheta_{GX}\hl{FG\mu_{X}\epsilon_{GX}}
\bynt{epsilon} \delta_{GX}\hl{F\vheta_{GX}\epsilon_{FGX}}\mu_{X}
\stackrel{\eqref{eq:adj-F}}{=} \delta_{GX}1_{FGX}\mu_{X}\\
&\bydef[]{\mu_{X}} \delta_{GX}\pHi_{FGX,X}\apply{\zeta_{X}}
\stackrel{\eqref{eq:adj-phi}}{=}
\hl{\delta_{GX}\vheta_{FGX}}G\zeta_{X}
\bynt{vheta} \vheta_{FFGX}\hl{GF\delta_{GX}G\zeta_{X}} \\
&=\vheta_{FFGX}G\apply{F\delta_{GX}\zeta_{X}}
\stackrel{\eqref{eq:adj-phi}}{=}
\pHi_{F^2GX,X}\apply{F\delta_{GX}\zeta_{X}}.
\end{align*}
Furthermore, the remaining equalities,
\begin{align*}
F\delta_{X}\delta_{X}
&= F\delta_{X}\delta_{X}\hl{1_{FX}}
\stackrel{\eqref{eq:adj-F}}{=}
F\delta_{X}\hl{\delta_{X}F\vheta_{X}}\epsilon_{FX}
\bynt{delta}F\delta_{X}F^2\vheta_{X}\hl{\delta_{GFX}\epsilon_{FX}}\\
&\bydef[]{\zeta_{FX}} F\apply{\hl{\delta_{X}F\vheta_{X}}} \zeta_{FX}
\bynt{delta} F\apply{F^2\vheta_{X}\delta_{GFX}}\zeta_{FX}
= F^3\vheta_{X}F\delta_{GFX}\zeta_{FX}
%
\intertext{and}
%
\delta_{FX}\delta_{X}
&=\delta_{FX}\delta_{X}\hl{1_{FX}}
\stackrel{\eqref{eq:adj-F}}{=}
\delta_{FX}\hl{\delta_{X}F\vheta_{X}}\epsilon_{FX}
\bynt{delta}\delta_{FX}F^2\vheta_{X}\hl{\delta_{GFX}\epsilon_{FX}}\\
&\bydef[]{\zeta_{FX}} \hl{\delta_{FX}F^2\vheta_{X}}\zeta_{FX}
\bynt{delta} F^2F\vheta_{X}\delta_{FGFX}\zeta_{FX}
= F^3\vheta_{X}\delta_{FGFX}\zeta_{FX}
\end{align*}
can be verified.\qedhere
\end{enumerate}
\end{proof}
\par
\begin{proposition}\label{prop:Fmon-Gcomon}
Let \m{\cat} be a category and \m{F,G \in \EndOp \cat} be two adjoint
endo\dash{}functors (\m{F \ladjoint G}). We denote the corresponding
natural equivalence between the hom\dash{}sets by
\m{\mor{\Hom(F,-)}{\pHi}{\Hom(-,G)}}, the unit by
\m{\mor{1_{\cat}}{\vheta}{GF}} and the co\dash{}unit by
\m{\mor{FG}{\epsilon}{1_{\cat}}}.
\par
Furthermore, let two natural transformations \m{\mor{FF}{\delta}{F}} and
\m{\mor{1_{\cat}}{\eta}{F}} be given and the corresponding natural
transformations \m{\mor{FFG}{\zeta}{1_{\cat}}}, \m{\mor{FG}{\mu}{G}},
\m{\mor{G}{\tilde{\delta}}{GG}} and \m{\mor{G}{\tilde{\eta}}{1_{\cat}}} be
defined as in Lemma~\ref{lem:Fmon-def-Gcomon}.
\par
Then the following equivalences hold:
\begin{enumerate}[(a)]
\item $\begin{aligned}[t]
\forall X \in \cat\colon \ \eta_{FX}\delta_{X} = 1_{FX}
&\iff\forall X \in \cat\colon\ \tdelta_{X} G\teta_{X} = 1_{GX}\\
&\iff\forall X \in \cat\colon\ \eta_{FGX}\zeta_{X}=\epsilon_{X}.
\end{aligned}$
\item $\begin{aligned}[t]
\forall X \in \cat\colon\ F\eta_{X}\delta_{X} = 1_{FX}
&\iff\forall X \in\cat\colon\ F\eta_{GX}\zeta_{X}=\epsilon_{X}\\
&\iff\forall X \in\cat\colon\ \tdelta_{X} \teta_{GX} = 1_{GX}.
\end{aligned}$
\item $\begin{aligned}[t]
\forall X \in \cat\colon\
F\delta_{X} \delta_{X} = \delta_{FX}\delta_{X}
\iff
\forall X \in \cat\colon \
\tdelta_{X}\tdelta_{GX} = \tdelta_{X}G\tdelta_{X}.
\end{aligned}$
\item \m{\apply{F,\delta,\eta}} is a \emPh{monad} if and only if
\m{\apply{G,\tdelta,\teta}} is a \emPh{comonad}.
\end{enumerate}
\end{proposition}
\begin{proof}
We rely upon Lemma~\ref{lem:Fmon-def-Gcomon} to prove the stated
equivalences.
Furthermore, note that for every \m{X\in \cat} the following holds:
\begin{equation}\label{eq:phi-eps=1}
\pHi_{GX,X}(\epsilon_{X})
\stackrel{\eqref{eq:adj-phi}}{=} \vheta_{GX}G\epsilon_{X}
\stackrel{\eqref{eq:adj-G}}{=} 1_{GX}.
\end{equation}
\begin{enumerate}[(a)]
\item First, for a fixed object \m{X \in\cat} it is easy to see, using
Equation~\eqref{eq:phi-eps=1} and
Lemma~\ref{lem:Fmon-def-Gcomon}\eqref{item:tdelta-Gteta} that the
equalities
\begin{align*}
\tdelta_{X}G\teta_{X} = 1_{GX}
&&\text{and}&&
\pHi_{GX,X}\apply{\eta_{FGX}\delta_{GX}\epsilon_{X}}
= \pHi_{GX,X}(\epsilon_{X})
\end{align*}
are equivalent. As \m{\pHi_{GX,X}} is a bijection, the latter
equality is equivalent to
\m{\eta_{FGX}\delta_{GX}\epsilon_{X} = \epsilon_{X}}. Taking into
account that \m{\zeta_{X}=\delta_{GX}\epsilon_{X}}, the equivalence
of the two statements on the right\dash{}hand side is proven.
\par
Now assume that \m{\eta_{FX}\delta_{X} = 1_{FX}} holds for all
\m{X \in \cat}. For every \m{Y \in \cat}, substituting \m{X = GY} in
this equality and composition with \m{\epsilon_{Y}} yields
\begin{equation*}
\eta_{FGY}\delta_{GY} \epsilon_{Y}
= 1_{FGY}\epsilon_{Y} = \epsilon_{Y}.
\end{equation*}
Conversely, suppose that this holds for all \m{Y \in \cat}.
Considering any \m{X \in \cat} and substituting \m{Y=FX} yields the
equality \m{\eta_{FGFX}\delta_{GFX}\epsilon_{FX} = \epsilon_{FX}}.
From this and
Lemma~\ref{lem:Fmon-def-Gcomon}\eqref{item:tdelta-Gteta} one obtains
\begin{equation*}
\eta_{FX}\delta_{X}
\stackrel{\text{\ref{lem:Fmon-def-Gcomon}%
\eqref{item:tdelta-Gteta}}}{=}
F\vheta_{X} \hl{\eta_{FGFX}\delta_{GFX}\epsilon_{FX}}
\vs F\vheta_{X} \epsilon_{FX}
\stackrel{\eqref{eq:adj-F}}{=} 1_{FX}.
\end{equation*}
\item Again, for fixed objects \m{X\in \cat} the equalities
\begin{align*}
\tdelta_{X}\teta_{GX} = 1_{GX}
&&\text{and}&&
\pHi_{GX,X}\apply{F\eta_{GX}\delta_{GX}\epsilon_{X}}
= \pHi_{GX,X}(\epsilon_{X})
\end{align*}
are equivalent, using Equation~\eqref{eq:phi-eps=1} and
Lemma~\ref{lem:Fmon-def-Gcomon}\eqref{item:tdelta-tetaG}. As
\m{\pHi_{GX,X}} is bijective, the latter equality is equivalent to
\m{F\eta_{GX}\delta_{GX}\epsilon_{X}=\epsilon_{X}}, showing that the
two assertions on the right\dash{}hand side are equivalent. \par
As above assume now that \m{F\eta_{X}\delta_{X}=1_{FX}} holds for
all \m{X\in\cat}. Substituting \m{X=GY} for an arbitrary
\m{Y \in \cat} and composing with \m{\epsilon_{Y}}, yields
\begin{equation*}
F\eta_{GY}\delta_{GY}\epsilon_{Y}=1_{FGY}\epsilon_{Y}=\epsilon_{Y}.
\end{equation*}
Conversely, if this equation holds for all \m{Y \in\cat}, then
substitution of \m{Y=FX} and application of
Lemma~\ref{lem:Fmon-def-Gcomon}\eqref{item:tdelta-tetaG} yield
\[F\eta_{X}\delta_{X}
\stackrel{\text{\ref{lem:Fmon-def-Gcomon}%
\eqref{item:tdelta-tetaG}}}{=}
F\vheta_{X}\hl{F\eta_{GFX}\zeta_{FX}}
\vs F\vheta_{X}\epsilon_{FX}
\stackrel{\eqref{eq:adj-F}}{=} 1_{FX}.\]
\item Assume that \m{F\delta_{X} \delta_{X} =\delta_{FX}\delta_{X}} holds
for all \m{X \in \cat} and consider any \m{Y \in \cat}. Substituting
\m{X=GY} in the given equality yields
\m{F\delta_{GY}\delta_{GY}
\ovflhbx{0.9pt}=\ovflhbx{0.87pt} \delta_{FGY}\delta_{GY}},
whence one obtains \m{F\delta_{GY}\zeta_{Y} = \delta_{FGY}\zeta_{Y}}
by composition with \m{\epsilon_{Y}}. From the latter equality one
obtains
\begin{align*}
\tdelta_{Y}\tdelta_{GY}\quad
&\stackrel[]{\text{\ref{lem:Fmon-def-Gcomon}%
\eqref{item:tdelta-Gtdelta-tdelta-tdeltaG}}}{=}
\pHi_{GY,G^2Y}(\pHi_{FGY,GY}(\pHi_{F^2GY,Y}(F\delta_{GY}
\zeta_{Y}))) \\
&\vs[]
\pHi_{GY,G^2Y}(\pHi_{FGY,GY}(\pHi_{F^2GY,Y}(%
\delta_{FGY}\zeta_{Y})))
\stackrel{\text{\ref{lem:Fmon-def-Gcomon}%
\eqref{item:tdelta-Gtdelta-tdelta-tdeltaG}}}{=}
\tdelta_{Y} G \tdelta_{Y}.
\end{align*}
Conversely, assume that this equality holds for all \m{Y\in \cat}.
Substituting \m{Y=\!GX} with an arbitrary \m{X \in \cat} yields
\begin{align*}
\pHi&_{GFX,G^2FX}(\pHi_{FGFX,GFX}(\pHi_{F^2GFX,FX}(F\delta_{GFX}%
\zeta_{FX})))
\stackrel{\text{\ref{lem:Fmon-def-Gcomon}%
\eqref{item:tdelta-Gtdelta-tdelta-tdeltaG}}}{=}
\tdelta_{FX}\tdelta_{GFX} \\
&=\tdelta_{FX} G \tdelta_{FX}
\stackrel{\text{\ref{lem:Fmon-def-Gcomon}%
\eqref{item:tdelta-Gtdelta-tdelta-tdeltaG}}}{=}
\pHi_{GFX,G^2FX}(\pHi_{FGFX,GFX}(\pHi_{F^2GFX,FX}(%
\delta_{FGFX}\zeta_{FX}))),
\end{align*}
whence \m{F\delta_{GFX} \zeta_{FX}=\delta_{FGFX}\zeta_{FX}} as
\m{\pHi} is a natural equivalence, so all its mappings are
bijective. Composing the result with \m{F^3\vheta_{X}} yields
\begin{equation*}
F\delta_{X}\delta_{X}
\stackrel{\text{\ref{lem:Fmon-def-Gcomon}%
\eqref{item:tdelta-Gtdelta-tdelta-tdeltaG}}}{=}
F^3\vheta_{X} \hl{F\delta_{GFX}\zeta_{FX}}
\vs \hl{F^3\vheta_{X}\delta_{FGFX}\zeta_{FX}}
\stackrel{\text{\ref{lem:Fmon-def-Gcomon}%
\eqref{item:tdelta-Gtdelta-tdelta-tdeltaG}}}{=}
\delta_{FX}\delta_{X}.
\end{equation*}
\item This statement is a combination of the equivalences just shown.%
\qedhere
\end{enumerate}
\end{proof}
\par
In the previous result we have established a relationship between monads
for \m{F} and comonads for an adjoint endo\dash{}functor \m{G}. This
connection extends to monadic algebras and comonadic coalgebras:
\par
\begin{proposition}\label{prop:Falg-Gcoalg}
Let \m{\cat} be a category and \m{F,G \in \EndOp \cat} two adjoint
endo\dash{}functors (\m{F \ladjoint G}). We denote the corresponding
natural equivalence between the hom\dash{}sets by
\m{\mor{\Hom(F,-)}{\pHi}{\Hom(-,G)}}, the unit if the adjunction by
\m{\mor{1_{\cat}}{\vheta}{GF}} and the co\dash{}unit by
\m{\mor{FG}{\epsilon}{1_{\cat}}}.
\par
Furthermore, let two natural transformations \m{\mor{FF}{\delta}{F}} and
\m{\mor{1_{\cat}}{\eta}{F}} be given and the corresponding natural
transformations \m{\mor{FFG}{\zeta}{1_{\cat}}}, \m{\mor{FG}{\mu}{G}},
\m{\mor{G}{\tilde{\delta}}{GG}} and \m{\mor{G}{\tilde{\eta}}{1_{\cat}}} be
defined as in Lemma~\ref{lem:Fmon-def-Gcomon}.
\par
Assume that \m{\apply{F,\delta,\eta}} is a \emPh{monad} with its
associated \emPh{comonad} \m{\apply{G,\tdelta,\teta}} as in
Proposition~\ref{prop:Fmon-Gcomon}. Let \m{X \in \cat} be an object and
\m{\mor{FX}{\aLpha}{X}} a morphism. Defining the morphism
\m{\mor{X}{\bEta\defeq \pHi_{X,X}(\aLpha) = \vheta_{X}G\aLpha}{GX}},
we have
\begin{enumerate}[(a)]
\item\label{item:beta-tdelta-delta-alpha}
\m{\bEta\tdelta_{X} = \pHi_{X,GX}(\pHi_{FX,X}(\delta_{X}\aLpha))}
and \m{\bEta G\bEta = \pHi_{X,GX}(\pHi_{FX,X}(F\aLpha \aLpha))}.
\item\label{item:beta-teta-eta-alpha}
\m{\bEta\teta_{X}= \eta_{X}\aLpha}.
\item\label{item:alpha-mon-if-beta-comon}
\begin{minipage}[t]{143.9pt}%{0.35\textwidth}
\m{(X,\aLpha)} is a \emPh{monadic algebra}\\
w.r.t.\ \m{\apply{F,\delta,\eta}}
\end{minipage}
\hfill
\begin{minipage}[t]{32.7pt}
if and\\ only if
\end{minipage}
\hfill
\begin{minipage}[t]{166.5pt}%{0.45\textwidth}
\m{(X,\bEta)} is a \emPh{comonadic coalgebra}\\
w.r.t.\ \m{\apply{G,\tdelta,\teta}}.
\end{minipage}
\item Defining \m{\Phi\apply{(X,\aLpha)} \defeq (X,\bEta)} on objects and
\[\Phi\apply{\mor{(X,\aLpha)}{h}{(X',\aLpha')}}
\defeq \mor{\Phi((X,\aLpha))}{h}{\Phi((X',\aLpha'))}\]
on homomorphisms yields a well\dash{}defined functor between the
category of monadic \nbdd{F}algebras and comonadic
\nbdd{G}coalgebras making both categories \emPh{iso\-morph\-ic}.
\end{enumerate}
\end{proposition}
\par
At this point it should be noted that the previous result is not entirely
new. It seems to be the case that it has passed into common knowledge, yet
we found it hard to give a specific reference, e.g.\ to one of the common
text books on category theory.
In~\cite[2.6(1)]{BoehmBrzWisb_MonComon} the authors collect the proof from
different references, one of which is the original paper by Eilenberg and
Moore, \cite[Theorem~3.1]{EilenbergMoore_AdjointFunctorsTriples}, showing
that every monad arises from a naturally given adjunction. Namely, this
adjunction is the one between the free and the forgetful functor of the
category of monadic algebras\footnote{%
In~\cite{BoehmBrzWisb_MonComon} these algebras are called
\nbd{\m{\mathbb{F}}}modules of the monad
\m{\mathbb{F} =\apply{F,\delta,\eta}}.}
belonging to the given monad, later also known as Eilenberg\dash{}Moore
algebras of the monad and Eilenberg\dash{}Moore category of the monad,
respectively.
\par
Our motivation for giving an explicit proof here was in particular to show
in detail the concrete constructions that link the monadic algebras and
comonadic coalgebras for an adjoint pair of endo\dash{}functors, so that
they are easily applicable in the concrete case of dynamical systems.
\par
\begin{proof} The results of the proposition are proven using similar
manipulations as in the proof of Lemma~\ref{lem:Fmon-def-Gcomon}. Recall
that for objects \m{X,Y \in \cat} and any morphism \m{\mor{X}{h}{Y}} the
following diagrams commute by the naturality of the transformations
\m{\tdelta} and \m{\teta}:\par
\noindent%
\begin{subequations}\label{diag:nat-trans-tilde}
\begin{minipage}{0.49\linewidth}
\begin{align}\tag{\ref{diag:nat-trans-tilde}\m{\tdelta}}%
\label{diag:trans-tdelta}
\begin{xy}\xymatrix@!C{%
GGX\ar[r]^{GGh}& GGY\\
GX\ar[r]^{Gh}\ar[u]^{\tdelta_{X}}&GY\ar[u]_{\tdelta_{Y}}
}\end{xy}
\end{align}
\end{minipage}
\begin{minipage}{0.49\linewidth}
\begin{align}\tag{\ref{diag:nat-trans-tilde}\m{\teta}}%
\label{diag:trans-teta}
\begin{xy}\xymatrix@!C{%
GX\ar[r]^{Gh}\ar[d]^{\teta_{X}}& GY\ar[d]_{\teta_{Y}}\\
X\ar[r]^{h}&Y
}\end{xy}
\end{align}
\end{minipage}
\end{subequations}
\begin{enumerate}[(a)]
\item We start with the longest calculation:
\begin{align*}
\bEta\tdelta_{X}
&\bydef[]{\bEta} \vheta_{X} \hl{G\aLpha \tdelta_{X}}
\bynt{tdelta} \vheta_{X} \tdelta_{FX}G^2\aLpha
\bydef{\tdelta_{FX}} \hl{\vheta_{X} \vheta_{GFX}}G\mu_{FX}G^2\aLpha\\
&\bynt[]{vheta} \vheta_{X}\hl{GF\vheta_{X}G\mu_{FX}G^2\aLpha}
=\vheta_{X}G\apply{F\vheta_{X}\mu_{FX}G\aLpha}
\stackrel{\eqref{eq:adj-phi}}{=}
\pHi_{X,GX}\apply{F\vheta_{X}\mu_{FX}G\aLpha},
\end{align*}
\begin{align*}
F\vheta_{X}\mu_{FX}G\aLpha\quad
&\bydef[]{\mu_{FX}} \hl{F\vheta_{X}\vheta_{FGFX}}G\zeta_{FX}G\aLpha
\bynt{vheta} \vheta_{FX}\hl{GFF\vheta_{X}G\zeta_{FX}G\aLpha}\\
&= \vheta_{FX}G\apply{FF\vheta_{X}\zeta_{FX}\aLpha}
\stackrel{\eqref{eq:adj-phi}}{=}
\pHi_{FX,X}\apply{F^2\vheta_{X}\zeta_{FX}\aLpha}
\end{align*}
and
\begin{align*}
F^2\vheta_{X}\hl{\zeta_{FX}\aLpha}\quad
&\bynt[]{zeta} \hl{F^2\vheta_{X}F^2G\aLpha}\zeta_{X}
= F^2\apply{\vheta_{X}G\aLpha}\zeta_{X}
\bydef{\zeta_{X}}
\hl{F^2\apply{\vheta_{X}G\aLpha}\delta_{GX}}\epsilon_{X}\\
&\bynt[]{delta} \delta_{X} F\apply{\vheta_{X}G\aLpha}\epsilon_{X}
=\delta_{X} F\vheta_{X}\hl{FG\aLpha\epsilon_{X}}
\bynt{epsilon} \delta_{X}\hl{F\vheta_{X}\epsilon_{FX}}\aLpha \\
&\stackrel[]{\eqref{eq:adj-F}}{=} \delta_{X}1_{FX}\aLpha
= \delta_{X}\aLpha.
\end{align*}
The second part is less complicated:
\begin{align*}
\bEta G\bEta\
&\bydef[]{\bEta}\vheta_{X}G\aLpha G\bEta\vheta_{X}
= \vheta_{X}G(\aLpha\bEta)
\stackrel{\eqref{eq:adj-phi}}{=} \pHi_{X,GX}(\aLpha\bEta)
\intertext{and}
\aLpha\bEta\
&\bydef[]{\bEta} \hl{\aLpha\vheta_{X}}G\aLpha
\bynt{vheta} \vheta_{FX}\hl{GF\aLpha G\aLpha}
= \vheta_{FX} G\apply{F\aLpha\aLpha}
\stackrel{\eqref{eq:adj-phi}}{=} \pHi_{FX,X}\apply{F\aLpha\aLpha}.
\end{align*}
\item Applying similar methods one can verify
\begin{align*}
\bEta\teta_{X}\
&\bydef[]{\bEta} \vheta_{X}\hl{G\aLpha\teta_{X}}
\bynt{teta} \vheta_{X}\teta_{FX}\aLpha
\bydef{\teta_{FX}} \hl{\vheta_{X} \eta_{GFX}}\epsilon_{FX}\aLpha
\bynt{eta} \eta_{X}\hl{F\vheta_{X}\epsilon_{FX}}\aLpha\\
&\stackrel[]{\eqref{eq:adj-F}}{=} \eta_{X}1_{FX} \aLpha
= \eta_{X}\aLpha.
\end{align*}
\item By Item~\eqref{item:beta-tdelta-delta-alpha} and the bijectivity of
the morphisms \m{\pHi} the equality
\m{\delta_{X}\aLpha = F\aLpha\aLpha} is equivalent to
\m{\bEta\tdelta_{X} = \bEta G\bEta}.
Likewise, by Item~\eqref{item:beta-teta-eta-alpha}
\m{\eta_{X}\aLpha = 1_{X}} holds if and only if
\m{\bEta\teta_{X}= 1_{X}}. Therefore,
\m{(X,\aLpha)} is a monadic algebra exactly if \m{(X,\bEta)} is a
comonadic coalgebra.
\item It remains to be shown that the exhibited correspondence extends
nicely to homomorphisms. Functoriality of \m{\Phi} is trivial once
it has been shown that \m{\Phi} is well\dash{}defined. To this end
consider arbitrary \nbd{\m{F}}algebras \m{(X,\aLpha)} and
\m{(X',\aLpha')} and a morphism \m{\mor{X}{h}{X'}}. Name the images
of \m{\Phi} \m{(X,\bEta)\defeq \Phi\apply{(X,\aLpha)}} and
\m{(X',\bEta') \defeq \Phi\apply{\apply{X',\aLpha'}}},
i.e.\ \m{\bEta \defeq \vheta_{X} G\aLpha} and
\m{\bEta' \defeq \vheta_{X'}G\aLpha'}. It will be shown that \m{h}
satisfies the homomorphism property w.r.t.\ \m{(X,\aLpha)} and
\m{(X',\aLpha')}, i.e.\ \m{\aLpha h= Fh \aLpha'}, if and only if it
satisfies it w.r.t.\ \m{(X,\bEta)} and
\m{(X'\ovflhbx{0.5pt},\bEta')},
\ie{}\ovflhbx{0.265pt} \m{h \bEta' \ovflhbx{0.5pt}= \bEta Gh}. So
the task is to verify that the left diagram commutes if and only if
the one on the right\dash{}hand side commutes:
\begin{align*}
\begin{xy}\xymatrix@!C{%
FX\ar[r]^{Fh}\ar[d]^{\aLpha}& FX'\ar[d]_{\aLpha'}\\
X\ar[r]^{h}&X'
}\end{xy}&&
\begin{xy}\xymatrix@!C{%
GX\ar[r]^{Gh}& GX'\\
X\ar[r]^{h}\ar[u]^{\bEta}&X'\ar[u]_{\bEta'}
}\end{xy}
\end{align*}
This can be seen as follows
\begin{align*}
h \bEta' \
&\bydef[]{\bEta'}
\hl{h \vheta_{X'}} G\aLpha'
\bynt{vheta} \vheta_{X} \hl{GFhG\aLpha'}
= \vheta_{X} G\apply{Fh \aLpha'}
\stackrel{\eqref{eq:adj-phi}}{=} \pHi_{X,X'}(Fh \aLpha')\\
\bEta Gh \
&\bydef[]{\bEta} \vheta_{X} \hl{G\aLpha Gh}
= \vheta_{X} G\apply{\aLpha h}
\stackrel{\eqref{eq:adj-phi}}{=} \pHi_{X,X'}(\aLpha h).
\end{align*}
As \m{\pHi_{X,X'}} is bijective, the desired equivalence holds.
\par
As \m{\pHi_{X,X}} is bijective, one can define for any
\nbd{\m{G}}coalgebra \m{(X,\bEta)} an \nbd{\m{F}}algebra
\m{(X,\aLpha)\defeq \Phi^{-1}((X,\bEta))
\defeq \apply{X,\pHi_{X,X}^{-1}(\bEta)}}.
By Item~\eqref{item:alpha-mon-if-beta-comon} and since \m{\pHi_{X,X}}
is bijective, this transforms comonadic \nbdd{G}coalgebras into
monadic \nbdd{F}algebras. By the equivalence just proven, also
\[\Phi^{-1}\apply{\mor{(X,\bEta)}{h}{(X',\bEta')}}
\defeq \mor{\Phi^{-1}((X,\bEta))}{h}{\Phi^{-1}((X,\bEta'))}\]
is well\dash{}defined on homomorphisms, yielding an inverse functor
for \m{\Phi}.\qedhere
\end{enumerate}
\end{proof}
\par
It is evident from the proof, that \m{\Phi} and its inverse can be seen as
inverse functors between arbitrary \nbd{\m{F}}algebras and
\nbd{\m{G}}coalgebras that restrict docilely to monadic algebras w.r.t.\
\m{\apply{F,\delta,\eta}} and comonadic coalgebras w.r.t.\
\m{\apply{G,\tdelta,\teta}}, respectively.
\par
Dualising the two previous results yields the converse implication:
\par
\begin{proposition}\label{prop:Gcoalg-Falg}
Let \m{\cat} be a category and \m{F,G \in \EndOp \cat} be two adjoint
endo\dash{}functors (\m{F \ladjoint G}). We denote the corresponding
natural equivalence between the hom\dash{}sets by
\m{\mor{\Hom(F,-)}{\pHi}{\Hom(-,G)}}, the unit by
\m{\mor{1_{\cat}}{\vheta}{GF}} and the co\dash{}unit by
\m{\mor{FG}{\epsilon}{1_{\cat}}}.
\par
Furthermore, let two natural transformations \m{\mor{G}{\tdelta}{GG}} and
\m{\mor{G}{\teta}{1_{\cat}}} be given. Define natural transformations
\m{\mor{FF}{\hat{\tdelta}}{F}} and \m{\mor{1_{\cat}}{\hat{\teta}}{F}}
dually as in Lemma~\ref{lem:Fmon-def-Gcomon}, i.e.\
\m{\hat{\tdelta}_{Y}\defeq
\pHi_{FY,FY}^{-1}(\pHi_{Y, GFY}^{-1}(\vheta_{Y}\tdelta_{FY}))}
and \m{\hat{\teta}_{Y} \defeq \vheta_{Y} \teta_{FY}}.
\par
Let \m{X \in \cat} be an object and \m{\mor{X}{\bEta}{GX}} a morphism.
Defining the morphism
\m{\mor{FX}{\aLpha\defeq \pHi^{-1}_{X,X}(\bEta)}{X}}, we have
\begin{enumerate}[(a)]
\item \m{\mor{FF}{\hat{\tdelta}}{F}} and
\m{\mor{1_{\cat}}{\hat{\teta}}{F}}
are indeed natural transformations.
\item \m{\apply{F,\hat{\tdelta},\hat{\teta}}} is a monad if and only if
\m{\apply{G,\tdelta, \teta}} is a comonad.
\item \begin{minipage}[t]{143.9pt}%{0.35\textwidth}
\m{(X,\aLpha)} is a \emPh{monadic algebra}\\
w.r.t.\ \m{\apply{F,\hat{\tdelta},\hat{\teta}}}
\end{minipage}
\hfill
\begin{minipage}[t]{32.7pt}
if and\\ only if
\end{minipage}
\hfill
\begin{minipage}[t]{166.5pt}%{0.45\textwidth}
\m{(X,\bEta)} is a \emPh{comonadic coalgebra}\\
w.r.t.\ \m{\apply{G,\tdelta,\teta}}.
\end{minipage}
\end{enumerate}
\end{proposition}
\begin{proof}
Consider the situation given in the proposition. Then
\m{F,G\in \EndOp\cat} can also be considered as endo\dash{}functors
\m{F,G \in \EndOp\catop} w.r.t.\ the opposite category of \m{\cat} (see
Remark~\ref{rem:opp-cat}). They are still adjoint, but \m{G\ladjoint F}
(see \eg~\cite[19.6]{cats}) and the corresponding natural equivalence is
\[\apply{\mor{\Hom(-,G)}{\pHi^{-1}}{\Hom(F,-)}}
=\apply{\mor{\Hom^{\partial}(G,-)}{\pHi^{-1}}{\Hom^{\partial}(-,F)}},\]
the unit is \m{\mor{1_{\catop}}{\epsilon}{FG}} and the co\dash{}unit is
\m{\mor{GF}{\vheta}{1_{\catop}}}. In \m{\catop} the natural
transformations \m{\mor{G}{\tdelta}{GG}} and \m{\mor{G}{\teta}{1_{\cat}}}
become \m{\mor{GG}{\tdelta}{G}} and \m{\mor{1_{\catop}}{\teta}{G}}, and
the morphism \m{\mor{X}{\bEta}{GX}} becomes \m{\mor{GX}{\bEta}{X}}.
Applying Propositions~\ref{prop:Fmon-Gcomon} and~\ref{prop:Falg-Gcoalg} to
this situation (in \m{\catop}) and reinterpreting the results in \m{\cat}
yields exactly the stated claims.
\end{proof}
\par
\begin{proposition}\label{prop:G->F--F->G--invers}
Let \m{\cat} be a category and \m{F,G \in \EndOp \cat} be two adjoint
endo\dash{}functors (\m{F \ladjoint G}). We denote the corresponding
natural equivalence between the hom\dash{}sets by
\m{\mor{\Hom(F,-)}{\pHi}{\Hom(-,G)}}, the unit by
\m{\mor{1_{\cat}}{\vheta}{GF}} and the co\dash{}unit by
\m{\mor{FG}{\epsilon}{1_{\cat}}}.
\par
The constructions of comonads out of monads and vice versa, presented in
the two previous propositions are mutually inverse, i.e.\
\begin{enumerate}[(a)]
\item \m{\displaystyle \apply{F,\delta, \eta}
\mapsto
\apply{G,\tdelta,\teta}
\mapsto
\apply{F,\hat{\tdelta},\hat{\teta}} = \apply{F,\delta, \eta}}.
\item \m{\displaystyle \apply{G,\tdelta,\teta}
\mapsto
\apply{F,\hat{\tdelta},\hat{\teta}}
\mapsto
\apply{G,\tilde{\hat{\tdelta}},\tilde{\hat{\teta}}}
= \apply{G,\tdelta,\teta}}.
\end{enumerate}
An analogous statement holds w.r.t.\ the monadic algebras and comonadic
coalgebras.
\end{proposition}
\begin{proof}
The final remark about algebras and coalgebras is trivial once the
assertions about the monads and comonads have been shown. It follows
directly from the bijectivity of the mapping \m{\pHi_{X,X}} and its
inverse. Thus, we will only prove the results dealing with monads.
\begin{enumerate}[(a)]
\item By definition one has
\m{\tdelta_{X}= \pHi_{GX,GX}\apply{\pHi_{FGX,X}\apply{\zeta_{X}}}}
and \m{\teta_{X} = \eta_{GX}\epsilon_{X}}.
It first has to be verified that
\m{\hat{\tdelta}_{X}
\bydef{\hat{\tdelta}}
\pHi^{-1}_{FX,FX}\apply{\pHi^{-1}_{X,GFX}\apply{%
\vheta_{X}\tdelta_{FX}}}
= \delta_{X}},
or equivalently
\m{\vheta_{X}\tdelta_{FX}
= \pHi_{FX,FX}\apply{\pHi_{X,GFX}\apply{\delta_{X}}}}.
Indeed, in detail we have
\begin{align*}
\vheta_{X}\tdelta_{FX} \quad
&\bydef[]{\tdelta_{FX}} \hl{\vheta_{X}\vheta_{GFX}}G\mu_{FX}
\bynt{vheta} \vheta_{X}\hl{GF\vheta_{X}G\mu_{FX}}
= \vheta_{X}G\apply{F\vheta_{X}\mu_{FX}} \\
&\stackrel[]{\eqref{eq:adj-phi}}{=}
\pHi_{X,GFX}\apply{F\vheta_{X}\mu_{FX}},\\
F\vheta_{X}\mu_{FX} \quad
&\bydef[]{\mu_{FX}} \hl{F\vheta_{X}\vheta_{FGFX}}G\zeta_{FX}
\bynt{vheta} \vheta_{FX}\hl{GF^2\vheta_{X}G\zeta_{FX}}
= \vheta_{FX}G\apply{F^2\vheta_{X}\zeta_{FX}}\\
&\stackrel[]{\eqref{eq:adj-phi}}{=}
\pHi_{FX,FX}\apply{F^2\vheta_{X}\zeta_{FX}}
\end{align*}
and
\begin{equation*}
F^2\vheta_{X}\zeta_{FX}
\bydef{\zeta_{FX}} \hl{F^2\vheta_{X}\delta_{GFX}}\epsilon_{FX}
\bynt{delta} \delta_{X}\hl{F\vheta_{X}\epsilon_{FX}}
\stackrel{\eqref{eq:adj-F}}{=} \delta_{X} 1_{FX} = \delta_{X}.
\end{equation*}
The remaining equality is easier to see:
\begin{equation*}
\hat{\teta}_{X}
\bydef{\hat{\teta}_{X}} \vheta_{X}\teta_{FX}
\bydef{\teta_{FX}} \hl{\vheta_{X}\eta_{GFX}}\epsilon_{FX}
\bynt{eta} \eta_{X} \hl{F\vheta_{X}\epsilon_{FX}}
\stackrel{\eqref{eq:adj-F}}{=} \eta_{X} 1_{FX} = \eta_{X}.
\end{equation*}
\item This fact follows from the previous item by dualisation, similarly
as in the proof of Proposition~\ref{prop:Gcoalg-Falg}.\qedhere
\end{enumerate}
\end{proof}
\par
As a consequence of Propositions~\ref{prop:Falg-Gcoalg},
\ref{prop:Gcoalg-Falg} and~\ref{prop:G->F--F->G--invers}, it does not
matter if we regard (abstract) dynamical systems as monadic algebras or
comonadic coalgebras. The coalgebraic perspective however offers us some
variability that is not necessarily available on the side of algebras.
Slight modifications of the signature \m{-^T} may result in a functor that
fails to have a left\dash{}adjoint, and thus the corresponding coalgebras
may lack a counterpart on the algebraic side.
\par
From the applications of coalgebra to transition systems in computer
science, a decent choice of related signature functors for the coalgebraic
formulation suggests itself. For our convenience and since it is very
common for transition systems, we state these functors for the case
\m{\cat=\Set}. Using \m{-^T} every state \m{x} of the coalgebra is mapped
to a \nbdd{T}sequence of successor states, the trajectory of \m{x\in X}.
This closely corresponds to a deterministic automaton with state
set \m{X} and possibly infinite alphabet \m{T}.
Its behaviour can be extended by observations (or outputs) from
a fixed set \m{A}. This is possible in at least two ways: one may add one
observation per trajectory, resulting in the functor
\m{X\mapsto A\times X^T}, or one per each successor state, yielding the
functor \m{X\mapsto \apply{A\times X}^T}. Instead of using a fixed set
\m{A} as observables, one may also try the state space itself, giving rise
to \m{X\mapsto X\times X^T}.
\par
Besides, non\dash{}determinism can be represented without any difficulties:
instead of assigning to each state a sequence of future states, one may
assign a \nbdd{T}sequence of subsets of possible successor states. This
is expressible using the endo\dash{}functor \m{X\mapsto \powerset{X}^T}.
\par
Of course, all these different features may also be combined in one
functor, such as \m{X\mapsto \apply{A\times \powerset{X}}^T}.
\par
%%%%%%%%% sorry, does not work %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \par\smallskip
% Finally, we also would like to mention that dynamical systems can be
% understood as weighted automata, too. The time structures \m{\N}, \m{\Z},
% \m{\R}, \m{\R_{\geq 0}}, \m{\R_{\leq 0}}, which are normally used for
% dynamical systems, indeed do not only carry the structure of a monoid (with
% addition), but also of a semiring (with addition and multiplication or
% maximum or minimum). This encourages a representation as a weighted
% automaton over a semiring given by the time space, \ie\ by a functor
% \m{X\mapsto T^{\apply{A\times X \coprod \set{0,1}}}}, where \m{A} is a
% one\dash{}element alphabet. \textbf{Question:} what should the weight of a
% transition from \m{x} to \m{y} be? There may be several, even infinitely
% many, or no time element \m{t\in T} such that \m{\aLpha(t,x)=y}. In the
% special cases \m{\N,\Z,\R,\R_{\geq 0}} one could maybe use the infimum
% over all such time points (if it exists) \dots
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We leave it as a task for future investigations to generalise these
functors to categories like \m{\Top} or \m{\Mea}, and to explore the
increased expressivity for particular examples of dynamical systems.
\par
\begin{comment}
\begin{remark}
\EM{Which adjoint endo\dash{}functors exist on \m{\Set}? \m{T\times -} and \m{-^T}!}
\end{remark}
\todo[inline]{delete this.}
\end{comment}
%\input{algebraicChaos.tex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% Open Problems and Future Research %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \section{Problems and Prospects for Future Research}%
% \label{SectionOpenProblems}
% Finally, some open problems are presented that emerged during the
% origination process of this work but, unfortunately, could not be solved
% in due time. Furthermore, we are going to have a look on interesting
% topics for future research.\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% Acknowledgements %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \addsec{Acknowledgements}\label{Section_Acknowledgements}
% Say something nice about people who supported your work.
% \backmatter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% List of Tables %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \listoftables
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% List of Symbols %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \nomenclature[EndC]{\m{\EndOp{\cat}}}{class of all endo\dash{}functors of a category \m{\cat}}
% \cleardoublepage
% \ohead{Index of Notation}
% \renewcommand{\nomname}{Index of Notation}
% \printnomenclature
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% Index %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \index{monadic algebra|see{algebra, monadic}}
% \cleardoublepage
% \ohead{\headmark}
% \renewcommand{\indexname}{Index of Terms}
% \thispagestyle{empty}
% \printindex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% Bibliography %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\small
% \bibliographystyle{amsplain}
\bibliographystyle{amsalpha}
\bibliography{bibtexfile}
\smallskip
\myContact{Mike Behrisch}{%
\TUDname,
\InstitutALG,
\Postleitzahletc
}{mike.behrisch@tu-dresden.de}%
%{+49\,351\,463\,34224}{+49\,351\,463\,34235}
\myContact{Sebastian Kerkhoff}{%
\TUDname,
\InstitutALG,
\Postleitzahletc
}{sebastian.kerkhoff@tu-dresden.de}%
%{+49\,351\,463\,34059}{+49\,351\,463\,34235}
\myContact{Reinhard Pöschel}{%
\TUDname,
\InstitutALG,
\Postleitzahletc
}{reinhard.poeschel@tu-dresden.de}%
%{+49\,351\,463\,37515}{+49\,351\,463\,34235}
\myContact{Friedrich Martin Schneider}{%
\TUDname,
\InstitutALG,
\Postleitzahletc
}{martin.schneider@tu-dresden.de}%
%{+49\,351\,463\,34234}{+49\,351\,463\,34235}
\myContact{Stefan Siegmund}{%
\TUDname,
\InstitutANA,
\Postleitzahletc
}{stefan.siegmund@tu-dresden.de}%
%{+49\,351\,463\,34633}{+49\,351\,463\,34664}
\end{document}