2.1 Types

Informally, types annotate data by signaling which syntax rules apply to the data. We write $a:A$ and say “a is a term of type A” or “a inhabits A”. For example, $a: \mathbb {N}$ signals that a can only be used as a natural number. A type A is inhabited if there exists at least one term $a:A$ and uninhabited if no term of type A exists. The void type $\bot $ has no inhabitants by definition. Deciding whether a type is inhabited or not is computationally undecidable [Reference Hindley and Seldin18, pp. 66–67]. Therefore, in computational settings, types are permitted to be neither inhabited nor uninhabited. Type annotations enable us to use symbols according to their logical purpose; for example, $a:A$ is analogous to $a\in A$ , but type theories do not have the axioms of set theory.

Types are introduced from two sources. Some are predefined by the context: they are given a priori, such as the type of natural numbers $\mathbb {N}$ . Others are created using type-builders: these construct new types from existing ones. We use both $A\to B$ and $B^{A}$ to denote the type of functions, and set $\operatorname {\mathrm {Dom}} (A\to B) = A$ and $\operatorname {\mathrm {Codom}} (A\to B) = B$ . If n is a natural number, then an inhabitant of type $A^n$ can be interpreted as an n-tuple $(a_1,\ldots ,a_n)$ with each $a_i: A$ , or alternatively as a function $\{1,\ldots ,n\}\to A$ . There is a unique function $\bot \to A$ (akin to the uniqueness of a function $\varnothing \to A$ ), so $A^0$ is a type with a single inhabitant – it is not void.

The notation $\prod _{i: I}A_i$ together with projection maps $\pi _i: \left (\prod _{i: I}A_i\right ) \to A_i$ is used for Cartesian products, and $\bigsqcup _{i: I} A_i$ together with inclusion maps $\iota _i : A_i \to \bigsqcup _{i: I} A_i$ is used for disjoint unions. (The tradition in type theory is to use $\sum _{i: I}A_i$ instead of $\bigsqcup _{i: I} A_i$ , but this conflicts with algebraic uses of $\Sigma $ .)

2.2 Propositions as types

In set theory, propositions are part of the existing foundations. In type theory, propositions coevolve with the theory as special types. A proposition P in logic is associated to a type $\hat {P}:\mathrm {Type}$ . (Only in this section do we distinguish propositions P in logic from propositions as types with the notation $\hat {P}$ .) If the type $\hat {P}$ is inhabited by data $p:\hat {P}$ , then the term p is regarded as a proof that P is true. For example, an implication $P \Rightarrow Q$ (here $\Rightarrow $ means “implies” with weakening and contraction laws) can be proved by means of a function $f:\hat {P}\to \hat {Q}$ , where $\hat {P}$ and $\hat {Q}$ are the respective types associated with P and Q, because it suffices to assume P and derive a proof of Q. Likewise, if we assume that there is a term $p:\hat {P}$ and apply the function f, then it produces a term $f(p):\hat {Q}$ .

In classical logic, it is only the existence of a proof for a proposition that is relevant. Analogously, in type theory, $\hat {P}:\mathrm {Type}$ is a mere proposition, written $\hat {P}:\mathrm {Prop}$ , if it has at most one inhabitant.

Consider the function $\hat {P}:A\to \mathrm {Prop}$ . Now $(\forall a\in A)(P(a))$ and $(\exists a\in A)(P(a))$ are expressed by terms of type $\prod _{a:A}\hat {P}_a:\mathrm {Prop}$ and $\|\bigsqcup _{a:A} \hat {P}_a\|:\mathrm {Prop}$ , respectively, where $\|A\|$ truncates a type to a single term if it has any terms [34, §3.7]. The negation of a proposition P is , which accords with functions of type $\hat {P}\to \bot $ . For additional details, see [Reference Hindley and Seldin18, Chapters 12–13], [34, Chapter 3].

2.3 Equality

In Zermelo set theories, all data are sets and there is a single notion of equality afforded by the Axiom of extensionality: two sets are equal if, and only if, they have the same elements. In type theory, terms and types are separate entities, and this single axiom is replaced by several distinct notions of equality more representative of computational behavior. Each type theory is built on a rewriting system (such as a $\lambda $ -calculus or combinatory logic). Employing the language of [Reference Hindley and Seldin18, §1D and §2D], we judge data as equal if their normal forms in this rewriting system coincide; and followed by some sentences M means that “within the given scope M, the variable s should be substituted by the data t”.

Type theories include axioms that allow equality after taking normal forms to count as ( $definitional$ ) equality–the type theory sees no difference between the data [Reference Hindley and Seldin18, p. 193]. For example, if we build the type $\mathbb {Z}/n$ which depends on a term $n:\mathbb {N}$ , then some type systems judge that $\mathbb {Z}/(m+m)$ is equal to $\mathbb {Z}/2m$ because $m+m$ and $2m$ have the same normal form. But the function $\gcd (m,2m)$ is more complicated and its normal form may differ from m. Hence, the type system does not judge $\mathbb {Z}/\gcd (m,2m)$ as equal to $\mathbb {Z}/m$ ; neither does it assert they are not equal; instead it withholds judgment.

To construct an equality that mimics set theory, Per Martin-Löf developed a notion of propositional equality that imitates the Leibniz Law [Reference Feldman13]:

$$ \begin{align*} (s = t) \iff \left[(\forall P(x))\; P(s)\Longleftrightarrow P(t)\right], \end{align*} $$

where $P(x)$ runs over all predicates of a single variable x. For every type A and terms $s,t:A$ , we define an auxiliary type $s=_A t$ , where terms are proofs that s equals t, with the rule that, given a function $f:A\to B$ , there is a function

(2.2) $$ \begin{align} \text{path}(f): (s =_A t)\to (f(s) =_B f(t)). \end{align} $$

For example, a proof $p: (\gcd (m,2m) =_{\mathbb {N}} m)$ can be transported along a path to $q: (\mathbb {Z}/\gcd (m,2m) =_{\mathbb {Z}/m} \mathbb {Z}/m)$ allowing programs to treat these types as equal. Thus, computational evidence enhances the reach of equality, see [Reference Hindley and Seldin18, §3.5], [34].

For readability we often omit the subscript A in $s=_A t$ . By slight abuse of notation, writing “ $s=t$ ” as a logical statement in text should be interpreted as “the type $s=_At$ is inhabited”.

2.4 Subtypes and inclusion functions

Sets are a special case of types: we write $S:\mathrm {Set}$ for a type S if the type $s=_S t$ is a mere proposition for all $s,t:S$ . Let A be a type. If $P : A \to \mathrm {Prop}$ , then

is the subtype of A defined by P. We also write this as . Terms of type B have the form $\langle a, p\rangle $ for $a:A$ and $p:\mathrm {Prop}$ , where p is a proof that $P(a)$ is inhabited. We sometimes use set theory notation to improve readability when describing a subtype. For more details, see [34, §3.5]. For a typed function $f:A\to B$ , the image $\{f(a)\mid a:A\}$ is shorthand for $\{b:B\mid (\exists a:A)(f(a)=b)\}$ .

Subtypes have an associated inclusion function $\alpha :B\to A$ where . A subtlety is that if $C\subset B$ with inclusion map $\beta :C\to B$ , then the composition $\alpha \beta :C\to A$ is injective but does not show directly that $C\subset A$ . A term of type , with $Q : B\to \mathrm {Prop}$ , has the form $\langle \langle a,p\rangle ,q\rangle $ , which differs from terms of type B. A small modification addresses the fact that the relation $\subset $ is not strictly transitive. Define a subtype , where , and inclusion $\gamma : C' \to A$ . Now construct a map $\sigma : C\to C'$ given by

$$ \begin{align*} \langle \langle a,p\rangle,q\rangle \mapsto \langle a,\langle p,q\rangle\rangle, \end{align*} $$

where $a:A$ and $\langle p,q\rangle : R(a)$ . Thus, $\alpha \beta =\gamma \sigma $ , and the composition $\alpha \beta $ is equivalent to $\gamma $ . Hence, $\subset $ is transitive up to this equivalence.

2.5 Partial functions

In type theory, functions are ultimately programs so they may fail to halt. Since our concern lies with algebraic obstacles rather than decidability, we confine our model to algebras that have decidable operations, such as polynomial and integer operations, look-up tables, and strongly normalizing rewriting systems. Thus, all functions are total: given an input, they produce an output. However, it is helpful to identify inputs we regard as “undefined,” or “leading to errors.” For example, a division operator may allow $0$ as an input and return an error token as output. We call such functions partial functions and regard them as “undefined” at such inputs.

To accommodate such partial operations, we extend types by adjoining the symbol $\bot $ (the void type) to represent “undefined”. For a type A, we define

(2.3)

with inclusion $\iota _A:A\hookrightarrow A^?$ . For $a:A^?$ , we write $a:A$ in this setting as shorthand for “there exists $a':A$ such that $a=\iota _A(a')$ .” This allows us to define an endofunctor Q on the category of types that maps a morphism $f:A\to B$ to $f^?:A^?\to B^?$ , such that $f^?(a)=f(a)$ for $a:A$ and $f^?(\bot )=\bot $ . The canonical projection $\mu : QQ \Rightarrow Q$ , with components $\mu _A: (A^?)^? \to A?$ , is a natural isomorphism. Hence, it suffices to work with single applications of Q, and $\bot $ will serve as the designated symbol for undefined elements throughout.

This discussion also motivates a notion of “directional equality” similar to that in [Reference Freyd and Scedrov14, 1.12]. For $a,b: A^?$ , define

(2.4)

By slight abuse of notation, for function terms $f,g : A^?\to B^?$ we denote function extensionality also by $f=g$ , that is, we define

2.6 Certifying that the trivial group is characteristic

As an illustration, we present a type verifying the characteristic property of the trivial subgroup. Let $G : \mathrm {Group}$ be a group with identity $1:G$ . Let be the subtype of G representing the trivial subgroup. Recall that terms of H have the form $\langle x, p\rangle $ , where $x:G$ and p is a term of type $x=1$ , and there is a map $\iota :H\to G$ , $\langle x,p\rangle \mapsto x$ . If $h,k:H$ , then $\iota (h)=\iota (k)=1$ , and, by (2.2), for every $\varphi :\operatorname {\mathrm {Aut}}(G)$ there is an invertible function of type

