\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{allegory}

\hypertarget{context}{}\subsubsection*{{Context}}\label{context}

\hypertarget{category_theory}{}\paragraph*{{Category theory}}\label{category_theory}

[[!include category theory - contents]]

\hypertarget{relations}{}\paragraph*{{Relations}}\label{relations}

[[!include relations - contents]]

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{definition}{Definition}\dotfill \pageref*{definition} \linebreak
\noindent\hyperlink{examples}{Examples}\dotfill \pageref*{examples} \linebreak
\noindent\hyperlink{maps_tabulations_and_units}{Maps, tabulations, and units}\dotfill \pageref*{maps_tabulations_and_units} \linebreak
\noindent\hyperlink{division_allegories}{Division allegories}\dotfill \pageref*{division_allegories} \linebreak
\noindent\hyperlink{power_allegories}{Power allegories}\dotfill \pageref*{power_allegories} \linebreak
\noindent\hyperlink{freydscedrov_definition}{Freyd-Scedrov definition}\dotfill \pageref*{freydscedrov_definition} \linebreak
\noindent\hyperlink{variant_notion}{Variant notion}\dotfill \pageref*{variant_notion} \linebreak
\noindent\hyperlink{syntactic_allegories}{Syntactic allegories}\dotfill \pageref*{syntactic_allegories} \linebreak
\noindent\hyperlink{the_existential_quantifier}{The existential quantifier}\dotfill \pageref*{the_existential_quantifier} \linebreak
\noindent\hyperlink{related_entries}{Related entries}\dotfill \pageref*{related_entries} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

In [[category theory]], an \emph{allegory} is a [[category]] with properties meant to reflect properties that hold in a category [[Rel]] of [[relations]]. The notion was first introduced (as far as we know) and certainly first made famous in the book \emph{[[Categories, Allegories]]} (\hyperlink{FreydScedrov}{Freyd-Scedrov}).