(2.5) $$ \begin{align} \varphi(1)=_G 1\; \longleftrightarrow\; \varphi(\iota(h))=_G \iota(k). \end{align} $$

The latter function depends on h and k, but we suppress this dependency to simplify the exposition. Let $\mathrm {idLaw}(\varphi ) : \varphi (1)=_{G} 1$ be a proof that $\varphi :\operatorname {\mathrm {Aut}}(G)$ fixes $1:G$ . Using (2.5), we define the term

$$\begin{align*}\mathrm{idMap}(\varphi) : \prod_{h:H}\left\|\bigsqcup_{k:H} \varphi(\iota(h)) =_G \iota(k)\right\| \end{align*}$$

that takes as input $h:H$ and produces $\langle 1,\mathrm {idLaw}(\varphi )\rangle : \left \|\bigsqcup _{k:H} \varphi (\iota (h))=_G \iota (k)\right \|$ . Therefore we obtain the term

$$ \begin{align*} \mathrm{idMap} & : \prod_{\varphi:\operatorname{\mathrm{Aut}}(G)}\prod_{h:H}\left\|\bigsqcup_{k:H} \varphi(\iota(h))=_G \iota(k)\right\|, \end{align*} $$

which certifies that H is characteristic in G; compare to (2.1). Recall that in MLTT, types correspond to propositions, and terms are programs that correspond to proofs. Thus, the term $\mathrm {idMap}$ is not an exhaustive tuple listing $\operatorname {\mathrm {Aut}}(G)$ , but a program (function) that takes as input $\varphi :\operatorname {\mathrm {Aut}}(G)$ and $h:H$ , and produces $k:H$ and $p: \varphi (\iota (h)) =_G \iota (k)$ .

3.1 Intentional and extensional formulations of algebra

It is natural to ask if algebraic structures such as groups and rings, that are introduced in standard texts such as [Reference Hungerford19] using extensional set theory, have logically consistent intentional formulations in foundations such as MLTT. While it is not within our purview to consider alternative foundations of algebra, we briefly compare type-theoretic formulations of groups with their long-standing and rigorous treatment in computational algebra.

Although systems such as GAP [15], Macauley [Reference Grayson, Stillman and Eisenbud16], Magma [Reference Bosma, Cannon and Playoust8], and SageMath [31] are not designed to use types robustly, they nevertheless facilitate a treatment of groups that is more intentional than extensional. In these systems, groups can be represented in many different ways, but for practical reasons they are generally not treated as sets of elements. For instance, a group G may be specified by a generating set Y of permutations. Algorithms such as the product replacement [Reference Holt, Eick and O’Brien12, §3.2.2] can then be used to select “random” elements of G as words in Y. However, basic questions such as membership – does a permutation belong to G? – often require clever algorithms to answer [Reference Holt, Eick and O’Brien12, Chapter 4].

Even the question of whether two elements in a group are equal is often not immediate. (There are models, such as finitely presented groups, where this question is not decidable.) In standard models for computation with groups, effective equality testing is usually available, but it is not always done by simply asking if two pieces of data are identical. For example, do elements a and b of $G=\langle Y\rangle $ coincide in $G / \zeta (G)$ ? Equivalently, is $ab^{-1} \in \zeta (G)$ ? Even if we do not know generators for $\zeta (G)$ , we can answer the latter question efficiently by deciding whether $ab^{-1}$ commutes with every element of Y. In this sense, asking whether $a=b$ in computational algebra (where a program settles the question) is closer to writing $a=b$ in type theory (where evidence is provided by a proof) than it is to the (trivial) question in set theory (cf. Section 2.3).

3.2 Operators, grammars, and signatures

Informally, a grammar is a description of rules for formulas.

Example 3.2. A signature for additive formulas specifies three operators:

$$ \begin{align*} \texttt{<Add>::= (<Add>+ <Add>)~|~0~|~(-<Add>)} \end{align*} $$

The bivalent addition $(+)$ depends on terms to the left and right; zero ( $0$ ) depends on nothing; and univalent negation ( $-$ ) is followed by a term.

It is easy to reject $+-+\,2\,3\,7$ since it is not meaningful. However, we might write $2+3-7$ intending $(2+3)+(-7)$ ; the BNF grammar <Add> accepts only the latter.

The purpose of the signature is to formulate important algebraic concepts such as homomorphisms. To declare that a function $f:A\to B$ is a homomorphism between additive groups, we use the signature of Example 3.2 as follows:

$$ \begin{align*} f((x+y)) & = (f(x)+f(y)), & f(0) & =0, & f((-x)) & = (- f(x)). \end{align*} $$

3.3 Algebraic structures

An algebra is a single type with a signature [Reference Cohn10, §II.2].

Definition 3.3. An algebraic structure with signature $\Omega $ is a type A and a function $\omega \mapsto \omega _A$ , where $\omega :\Omega $ and $\omega _A:A^{|\omega |}\to A$ . A homomorphism between algebraic structures A and B, each having signature $\Omega $ , is a function $f:A\to B$ such that, for every $\omega :\Omega $ and $a_1,\ldots ,a_{|\omega |}:A$ ,

$$ \begin{align*} f(\omega_A(a_1,\ldots, a_{|\omega|})) & = \omega_B(f(a_1),\ldots, f(a_{|\omega|})). \end{align*} $$

As in Section 2.2, we extend these propositions to types as follows:

Terms of type $\mathrm {Alge}_{\Omega }$ are $\Omega $ -algebras.

For example, consider the additive group signature from Example 3.2. The underlying structure of an additive group can be described by a type (set) A together with assignments of the operators in Add such as (<Add> + <Add>) to $+_A : A\times A\to A$ . The nullary operator 0 is then identified with a term $0:A$ .

3.4 Free algebras and formulas

We now extend signatures to include variables that allow us to work with formulas.

Example 3.5. To describe formulas in variables $x,y$ and z, we extend the additive signature $\Omega =\texttt {Add}$ of Example 3.2 as follows:

$$ \begin{align*}\texttt{ {<Add<X{>}>} ::= (<Add<X{>}> + <Add<X{>}> ) | 0 | (-<Add<X{>}> ) | x | y | z}. \end{align*} $$

Here, $x+y$ and $(-x)+(0+z)$ have type $\texttt {Add}\langle X\rangle $ , but $x-$ and $x+7$ do not. The operations on the formulas $\Phi _1(X),\Phi _2(X):\texttt {Add}\langle X\rangle $ are:

Thus, $\texttt {Add}\langle X\rangle $ is the free additive algebra, but it lacks laws such as $x+y = y+x$ and $x + (-x) = 0$ . We explain how to impose these laws in Section 3.5.

Consequently, we write for formulas $\Phi :\Omega \langle X\rangle $ and $a:A^X$ .

Remark 3.7. The construction in Fact 3.6 is categorical in nature, and we use it in Section 7 to construct characteristic subgroups. The category of $\Omega $ -algebras has objects of type $\mathrm {Alge}_{\Omega }$ together with homomorphisms. The pair of functors (given only by their object maps)

$$\begin{align*}X\mapsto \Omega\langle X\rangle\quad\text{ and }\quad \langle A:\mathrm{Type},\ (\omega:\Omega)\mapsto (\omega_A:A^{|\omega|}\to A)\rangle\mapsto A \end{align*}$$

forms an adjoint functor pair between the categories of types and $\Omega $ -algebras; see Section 4.5 for related discussion.

3.5 Laws and varieties

Let $\Omega $ be a signature. We now describe the variety of $\Omega $ -algebras whose operators satisfy a list of (equational) laws such as the axioms of a group. Let X be a type for variables. A law is a term of type $\Omega \langle X\rangle ^2$ . We index laws by a type L, so they are terms $\mathcal {L}: L \to \Omega \langle X\rangle ^2$ and are written $\ell \mapsto (\Lambda _{1,\ell }, \Lambda _{2,\ell })$ .

An $\Omega $ -algebra ${A}$ is in the variety for the laws $\mathcal {L}: L \to \Omega \langle X\rangle ^2$ if

$$ \begin{align*} \begin{array}{lll} (\forall a: {A}^X)& (\forall \ell: {L})& \Lambda_{1,\ell}(a) = \Lambda_{2,\ell}(a). \end{array} \end{align*} $$

We write $\mathrm {Alge}_{\Omega ,\mathcal {L}}$ for the type of all $\Omega $ -algebras in the variety for the laws $\mathcal {L}$ ; this is a subtype of $\mathrm {Alge}_{\Omega }$ . The category of $\Omega $ -algebras in the variety for $\mathcal {L}$ has object type $\mathrm {Alge}_{\Omega ,\mathcal {L}}$ and morphism type

with $\mathrm {Hom}_{\Omega }(A,B)$ as in Definition 3.3.

Example 3.8. The signature $\Omega $ for groups is the following:

$$ \begin{align*}{\texttt{ {<G>::= (<G> <G>)} | 1 | (<G>)}^{-\texttt{1}}.} \end{align*} $$

The variety of groups uses three laws, indexed by with variables , where, for example,

Thus, $\Lambda _{1,\texttt {asc}}(g,h,k)=g(hk)$ and $\Lambda _{2,\texttt {asc}}(g,h,k)=(gh)k$ , and associativity is imposed on the $\Omega $ -algebra G by requiring a term (“proof”) of type

$$\begin{align*}\prod_{g:G}\prod_{h:G}\prod_{k:G} g(hk)=_G (gh)k. \end{align*}$$

Encoding $1x=x$ and $x^{-1} x=1$ as additional laws gives a complete description of the variety of groups. Laws need not be algebraically independent: for example, $x1=x$ and $xx^{-1}=1$ are often also encoded.

For clarity, henceforth we write laws as propositions. For example, we write $g(hk)=(gh)k$ rather than terms of a mere proposition type.

3.6 Categories as algebraic structures

We cannot always compose a pair of morphisms in a category: composition may be a partial function. Hence, the morphisms need not form an algebraic structure under composition. We address this limitation by identifying precisely when the operators yield partial functions.

Example 3.9. The type of each function is given as

Technically, to quantify over all types, we shift to a larger universe $\text {Type}_1$ ; see Remark 3.17. For $f:A\to B$ and $g:\mathrm {Fun}$ , define

(3.1)

where $f\circ g$ is the usual composition of functions. The condition $f\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } g$ guards against composing noncomposable functions (one can think of $f\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } g$ as saying “what enters f must match what exits g”). Note that $\mathbin {\blacktriangleleft } (f\mathbin {\blacktriangleleft })=\mathbin {\blacktriangleleft } \operatorname {\mathrm {id}}_{A}=\operatorname {\mathrm {id}}_{A}=f\mathbin {\blacktriangleleft }$ , and similarly $(\mathbin {\blacktriangleleft } f)\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } f$ .

The definitions in (3.1) motivate an algebraic structure on $\mathrm {Fun}^?$ . We define the composition signature:

(3.2) $$ \begin{align} \texttt{<Comp>::= (<Comp> <Comp>) | }(\mathbin{\blacktriangleleft} \texttt{<Comp>})\texttt{ | }(\texttt{<Comp>}\mathbin{\blacktriangleleft})\texttt{ | } \bot \end{align} $$

Definition 3.10. Let $\Omega $ be the composition signature of (3.2). An abstract category $\mathsf {A}$ is an $\Omega $ -algebra on a type C satisfying the law

$$\begin{align*}f(gh) = (fg)h\end{align*}$$

in variables $f,g,h$ , together with the following source–target laws and $\bot $ -sink laws:

$$ \begin{align*} \mathbin{\blacktriangleleft} (f\mathbin{\blacktriangleleft}) & = f\mathbin{\blacktriangleleft} & (\mathbin{\blacktriangleleft} f) f & = f & \mathbin{\blacktriangleleft} (fg) & = \mathbin{\blacktriangleleft} (f (\mathbin{\blacktriangleleft} g))\\ (\mathbin{\blacktriangleleft} f)\mathbin{\blacktriangleleft} & = \mathbin{\blacktriangleleft} f & f (f\mathbin{\blacktriangleleft}) & = f & (fg)\mathbin{\blacktriangleleft} & = ((f\mathbin{\blacktriangleleft})g)\mathbin{\blacktriangleleft} \end{align*} $$

$$ \begin{align*} \bot\mathbin{\blacktriangleleft} &= \bot & \mathbin{\blacktriangleleft} \bot &= \bot & f\bot &= \bot & \bot f &= \bot. \end{align*} $$

We refer to the operators $(-)\mathbin {\blacktriangleleft }$ and $\mathbin {\blacktriangleleft } (-)$ in Definition 3.10 as guards. Note that $\mathbin {\blacktriangleleft } f=\bot $ or $f\mathbin {\blacktriangleleft }=\bot $ if, and only if, $f=\bot $ ; this follows from the laws $ (\mathbin {\blacktriangleleft } f) f = f$ and $f(f\mathbin {\blacktriangleleft })=f$ .

Conventional categories can be treated as abstract categories. First, the morphisms of the category can be packaged as a disjoint union into a common type A, which possibly requires an enlarged universe. Then we use $A^?$ as the carrier type for the abstract category $\mathsf {A}$ , where the nullary operator $\bot :\Omega $ is identified with the term $\bot $ in $A^?$ ; see (2.3). We write $a:\mathsf {A}$ to indicate that a is a term of the carrier type $A^?$ . Henceforth, we assume that all abstract categories have carrier types of the form $A^?$ .

A useful subtype of an abstract category $\mathsf {A}$ is the type of identities:

Since $\mathbin {\blacktriangleleft } (a\mathbin {\blacktriangleleft })=a\mathbin {\blacktriangleleft }$ and $(\mathbin {\blacktriangleleft } a)\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } a$ , we also have .

Proof . For a term f in an abstract category,

$$\begin{align*}\mathbin{\blacktriangleleft} (\mathbin{\blacktriangleleft} f)=\mathbin{\blacktriangleleft} ((\mathbin{\blacktriangleleft} f)\mathbin{\blacktriangleleft})=(\mathbin{\blacktriangleleft} f)\mathbin{\blacktriangleleft}=\mathbin{\blacktriangleleft} f. \end{align*}$$

A similar argument shows $(f\mathbin {\blacktriangleleft })\mathbin {\blacktriangleleft } =f\mathbin {\blacktriangleleft }$ , so (a) holds. For (b), it remains to consider terms $f,g$ such that $\mathbin {\blacktriangleleft } (fg)$ is not $\bot $ . This means that $fg$ is not $\bot $ , and hence $f\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } g$ with both $f\mathbin {\blacktriangleleft }$ and $\mathbin {\blacktriangleleft } g$ not $\bot $ . Now

$$\begin{align*}\mathbin{\blacktriangleleft} (fg) = \mathbin{\blacktriangleleft} (f(\mathbin{\blacktriangleleft} g))=\mathbin{\blacktriangleleft} (f(f\mathbin{\blacktriangleleft}))=\mathbin{\blacktriangleleft} f,\end{align*}$$

as claimed. The other formula follows similarly.

Let $\mathsf {C}$ be a category with object type $\mathsf {C}_0$ . Form the type of all morphisms of $\mathsf {C}$ :

(3.3)

For objects $U,V:\mathsf {C}_0$ , there is an inclusion map (see Section 2.1)

$$ \begin{align*} \iota_{UV} & : \mathsf{C}_1(U,V)\hookrightarrow \mathsf{C}_1. \end{align*} $$

Thus, for each $\varphi :\mathsf {C}_1$ , there exist unique $U,V:\mathsf {C}_0$ and $f:\mathsf {C}_1(U,V)$ such that $\varphi =\iota _{UV}(f)$ .

Proof . Let $f,g:\mathsf {C}_1^?$ . If $f=\bot $ or $g=\bot $ , then all the equations in Definition 3.10 become $\bot =\bot $ . It remains to consider the case that $f,g,h:\mathsf {C}_1$ . If $f:U \to V$ in $\mathsf {C}$ , then ◂ (f◂) =id_{Codomid U} =id _U = f ◂. Similarly, $(\mathbin {\blacktriangleleft } f)\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } f$ , and $\mathbin {\blacktriangleleft } (f\mathbin {\blacktriangleleft }) = f\mathbin {\blacktriangleleft }$ and $(\mathbin {\blacktriangleleft } f)\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } f$ .

Observe that $(\mathbin {\blacktriangleleft } f)f$ is defined and equals $\operatorname {\mathrm {id}}_{V}f=f$ ; also $f(f\mathbin {\blacktriangleleft })$ is defined and equals $f\operatorname {\mathrm {id}}_{U}=f$ . For $g:\mathsf {C}_1(U',V')$ , the expression $\mathbin {\blacktriangleleft } (fg)$ is defined whenever $f\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } g$ , and $f(\mathbin {\blacktriangleleft } g)$ is defined whenever $f\mathbin {\blacktriangleleft } = \mathbin {\blacktriangleleft } (\mathbin {\blacktriangleleft } g)$ . Since $\mathbin {\blacktriangleleft } (-)$ is idempotent by Lemma 3.11 (a), both $\mathbin {\blacktriangleleft } (fg)$ and $f(\mathbin {\blacktriangleleft } g)$ are defined when $f\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } g$ . Thus, $f\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } g$ implies

$$\begin{align*}\mathbin{\blacktriangleleft} (fg) = \operatorname{\mathrm{id}}_{V} = \mathbin{\blacktriangleleft} (f(f\mathbin{\blacktriangleleft})) = \mathbin{\blacktriangleleft} (f(\mathbin{\blacktriangleleft} g)) , \end{align*}$$

so $\mathbin {\blacktriangleleft } (fg) = \mathbin {\blacktriangleleft } (f (\mathbin {\blacktriangleleft } g))$ . Similar arguments hold for $(fg)\mathbin {\blacktriangleleft } = ((f\mathbin {\blacktriangleleft })g)\mathbin {\blacktriangleleft }$ and for $f(gh) = (fg)h$ .

Example 3.13. Let $\mathsf {A}$ be an abstract category with and additional morphisms $a_{12},a_{23},a_{13},\acute {a}_{13},b_{45},b_{54}$ , where $x_{ij}\mathbin {\blacktriangleleft } = e_j$ and $\mathbin {\blacktriangleleft } x_{ij}=e_i$ . Using the composition signature from (3.2), $\mathsf {A}$ is an algebraic structure with multiplication defined in Table 2, where each instance of $\bot $ is omitted. It is not easy to discern structure from this table, so two additional visualizations of $\mathsf {A}$ are given in Figure 1, again with $\bot $ omitted. The first is the Cayley graph of the multiplication with undefined products omitted. The second is the Peirce decomposition, which we now discuss.

Table 2

The multiplication table for $\mathsf {A}~$ .

Figure 1

Visualizing the abstract category $\mathsf {A}$ in Example 3.13.

3.7 Peirce decomposition of abstract categories

Treating categories as algebraic structures allows us to frame aspects of category theory in algebraic terms. Our goal is an elementary representation theory of categories. In particular, we seek matrix-like structures – known as Peirce decompositions in ring theory – for abstract categories.

One can recover from an abstract category $\mathsf {A}$ notions of objects and morphisms by considering the identities . Using the laws in Definition 3.10, if , then $e=e\mathbin {\blacktriangleleft }$ and so $ee=e(e\mathbin {\blacktriangleleft })=e$ ; more generally,

In algebraic terms, the subtype is a type of pairwise orthogonal idempotents. For subtypes X and Y of $\mathsf {A}$ , define

Given , we define three subtypes:

These subtypes appear in Figure 2 in the left, middle, and right images, respectively. If $e\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } a$ for $a:\mathsf {A}$ , then $ea=(e\mathbin {\blacktriangleleft })a=(\mathbin {\blacktriangleleft } a)a=a$ .

Figure 2

Visualizing the Peirce decomposition of $\mathsf {A}$ .

If $a: \mathsf {A}$ , then $a: \mathsf {A} (a\mathbin {\blacktriangleleft })$ , from which we deduce the following.