Freyd and Scedrov argue that a categorical calculus of relations is an alternative and often more amenable framework for developing concepts traditionally couched in ``functional'' language (i.e., concepts which apply to [[sets]] and [[functions]]); for instance, a principal \emph{raison d'etre} for [[regular categories]] is precisely that one can do [[relational calculus]] in them (as had been long known, e.g., [[Saunders MacLane]] showed how to calculate with relations to do [[diagram chasing|diagram chases]] in [[abelian categories]]). Allegories, and correlative notions such as [[bicategory of relations|bicategories of relations]], also offer a smooth approach to [[regular and exact completion|regular and exact completions]], as used for example in the construction of [[realizability topos|realizability toposes]].

A signal feature of allegories is emphasis on the \emph{modular law} (see def. \ref{Allegory} below), which generalizes the [[modular lattice|modular law]] in lattices to more general relations, and which generalizes also so-called [[Frobenius reciprocity]] in [[categorical logic]].

\hypertarget{definition}{}\subsection*{{Definition}}\label{definition}

\begin{defn}
\label{Allegory}\hypertarget{Allegory}{}
An \textbf{allegory} is a [[locally posetal 2-category]] $A$ equipped with an [[involution]] $(-)^o \colon A^{op} \to A$ which is the [[identity]] on [[objects]], such that

\begin{enumerate}%
\item the involution is order preserving and distributes over composition, i.e. $(\psi\phi)^o = \phi^o\psi^o$,
\item each [[hom-object|hom-poset]] $A(x,y)$ has binary [[meet|meets]], and
\item the \emph{[[modular lattice|modular law]]} holds: for $\phi\colon x\to y$, $\psi\colon y\to z$, and $\chi\colon x\to z$, we have $\psi \phi \cap \chi \le \psi (\phi \cap \psi^o \chi)$.

\end{enumerate}
\end{defn}
From these properties we immediately get that

\begin{displaymath}
(\phi \cap \psi)^o = \phi^o \cap \psi^o
\end{displaymath}
and

\begin{displaymath}
(\phi \cap \psi) \chi \leq \phi\chi \cap \psi\chi
\quad\text{and}\quad
  \chi (\phi \cap \psi) \leq \chi\phi \cap \psi\chi.
\end{displaymath}
$\backslash$begin\{proof\} The first claim follows from the observation that

\begin{displaymath}
\begin{aligned}
    \chi \leq (\phi \cap \psi)^o
  &\iff
    \chi^o \leq \phi \cap \psi
&\quad&(.)^o\;\text{monotone and involutive}
\\
  &\iff
    \chi^o \leq \phi \; \text{ and } \; \chi^o \leq \psi
&&\text{meet properties}
\\
  &\iff
    \chi \leq \phi^o \; \text{ and } \; \chi \leq \psi^o
&&(.)^o\;\text{ monotone and involutive}
\\
  &\iff
    \chi \leq \phi^o \cap \psi^o
&&\text{meet properties.}
\end{aligned}
\end{displaymath}
For the claim $(\phi \cap \psi) \chi \leq \phi\chi \cap \psi\chi$ we use the [[horizontal composition]] in a [[locally posetal 2-category]], i.e. the fact that composition is monoton. Due to $\phi \cap \psi \leq \phi$ we get $(\phi \cap \psi)\chi \leq \phi\chi$. Analogously, we get that $(\phi \cap \psi)\chi \leq \psi\chi$. Hence $(\phi \cap \psi) \chi \leq \phi\chi \cap \psi\chi$. The claim $\chi (\phi \cap \psi) \leq \chi\phi \cap \psi\chi$ follows the the same arguments or by applying involution and the first claim. $\backslash$end\{proof\}

\hypertarget{examples}{}\subsection*{{Examples}}\label{examples}

\begin{itemize}%
\item If $C$ is a [[regular category]] and $Rel(C)$ is the [[locally posetal 2-category|locally posetal]] [[bicategory]] of [[internal relation|internal relations]], then $Rel(C)$ is an allegory.


\item Any [[first-order hyperdoctrine with equality]] similarly gives rise to an allegory, as does any abstract [[bicategory of relations]] in the sense of Carboni-Walters.


\item Any [[modular lattice]] can be regarded as a one-object allegory if we take composition to be union and the involution to be the identity.



\end{itemize}
\hypertarget{maps_tabulations_and_units}{}\subsection*{{Maps, tabulations, and units}}\label{maps_tabulations_and_units}

A \textbf{map} $r\colon x \to y$ in an allegory is a morphism that has a [[right adjoint]]. If $r \dashv s$, then $s = r^o$ (hint: use the modular law to show $r \dashv s \cap r^o$ and $r \cap s^o \dashv s$). The [[unit of an adjunction|unit of the adjunction]] $id_x \leq r^o r$ entails that the morphism is \textbf{[[entire relation|entire]]} (sometimes also called \emph{total}) while the [[unit of an adjunction|counit of the adjunction]] $r r^o \leq id_y$ states the fact hat the morphism is \textbf{[[functional relation|functional]]} (sometimes also called \emph{univalent}).

Any 2-category has a [[bicategory of maps]]. In an allegory, the ordering between maps is discrete, meaning that if $f \leq g$ then $f = g$. Consequently, the bicategory of maps of an allegory is a [[category]].

A \textbf{tabulation} of a morphism $\phi$ is a pair of maps $f,g$ such that $\phi = g f^o$ and $f^o f \cap g^o g = 1$. An allegory is \textbf{tabular} if every morphism has a tabulation, and \textbf{pretabular} if every morphism is contained in one that has a tabulation.

Every [[regular category]], and indeed every [[locally regular category]], has a tabular allegory of internal binary relations. Conversely, by restricting to the morphisms with left adjoints (``maps'') in a tabular allegory, we obtain a locally regular category. These constructions are inverse, so tabular allegories are equivalent to locally regular categories.

A locally regular category has finite products if and only if its tabular allegory of relations has top elements in its hom-posets.

Finally, a \textbf{unit} in an allegory is an object $U$ such that $1_U$ is the greatest morphism $U\to U$, and every object $X$ admits a morphism $\phi\colon X\to U$ such that $1_X\le \phi^o\phi$. A locally regular category has a terminal object (hence is regular) if and only if its tabular allegory of relations has a unit.

Thus, regular categories are equivalent to unital (or unitary) tabular allegories. For more details, see [[Categories, Allegories]] (\hyperlink{FreydScedrov}{Freyd-Scedrov}), the [[Elephant]] (\hyperlink{Johnstone}{Johnstone}), or [[toddtrimble:Theory of units and tabulations in allegories]].

\hypertarget{division_allegories}{}\subsection*{{Division allegories}}\label{division_allegories}

A \textbf{union allegory} is an allegory whose hom-posets have finite joins that are preserved by composition. Thus a union allegory is locally a [[lattice]]. If additionally it is locally a [[distributive lattice]], it is called a \textbf{distributive allegory}. The category of maps in a unitary tabular union allegory is a [[coherent category]] (a ``pre-logos''), and conversely the bicategory of relations in a coherent category is a (unitary tabular) distributive allegory. In particular, every unitary tabular union allegory is distributive, but in the non-tabular case this can fail: for instance, any [[modular lattice]] can be regarded as a one-object union allegory and need not be distributive.

A \textbf{division allegory} is a distributive allegory in which composition on one (and therefore the other) side has a right adjoint (left or right division). That is: given $r: A \to B$ and $s \colon A \to C$, there exists $r/s: B \to C$ such that

\begin{displaymath}
t \leq s/r \in \hom(B, C) \Leftrightarrow t \circ r \leq s \in \hom(A, C)
\end{displaymath}
(so that $- \circ r$ has right adjoint $-/r$: an example of a right [[Kan extension]]). Composition on the other side, $r \circ -$, has a right adjoint (an example of a right Kan lift) given by

\begin{displaymath}
r\backslash u \coloneqq (u^o/r^o)^o.
\end{displaymath}
In the bicategory of sets and relations, with notation as above, we have

\begin{displaymath}
(s/r)(b, c) \dashv \vdash \forall_{a \colon A} r(a, b) \Rightarrow s(a, c)
\end{displaymath}
where $r(a, b)$ is shorthand for ``$(a, b)$ belongs to $r$''.

The category of maps (functional relations) of a unitary/unital tabular division allegory is a [[logos]], and conversely the bicategory of relations in a logos is a unitary tabular division allegory. (\hyperlink{FreydScedrov}{Freyd-Scedrov}, 2.32, p. 227.)

\hypertarget{power_allegories}{}\subsection*{{Power allegories}}\label{power_allegories}

A \textbf{power allegory} is, \emph{more or less}, an allegory $\mathcal{A}$ such that the inclusion functor $i: Map(\mathcal{A}) \to \mathcal{A}$ has a right adjoint $P$. The idea is that $P$ assigns to an object $A$ a power object $P(A)$, as in topos theory; if we summarize the notion of topos as a regular category $\mathbf{E}$ for which the inclusion $i: \mathbf{E} \to Rel(\mathbf{E})$ has a right adjoint $P$, then it becomes apparent that the notion of power allegory is similar except that it takes the ``relation side'' as primary and derives the ``function side'' as $Map(\mathcal{A})$, whereas in topos theory it's just the other way around. But in either case the adjunction $i \dashv P$ is fundamental.

Since the inclusion $i$ is the identity on objects, the counit of the adjunction $i \dashv P$ at an object $B$ may be written

\begin{displaymath}
\ni_B: P(B) \to B
\end{displaymath}
and we have a kind of [[comprehension scheme]] that to each $r: A \to B$ there is a unique map $\chi_r: A \to P(B)$, the \emph{characteristic map} of $r$, such that $r = \ni_B \circ \chi_r$. (If $A$ and $B$ are related by a property $r$, then for each $a$ there is a subobject $\chi_r(a)$ of $B$ consisting of elements $b$ so related to $a$.) In the case $r = 1_A: A \to A$, the characteristic map $\chi_{1_A}: A \to P(A)$ is called the \emph{singleton map} of $A$, and more general $\chi_r$ may be defined as $P(r) \sigma_A$.

\hypertarget{freydscedrov_definition}{}\subsubsection*{{Freyd-Scedrov definition}}\label{freydscedrov_definition}

The exact definition of power allegory is a matter for consideration. One can get a certain distance just by adopting the naive definition suggested above, that a power allegory is nothing more than an allegory for which the inclusion $Map(\mathcal{A}) \to \mathcal{A}$ has a right adjoint $P$. (Below we introduce a similar notion that we call a $P$-allegory.) But it seems hard to develop a theory from the naive notion that rises to a level comparable to topos theory.

Freyd and Scedrov start with a structure of division allegory (thus packing in a good amount of internal logic from the start) and introduce the fundamental adjunction $i \dashv P$ in terms of that structure. For them, a \emph{power allegory} is defined to be a division allegory which associates to each object $B$ a morphism $\ni_B \colon P(B) \to B$ such that for all $r \colon A \to B$

\begin{itemize}%
\item $1_A \leq (r \backslash \ni_B) \circ (\ni_B \backslash r)$

\end{itemize}
which expresses the truth of the formula $\forall_{a \colon A} \exists_{S: P(B)} \forall_{b \colon B} S \ni_B b \Leftrightarrow r(a, b)$, and

\begin{itemize}%
\item $(\ni_B \backslash \ni_B) \wedge (\ni_B \backslash \ni_B)^o \leq 1_{P(B)}$

\end{itemize}
which internalizes an axiom of extensionality, which reads $\forall_{b \colon B} (S \ni_B b) \Leftrightarrow (T \ni_B b) \vdash S = T$. Given those axioms, and given $r: A \to B$, one may define

\begin{displaymath}
\chi_r \coloneqq (\ni_B \backslash r) \wedge (r\backslash \ni_B)^o,
\end{displaymath}
which internalizes the formula-definition $\chi_r(a, S) \coloneqq \forall_b S \ni_B b \Leftrightarrow r(a, b)$, and then show $\chi_r$ is a map. (\hyperlink{FreydScedrov}{Freyd-Scedrov}, pp. 235-236.)

The bicategory of relations in a [[topos]] is a power allegory; conversely, the category of maps in a unitary tabular power allegory is a topos.

\hypertarget{variant_notion}{}\subsubsection*{{Variant notion}}\label{variant_notion}

Nevertheless, the spare elegance of the naive definition gives one something to shoot for. It appears that quite a decent theory can be developed just by adding the assumption of coproducts in an allegory: a reasonable and fairly mild assumption. (Most allegories don't admit many colimits; for example having coequalizers is pretty rare. But the standard examples do have finite coproducts, coinciding with coproducts on the maps/functional side.)

\begin{defn}
\label{}\hypertarget{}{}
A $P$-allegory is an allegory $\mathcal{A}$ with finite coproducts\footnote{We mean coproducts as certain conical colimits \emph{qua} [[locally posetal 2-category]].}  for which the inclusion $i: Map(\mathcal{A}) \to \mathcal{A}$ has a right adjoint $P$.

\end{defn}
As before, the counit is denoted $\ni: i P \to 1_{\mathcal{A}}$. It is perhaps surprising that the notion of $P$-allegory is at least as strong as power allegory in the Freyd-Scedrov sense:

\begin{theorem}
\label{}\hypertarget{}{}
Any $P$-allegory is a division allegory in which the Freyd-Scedrov conditions on $\ni$ are satisfied.

\end{theorem}
\begin{proof}
For now we content ourselves with a description of the division structure. Let $r: A \to C$ and $s: B \to C$ be morphisms; we construct a right Kan lift $s \backslash r$ of $r$ through $s$. This means that for all $t: A \to B$ we have $s \circ t \leq r$ if and only if $t \leq s \backslash r$. We begin by constructing the right Kan lift for the case $r = s = \ni_C: P C \to C$.

Define the internal union $\bigcup_C$ by $\bigcup_C = P(\ni_C): P P C \to P C$, and define an internal order relation $[\Rightarrow]_C: P C \to P C$ by $P C \stackrel{\in_{P C}}{\to} P P C \stackrel{\bigcup_C}{\to} P C$. (Here $\in \coloneqq \ni^o$.) Define $[\Leftarrow]_C \coloneqq [\Rightarrow]_C^o$.

We now show $[\Leftarrow]_C = \ni_C \backslash \ni_C$. That is, for $R: P C \to P C$, we show $\ni_C R \leq \ni_C$ is equivalent to $R \leq [\Leftarrow]$. The backward implication is easy; for the forward implication, one may prove it first for \emph{reflexive} $R$ where we have an actual equation $\ni_C R = \ni_C$. It follows that $P(\ni_C) P(R) = P(\ni_C)$, whence $P(R) \leq \bigcup_C^o \bigcup_C$. A short calculation then yields $R = \ni_C P(R) \sigma_{P C} = \ni_C \bigcup_C^o \bigcup_C \sigma_{P C} = \ni_C \bigcup_C^o = [\Leftarrow]$. The case for general $R$ reduces to the reflexive case: form the reflexive completion $1 \vee R$ as the composite

\begin{displaymath}
C \stackrel{\langle 1_{P C}, R \rangle}{\to} C + C \stackrel{\nabla}{\to} C
\end{displaymath}
which is where coproducts come in; here $\nabla$ is the codiagonal and we use the fact that $C + C$ in an allegory is a biproduct to form the pairing for the first arrow. It is easy to show that $\ni_C(1 \vee R) = \ni_C \vee \ni_C R = \ni_C$, and then we derive $R \leq 1 \vee R \leq [\Leftarrow]$ from before. Thus we have shown $[\Leftarrow]_C = \ni_C \backslash \ni_C$.

For general $r: A \to C, s: B \to C$, we claim the right Kan lift $s \backslash r: A \to B$ is given by $\chi_s^o (\ni_C \backslash \ni_C) \chi_r$. For, we have $r = \ni_C \chi_r$, whence

\begin{displaymath}
\begin{aligned}
    s t &\leq r & 
  \;&\iff & \ni_C \chi_s t &\leq \ni_C \chi_r 
\\ 
 &&& \iff & \ni_C \chi_s t \chi_r^o &\leq \ni_C 
\\ 
 &&& \iff & \chi_s t \chi_r^o &\leq \ni_C \backslash \ni_C 
\\ 
 &&& \iff & t &\leq \chi_s^o (\ni_C \backslash \ni_C) \chi_r
\end{aligned}
\end{displaymath}
thus proving the claim.

Further details may be found \href{https://ncatlab.org/toddtrimble/published/Note+on+power+allegories}{here}.

\end{proof}
Thus the notion of $P$-category is just as strong as the Freyd-Scedrov notion of power allegory, and one can then piggy-back on their further developments.

\hypertarget{syntactic_allegories}{}\subsection*{{Syntactic allegories}}\label{syntactic_allegories}

Let $T$ be a [[regular theory]]. There is then an allegory $\mathcal{A}_T$ given as follows:

\begin{itemize}%
\item the objects are finite strings of [[sorts]] of $T$;


\item a morphism $\vec X \to \vec Y$ is a predicate $P(\vec x, \vec y)$ of sort $\vec X, \vec Y$ (or rather a provable-equivalence class of such predicates);


\item the identity $\vec X \to \vec X$ is (named by) $x_1 = x_1 \wedge x_2 = x_2 \wedge \cdots \wedge x_n = x_n$;


\item the composite of $R \colon \vec X \to \vec Y$ and $S \colon Y \to \vec X$ is named by $\exists \vec y. R(\vec x, \vec y) \wedge S(\vec y, \vec z)$.



\end{itemize}
That $\mathcal{A}_T$ is an allegory is B.311 in \hyperlink{FreydScedrov}{Freyd--Scedrov}; that it is in fact unitary and pre-tabular is B.312.

Further structure on $T$ gives rise to further structure on $\mathcal{A}_T$ (B.313): if $T$ is a [[coherent theory|coherent]], [[first-order theory|first-order]] or [[higher-order logic|higher-order]] theory, then $\mathcal{A}_T$ will be a distributive, division or power allegory respectively.

Every pre-tabular allegory has a tabular completion, given by splitting its coreflexive morphisms (i.e. those endomorphisms $R$ such that $R \subset id$). The category of maps in the coreflexive splitting of $\mathcal{A}_T$ is precisely the [[syntactic category]] of $T$.

\hypertarget{the_existential_quantifier}{}\subsubsection*{{The existential quantifier}}\label{the_existential_quantifier}

There are two possible ways to interpret a regular formula of the form $\exists y. R(x,y) \wedge S(y,z)$ in a unitary pre-tabular allegory, if $R$ and $S$ are interpreted as $r \colon X \to Y$ and $s \colon Y \to Z$ respectively: as the composite $s \cdot r$, or more `literally' by:

\begin{itemize}%
\item pulling $r$ and $s^o$ back to the same hom set and taking their intersection: $(p_1^o r p_1) \cap (p_2^o s^o p_2) \colon X \times Z \to Y \times Y$;


\item then forcing the two $Y$s to be equal by post-composing with $\Delta_Y^o \colon Y \times Y \to Y$, applying the existential quantifier by post-composing with the unique map $!_Y$ to the unit, and post-composing with $!_Z^o$ to get a morphism into $Z$;


\item then forcing the $Z$ in the domain to be equal to the $Z$ in the codomain by taking the meet with $p_2 \colon X \times Z \to Z$;


\item and finally pulling back along (precomposing with the right adjoint of) $p_1 \colon X \times Z \to X$ to get a morphism $X \to Z$.



\end{itemize}
We would like to know that these morphisms are equal, so that an existential formula will have a unique interpretation:

\begin{prop}
\label{}\hypertarget{}{}
\begin{displaymath}
s r = (p_2 \cap !_Z^o !_Y \Delta_Y^o ((p_1^o r p_1) \cap (p_2^o s^o p_2))) p_1^o
\end{displaymath}
\end{prop}
\begin{proof}
We show inclusion in each direction.

Firstly, $s r = s r \cap p_2 p_1^o$, because the product projections tabulate the top morphism. Notice also that the RHS above is equal to

\begin{displaymath}
(\top_{Y Z} (r p_1 \cap s^o p_2) \cap p_2) p_1^o
\end{displaymath}
where $\top_{Y Z}$ is the top morphism $Y \to Z$.

Now we can calculate:

\begin{displaymath}
\begin{aligned}
  s r \cap p_2 p_1^o
  & = (s r p_1 \cap p_2) p_1^o &\quad& \text{modular law} \\
  & = (s r p_1 \cap p_2 \cap p_2) p_1^o \\
  & \leq (s(r p_1 \cap s^o p_2) \cap p_2) p_1^o && \text{modular law} \\
  & \leq (\top_{Y Z} (r p_1 \cap s^o p_2) \cap p_2) p_1^o
\end{aligned}
\end{displaymath}
In the other direction, we have

\begin{displaymath}
\begin{aligned}
  (\top_{Y Z} (r p_1 \cap s^o p_2) \cap p_2) p_1^o
  & \leq (\top_{Y Z} s^o (s r p_1 \cap p_2) \cap p_2) p_1^o 
&\quad& \text{modular law} \\
  & \leq (\top_{Y Y} (s r p_1 \cap p_2) \cap p_2) p_1^o
&& \top_{Y Z} s^0 \leq \top_{Y Y}\\
  & = (p_2 (p_1^o s r p_1 \cap p_1^o p_2) \cap p_2) p_1^o 
&& \top{Y Y} = p_2 p_1^o \\
  & = p_2 (p_1^o s r p_1 \cap p_1^o p_2 \cap p_2^o p_2) p_1^o
&& \text{modular law} \\
  & = p_2 (p_1^o s r p_1 \cap (p_1^o \cap p_2^o) p_2) p_1^o
&& \text{maps distribute} \\
  & = p_2 (p_1^o s r p_1 \cap \Delta p_2) p_1^o
&& \text{see below} \\
  & = p_2 \Delta (\Delta^o p_1^o s r p_1 \cap p_2) p_1^o
&& \text{modular law} \\
  & = (s r p_1 \cap p_2) p_1^o 
&& p_1 \Delta = p_2 \Delta = id \\
  & = s r \cap p_2 p_1^o
&& \text{modular law}
\end{aligned}
\end{displaymath}
and we are back to where we started. In the fourth-last step we used the fact that if $p_1, p_2 \colon Z \times Z \to Z$ are the projections, then $p_1 \cap p_2 = \Delta^o$. But $\Delta = \langle id, id \rangle$, and from lemma 1 [[finnlawler:allegory|here]] we have that $\langle id, id \rangle = p_1^o \cap p_2^o$.

\end{proof}
\hypertarget{related_entries}{}\subsection*{{Related entries}}\label{related_entries}

Other attempted axiomatizations of the same idea ``something that acts like the category of relations in a regular category'' include:

\begin{itemize}%
\item [[bicategory of relations]] (a special sort of [[cartesian bicategory]])


\item [[1-category equipped with relations]]



\end{itemize}
Discussion of the relation between pretabular unitary allegories and bicategories of relations, and also between tabular unitary allegories and regular categories is in

\begin{itemize}%
\item [[toddtrimble:Theory of units and tabulations in allegories]]

\end{itemize}
\hypertarget{references}{}\subsection*{{References}}\label{references}

The standard monograph is

\begin{itemize}%
\item [[Peter Freyd]] and Andre Scedrov, \emph{[[Categories, Allegories]]}, Mathematical Library Vol 39, North-Holland (1990). ISBN 978-0-444-70368-2.

\end{itemize}
The notion is discussed also in chapter A3 of

\begin{itemize}%
\item [[Peter Johnstone]], \emph{[[Sketches of an Elephant]]}

\end{itemize}
In

\begin{itemize}%
\item [[Bob Walters]], \emph{Categorical algebras of relations} (\href{http://rfcwalters.blogspot.com/2009/10/categorical-algebras-of-relations.html}{blog post} )

\end{itemize}
it is shown that any [[bicategory of relations]] is an allegory.

See also

\begin{itemize}%
\item Wikipedia, \emph{\href{http://en.wikipedia.org/wiki/Allegory_%28category_theory%29}{Allegory}}

\end{itemize}
An introduction headed towards applications in computer science and, in particular, fuzzy controllers can be found in

\begin{itemize}%
\item Michael Winter, \emph{Goguen Categories} (2007)

\end{itemize}
[[!redirects tabular allegory]] [[!redirects union allegory]] [[!redirects division allegory]] [[!redirects power allegory]]

[[!redirects allegories]] [[!redirects tabular allegories]] [[!redirects union allegories]] [[!redirects division allegories]] [[!redirects power allegories]]



\end{document}