Proposition 3.15. If $\mathsf {A}$ is an abstract category, then $a\mapsto (\mathbin {\blacktriangleleft } a)a$ , $a\mapsto a(a\mathbin {\blacktriangleleft })$ , and $a\mapsto (\mathbin {\blacktriangleleft } a)a(a\mathbin {\blacktriangleleft })$ induce invertible functions $($ denoted by “ $\leftrightarrow $ ” $)$ of the following types:

Proposition 3.15, which we use to prove Theorem 5.4, allows us to draw upon intuition from matrix algebras. The morphisms of a category appear in its multiplication table, as in Table 2. Products of morphisms and slices are defined, as with matrix products, only when the inner indices agree. In this model, can be visualized as the identity matrix, where the entries on the diagonal are the individual identities . In Figure 1b, that product is represented in a matrix-like form respecting the conditions of the Peirce decomposition.

Remark 3.16. While types for categories and abstract categories differ, every theorem stated in one setting translates to a corresponding theorem in the other. More precisely, the translation is a model-theoretic definable interpretation [Reference Marker24, §1.4]: there is a prescribed formula that translates every theorem and its proof between the two theories. Example 3.13 shows how the model of categories with both objects and morphisms may be interpreted as definable types in the theory of categories with only morphisms (abstract categories). Conversely, if $\mathsf {A}$ is an abstract category, then we obtain a category $\mathsf {C}$ with object type as follows. For objects $e,f: \mathsf {C}_0$ , we define

where the identity morphisms of $\mathsf {C}$ are $e:\mathsf {C}_1(e,e)$ . To compose morphisms $fae : \mathsf {C}_1(e,f)$ with $gbf:\mathsf {C}_1(f,g)$ for objects $e,f,g:\mathsf {C}_0$ , we define

Hence, we no longer distinguish between categories and abstract categories.

3.8 Varieties as categories

Proposition 3.12 shows that a category is an algebraic structure with the composition signature. Conversely, for every signature $\Omega $ , the type $\mathrm {Alge}_{\Omega ,\mathcal {L}}$ of $\Omega $ -algebras in the variety for the laws $\mathcal {L}$ forms a category with morphism type $\mathrm {Hom}_{\Omega ,\mathcal {L}}$ (Section 3.5). Indeed, as in Proposition 3.12, $\mathrm {Alge}_{\Omega ,\mathcal {L}}$ is an abstract category on $(\mathrm {Hom}_{\Omega ,\mathcal {L}})^?$ , and is therefore an algebraic structure with the composition signature.

Freyd originally explored the concept of essentially algebraic structures using partial functions, but did not include $\bot $ as an operator (see [Reference Freyd and Scedrov14, §1.2]). This required dealing with implications such as “if $f\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } g$ then $(fg)\mathbin {\blacktriangleleft }=g\mathbin {\blacktriangleleft }$ ,” which in turn entails working in a quasi-variety. But a quasi-variety is not closed under homomorphic images, so no analogue of Noether’s Isomorphism Theorem (see Theorem 3.18) exists. An earlier version of this paper used this approach, but implementing our methods revealed the simpler approach of transforming categories into varieties (see Section 9).

We reserve $\mathsf {E}$ to denote a variety treated as category.

Under the correspondence of Remark 3.16, morphisms between abstract categories yield functors between categories, but the converse need not follow. A functor $\mathcal {F} : \mathsf {C}\to \mathsf {D}$ between categories retains the homomorphism properties of most of the operators: $\mathcal {F}(c\mathbin {\blacktriangleleft }) = \mathcal {F}(c)\mathbin {\blacktriangleleft }$ , $\mathcal {F}(\mathbin {\blacktriangleleft } c) = \mathbin {\blacktriangleleft } \mathcal {F}(c)$ , and $\mathcal {F}(\bot ) = \bot $ . But it relaxes composition to a directional equality:

This translation serves two of our goals. The first is an elementary representation theory for categories: by regarding categories as “monoids with partial operators,” we mimic monoid actions. The second is to treat a category as a single data type with operations defined on it. This is considerably easier to implement as a computer program. Both GAP and Magma are designed for such algebras. While there are advantages to the usual description of categories, the translation to abstract categories is essential for our approach to computing with and within categories.

We conclude this section with Noether’s Isomorphism Theorem, see [Reference Cohn10, Theorem II.3.7]; it guarantees that images and coimages exist in a variety.

Theorem 3.18 (Noether’s Isomorphism Theorem).

Let $\varphi : E_1 \to E_2$ be a morphism of $\Omega $ -algebras. There exists an $\Omega $ -algebra $\mathrm {Coim}(\varphi )$ and epimorphism $\mathrm {coim}(\varphi ) : E_1 \twoheadrightarrow \mathrm {Coim}(\varphi )$ , an $\Omega $ -algebra $\mathrm {Im}(\varphi )$ and monomorphism $\mathrm {im}(\varphi ) : \mathrm {Im}(\varphi ) \hookrightarrow E_2$ , and an isomorphism $\psi :\mathrm {Coim}(\varphi ) \to \mathrm {Im}(\varphi )$ such that the following diagram commutes:

The morphism $\mathrm {im}(\varphi )$ from Theorem 3.18 is the image of $\varphi $ , and the morphism $\mathrm {coim}(\varphi )$ is the coimage of $\varphi $ . These maps possess universal properties [Reference Riehl28, §E.5].

3.9 Subobjects and images

We close with a list of facts about varieties, which we use heavily in Section 5. We first define a preorder that enables abbreviation of compositions of multiple homomorphisms. To motivate this, assume $\varphi : E_1\to E_2$ is a homomorphism of algebras. Theorem 3.18 states there exists $\theta : E_1 \to \mathrm {Im}(\varphi )$ such that $\varphi = \mathrm {im}(\varphi ) \theta $ . We denote this by $\varphi \ll \mathrm {im}(\varphi )$ and make the following more general definition. For morphisms $a,b: \mathsf {E}$ ,

(3.4) $$ \begin{align} a &\ll b \iff \left[(\exists c:\mathsf{E})\;\; a=bc\right], \end{align} $$

(3.5) $$ \begin{align} a &\gg b \iff \left[(\exists d:\mathsf{E})\;\; a=db\right]. \end{align} $$

Two monomorphisms $a,b:\mathsf {E}$ are equivalent if $a\ll b$ and $b\ll a$ . Similarly, epimorphisms $c,d:\mathsf {E}$ are equivalent if $c\gg d$ and $d\gg c$ .

Proof . By Theorem 3.18, there exist isomorphisms $\psi _b, \psi _{ab} : \mathsf {E}$ such that

$$ \begin{align*} b &= \mathrm{im}(b)\psi_b\mathrm{coim}(b), & ab &= \mathrm{im}(ab)\psi_{ab}\mathrm{coim}(ab). \end{align*} $$

By the universal property of coimages, there exists a unique morphism $\pi :\mathsf {E}$ such that $\mathrm {coim}(ab) = \pi \,\mathrm {coim}(b)$ . Therefore

$$ \begin{align*} a\,\mathrm{im}(b)\psi_b\mathrm{coim}(b) = ab = \mathrm{im}(ab) \psi_{ab} \mathrm{coim}(ab) = \mathrm{im}(ab) \psi_{ab} \pi\, \mathrm{coim}(b). \end{align*} $$

Since $\mathrm {coim}(b)$ is an epimorphism, $a\,\mathrm {im}(b) = \mathrm {im}(ab) \psi _{ab} \pi \psi _b^{-1} \ll \mathrm {im}(ab)$ .

Proof. The first claim follows from the universal property of images, so we assume a is monic. By Theorem 3.18, there exists an isomorphism $\psi _b : \mathsf {E}$ such that

$$ \begin{align*} b &= \mathrm{im}(b)\psi_b\mathrm{coim}(b). \end{align*} $$

Since $a\,\mathrm {im}(b)$ is monic and $ab=(a\,\mathrm {im}(b))(\psi _b\mathrm {coim}(b))$ , by the universal property of images, there exists a morphism $\iota : \mathsf {E}$ such that $\mathrm {im}(ab) = a\,\mathrm {im}(b)\iota \ll a\,\mathrm {im}(b)$ .

Varieties have a coproduct [Reference Riehl28, p. 81] given by the free product [Reference Riehl28, p. 183]. An example concerning groups is given in [Reference Riehl28, Corollary 4.5.7]. We list some facts concerning coproducts in varieties.

Finally, if a is monomorphism satisfying $\mathbin {\blacktriangleleft } a=e$ , for some identity e, then $a\mathbin {\blacktriangleleft }$ can be regarded as a subobject of the object associated to e. Given a collection $\{a_i\mid i:I\}$ of such monomorphisms, consider the smallest subobject containing all set-wise images of the $a_i\mathbin {\blacktriangleleft }$ . The coproduct allows us to effectively “glue” together all of the monomorphisms, but the result is not a monomorphism. To obtain a monomorphism, we take the image of the coproduct, namely

(3.6) $$ \begin{align} \text{im}\,\left( \coprod_{i:I} a_i \right). \end{align} $$

4.1 Category actions

Our formulation of category actions generalizes the familiar notion for groups and also actions of monoids and groupoids [Reference Kilp, Knauer and Mikhalev20, §I.4]. The technical aspects of the definition concern the additional guards, denoted $\lhd $ , needed to express where products are defined. Their use is similar to the guards $\blacktriangleleft $ introduced for abstract categories in Definition 3.10.

Definition 4.1. Let $\mathsf {A}$ be an abstract category with guards $(-)\mathbin {\blacktriangleleft }$ and $\mathbin {\blacktriangleleft } (-)$ . Let X be a type. A ( $left$ ) category action of $\mathsf {A}$ on X consists of a type , functions and that output $\bot $ if, and only if, the input is $\bot $ , and a function $\cdot : \mathsf {A}\times X^?\to X^?$ that satisfies the following rules:

Given a left action of $\mathsf {A}$ on a type Y, a function $\mathcal {M}:X^?\to Y^?$ is an $\mathsf {A}$ -morphism if $\mathcal {M}(a\cdot x) = a \cdot \mathcal {M}(x)$ whenever $a:\mathsf {A}$ and $x:X$ with $a\lhd =\lhd x$ ; that is, .

Right category actions are similarly defined. We unpack the symbolic expressions in Definition 4.1. Condition (1) states that the functions $(-)\lhd $ and $\lhd (-)$ serve as guards for the function $\cdot : \mathsf {A}\times X^?\to X^?$ : namely, (1) characterizes precisely when $\cdot $ is defined. The first part of condition (2) asserts that $(-)\lhd $ respects the $(-)\mathbin {\blacktriangleleft }$ identity of $\mathsf {A}$ ; the second part states that identity morphisms of $\mathsf {A}$ act as identities. Condition (3) is the familiar group action axiom in the setting of partial functions.

For subtypes $S\subset \mathsf {A}$ and $Y\subset X$ , we write

From Definition 4.1, an $\mathsf {A}$ -morphism $\mathcal {M}:X^?\to Y^?$ maps a term $b:(\mathsf {A}\cdot X)$ to a term of Y; we say that $\mathcal {M}$ is defined on $\mathsf {A}\cdot X$ .

Recall from Remark 3.16 that we identify categories and abstract categories. We say that a category $\mathsf {C}$ acts on a type X if its morphism type $\mathsf {C}_1^?$ acts on X (cf. Proposition 3.12).

Example 4.3. Let $\mathsf {C}$ be a category with object type $\mathsf {C}_0$ and morphism type $\mathsf {C}_1^?$ . Set . Define $(-)\lhd : \mathsf {C}_1^? \to \mathsf {C}_0^?$ via and define $\lhd (-) : \mathsf {C}_0^? \to \mathsf {C}_0^?$ via . Let $\cdot : \mathsf {C}_1^? \times \mathsf {C}_0^?\to \mathsf {C}_0^?$ be defined by

This defines a full left action of $\mathsf {C}$ on $\mathsf {C}_0$ . A full right action is defined similarly.

4.2 Capsules

As identified in Section 1.2, we focus on the action of one category $\mathsf {A}$ on another category $\mathsf {X}$ ; we call these “category modules” capsules. Note the subtle change in notation from X to $\mathsf {X}$ to emphasize this setting. In this case, $\mathsf {X}$ already has a candidate type for $\lhd \mathsf {X}$ , namely . Since a category has its own operation of composition, the action by $\mathsf {A}$ respects composition. For example, given a group homomorphism $\varphi :G\to H$ , we get an action that satisfies $g\cdot (hh')=(g\cdot h)h'$ .

Definition 4.5. A category $\mathsf {X}$ is a left $\mathsf {A}$ -capsule if there is a full left $\mathsf {A}$ -action on $\mathsf {X}$ with such that the following hold:

A right $\mathsf {A}$ -capsule is similarly defined. We present our results below for left $\mathsf {A}$ -capsules, but they can be formulated for both.

Much of our intuition on actions draws on familiar themes in representation theory. A reader may be assisted by translating “ $\mathsf {A}$ -capsule” to “A-module” and considering the matching statement for modules. We write ${_{\mathsf {A}} {\mathsf {X}}}$ to indicate the presence of a left $\mathsf {A}$ -capsule action on $\mathsf {X}$ .

From now on, if a category $\mathsf {A}$ acts on itself, then we assume it is by the (left) regular action, where $\cdot : \mathsf {A}\times \mathsf {A} \to \mathsf {A}$ is given by composition in $\mathsf {A}$ . Moreover, a category action on another category is implicitly understood to be on the morphisms. We now show that capsules arise from morphisms between categories.

The following lemma proves one direction of Proposition 4.6.

Proof. Condition (1) of Definition 4.1 is satisfied by the defined action.

For the first part of condition (2), let $a:\mathsf {A}$ . Since $\mathcal {F}$ is a morphism and $(-)\mathbin {\blacktriangleleft }$ is everywhere defined, $\mathcal {F}(a\mathbin {\blacktriangleleft })=\mathcal {F}(a)\mathbin {\blacktriangleleft }$ . Hence, by Lemma 3.11 (a),

$$ \begin{align*} (a\mathbin{\blacktriangleleft})\lhd & = \mathcal{F}(a\mathbin{\blacktriangleleft})\mathbin{\blacktriangleleft} = (\mathcal{F}(a)\mathbin{\blacktriangleleft})\mathbin{\blacktriangleleft} = \mathcal{F}(a)\mathbin{\blacktriangleleft} = a\!\lhd. \end{align*} $$

For the second part of condition (2), let $a:\mathsf {A}$ and $x:\mathsf {X}$ with $a\lhd =\lhd x$ , so $\mathcal {F}(a)\mathbin {\blacktriangleleft } =\mathbin {\blacktriangleleft } x$ by definition. Thus,

$$ \begin{align*}(a\mathbin{\blacktriangleleft}) \cdot x = \mathcal{F}(a\mathbin{\blacktriangleleft})x = (\mathcal{F}(a)\mathbin{\blacktriangleleft})x = (\mathbin{\blacktriangleleft} x) x = x,\end{align*} $$

so for every $a:\mathsf {A}$ and $x:\mathsf {X}$ .

For condition (3), let $a,b:\mathsf {A}$ and $x:\mathsf {X}$ with $a\mathbin {\blacktriangleleft } = \mathbin {\blacktriangleleft } b$ and $(ab)\lhd =\lhd x$ , so $(ab)\cdot x$ is defined and $(ab)\mathbin {\blacktriangleleft }=b\mathbin {\blacktriangleleft }$ . We need to show that $(ab)\cdot x=a\cdot (b\cdot x)$ . Since $\mathcal {F}$ is a morphism,

$$ \begin{align*}(ab)\lhd=(\mathcal{F}(ab))\mathbin{\blacktriangleleft}=\mathcal{F}((ab)\mathbin{\blacktriangleleft})=\mathcal{F}(b\mathbin{\blacktriangleleft})=\mathcal{F}(b)\mathbin{\blacktriangleleft}=b\lhd. \end{align*} $$

Hence, $(ab)\lhd =\lhd x$ implies $b\lhd =\lhd x$ . Thus, $\mathcal {F}(b)x$ is defined. Also, $a\mathbin {\blacktriangleleft } = \mathbin {\blacktriangleleft } b$ implies $\mathcal {F}(a)\mathbin {\blacktriangleleft } = \mathbin {\blacktriangleleft } (\mathcal {F}(b))$ , so

$$\begin{align*}a \lhd = \mathcal{F}(a)\mathbin{\blacktriangleleft} = \mathbin{\blacktriangleleft} (\mathcal{F}(b)) =\mathbin{\blacktriangleleft} (\mathcal{F}(b)x)=\mathbin{\blacktriangleleft} (b\cdot x)=\lhd (b\cdot x). \end{align*}$$

It follows that $a\cdot (b\cdot x)$ is defined. Since $\mathcal {F}$ is a morphism,

$$ \begin{align*}a\cdot (b\cdot x) = \mathcal{F}(a)(\mathcal{F}(b)x) = \mathcal{F}(ab)x = (ab)\cdot x, \end{align*} $$

and therefore for every $a,b:\mathsf {A}$ and $x:\mathsf {X}$ .

To see that the action is full, consider $a: \mathsf {A}$ and define $x=\mathcal {F}(a)\mathbin {\blacktriangleleft }$ . By the laws of an abstract category, $a \lhd = \mathcal {F}(a)\mathbin {\blacktriangleleft } = \mathbin {\blacktriangleleft } ({\mathcal {F}(a)\mathbin {\blacktriangleleft }}) = \mathbin {\blacktriangleleft } x = \lhd x$ . Finally, $(a\cdot x)y=\mathcal {F}(a)xy = a\cdot (xy)$ , so $\mathsf {X}$ is a left $\mathsf {A}$ -capsule.

Our proof of the reverse direction of Proposition 4.6 uses the following result.

Proof. Let $a:\mathsf {A}$ . If $a=\bot $ , then $\bot $ is the unique $x: \mathsf {X}$ with $a\lhd = \bot = \lhd x$ . Now suppose a is not $\bot $ . Since the action is full, there exists $x:\mathsf {X}$ such that $a\lhd = \lhd x$ , so $a\cdot x$ is defined. Since $\mathsf {X}$ is a left $\mathsf {A}$ -capsule, $a\lhd = \lhd x = \mathbin {\blacktriangleleft } x$ , so

$$\begin{align*}\lhd(\mathbin{\blacktriangleleft} x)=\mathbin{\blacktriangleleft} (\mathbin{\blacktriangleleft} x)=\mathbin{\blacktriangleleft} x. \end{align*}$$

Hence, $a\cdot (\mathbin {\blacktriangleleft } x)$ is defined and has type . Suppose and with $a\lhd = \lhd e = \lhd f$ , so that and . Then

$$\begin{align*}e = \mathbin{\blacktriangleleft} e = \lhd e = \lhd f = \mathbin{\blacktriangleleft} f = f, \end{align*}$$

so $a\cdot e = a\cdot f$ , and there is exactly one term with type .

Under the assumptions of Lemma 4.8, we simplify notation and identify with its unique term.

Proof of Proposition 4.6.

By Lemma 4.7, it remains to prove the forward direction and uniqueness. Suppose that $\mathsf {X}$ is a left $\mathsf {A}$ -capsule. By Lemma 4.8, for each $a:\mathsf {A}$ there is a unique such that $(a\mathbin {\blacktriangleleft })\cdot \mathcal {F}(a\mathbin {\blacktriangleleft })$ is defined. Since $\mathsf {X}$ is a left $\mathsf {A}$ -capsule and $\mathcal {F}(a\mathbin {\blacktriangleleft })$ is an identity,

$$\begin{align*}(a\mathbin{\blacktriangleleft})\lhd=a\lhd=\lhd\mathcal{F}(a\mathbin{\blacktriangleleft})=\mathbin{\blacktriangleleft} \mathcal{F}(a\mathbin{\blacktriangleleft})=\mathcal{F}(a\mathbin{\blacktriangleleft}). \end{align*}$$

Thus, $a\cdot \mathcal {F}(a\mathbin {\blacktriangleleft })$ is also defined. Put . If $x:\mathsf {X}$ , then $a\cdot x$ is defined whenever

$$\begin{align*}\mathbin{\blacktriangleleft} x=\lhd x=a\lhd=\mathcal{F}(a\mathbin{\blacktriangleleft})=\mathcal{F}(a\mathbin{\blacktriangleleft})\mathbin{\blacktriangleleft}. \end{align*}$$

Hence, $\mathcal {F}(a\mathbin {\blacktriangleleft })x$ is also defined in $\mathsf {X}$ . Because $\mathcal {F}(a\mathbin {\blacktriangleleft })$ is an identity, $\mathcal {F}(a\mathbin {\blacktriangleleft })x=x$ . Since $\mathsf {X}$ is a left $\mathsf {A}$ -capsule, $a\cdot x=a\cdot (\mathcal {F}(a\mathbin {\blacktriangleleft }) x)=(a\cdot \mathcal {F}(a\mathbin {\blacktriangleleft }))x=\mathcal {F}(a)x$ . Hence, it remains to prove that $\mathcal {F}:\mathsf {A}\to \mathsf {X}$ is a morphism of categories.

For $a,b: \mathsf {A}$ , by the action laws

Thus, . But $\mathsf {X}$ is a left $\mathsf {A}$ -capsule, so Fact 3.14 implies that

(4.1)

Hence, . By Lemma 3.11 (b) and (4.1) for all $a:\mathsf {A}$ ,

$$\begin{align*}\mathcal{F}(a)\mathbin{\blacktriangleleft} ~=~ (a\cdot \mathcal{F}(a\mathbin{\blacktriangleleft}))\mathbin{\blacktriangleleft} ~=~ (\mathcal{F}(a) \mathcal{F}(a\mathbin{\blacktriangleleft}))\mathbin{\blacktriangleleft} ~=~ \mathcal{F}(a\mathbin{\blacktriangleleft})\mathbin{\blacktriangleleft} ~=~ \mathcal{F}(a\mathbin{\blacktriangleleft}). \end{align*}$$

Similarly, $\mathcal {F}(\mathbin {\blacktriangleleft } a) = \mathbin {\blacktriangleleft } \mathcal {F}(a)$ . Hence, $\mathcal {F}$ is a morphism.

Lastly, we prove uniqueness of $\mathcal {F}$ . Suppose there exists $\mathcal {G}: \mathsf {A}\to \mathsf {X}$ such that $a\cdot x = \mathcal {G}(a)x$ for every $a:\mathsf {A}$ and $x:\mathsf {X}$ whenever $a\lhd = \lhd x$ . Since $a\lhd =\mathcal {F}(a\mathbin {\blacktriangleleft })$ , it follows that $\mathcal {G}(a)\mathbin {\blacktriangleleft }=\mathcal {F}(a\mathbin {\blacktriangleleft })$ , so $\mathcal {G}(a) = \mathcal {G}(a)\mathcal {F}(a\mathbin {\blacktriangleleft }) = a\cdot \mathcal {F}(a\mathbin {\blacktriangleleft }) = \mathcal {F}(a)$ .

If $\mathsf {B}$ is a subcategory of $\mathsf {A}$ with inclusion $\mathcal {I} : \mathsf {B}\to \mathsf {A}$ , then the (left) regular action of $\mathsf {B}$ on $\mathsf {A}$ is defined to be the action given by $\mathcal {I}$ . In other words, the regular action of $\mathsf {B}$ on $\mathsf {A}$ is given by $b\cdot a = \mathcal {I}(b)a$ for $a:\mathsf {A}$ and $b:\mathsf {B}$ . By Lemma 4.7, each regular action defines a capsule. With regular actions we sometimes omit the “ $\cdot $ ”.

4.3 Category biactions and cyclic bicapsules

We now define the concepts appearing in Theorem 2(3).

We sometimes write ${_{\mathsf {A}}X_{\mathsf {B}}}$ for an $(\mathsf {A},\mathsf {B})$ -biaction on X for clarity. Notice that an $(\mathsf {A},\mathsf {B})$ -morphism $\mathcal {M}:X^?\to Y^?$ must be defined on $\mathsf {A}\cdot X\cdot \mathsf {B}$ . As with capsule morphisms, we do not need to establish guards. We abbreviate $(\mathsf {A},\mathsf {A})$ -bicapsule to $\mathsf {A}$ -bicapsule, $(\mathsf {A},\mathsf {A})$ -morphism to $\mathsf {A}$ -bimorphism, and $(\mathsf {A},\mathsf {A})$ -biaction to $\mathsf {A}$ -biaction. Just as ring homomorphisms are not always linear maps, morphisms of capsules need not be morphisms of categories since they need not send identities to identities.

Motivated by Proposition 4.6, we show that bicapsules provide a computationally useful perspective to record natural transformations of functors. If $\mathcal {F},\mathcal {G}:\mathsf {A}\to \mathsf {B}$ are functors and $\mu : \mathcal {G}\Rightarrow \mathcal {F}$ is a natural transformation, then, using Remark 3.16, the natural transformation property written with guards is

$$\begin{align*}\mathcal{F}(a)\mu_{a\mathbin{\blacktriangleleft}} = \mu_{\mathbin{\blacktriangleleft} a}\mathcal{G}(a) \end{align*}$$

for every morphism a in $\mathsf {A}$ .

We summarize the conclusion in Proposition 4.10 (b), namely $\mu _e = \mathcal {M}(e)$ for every , by writing . While consists of many terms, each of the types and is inhabited by a unique term, so plays a role similar to multiplying by $1$ . Since $\mathcal {M}:\mathsf {A}\to \mathsf {X}$ is an $\mathsf {A}$ -bimorphism,

$$ \begin{align*} (\forall a:\mathsf{A}) && \mathcal{M}(a)~=~a\cdot \mathcal{M}(\mathbin{\blacktriangleleft} a)~=~\mathcal{M}(a\mathbin{\blacktriangleleft})\cdot a, \end{align*} $$

which shows that $\mathcal {M}$ is determined by . We write

(4.2)

The bicapsule in (4.2) is the cyclic $\mathsf {A}$ -bicapsule determined by .

4.4 Units and counits

A unit in a category $\mathsf {A}$ is a natural transformation $\mu :\operatorname {\mathrm {id}}_{\mathsf {A}}\Rightarrow \mathcal {H}$ , where $\mathcal {H}:\mathsf {A}\to \mathsf {A}$ is a functor. Similarly, a counit is a natural transformation $\nu :\mathcal {H}\Rightarrow \operatorname {\mathrm {id}}_{\mathsf {A}}$ . We will prove that units and counits are responsible for all characteristic structure. It therefore makes sense to translate these into capsule actions. We show that a unit $\mu $ is characterized as an $(\mathsf {A},\mathsf {B})$ -bimorphism $\mathcal {M}:\mathsf {A}\to \mathsf {B}$ and a counit $\nu $ by an $(\mathsf {A},\mathsf {B})$ -morphism $\mathcal {N}:\mathsf {B}\to \mathsf {A}$ . As the relationship is dual, and we emphasize substructures instead of quotients, we consider this relationship only for counits.

4.5 Adjoint functor pairs

Adjoint functor pairs are an important special case of natural transformations. We give one of many equivalent definitions [Reference Riehl28, §4.1].

Definition 4.12. Let $\mathsf {A}$ and $\mathsf {B}$ be categories. An adjoint functor pair is a pair of functors $\mathcal {F}:\mathsf {B}\to \mathsf {A}$ and $\mathcal {G} : \mathsf {A} \to \mathsf {B}$ with the following property. For every object U in $\mathsf {B}$ and V in $\mathsf {A}$ , there is an invertible function

$$\begin{align*}\Psi_{UV} : \mathsf{A}_1(\mathcal{F}(U),V) \to \mathsf{B}_1(U, \mathcal{G}(V)) \end{align*}$$

that is natural in the following sense: if $b:\mathsf {B}_1(X,U)$ and $a: \mathsf {A}_1(V,Y)$ for objects X in $\mathsf {B}$ and Y in $\mathsf {B}$ then, for $x : \mathsf {A}_1(\mathcal {F}(U),V)$ ,

(4.3) $$ \begin{align} \Psi_{XY}(a x \mathcal{F}(b)) = \mathcal{G}(a)\Psi_{UV}(x)b. \end{align} $$

We say $\mathcal {F}$ is left-adjoint to $\mathcal {G}$ and $\mathcal {G}$ is right-adjoint to $\mathcal {F}$ and write $\mathcal {F} : \mathsf {B} \dashv _{\Psi } \mathsf {A} : \mathcal {G}$ .

We now characterize adjoint functor pairs in terms of bicapsules. A reader may find it useful to review the translation between categories and abstract categories in Remark 3.16. The invertibility of $\Psi _{UV}$ in Definition 4.12 is equivalent to a pseudo-inverse property of morphisms of bicapsules.

For types X and Y, functions $\mathcal {M} : X^?\to Y^?$ and $\mathcal {N} : Y^?\to X^?$ are pseudo-inverses if, for $x:X^?$ and $y:Y^?$ , $\mathcal {M}\mathcal {N}\mathcal {M}(x)= \mathcal {M}(x)$ and $\mathcal {N}\mathcal {M}\mathcal {N}(y)= \mathcal {N}(y)$ .

4.6 A computational model for natural transformations

We use the algebraic perspective of Section 3.6 to discuss briefly a model for computing with natural transformations. The next definition formalizes how to treat morphisms of a category as functors between two other categories.

Definition 4.14. Let $\mathsf {N}$ , $\mathsf {A}$ and $\mathsf {B}$ be abstract categories. A natural map of $\mathsf {N}$ from $\mathsf {A}$ to $\mathsf {B}$ consists of functions and that satisfy the following properties:

The use of in (1) and (4) depends only on $xy$ and $st$ , respectively, being defined. For the composition signature $\Omega $ from (3.2), conditions (1) and (2) imply that there is a function given by $e\mapsto (x\mapsto e\cdot x)$ where $\mathrm {Hom}_{\Omega }(\mathsf {A}, \mathsf {B})$ is the type of morphisms between abstract categories; see also Definition 3.10. This function enables us to treat the objects of $\mathsf {N}$ as functors from $\mathsf {A}$ to $\mathsf {B}$ . As illustrated in Example 4.15, conditions (3) and (4) are equivalent to the commutative diagrams in Figure 3 in the shaded $(2,2)$ and $(3,1)$ entries, respectively.

Example 4.15. We illustrate how the four conditions of Definition 4.14 translate to categories with objects and morphisms. Let $\mathsf {A}$ and $\mathsf {B}$ be two such categories, and let $\Omega $ be the composition signature from (3.2). Then $\mathrm {Hom}_{\Omega }(\mathsf {A},\mathsf {B})$ is the type of functors from $\mathsf {A}$ to $\mathsf {B}$ . Let $\mathsf {N}$ be the category whose objects are the functors in $\mathrm {Hom}_{\Omega }(\mathsf {A},\mathsf {B})$ and whose morphisms are natural transformations. Let $\eta : \mathcal {F} \Rightarrow \mathcal {G}$ be a natural transformation between $\mathcal {F},\mathcal {G}: \mathrm {Hom}_{\Omega }(\mathsf {A},\mathsf {B})$ . Treating $\mathsf {N}$ as an abstract category, the guards are defined as follows: and . Define by $(\operatorname {\mathrm {id}}_{\mathcal {F}}, \varphi ) \longmapsto \mathcal {F}(\varphi )$ , and by $(\eta , \operatorname {\mathrm {id}}_X) \longmapsto \eta _X$ . Now the conditions of Definition 4.14 become:

Figure 3

A natural map of $\mathsf {N}$ (displayed in the left dotted column) from $\mathsf {A}$ (displayed in top row) to $\mathsf {B}$ (shaded gray).

The theory of functors and natural transformations is equivalent to that of natural maps on abstract categories, but the latter allows us to use multiple encodings of functors and natural transformations such as those available in computer algebra systems. If, for example, we compute the derived subgroup $\gamma _2(G)$ of a group G in Magma, then the system may use an encoding for $\gamma _2(G)$ that differs from that supplied for G. In such cases, Magma also returns an inclusion homomorphism $\lambda _G : \gamma _2(G)\hookrightarrow G$ .

5.1 Natural transformations express characteristic subgroups

Suppose that H is a characteristic subgroup of a group G. Hence, every automorphism $\varphi :G\to G$ restricts to an automorphism $\varphi |_H:H\to H$ of H. In categorical terms, we now treat as the subcategory of $\mathsf {Grp}$ consisting of a single object G and all isomorphisms $G\to G$ . Likewise, we treat as a subcategory of $\mathsf {Grp}$ . The restriction defines a functor $\mathcal {C}:\mathsf {A}\to \mathsf {B}$ . Of course, $\mathsf {Aut}(G)$ and $\mathsf {Aut}(H)$ are also groups and $\mathcal {C}$ is a group homomorphism, but the discussion below justifies the functor language.

Now we use the fact that H is a subgroup of G (by using the inclusion map $\rho _G:H\hookrightarrow G$ ). That $\varphi (H)$ is a subgroup of H can be expressed as φρ _G = ρ _G φ| _H = ρ _G C(φ). Recognizing the different categories, we use the inclusion functors $\mathcal {I}:\mathsf {A}\to \mathsf {Grp}$ and $\mathcal {J}:\mathsf {B}\to \mathsf {Grp}$ to deduce the following:

$$ \begin{align*} \mathcal{I}(\varphi)\rho_G=\rho_G\mathcal{J}\mathcal{C}(\varphi). \end{align*} $$

Thus, a characteristic subgroup determines a natural transformation

$$\begin{align*}\rho:\mathcal{J}\mathcal{C}\Rightarrow \mathcal{I}. \end{align*}$$

The next definition generalizes Definition 1.1.

A common way to illustrate categories, functors, and natural transformations uses a 2-dimensional diagram where categories are vertices, functors are directed edges, and natural transformations are oriented 2-cells. The next diagram illustrates the counital discussed above.

We now generalize the notion of a characteristic subgroup to an arbitrary algebra in a variety.

Using the language of Definition 5.2, a characteristic subgroup H of a group G determines and is determined by a -invariant monomorphism $H\hookrightarrow G$ . For fully invariant subgroups, the corresponding monomorphism is $\mathsf {Grp}$ -invariant.

5.2 The extension problem and representation theory

In Section 5.1, we observed that a characteristic subgroup H of G determines a functor $\mathcal {C} : \mathsf {A} \to \mathsf {B}$ and a natural transformation $\rho : \mathcal {JC}\Rightarrow \mathcal {I}$ , where $\mathsf {A}$ and $\mathsf {B}$ are categories with one object, namely G and H respectively. If a group $\hat {G}$ is isomorphic to G, then, by Fact 1.2, $\hat {G}$ has a characteristic subgroup corresponding to H. It seems plausible that we may be able to extend the functor $\mathcal {C}$ to more groups and, hence, to larger categories. We now make this notion of extension precise and generalize it to the setting of varieties of algebras.

Fix a variety $\mathsf {E}$ . Let $\mathsf {A}$ , $\mathsf {B}$ , and $\mathsf {C}$ be subcategories of $\mathsf {E}$ where $\mathsf {A} \leqslant \mathsf {C}$ . We have inclusion functors $\mathcal {I}:\mathsf {A}\to \mathsf {E}$ , $\mathcal {J}:\mathsf {B}\to \mathsf {E}$ , $\mathcal {K}:\mathsf {C}\to \mathsf {E}$ and $\mathcal {L}:\mathsf {A}\to \mathsf {C}$ such that $\mathcal {I}=\mathcal {K}\mathcal {L}$ . Suppose that $\rho :\mathcal {J}\mathcal {C}\Rightarrow \mathcal {I}$ is a monic counital as depicted in Figure 4(a). The extension problem asks whether there is a functor $\mathcal {D}:\mathsf {C}\to \mathsf {E}$ and a natural transformation $\sigma :\mathcal {D}\Rightarrow \mathcal {K}$ such that

(5.1) $$ \begin{align} \rho_X = \sigma_{\mathcal{L}(X)}\tau_X \end{align} $$

for some invertible morphism $\tau _X : \mathcal {JC}(X) \to \mathcal {DL}(X)$ for all objects X of $\mathsf {A}$ . This is depicted in Figure 4(b).

Figure 4

Extending a counital.

For now, we are concerned only with the existence and construction of such extensions. For use within an isomorphism test, it will be necessary to develop tools to compute efficiently with categories; the data types of Section 4.6 are designed for that purpose.

In light of Proposition 4.10, we can explore the natural transformations from Figure 4 through the lens of actions. Recall that concatenation always denotes regular actions. The natural transformation $\rho $ defined above is encoded as an $\mathsf {A}$ -bimorphism $\mathcal {R}:\mathsf {A}\to \mathsf {E}$ , where , and this bimorphism defines a cyclic $\mathsf {A}$ -bicapsule via (4.2), which we fix throughout.

Our goal in part is to extend the cyclic $\mathsf {A}$ -bicapsule $\Delta $ to a cyclic $\mathsf {C}$ -bicapsule $\Sigma $ . Specifically, we will define , where $\sigma : \mathcal {D} \Rightarrow \mathcal {K}$ is depicted in Figure 4(b). This is the content of Theorem 5.4, but given in the general setting of algebras in a variety. By construction (Proposition 4.10), the left actions on $\Delta $ and $\Sigma $ are regular; hence, we focus on right actions.

Example 5.3. For the purposes of illustration, we consider a familiar construction that is similar to our context, namely Frobenius reciprocity and Morita condensation [Reference Rowen30, Theorem 25A.19]. Here E is a ring, and A and C are subrings. Considering a Peirce decomposition of E, let and be idempotents in E such that . Then is a (nonunital) subring of E, and is a subring of both C and E. Furthermore, is an $(A,C)$ -bimodule and is a $(C,A)$ -bimodule. Suppose $\Delta $ is a right A-module and $\Sigma $ a right C-module. The theory of induction and restriction provides us, respectively, with a right C-module and a right A-module: namely,

Thus, yields a map $\Delta \cong \Delta \otimes _A A\to \mathrm {Res}_A^C(\mathrm {Ind}_A^C(\Delta ))$ . If, for example, , then $\Delta \cong \mathrm {Res}_A^C(\mathrm {Ind}_A^C(\Delta ))$ .

Guided by the Peirce decomposition from Example 5.3, we seek similar constructions for categories and capsules. Recall that $\mathsf {E}$ contains a subcategory $\mathsf {C}$ that contains a subcategory $\mathsf {A}$ . This containment implies that is contained in (or rather embeds under the inclusion functors into) . The bicapsule action of $\mathsf {A}$ on $\Delta $ induces a $\mathsf {C}$ -bicapsule, denoted $\mathrm {Ind}_{\mathsf {A}}^{\mathsf {C}}(\Delta )$ . By mimicking modules, we can consider a formal extension process. We form the type $\Delta \otimes _{\mathsf {A}}\mathsf {C}$ whose terms are pairs, denoted $\delta \otimes c$ for $\delta :\Delta $ and $c:\mathsf {C}$ , subject to the equivalence relation $(\delta \cdot a)\otimes c=\delta \otimes (ac)$ . Then we equip this type with the right $\mathsf {C}$ -action $(\delta \otimes c)\cdot c'=\delta \otimes (cc')$ . Defining , we write

We return to this construction in Section 8. Finally, since $\Delta = \mathsf {A}\rho \cdot \mathsf {A}$ and $\mathsf {C}$ are both subtypes of $\mathsf {E}$ , the product in $\mathsf {E}$ defines a map $\Delta \times \mathsf {C}\to \mathsf {E}$ that factors through $\Delta \otimes _{\mathsf {A}}\mathsf {C}$ . The image of the map is a cyclic $\mathsf {C}$ -bicapsule $\Sigma $ embedded in $\mathsf {E}$ , with corresponding $\mathsf {C}$ -bimorphism $\mathcal {S}:\mathsf {C}\to \mathsf {E}$ . The following theorem states that this is always possible if $\mathsf {A}$ is full in $\mathsf {C}$ . Table 3 summarizes some of the notation fixed throughout this section.

Table 3

Data for the proof of Theorem 5.4.

Theorem 5.4 (Extension).

Let $\mathsf {E},\mathsf {C},\mathsf {A},\Delta $ be as in Table 3. If $\mathsf {A}$ is full in $\mathsf {C}$ , then there is a cyclic $\mathsf {C}$ -bicapsule $ {\Sigma }$ on $\mathsf {E}$ and unique cyclic $\mathsf {A}$ -bicapsules $ \mathsf{Y}$ , $ {\Lambda }$ on $\mathsf {E}$ such that

$$\begin{align*}\Delta = \mathrm{Res}_{\mathsf{A}}^{\mathsf{C}}(\Sigma)\otimes_{\mathsf{A}}\Upsilon\quad\text{and}\quad \mathrm{Res}_{\mathsf{A}}^{\mathsf{C}}(\Sigma) = \Delta \otimes_{\mathsf{A}} \Lambda. \end{align*}$$

We briefly describe the idea of the proof. We start with a cyclic $\mathsf {A}$ -bicapsule $\Delta $ with associated $\mathsf {A}$ -bimorphism $\mathcal {R}:\mathsf {A}\to \mathsf {E}$ . We seek an extension of $\mathcal {R}$ to a $\mathsf {C}$ -bimorphism $\mathcal {S}\colon \mathsf {C}\to \mathsf {E}$ that satisfies $\mathcal {S}\mathcal {L}=\mathcal {R}$ , where $\mathcal {L}\colon \mathsf {A}\to \mathsf {C}$ is the inclusion functor. If this holds, then, for every and every $c:\mathsf {C}$ with $c\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } \mathcal {R}(e)$ ,

$$\begin{align*}c\cdot\mathcal{R}(e)= c\cdot \mathcal{S}\mathcal{L}(e)=\mathcal{S}(c\cdot e)=\mathcal{S}(c)=\mathcal{S}(\mathbin{\blacktriangleleft} c)\cdot c.\end{align*}$$

We now derive some necessary conditions for a putative $\mathcal {S}$ of this type. Recall from (3.4) that the notation $\alpha \ll \beta $ for morphisms $\alpha $ and $\beta $ implies that there is a morphism $\gamma $ such that $\alpha =\beta \gamma $ . Applying Lemma 3.20 to $c\cdot \mathcal {R}(e)=\mathcal {S}(c\mathbin {\blacktriangleleft })\cdot c$ yields $\mathrm {im}(c\cdot \mathcal {R}(e))\ll \mathrm {im}(\mathcal {S}(\mathbin {\blacktriangleleft } c))$ . For define

The left $\mathsf {A}$ -actions on $\mathsf {C}$ and $\mathsf {E}$ are regular, as is the left $\mathsf {C}$ -action on $\mathsf {E}$ . Hence, for $\langle e,c\rangle :\mathbb {U}_{\mathsf {C}}(f)$ ,

Therefore , so $c\cdot \mathcal {R}(e)$ is defined. Since $\mathrm {im}(c\cdot \mathcal {R}(e))\ll \mathrm {im}(\mathcal {S}(f))$ holds for every $\langle e,c\rangle :\mathbb {U}_{\mathsf {C}}(f)$ , we can make a single inclusion (see (3.6)):

(5.2) $$ \begin{align} \mathrm{im}\, \left(\coprod_{{\langle e,c\rangle \in \mathbb{U}_{\mathsf{C}}(f)}} \mathrm{im}(c\cdot \mathcal{R}(e))\right) \ll \mathrm{im}(\mathcal{S}(f)). \end{align} $$

Observe that (5.2) also holds if, instead of $\mathcal {R}=\mathcal {SL}$ , we assume that there exists $\mathcal {T}:\mathsf {A}\to \mathsf {E}$ such that $\mathcal {R}(a)=\mathrm {Res}_{\mathsf {A}}^{\mathsf {C}}(\mathcal {S})(a)\mathcal {T}(a\mathbin {\blacktriangleleft })$ for all $a:\mathsf {A}$ ; here denotes the restriction of $\mathcal {S}$ to $\mathsf {A}$ . This motivates us to choose $\mathcal {S}$ such that $\mathcal {S}(c)$ is defined as the left hand side of (5.2), and then solve for a suitable $\mathcal {T}$ .

In the language of bimorphisms, Theorem 5.4 asserts that there exists an $\mathsf {A}$ -bimorphism $\mathcal {T}\colon \mathsf {A}\to \mathsf {E}$ such that, for $a:\mathsf {A}$ ,

(5.3)

where $\mathcal {S}$ is the $\mathsf {C}$ -bimorphism corresponding to $\Sigma $ ; we use this language in its proof. The second equality in (5.3) reflects the tensor product over $\mathsf {A}$ shown in Theorem 5.4.

5.3 Building blocks

We prove Theorem 5.4 in Section 5.4 using the three intermediate results presented in this section.

Proof. We assume (1) holds and prove (2). By Proposition 4.10 (b), there exists a unique functor $\mathcal {G} : \mathsf {C}\to \mathsf {E}$ that induces the action of $\mathsf {C}$ on the right of $\mathsf {E}$ . Since $\mathcal {S}$ is a function and a $\mathsf {C}$ -bimorphism by assumption, $c\lhd = \lhd \sigma _{c\mathbin {\blacktriangleleft }}$ for all $c:\mathsf {C}$ , and

$$ \begin{align*} c\cdot \sigma_{c\mathbin{\blacktriangleleft}} & = \mathcal{S}(c) =\mathcal{S}((\mathbin{\blacktriangleleft} c)\cdot c)= \mathcal{S}(\mathbin{\blacktriangleleft} c)\cdot c = ((\mathbin{\blacktriangleleft} c) \cdot \sigma_{(\mathbin{\blacktriangleleft} c)\mathbin{\blacktriangleleft}}) \cdot c =\sigma_{\mathbin{\blacktriangleleft} c}\mathcal{G}(c). \end{align*} $$

Thus, (2) holds.

We now assume (2) holds and prove (1). First, we show that $x:\mathsf {E}$ satisfying $c\cdot \sigma _{c\mathbin {\blacktriangleleft }} = \sigma _{\mathbin {\blacktriangleleft } c}x$ is unique. Suppose $y:\mathsf {E}$ satisfies $c\cdot \sigma _{c\mathbin {\blacktriangleleft }} = \sigma _{\mathbin {\blacktriangleleft } c}y$ , so $\sigma _{\mathbin {\blacktriangleleft } c}x = \sigma _{\mathbin {\blacktriangleleft } c}y$ . Since $\sigma _{\mathbin {\blacktriangleleft } c}$ is a monomorphism, $x=y$ . We denote this unique morphism by $u_c:\mathsf {E}$ . Since $\sigma _{\mathbin {\blacktriangleleft } c}u_c$ is defined for all $c:\mathsf {C}$ ,

$$ \begin{align*} \mathbin{\blacktriangleleft} u_{\mathbin{\blacktriangleleft} c} = (\sigma_{\mathbin{\blacktriangleleft} (\mathbin{\blacktriangleleft} c)})\mathbin{\blacktriangleleft} = (\sigma_{\mathbin{\blacktriangleleft} c})\mathbin{\blacktriangleleft} = \mathbin{\blacktriangleleft} u_c. \end{align*} $$

Next, we define a right $\mathsf {C}$ -capsule structure on $\mathsf {E}$ as follows. Let be given by , and let be given by . For all $c:\mathsf {C}$ and $x:\mathsf {E}$ , let , which is defined if, and only if, $x\mathbin {\blacktriangleleft } = \mathbin {\blacktriangleleft } u_c$ . Condition (2) of Definition 4.1 follows from $\lhd (\mathbin {\blacktriangleleft } c) = \mathbin {\blacktriangleleft } u_{\mathbin {\blacktriangleleft } c} = \mathbin {\blacktriangleleft } u_c = \lhd c$ and for all since $\sigma _e$ is monic. Lastly, let $c,d:\mathsf {C}$ with $c\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } d$ . Now $(cd) \cdot \sigma _{(cd)\mathbin {\blacktriangleleft }} = \sigma _{\mathbin {\blacktriangleleft } (cd)}u_{cd} = \sigma _{\mathbin {\blacktriangleleft } c}u_{cd}$ and, since we have a regular left action,

$$ \begin{align*} (cd) \cdot \sigma_{(cd)\mathbin{\blacktriangleleft}} = c \cdot (d \cdot \sigma_{(cd)\mathbin{\blacktriangleleft}}) = c\cdot (d\cdot \sigma_{d\mathbin{\blacktriangleleft}}) = c\cdot \sigma_{\mathbin{\blacktriangleleft} d} u_d = \sigma_{\mathbin{\blacktriangleleft} c}u_cu_d. \end{align*} $$

Since $\sigma _{\mathbin {\blacktriangleleft } c}$ is a monomorphism, $u_{cd}=u_cu_d$ . Hence, this defines a right $\mathsf {C}$ -capsule on $\mathsf {E}$ since for all $c:\mathsf {C}$ . Since $\mathsf {C}$ acts regularly on $\mathsf {E}$ on the left, there exists a $\mathsf {C}$ -bicapsule $\Sigma $ on $\mathsf {E}$ by Proposition 4.6, with the regular left and right actions just defined. Finally, we prove that $\mathcal {S}$ is a $\mathsf {C}$ -bimorphism. For all $c,x,y:\mathsf {C}$ ,

$$ \begin{align*} \mathcal{S}(cx) &= (cx)\cdot \sigma_{(cx)\mathbin{\blacktriangleleft}} = (cx)\cdot \sigma_{x\mathbin{\blacktriangleleft}} = c\cdot (x\cdot \sigma_{x\mathbin{\blacktriangleleft}}) = c\cdot \mathcal{S}(x), \end{align*} $$

provided $c\mathbin {\blacktriangleleft }=\mathbin {\blacktriangleleft } x$ . If $y\mathbin {\blacktriangleleft } = \mathbin {\blacktriangleleft } c$ , then

$$ \begin{align*} \mathcal{S}(yc) &= (yc)\cdot \sigma_{(yc)\mathbin{\blacktriangleleft}} = (yc)\cdot \sigma_{c\mathbin{\blacktriangleleft}} = y\cdot (c\cdot \sigma_{c\mathbin{\blacktriangleleft}}) = y\cdot (\sigma_{\mathbin{\blacktriangleleft} c}u_c) = (y\cdot \sigma_{y\mathbin{\blacktriangleleft}})u_c \\ &= \mathcal{S}(y)\cdot c. \end{align*} $$