# On the Multicategorical Meta-Theorem and
the Completeness of Restricted Algebraic Deduction Systems

David Forsman
Université catholique de Louvain
<EMAIL_ADDRESS>
###### Abstract

Eight categorical soundness and completeness theorems are established within
the framework of algebraic theories. Exactly six of the eight deduction
systems exhibit complete semantics within the cartesian monoidal category of
sets. The multicategorical meta-theorem via soundness and completeness enables
the transference of properties of families of models from the cartesian
monoidal category of sets to $\Delta$-multicategories $C$.

A bijective correspondence $R\mapsto\Delta_{R}$ is made between context
structures $R$ and structure categories $\Delta$, which are wide subcategories
of FinOrd consisting of finite ordinals and functions. Given a multisorted
signature $\sigma$ with a context structure $R$, an equational deduction
system $\vdash_{R}$ is constructed for $R$-theories. The models within
$\Delta_{R}$-multicategories provide a natural semantic framework for the
deduction system $\vdash_{R}$ for modelable context structures $R$. Each of
the eight modelable context structures $R$ is linked with a soundness and
completeness theorem for the deduction system $\vdash_{R}$.

###### Contents

  1. 1 Introduction
  2. 2 Multicategories
    1. 2.1 Structure Categories
    2. 2.2 $\Delta$-Multicategories
  3. 3 Universal algebra
    1. 3.1 Syntax
    2. 3.2 Soundness
    3. 3.3 Completeness in Sets
  4. 4 Categorical completeness
  5. 5 Conclusion

##  1 Introduction

In logic there is a blurred distinction between syntax and semantics. Often
one has in mind a structure or a family of structures about which one would
like to know more. Mathematical logic studies this phenomenon through the
concepts of language and the structures to which language refers, called
syntax and semantics respectively. Specifically, syntax consists of an
alphabet, propositions, and the associated deduction system for propositions.
Traditionally, semantics refers to the models consisting of sets, functions
and relations compatible with a given syntax. Soundness is the property that
the deduction rules of the syntax are compatible with the associated models.
Completeness then describes the maximality of the deduction system in the
sense that every property of all models that can be expressed in the language
is obtained by deduction.

Soundness and completeness theorems allow us to study the class of models of a
theory by studying only the syntax of the theory. There is a meaningful
consequence of the soundness and completeness of a given syntax. Namely, if
the soundness of a deduction system holds for some collection $A$ of models,
and the completeness of the deduction holds for some family $B$ of models,
then one can transfer properties from the class $B$ to the class $A$. This
creates a path for results to pass from $B$ to $A$. We call this notion a
meta-theorem.

The Eckmann-Hilton argument establishes a condition under which two unital
magma structures on the same set form a single commutative monoid. This
argument extends from the monoidal category of sets to any symmetric monoidal
category. An intriguing question arises: does this generalization follow
simply because the claim holds in the context of sets? The answer is
affirmative. For any equational linear theory $E\cup\\{\phi\\}$ we demonstrate
$E\vDash_{\textbf{Set}}\phi$ implies $E\vDash_{C}\phi$ for all symmetric
multicategories $C$. This result is further generalized to
$\Delta$–multicategories across six distinct structure categories $\Delta$.

We introduce four main concepts in this paper:

  1. 1.

Context Structure $R$ dictates when a sequence of variables $c$ forms a
context for another sequence $v$ via the relation $cRv$.

  2. 2.

Equational Deduction System $\vdash_{R}$ defined by an algebraic signature
$\sigma$ equipped with a context structure $R$.

  3. 3.

Bijection $R\mapsto\Delta_{R}$ maps context structures $R$ to structure
categories $\Delta$, where a structure category is a suitable wide subcategory
of FinOrd encompassing finite ordinals and functions.

  4. 4.

$\Delta$-multicategory $C$ is endowed with a specified $\Delta$–action on its
hom-sets.

While there are infinitely many context structures $R$, our focus centers on
eight specific structures called modelable context structures. These
structures enable $R$-theories to have models within
$\Delta_{R}$-multicategories. We establish the soundness and completeness of
$\vdash_{R}$ for each modelable $R$ with respect to categorical semantics.
Notably, six out of these eight modelable context structures achieve complete
semantics just in sets. The Multicategorical Meta-Theorem emerges as a
corollary:

######  Theorem (Multicategorical Meta-Theorem).

Let $\sigma$ be a signature with a cartesian or balanced and modelable context
structure $R$. Let $E\cup\\{\phi\\}$ be an $R$-theory. Let $C$ be a
$\Delta_{R}$-multicategory. Then

$E\vDash_{\textbf{Set}}\phi\text{ implies }E\vDash_{C}\phi.$

The remainder of this paper is structured as follows: In Section 2, we define
the notion of a structure category $\Delta$ as a wide subcategory of FinOrd
consisting of functions between finite ordinals. A structure category $\Delta$
enables the definition of $\Delta$–multicategories through its action on the
homsets of a multicategory. Section 3 introduces the basic concepts in
universal algebra, divided into subsections covering syntax, soundness, and
completeness within the context of sets. Syntax encompasses signatures
equipped with a context structure $R$, $R$-terms, and $R$-theories. We
establish a bijective correspondence $R\mapsto\Delta_{R}$ between context
structures and structure categories, identifying precisely eight modelable
context structures $R$. The soundness subsection addresses the definition of
models in $\Delta_{R}$-multicategories for $R$-theories, demonstrating
soundness across all models in $\Delta_{R}$ categories. In the completeness
subsection, we establish that six out of the eight deduction systems
$\Delta_{R}$ exhibit complete semantics within the cartesian multicategory of
sets, culminating in the Multicategorical Meta-Theorem, a central result of
this paper.

Section 4 is dedicated to constructing the universal model for a
$\sigma,R$-theory $E$ and proving the categorical completeness of
$R$-deduction for a modelable $R$. We construct the universal $E,R$-model by
developing a linear $\Sigma$-theory $\overline{E}$ that conservatively extends
$E$. The initial $\overline{E}$-model serves as the universal model, providing
a free multicategory equipped with a model for $E$. This construction is
closely related to the functorial semantics proposed by Lawvere [2]. A natural
transformation $\eta\colon F\Rightarrow G\colon M\rightarrow N$ in the
$2$-category of $\Delta$-multicategories can be interpreted as a homomorphism
from the model $F$ to $G$ of a theory $M$ in the $\Delta$-multicategory $N$.

Section 5 concludes the paper by summarizing the main findings.

##  2 Multicategories

Structures like cartesian and symmetric multicategories have been extensively
studied, as discussed in works such as [3] and [1]. We introduce
$\Delta$–multicategories, a generalization encompassing multicategories,
symmetric multicategories, and cartesian multicategories within a unified
framework. Initially, we define structure categories $\Delta$ as wide
subcategories of FinOrd comprising finite ordinals and functions. We proceed
to define the action of $\Delta$ on the homsets of a multicategory, leading to
the formal definition of $\Delta$–multicategories. Special cases include
instances where $\Delta$ comprises all functions, bijections, or identities,
corresponding respectively to cartesian multicategories, symmetric
multicategories, and multicategories. This sets the stage for a bijective
correspondence between structure categories and context structures defined
later.

###  2.1 Structure Categories

A structure category is a wide subcategory of FinOrd of finite ordinal closed
under coproduct of functions and components of similarities. We give
infinitely many examples of structure categories using the notion of a
structure monoid.

######  Definition 2.1 (Finite Ordinals).

We define the category FinOrd of finite ordinals and functions as follows:

  * •

Objects are sets $[n]\coloneqq\\{m\in\mathbb{N}\mid 0<m\leq n\\}$ for
$n\in\mathbb{N}$, called finite ordinals.

  * •

Morphism $[m]\rightarrow[n]$ is a function $[m]\rightarrow[n]$. The
composition is the usual function composition.

We define the $k$-ary coproduct functor
$+_{k}\colon\textbf{FinOrd}^{k}\rightarrow\textbf{FinOrd}$.

We define $+_{k}([m_{1}],\ldots,[m_{k}])=[m_{1}+\ldots+m_{k}]$ for
$m_{1},\ldots,m_{k}\in\mathbb{N}$ and for functions
$f_{i}\colon[m_{i}]\rightarrow[n_{i}],0<i\leq k,$ between finite ordinals we
set

$+_{n}(f_{1},\ldots,f_{k})=f_{1}+\ldots+f_{k}\colon[M_{k}]\rightarrow[N_{k}],M_{i-1}+x\mapsto
N_{i-1}+f_{i}(x)$

for $0<x\leq m_{i}$ and $i\leq k$. Here $M_{i}=\Sigma_{j\leq i}m_{i}$ and
$N_{i}=\Sigma_{j\leq i}n_{i}$ for $i\leq k$.

######  Definition 2.2 (Similarity of a function).

Let $\theta\colon[m]\rightarrow[n]$ be a function between finite ordinals. For
a category $C$, we set $\theta^{*}\colon C^{n}\rightarrow C^{m}$, where
$(x_{1},\ldots,x_{n})\mapsto(x_{\theta(1)},\ldots,x_{\theta(m)})$. We define a
natural transformation
$\theta^{\prime}\colon+_{m}\circ\theta^{*}\Rightarrow+_{n}\colon\textbf{FinOrd}^{n}\rightarrow\textbf{FinOrd}$
by setting

$\theta^{\prime}_{k_{1},\ldots,k_{m}}\colon[L_{m}]\rightarrow[K_{n}]\text{,
where }L_{i-1}+x\mapsto K_{\theta(i)-1}+x$

for $k_{1},\ldots,k_{n}\in\mathbb{N}$. Here we denote
$L_{i}=k_{\theta(1)}+\ldots+k_{\theta(i)}$ and $K_{j}=k_{1}+\ldots+k_{j}$ for
$i\leq m$ and $j\leq n$. In addition, we call the natural transformation
$\theta^{\prime}$ the similarity natural transformation of $\theta$. The
function $\theta$ is recovered back via $\theta^{\prime}_{1,\ldots,1}=\theta$.

######  Definition 2.3 (Structure category).

A wide (containing all objects) subcategory $\Delta$ of FinOrd of finite
ordinals is said to be a structure category if the following holds:

  * •

$\Delta$ is closed under the coproduct of morphisms.

  * •

If a function $\theta\colon[m]\rightarrow[n]$ is in $\Delta$, then the
component
$\theta^{\prime}_{k_{1},\ldots,k_{n}}\colon[k_{\theta(1)}+\ldots+k_{\theta(m)}]\rightarrow[k_{1}+\ldots+k_{n}]$
of the similarity of $\theta$ is in $\Delta$ for
$k_{1},\ldots,k_{n}\in\mathbb{N}$.

There are infinitely many structure categories. Certain submonoids of natural
numbers with multiplicative structure allow us to define structure categories.

######  Definition 2.4 (Structure monoid).

Let $I\subset\mathbb{N}$. We call $I$ a structure monoid, if the two
conditions hold:

  * •

$1\in I$.

  * •

If $k,a_{1},\ldots,a_{k}\in I$, then $a_{1}+\ldots+a_{k}\in I$.

Each structure monoid $I$ determines structure categories
$\Delta_{I},\Delta^{I}$ and when $0\not\in I$ structure categories $\Psi_{I}$
and $\Psi^{I}$:

  * •

$\Delta^{I}$ consists of those functions $f\colon[m]\rightarrow[n]$ between
finite ordinals where the cardinality of the fiber $f^{-1}\\{i\\}$ is in $I$
for each $i\in[n]$.

  * •

$\Delta_{I}$ is the structure category generated by the functions
$[n]\rightarrow[1],n\in I$.

  * •

Assume $0\not\in I$. We set $\Psi_{I}$ to consist of those functions
$f\colon[m]\rightarrow[n]$ in $\Delta^{I}$, where
$\min(f^{-1}\\{i\\})\leq\min(f^{-1}\\{j\\})$ for all $i\leq j\leq n$.

  * •

Symmetrically, we set $\Psi^{I}$ similarly to $\Psi_{I}$ except we change
taking of minimum with taking of maximum when $0\not\in I$.

Notice that each structure monoid $I$ is a submonoid of $\mathbb{N}$ with the
multiplicative structure. Consider $a,b\in I$. Now $ab=a_{1}+\ldots+a_{b}\in
I$ where $a_{i}=a$ for $i\leq b$.

######  Lemma 2.5.

Let $\Delta$ be a structure category. Define the set $I\subset\mathbb{N}$
where $I$ consists of all the cardinalities of the fibers of functions in
$\Delta$. Then the following conditions hold:

  1. 1.

The set $I$ is a structure monoid.

  2. 2.

For each structure monoid $S$ the associated structures
$\Delta_{S}\subset\Psi_{S},\Psi^{S}\subset\Delta^{S}$ are structure
categories, when defined.

  3. 3.

If $\Delta$ has a single non-identity bijection, then $\Delta=\Delta^{I}$.

  4. 4.

Given a structure monoid $S$, then $\Delta_{S}=\Delta^{S}$ if and only if
$S=\mathbb{N}$.

  5. 5.

We have that $\Delta_{I}\subset\Delta\subset\Delta^{I}$.

  6. 6.

If $0\in I$, then $\Delta$ is one of the structure categories
$\Delta_{\\{0,1\\}},\Delta^{\\{0,1\\}}$ or $\Delta^{\mathbb{N}}$

###### Proof.

  1. 1.

Since $\Delta$ has an identity function on $[1]$, it follows that $1\in I$.
Assume that $k,a_{1},\ldots,a_{n}\in I$. Thus there are functions $g,f_{i}$
for $i\leq k$ where for some fiber of $g$ and $f_{i}$ attain the size of $k$
and $a_{i}$, respectively. We may assume that $g$ and $f_{i}$ have $[1]$ as
the codomain, since otherwise we can define such functions using the
associated similarity transformation. Now $g\circ(f_{1}+\ldots+f_{k})$ has the
fiber of size $a_{1}+\ldots+a_{k}$. Thus $a_{1}+\ldots+a_{k}\in I$.

  2. 2.

Let $S$ be a structure monoid. First, we show that $\Delta^{S}$ is a structure
category. Since identities have fibers of size $1$, it follows that
$\Delta^{S}$ has identities. Assume that $f,g$ are functions in $\Delta$. The
fibers of $f+g$ have the same sizes as the fibers of $f$ and $g$. Thus $f+g$
is in $\Delta$. Let $\theta\colon[m]\rightarrow[n]$ be a function in $\Delta$.
Let $k_{1},\ldots,k_{n}\in\mathbb{N}$ and denote
$L_{i}=k_{\theta(1)}+\ldots+k_{\theta(i)}$ and $K_{j}=k_{1}+\ldots+k_{j}$ for
$i\leq m$ and $j\leq n$. Consider the component
$\theta^{\prime}_{k_{1},\ldots,k_{n}}\colon[L_{m}]\rightarrow[K_{n}]$. Let
$j\in[K_{n}]$. Now $K_{l-1}<j\leq K_{l}$ for some unique $l\leq n$. By
definition $x\xmapsto{\theta^{\prime}}j$ if and only if $x=L_{i-1}+x^{\prime}$
where $\theta(i)=l$ and $x^{\prime}=j-K_{l-1}$. Thus $\theta^{\prime-1}(j)$
has the same cardinality as $\theta^{-1}(l)$. Hence $\theta^{\prime}$ is a
function in $\Delta^{I}$.

Next, assume that $0\not\in S$. Thus all the morhisms of $\Delta^{S}$ are
surjections. We show that $\Psi_{S}$ is a structure category.

First, $\Psi_{S}$ is a category, since it has identities and compositions of
functions, which is seen as follows: Let
$[k]\xrightarrow{f}[m]\xrightarrow{g}[n]$ be functions in $\Psi$. Let $i\leq
j\leq n$. Now

$\displaystyle\min((gf)^{-1}\\{i\\})$
$\displaystyle=\min(f^{-1}g^{-1}\\{i\\})$
$\displaystyle=\min(f^{-1}\\{\min(g^{-1}\\{i\\}\\}))$
$\displaystyle\leq\min(f^{-1}\\{\min(g^{-1}\\{j\\}\\}))$
$\displaystyle=\min((gf)^{-1}\\{j\\})$

The coproduct of two functions in $\Psi_{S}$ is in $\Psi_{S}$. To see the
closure under components of similarities, fix a function
$\theta\colon[m]\rightarrow[n]$ is in $\Psi_{S}$. Let
$k_{1},\ldots,k_{n}\in\mathbb{N}$ and denote
$L_{i}=k_{\theta(1)}+\ldots+k_{\theta(i)}$ and $K_{j}=k_{1}+\ldots+k_{j}$ for
$i\leq m$ and $j\leq n$. We need to show that
$\theta^{\prime}=\theta^{\prime}_{k_{1},\ldots,k_{n}}\colon[L_{m}]\rightarrow[K_{n}]$
is in $\Psi_{S}$. Consider $j_{1}\leq j_{2}\in[K_{n}]$. Now
$K_{l_{1}-1}<j_{1}\leq K_{l}$ and $K_{l_{2}-1}<j_{2}\leq K_{t}$ for some
unique $l_{1}\leq l_{2}\leq n$. Now $j_{a}=K_{l_{a}-1}+x_{a}$ for
$x_{a}=j_{a}-K_{l_{a}-1}$ and $a=1,2$. Let $i_{1}$ and $i_{2}$ be the least
elements $\theta$ maps to $l_{1}$ and $l_{2}$, respectively. Since $\theta$ is
in $\Psi_{S}$, we know that $i_{1}\leq i_{2}$. Now $L_{i_{a}-1}+x_{a}$ is the
least element $\theta^{\prime}$ maps to $j_{a}$ for $a=1,2$. Notice that
$i_{1}<i_{2}$ implies that $L_{i_{1}-1}+x_{1}\leq L_{i_{2}-1}$ and hence
$L_{i_{1}-1}+x_{1}<L_{i_{2}-1}+x_{2}$. If $i_{1}=i_{2}$, then $x_{1}\leq
x_{2}$ and thus $L_{i_{1}-1}+x_{1}\leq L_{i_{2}-1}+x_{2}$. Hence
$\theta^{\prime}$ is in $\Psi_{S}$.

The case $\Psi^{S}$ being a structure category is similar. Since the
generators of $\Delta_{S}$ are included in $\Psi_{S}$ and $\Psi^{S}$ it
follows that $\Delta_{S}\subset\Psi_{S},\Psi^{S}$.

  3. 3.

Assume that $\Delta$ has a single non-identity bijections $f$. A suitable
component of a similarity of $f$ yields a bijection $[2]\rightarrow[2]$ where
$1\mapsto 2$. By induction, we attain that $\Delta$ has all bijections. Let
$g\colon[m]\rightarrow[n]$ be a function in $\Delta$. Denote by $!_{k}$ the
unique function $[k]\rightarrow[1]$ for $k\in\mathbb{N}$. Notice that up to
pre-composition with bijection the functions
$!^{g^{-1}\\{1\\}}+\ldots+!^{g^{-1}\\{n\\}}$ and $g$ are the same. Since
$\Delta$ has all bijections and functions $!^{k},k\in I$, it follows that $g$
is in $\Delta$.

  4. 4.

Let $S$ be a structure monoid. Assume that $S=\mathbb{N}$. It suffices to show
that the bijection $[2]\rightarrow[2],1\mapsto 2$ is in $\Delta_{\mathbb{N}}$.
Consider the function
$(!^{2^{\prime}}_{2})\circ(!^{0}+id_{[2]}+!^{0})\colon[2]\rightarrow[4]\rightarrow[2]$.
This function is the bijection $[2]\rightarrow[2]$ mapping $1\mapsto 2$ and it
is in $\Delta_{\mathbb{N}}$. Thus $\Delta_{\mathbb{N}}=\Delta^{\mathbb{N}}$.

Assume then that $S\neq\mathbb{N}$. Let us consider the case that $0\in S$,
then $S=\\{0,1\\}$. Notice that $\Delta^{S}$ consists of all injections.
Notice that $\Delta_{S}$ contains all strictly increasing functions and
strictly increasing functions do define a structure category. Thus
$\Delta_{S}$ consists of strictly increasing functions and
$\Delta_{S}\neq\Delta^{S}$. If $0\not\in S$, then
$\Delta_{S}\subset\Psi_{S}\subsetneq\Delta^{S}$. Thus
$\Delta_{S}\subsetneq\Delta^{S}$.

  5. 5.

Consider $n\in I$. Thus there exists a function $\theta$ in $\Delta$ who has a
fiber of size $n$. A suitable component of the similarity $\theta^{\prime}$
yields exactly the function $[n]\rightarrow[1]$ and this is in $\Delta$. Since
$\Delta_{I}$ is generated by such function,
$\Delta_{I}\subset\Delta\subset\Delta^{I}$.

  6. 6.

Assume that $0\in I$. Thus $\Delta_{I}$ has all strictly increasing functions.
Assume that $\Delta$ has a function $f\colon[m]\rightarrow[n]$ that is not
strictly increasing. If $f$ is not an injection, then $m\in I$ for some $m>1$
and thus $I=\mathbb{N}$ and so $\Delta=\Delta^{\mathbb{N}}$. Assume that $f$
is an injection. It suffices to show that $\Delta$ has a non-identity
bijection. Now there exists $i<j\leq m$ such that $f(j)<f(i)$. Since $0\in S$
by inclusions and codiagonals we can construct the function
$[2]\rightarrow[m]$ and $[n]\rightarrow[2]$ such that composing them with $f$
yields a map $[2]\rightarrow[2]$, where $1\mapsto 2\mapsto 1$. Thus
$\Delta=\Delta^{I}$ and $I$ can only be either $\\{0,1\\}$ or $\mathbb{N}$.

∎

######  Example 2.6.

We will give examples of structure categories $\Delta$.

  1. 1.

For each structure monoid $I\subset\mathbb{N}$ we have the structure
categories $\Delta_{I}$ and $\Delta^{I}$.

     * •

If $I=\\{0,1\\},\\{1\\},\mathbb{N}_{>0},\mathbb{N}$ we have $\Delta_{I}$
consists of strictly increasing maps, identities, functions generated via
coproducts and similarities from increasing surjections and all functions,
respectively. With the same conditions on $I$, the structure category
$\Delta^{I}$ consists of injections, bijections, surjections and all
functions, respectively.

     * •

Let $N>0$. Define $I=I_{N}$ as $\\{1,n\mid n\geq N\\}$ or $\\{1,N,n\mid n\geq
2N-1\\}$. The set $I$ defines a structure monoid and we have four different
structure categories $\Delta_{I}\subset\Psi_{I},\Psi^{I}\subset\Delta^{I}$.
Since each $N>0$ defines a different structure category $\Delta^{I_{N}}$, it
follows that there are infinitely many structure categories.

     * •

Let $I$ be a structure monoid where $0\not\in I$. Then $\Psi_{I}$ consists of
those surjections $f\colon[m]\rightarrow[n]$ where $\min f^{-1}\\{i\\}\leq\min
f^{-1}\\{j\\}$ for $i\leq j\leq n$ and the cardinality of each fiber of $f$ is
in $I$.

     * •

Increasing functions do not define a structure category. Consider a non-
injective function $\theta\colon[m]\rightarrow[n]$. Assume that the fiber of
$f$ at $j\leq n$ has cardinality of at least $2$. Now define
$k_{l}=\begin{cases}0,\text{ if }l\neq j,\\\ 2,\text{ if }l=j.\end{cases}$ Now
$\theta(i_{1})=j=\theta(i_{2})$ for some $i_{1}<i_{2}\leq m$. Denote
$L_{i}=k_{\theta(1)}+\ldots+k_{\theta(i)}$ for $i\leq m$. Now
$\theta^{\prime}_{k_{1},\ldots,k_{n}}(L_{i_{1}}+2)=2$ but
$\theta^{\prime}_{k_{1},\ldots,k_{n}}(L_{i_{2}}+1)=1$ and
$L_{i_{1}}+2<L_{i_{2}}+1$. Hence $\theta^{\prime}_{k_{1},\ldots,k_{n}}$ is not
an increasing function.

###  2.2 $\Delta$-Multicategories

We define $\Delta$–multicategories, where $\Delta$ is a structure category.
These are multicategories $C$ equipped with a $\Delta$-action on the hom-sets
of $C$. The first two action axioms relating to composition and identities are
similar to the ones of monoid axioms, but the latter two require the coproduct
and similarity closure properties of a structure category.

######  Definition 2.7 ($\Delta-$Multicategory).

Let $\Delta$ be a structure category. A $\Delta$-multicategory $C$ consists of
a class of objects $S$ and choice of sets $C(a,b)$ for each $a\in S^{*}$ and
$b\in S$, where $S^{*}$ is the class $\bigsqcup_{n\in\mathbb{N}}S^{n}$ of
finite words of $S$. For $f\in C(a,b)$, we denote $f\colon a\rightarrow b$ for
$a\in S^{*}$ and $b\in S$. In addition $C$ is equipped with the following
structure:

  * •

A family of maps $\circ$ called the composition:

$\circ_{a^{1},\ldots,a^{n},b_{1}\ldots b_{n},c}\colon C(b_{1}\cdots
b_{n},c)\times C(a^{1},b_{1})\times\cdots\times C(a^{n},b_{n})\rightarrow
C(a^{1}\cdots a^{n},b)$

for $a^{1},\ldots,a^{n}\in S^{*}$ and $b_{1},\ldots,b_{n},c\in S$.

  * •

For each $a\in S$ there is a choice of a morphism $id_{a}\colon a\rightarrow
a$.

  * •

For each function $\theta\colon[m]\rightarrow[n]$ in $\Delta$ and
$a_{1},\ldots,a_{n},b\in S$ there is a function

$\theta_{a_{1}\cdots a_{n},b,*}\colon C(a_{\theta(1)}\cdots
a_{\theta(m)},b)\rightarrow C(a_{1}\cdots a_{n},b)$

Furthermore, for $C$ to be a $\Delta$–multicategory we require the following
axioms to be satisfied:

  * •

The associativity of composition:

$(h\circ(g^{1},\ldots,g^{n}))\circ(f^{1}_{1},\ldots,f^{1}_{m_{1}},\ldots,f^{n}_{1},\ldots,f^{n}_{m_{n}})=h\circ(g^{1}\circ(f^{1}_{1},\ldots,f^{1}_{m_{1}}),\ldots,g^{n}\circ(f^{n}_{1},\ldots,f^{n}_{m_{n}}))$

for $h\colon c_{1}\cdots c_{n}\rightarrow d,g^{i}\colon b^{i}_{1}\cdots
b^{i}_{m_{i}}\rightarrow c_{i}$ and $f^{i}_{j}\colon a^{i,j}\rightarrow
b^{i}_{j}$ where $i\leq n$ and $j\leq m_{i}$.

  * •

The identity laws:

$f\circ(id_{a_{1}},\ldots,id_{a_{n}})=f$

and

$id_{b}\circ f=f$

for $f\colon a\rightarrow b$, where $a=a_{1}\ldots a_{n}$ and $a_{i},b\in S$
for $i\leq n$.

  * •

The axioms of a $\Delta$-action:

    1. 1.

$(id_{[n]})_{a,b,*}=id_{C(a,b)}$

for $n\in\mathbb{N}$, $a\in S^{*}$ and $b\in S$, where the length of the word
$a$ is $n$.

    2. 2.

$(\tau\sigma)_{a,b,*}=\tau_{a,b,*}\circ\sigma_{a_{\tau(1)}\cdots
a_{\tau(m)},b,*}$

for functions $[k]\xrightarrow{\sigma}[m]\xrightarrow{\tau}[n]$ in $\Delta$
and $a\in S^{*},l(a)=n,$ and $b\in S$.

    3. 3.

$g\circ(\sigma^{1}_{a^{1},b_{1},*}(f_{1}),\ldots,\sigma^{n}_{a^{n},b_{n},*}(f_{n}))=(\sigma^{1}+\cdots+\sigma^{m})_{a^{1}\cdots
a^{n},c,*}(g\circ(f_{1},\cdots,f_{n}))$

for functions $\sigma^{i}\colon[k_{i}]\rightarrow[l_{i}],i\leq n$, in $\Delta$
and multimorphisms $g\colon b_{1}\cdots b_{n}\rightarrow c$ and $f_{i}\colon
a^{i}_{\sigma^{i}(1)}\cdots a^{i}_{\sigma^{i}(k_{i})}\rightarrow b_{i}$ where
$a^{i}=a^{i}_{1}\cdots a^{i}_{k_{i}}$ for $a^{i}_{1},\ldots,a^{i}_{k_{i}}\in
S$ and $i\leq n$.

    4. 4.

$\tau_{b_{1}\cdots
b_{n},c,*}(g)\circ(f_{1},\ldots,f_{n})=(\tau^{\prime}_{k_{1},\ldots,k_{n}})_{a^{1}\cdots
a^{n},c,*}(g\circ(f_{\tau(1)},\ldots,f_{\tau(m)}))$

for function $\tau\colon[m]\rightarrow[n]$ and multi-morphisms $f_{i}\colon
a^{i}\rightarrow b_{i},l(a^{i})=k_{i},$ and $g\colon b_{\tau(1)}\cdots
b_{\tau(m)}\rightarrow c$, $i\leq n$.

When the category $\Delta$ is the wide subcategory of FinOrd consisting of all
functions, bijections or identities, the corresponding
$\Delta$–multicategories are called cartesian multicategories, symmetric
multicategories and multicategories, respectively.

######  Definition 2.8 ($2$-category of $\Delta$–multicategories).

Let $\Delta$ be a structure category and let $M$ and $N$ be
$\Delta$–multicategories with classes of objects $R$ and $S$, respectively. A
morphism $T\colon M\rightarrow N$ of $\Delta$–multicategories consists of a
map $T\colon R\rightarrow S$ and functions $T=T_{a,b}\colon M(a,b)\rightarrow
N(\overline{T}(a),T(b))$, where $a\in R^{*},b\in R,$ and $\overline{T}\colon
R^{*}\rightarrow S^{*}$ is the unique monoid morphism extending $T\colon
R\rightarrow S$, also denoted as $T$. Additionally, $T$ respects composition,
identities and the $\Delta$-action:

  * •

$T(g\circ(f_{1},\ldots,f_{n}))=T(g)\circ(T(f_{1}),\ldots,T(f_{n}))$.

  * •

$T(id_{c})=id_{T(c)}$

  * •

$T(\theta_{a,b,*}(g))=\theta_{\overline{T}(a),T(b),*}(T(g))$.

A natural transformation $\eta\colon T_{1}\Rightarrow T_{2}\colon M\rightarrow
N$ consists of a family of morphisms $\eta_{r}\colon T_{1}(r)\rightarrow
T_{2}(r)$ making the multicategorical diagram

${T_{1}(a)}$${T_{1}(b)}$${T_{2}(a)}$${T_{2}(b)}$$\scriptstyle{T_{1}(f)}$$\scriptstyle{\eta_{a}}$$\scriptstyle{\eta_{b}}$$\scriptstyle{T_{2}(f)}$

commute for each multimorphism $f\colon a\rightarrow b$ in $M$. Here
$\eta_{a}$ denotes the sequence $\eta_{a}=(\eta_{a_{1}},\ldots,\eta_{a_{n}})$
for $a=a_{1}\cdots a_{n}$ where $a_{1},\ldots,a_{n}\in R$. The vertical and
horizontal composition is defined similarly as in the $2$-category of
categories. This determines the $2$-category $\Delta$-MultiCat of
$\Delta$–multicategories.

######  Lemma 2.9.

Let $\Delta$ be a structure category and let $(T,\mu\colon T^{2}\Rightarrow
T,\lambda\colon I\Rightarrow T)=T\colon M\rightarrow M$ be a monad in the
$2$-category $\Delta$-MultiCat. Then the underlying Kleisli and Eilenberg-
Moore categories associated to $T$ extend into a $\Delta$–multicategories.

###### Proof.

We define the Kleisli category $M_{T}$ as follows:

  * •

The objects of $M_{T}$ are the same as the objects of $M$.

  * •

A multi-morphism $a\rightarrow b$ in $M_{T}$ consists of a multimorphism
$f\colon a\rightarrow T(b)$ in $M$.

  * •

Let $g\colon b_{1}\cdots b_{n}\rightarrow c$ and $f_{i}\colon a^{i}\rightarrow
b_{i}$ be multimorphisms for $i\leq n$ in $M_{T}$. We define the composition
as follows:

$g\circ_{M_{T}}(f_{1},\ldots,f_{n})\coloneq\mu_{c}\circ_{M}T(g)\circ_{M}(f_{1},\ldots,f_{n}).$

The unit of the monad $T$ defines the identity morphisms of $M_{T}$.

  * •

Let $\theta\colon[m]\rightarrow[n]$ be a function in $\Delta$. We define
$\theta^{T}_{a,b,*}\colon M_{T}(a_{\theta},b)\rightarrow M_{T}(a,b)$ as the
function $\theta_{a,Tb,*}\colon M(a_{\theta},T(b))\rightarrow M(a,T(b))$,
where $a=a_{1}\cdots a_{n},a_{\theta}=a_{\theta(1)}\cdots a_{\theta(m)}$ and
$a_{1},\ldots,a_{n},b$ are objects of $M$.

We show that $M_{T}$ is a $\Delta$-multicategory:

  1. 1.

To show that the identity laws hold, fix $f\colon a=a_{1}\cdots
a_{n}\rightarrow b$ in $M_{T}$, where $a_{1},\ldots,a_{n}$ and $b$ are objects
of $M$. Now

$f\circ_{M_{T}}(\lambda_{a_{1}},\ldots,\lambda_{a_{n}})=\mu_{b}\circ
T(f)\circ(\lambda_{a_{1}},\ldots,\lambda_{a_{n}})=\mu_{b}\lambda_{Tb}f=f$

and

$\lambda_{b}\circ_{M_{T}}f=\mu_{b}\circ T(\lambda_{b})\circ f=f.$

Thus the identity laws hold.

  2. 2.

For associativity, fix multimorphisms $h\colon c_{1}\cdots c_{n}\rightarrow
d$, $g_{i}\colon b^{i}\rightarrow c_{i}$ and $f^{i}_{j}\colon
a^{i,j}\rightarrow b^{i}_{j}$ for $b^{i}=b^{i}_{1}\cdots b^{i}_{m_{i}}$ for
$i\leq n$ and $j\leq m_{i}$. Now

$\displaystyle(h\circ_{M_{T}}(g_{1},\ldots,g_{n}))\circ_{M_{T}}(f^{1}_{1},\ldots,f^{n}_{m_{n}})$
$\displaystyle=(\mu_{d}T(h)\circ(g_{1},\ldots,g_{n}))\circ_{M_{T}}(f^{1}_{1},\ldots,f^{n}_{m_{n}})$
$\displaystyle=\mu_{d}T(\mu_{d}T(h)\circ(g_{1},\ldots,g_{n}))\circ(f^{1}_{1},\ldots,f^{n}_{m_{n}})$
$\displaystyle=(\mu_{d}T(\mu_{d})TT(h)\circ(T(g_{1}),\ldots,T(g_{n})))\circ(f^{1}_{1},\ldots,f^{n}_{m_{n}})$
$\displaystyle=(\mu_{d}\mu_{Td}TT(h)\circ(T(g_{1}),\ldots,T(g_{n})))\circ(f^{1}_{1},\ldots,f^{n}_{m_{n}})$
$\displaystyle=((\mu_{d}T(h)\circ(\mu_{c_{1}},\ldots,\mu_{c_{n}}))\circ(T(g_{1}),\ldots,T(g_{n})))\circ(f^{1}_{1},\ldots,f^{n}_{m_{n}})$
$\displaystyle=(\mu_{d}T(h)\circ(\mu_{c_{1}}T(g_{1}),\ldots,\mu_{c_{n}}T(g_{n})))\circ(f^{1}_{1},\ldots,f^{n}_{m_{n}})$
$\displaystyle=\mu_{d}T(h)\circ(\mu_{c_{1}}T(g_{1})\circ(f^{1}_{1},\ldots,f^{1}_{m_{1}}),\ldots,\mu_{c_{n}}T(g_{n})\circ(f^{n}_{1},\ldots,f^{n}_{m_{n}}))$
$\displaystyle=\mu_{d}T(h)\circ(g_{1}\circ_{M_{T}}(f^{1}_{1},\ldots,f^{1}_{m_{1}}),\ldots,g_{n}\circ_{M_{T}}(f^{n}_{1},\ldots,f^{n}_{m_{n}}))$
$\displaystyle=h\circ_{M_{T}}(g_{1}\circ_{M_{T}}(f^{1}_{1},\ldots,f^{1}_{m_{1}}),\ldots,g_{n}\circ_{M_{T}}(f^{n}_{1},\ldots,f^{n}_{m_{n}}))$

  3. 3.

The $\Delta$–action axioms are satisfied since $T$ respects the action and
thus $M_{T}$ is a $\Delta$–multicategory.

We define the Eilenberg-Moore $\Delta$-multicategory $M^{T}$ as follows:

  * •

The objects are pairs $(a,f\colon Ta\rightarrow a)$ where the diagrams

${TTa}$${Ta}$${a}$${Ta}$${Ta}$${a}$${a}$$\scriptstyle{\mu_{a}}$$\scriptstyle{Tf}$$\scriptstyle{f}$$\scriptstyle{\lambda_{a}}$$\scriptstyle{id}$$\scriptstyle{f}$$\scriptstyle{f}$

commute.

  * •

A multimorphism $(a_{1},f_{1})\cdots(a_{n},f_{n})\rightarrow(a,f)$ in $M^{T}$
consist of a multimorphism $\alpha\colon a_{1}\cdots a_{n}\rightarrow a$ in
$M$ making the diagram

${Ta_{1}\cdots Ta_{n}}$${Ta}$${a_{1}\cdots
a_{n}}$${a}$$\scriptstyle{T(\alpha)}$$\scriptstyle{(f_{1},\ldots,f_{n})}$$\scriptstyle{f}$$\scriptstyle{\alpha}$

commute.

  * •

The composition in $M^{T}$ is defined as in $M$.

  * •

The action $\theta_{a,b,*}\colon M^{T}(a_{\theta},b)\rightarrow M^{T}(a,b)$ is
defined as in $M$ and a quick check shows that it is well defined.

Associativity and unitality axioms of a multicategory are satisfied making
$M^{T}$ a $\Delta$–multicategory. ∎

######  Example 2.10.

Here we give examples of different $\Delta$-multicategories.

  1. 1.

Each (cartesian/symmetric) monoidal category determines a
(cartesian/symmetric) multicategory.

  2. 2.

If $C$ is a $\Delta$-multicategory, then any full submulticategory of $C$ is
also a $\Delta$–multicategory. Denote the class of objects of $C$ by $S$. Let
$P$ be any subclass of $S$. We define the full submulticategory $A$ over $P$
as the one which has $P$ as the class of objects and $A(a,b)=C(a,b)$ for $a\in
P^{*}$ and $b\in P$. The $\Delta$-action restricts into $A$ and thus $A$ has
the structure of a $\Delta$-multicategory.

  3. 3.

The category of compactly generated Hausdorff spaces has two different
cartesian multicategory structures, one defined by its categorical product and
the other defined by restricting the cartesian structure of topological
spaces.

  4. 4.

The cartesian multicategory of sets is specifically defined as follows:

     * •

The objects are sets $X$.

     * •

A morphism $f\colon X_{1}\cdots X_{n}\rightarrow X$ is just a function
$\Pi_{i\leq n}X_{i}\coloneq\\{(x_{1},\ldots,x_{n})\mid x_{i}\in X_{i},i\leq
n\\}\rightarrow X$.

     * •

Composition is defined using usual function composition.

     * •

Let $\theta\colon[m]\rightarrow[n]$ be a function between finite ordinals and
let $f\colon X_{\theta(1)}\cdots X_{\theta(m)}\rightarrow X$ be a
multimorphism. We define
$\theta_{*}(f)(x_{1},\ldots,x_{n})=f(x_{\theta(1)},\ldots,x_{\theta(m)})$ for
$x_{i}\in X_{i}$ for $i\leq n$.

We will show only the last condition of the action axiom: Let
$\theta\colon[m]\rightarrow[n]$ and let $g\colon Y_{\theta(1)}\cdots
Y_{\theta(m)}\rightarrow Y$ and $f_{i}\colon X^{1}\rightarrow Y_{i}$ for
$i\leq n$. We show that

$\theta_{*}(g)\circ(f_{1},\ldots,f_{n})=(\theta^{\prime}_{k_{1},\ldots,k_{n}})_{*}(g\circ(f_{\theta(1)},\ldots,f_{\theta(m)})),$

where $k_{i}$ is the length of the word $X^{i}$ for $i\leq n$. Let
$x_{i}\in\Pi X^{i}$ for $i\leq n$. Now

$\displaystyle\theta_{*}(g)\circ(f_{1},\ldots,f_{n})(x_{1}\cdots x_{n})$
$\displaystyle=\theta_{*}(g)(f_{1}(x_{1}),\ldots,f_{n}(x_{n}))$
$\displaystyle=g(f_{\theta(1)}(x_{\theta(1)}),\ldots,f_{\theta(m)}(x_{\theta(m)}))$
$\displaystyle=(\theta_{k_{1},\ldots,k_{n}}^{\prime})_{*}(g\circ(f_{\theta(1)},\ldots,f_{\theta(m)}))(x_{1},\ldots,x_{n}).$

Thus
$\theta_{*}(g)\circ(f_{1},\ldots,f_{n})=\theta^{\prime}_{*}(g\circ(f_{1},\ldots,f_{n}))$.

  5. 5.

Interestingly, the category of relations on sets has a cartesian monoidal
structure given by its cartesian monoidal structure defined by the disjoint
union of sets and hence it has a cartesian multicategory structure. There is
another surjective-multicategory structure on the category of relations
determined by the powerset monad
$(\mathcal{P},\mu\colon\mathcal{PP}\Rightarrow\mathcal{P},\lambda\colon
I\Rightarrow\mathcal{P})$ on the surjective-multicategory of sets. We set

$\mathcal{P}(f\colon X_{1}\cdots X_{n}\rightarrow
X)(A_{1},\ldots,A_{n})=f(A_{1}\times\cdots\times A_{n})$

and

$x\xmapsto{\lambda_{X}}\\{x\\}\colon X\rightarrow\mathcal{P}(X)\text{ and
}\mathcal{A}\xmapsto{\mu_{X}}\bigcup\mathcal{A}\colon\mathcal{PP}(X)\rightarrow\mathcal{P}(X)$

for sets $X,X_{i}$ and $A_{i}\subset X_{i},i\leq n$. It is fast to check that
$\mathcal{P}$ is a morphism between the multicategories. It is equivariant
with respect the action of $\Delta^{\mathbb{N}_{1}}$ making $\mathcal{P}$ into
a monad on the surjective multicategory of sets. Thus, as the Kleisli-category
of the powerset monad, the category of relations inherits a surjective
multicategory structure. Let $\theta\colon[1]\hookrightarrow[2]$ and
$f\colon[1]\rightarrow[1]$. Consider
$\theta_{[1]\emptyset,[1],*}(f)\colon[1]\emptyset\rightarrow[1]$ which is the
empty map. Notice that $\mathcal{P}(\theta_{*}(f))$ is not a surjection, but
$\theta_{*}(\mathcal{P}(f))$ is. Hence $\mathcal{P}$ is not an endomorphism on
the cartesian multicategory of sets.

  6. 6.

The category of sets equipped with partial functions is a surjective multi-
category as the Kleisli multicategory of the list-monad $T$. The failure of
$\textbf{Set}^{T}$ to be a cartesian multicategory is related to the failure
of $\textbf{Set}^{\mathcal{P}}$ to be a cartesian multicategory.

##  3 Universal algebra

We define the syntax and semantics of universal algebra. Syntax contains
notions of a signature $\sigma$, a context structure $R$, an $R$–equational
theory $E$ and an $R$-deduction system $\vdash_{R}$. Semantics concentrates on
the models inhabiting in different multicategories and we define the
connection between syntax and semantics via the satisfiability of models. Once
the concepts are bolted down, we prove the soundness and completeness of some
of the associated deduction systems.

###  3.1 Syntax

Syntax refers to the construction of mathematical structures out of symbol
manipulation itself. We define a symbol as an element of a set and using
recursive constructions on symbols we create the languages appropriate to our
setting.

######  Definition 3.1 (Signature of universal algebra).

A signature $\sigma$ consists of the following data:

  * •

A set $S$ of sorts.

  * •

A set of function symbols $M$ with a typing $t\colon M\rightarrow S^{*}\times
S$. We denote $f\colon a\rightarrow b$ for $f\in M$ where $f\xmapsto{t}(a,b)$
and if $a=()$ is the empty sequence, then we say that $f$ is a constant symbol
and $f\colon b$.

  * •

A set of typed variables $t^{\prime}\colon V\rightarrow S$. Notation $x\colon
s$ means that $x\xmapsto{t^{\prime}}s$. We require the fibers of $t^{\prime}$
to be countably infinite.

We will often shorten and denote $\sigma=(S,M)$ or $\sigma=(S,M,V)$.

######  Definition 3.2 (Terms).

Fix a signature $\sigma=(S,M,V)$. We define a typed set Term $\rightarrow S$
of terms as follows:

  * •

$c\colon s,x\colon s\in\text{Term}$ for $c\colon s\in M$ and $x\colon s\in V$.

  * •

We define $f(t_{0},\ldots,t_{n})\colon b\in\text{Term}$ for $f\colon
a_{0}\cdots a_{n}\rightarrow b\in M$ and $t_{i}\colon a_{i}\in\text{Term}$ for
$i\leq n$.

We define a function $\tau\colon\text{Term}\rightarrow V^{*}$, where
$\tau(t)=\begin{cases}t,\text{ if $t$ is a variable symbol}\\\ (),\text{ if
$t$ is a constant symbol}\\\ \tau(t_{1})\ldots\tau(t_{n}),\text{ if
$t=f(t_{1},\ldots,t_{n})$}.\end{cases}$ Let $t$ be a term and denote
$\tau(t)=x_{1}\ldots x_{n}$. The set of variables of a term $t$ is
$\text{Var}(t)=\\{x_{1},\ldots,x_{n}\\}$ and similarly for words $v\in V^{*}$.

######  Definition 3.3 (Context Structure).

Let $V$ be a set, whose elements we call letters. We denote the set of finite
words of $V$ as $V^{*}$. We say that a word $v\in V^{*}$ is a context of $V$
if no element in $v$ repeats and we denote the set of the contexts of $V$ with
$C$. We call a relation $R\subset C\times V^{*}$ a context structure if it
satisfies the four conditions:

  1. 1.

$cRc$ for every $c\in C$.

  2. 2.

$cRv$ implies that all letters in $v$ are expressed in $c$.

  3. 3.

$cRv^{1}\cdots v^{n}$ and $v^{i}Rw^{i},$ for $v^{i},w^{i}\in V^{*}$ and $i\leq
n$, implies $cRw^{1}\cdots w^{n}$.

  4. 4.

If $cRv$, $s\colon\text{Var}(c)\rightarrow V^{*}$ and $dRs(c)$, then $dRs(v)$.
Here $s(v)=s(v_{1})\cdots s(v_{n})$ where $v=v_{1}\cdots v_{n}$ and
$v_{1},\ldots,v_{n}\in V$.

We call a word $v\in V^{*}$ an $R$-word if $cRv$ for some $c\in C$ and in such
case we say that $c$ is an $R$-context for $v$.

  * •

A context structure $R\subset C\times V^{*}$ on $V$ is said to be modelable if
$cRv^{1}\cdots v^{n}$ implies that there exists contexts $c^{1},\ldots,c^{n}$
where $cRc^{1}\cdots c^{n}$ and $c^{i}Rv^{i}$ for $i\leq n$.

  * •

A context structure $R$ is said to be balanced if $vRw$ implies that
$\text{Var}(v)=\text{Var}(w)$.

  * •

A balanced and modelable context structure is called balanced-complete.

There is a correspondence between structure categories $\Delta$ and context
structures $R$:

######  Theorem 3.4.

Let $V$ be an infinite set. Then the construction $R\mapsto\Delta_{R}$ defines
a bijection from context structures to structure categories, where
$\Delta_{R}$ consists of functions $\theta\colon[m]\rightarrow[n]$ where
$c_{1}\ldots c_{n}Rc_{\theta(1)}\cdots c_{\theta(m)}$ and $c=c_{1}\cdots
c_{n}$ is a context where $c_{1},\ldots,c_{n}\in V$.

###### Proof.

Fix a context structure $R$ on $V$ and fix an injection
$c\colon\mathbb{N}\rightarrow V$. Notice that $c^{n}\coloneqq c_{1}\cdots
c_{n}$ is a context for each $n\in\mathbb{N}$. We define a structure category
$\Delta_{R}$ to be the wide subcategory of FinOrd having the functions
$f\colon[m]\rightarrow[n]$, where $c^{n}Rc_{f}$, where $c_{f}\coloneqq
c_{f(1)}\cdots c_{f(m)}$. We will often use $d_{\theta}$ to denote
$d_{\theta(1)}\cdots d_{\theta(m)}$ where $d=d_{1}\cdots d_{n},d_{i}\in
V,i\leq n$ and $\theta\colon[m]\rightarrow[n]$.

We will show that $\Delta_{R}$ is a structure category. Since $c^{n}Rc^{n}$,
it follows that $id\colon[n]\rightarrow[n]$ is a morphism in $\Delta_{R}$ for
each $n\in\mathbb{N}$. Assume that $[k]\xrightarrow{f}[m]\xrightarrow{g}[n]$.
We need to show that $g\circ f\colon[k]\rightarrow[n]$ is a morphism in
$\Delta_{R}$. Now we have that $c^{m}Rc_{f}$ and $c^{n}Rc_{g}$. Consider the
renaming $s\colon c_{i}\mapsto c_{g(i)}$ for $i\leq m$. Notice that
$s(c^{m})=s(c_{1})\cdots s(c_{m})=c_{g}$. Since $c^{n}Rs(c^{m})=c_{g}$ and
$c^{m}Rc_{f}$, it follows that $c^{n}Rs(c_{f})=c_{g\circ f}$.

Now we show that $\Delta_{R}$ is closed under the coproduct of morphisms. Let
$f\colon[m_{i}]\rightarrow[n_{i}]$ be a morhpism in $\Delta_{R}$ for $i=1,2$.
We show that $c^{n_{1}+n_{2}}Rc_{f_{1}(1)}\cdots c_{n_{1}+f_{2}(m_{2})}$. By
definition of $f_{1}$ and $f_{2}$ being function in $\Delta_{R}$, we have that
$c^{n_{1}}Rc_{f_{1}}$ and $c^{n_{2}}Rc_{f_{2}}$. Consider
$c_{i}\xmapsto{s}c_{n_{1}+i}$ for $i\leq n_{2}$. Now
$s(c^{n_{2}})=c_{n_{1}+1}\cdots c_{n_{1}+n_{2}}Rc_{n_{1}+f_{2}(1)}\cdots
c_{n_{1}+f_{2}(m_{2})}=s(c_{f_{2}})$. Since $c^{n_{1}}Rc_{f_{1}}$ and
$c_{n_{1}+1}\cdots c_{n_{1}+n_{2}}Rc_{n_{1}+f_{2}(1)}\cdots
c_{n_{1}+f_{2}(m_{2})}$, we attain that $c^{n_{1}+n_{2}}Rc_{f_{1}(1)}\cdots
c_{n_{1}+f_{2}(m_{2})}=c_{f_{1}+f_{2}}.$

Next we show that $\Delta_{R}$ satisfies the similarity condition. Let
$\theta\colon[m]\rightarrow[n]$ be in $\Delta$. Let
$k_{1},\ldots,k_{n}\in\mathbb{N}$. We denote
$L_{i}=k_{\theta(1)}+\ldots+k_{\theta(i)}$ and $K_{j}=k_{1}+\cdots+k_{j}$ for
$i\leq m$ and $j\leq n$. We need to show that the map
$\theta^{\prime}_{k_{1},\ldots,k_{n}}=\theta^{\prime}\colon[L_{m}]\rightarrow[K_{n}]$
is a morphism in $\Delta$. By $c^{i,j}$ we mean the context $c_{i+1}\cdots
c_{j}$ for $i\leq j$. We show that $c^{K_{n}}Rc_{\theta^{\prime}}$. Let
$d_{i}=c^{K_{i-1},K_{i}}$ for $i\leq n$. Consider the mapping
$c_{i}\xmapsto{s}d_{i}$ for $i\leq n$. Now $c^{K_{n}}=d_{1}\cdots d_{n}$ and
so $c^{K_{n}}Rd_{\theta(1)}\cdots d_{\theta(m)}$. Notice that
$d_{\theta(1)}\cdots d_{\theta(m)}=c_{\theta^{\prime}}$. This is seen by the
fact that the the variable at position $L_{i-1}+j$ in $d_{\theta(1)}\cdots
d_{\theta(m)}$ is $c_{K_{\theta(i)-1}+j}=c_{\theta^{\prime}(L_{i-1}+j)}$ for
$0<j\leq k_{\theta(i)}$.

Conversely given a structure category $\Delta$, we set $(c,v)\in R_{\Delta}$,
if and only if $v=c_{\theta}$ for some $\theta\colon[l(v)]\rightarrow[l(c)]$.
Now we show that $R_{\Delta}$ is a context structure. The first two conditions
follow directly: Clearly $cRc$ for all contexts $c\in V^{*}$ and if $cRv$,
then $v=c_{f}=c_{f(1)}\cdots c_{f(l(v))}$ for some function $f$ and thus all
variables in $v$ are expressed in $c$.

Assume that $cRv_{1}\cdots v_{n}$ and $v_{i}Rw_{i}$ for $i\leq n$ with
$v_{i},w_{i}$ and $c$ having lengths $k_{i},l_{i},j\in\mathbb{N}$,
respectively for $i\leq m$. Thus we have functions
$g\colon[k_{1}+\ldots+k_{n}]\rightarrow[j]$ and
$f_{i}\colon[l_{i}]\rightarrow[k_{i}]$ for $i\leq n$ where $v_{1}\cdots
v_{n}=c_{g(1)}\cdots c_{g(k_{1}+\ldots+k_{n})}$ and
$w_{i}=v_{i,f_{i}(1)}\cdots v_{i,f_{i}(l_{i})}$. Thus we have
$g\circ(f_{1}+\ldots+f_{n})\colon[l_{1}+\ldots+l_{n}]\rightarrow[j]$ in
$\Delta$ and now $c_{g\circ(f_{1}+\ldots+f_{n})}=w_{1}\cdots w_{n}$.

Lastly, let $cRv$, $s\colon\text{Var}(c)\rightarrow V^{*}$ and assume that
$dRs(c)$. Thus $v=c_{\theta}$ and $s(v)=d_{\phi}$ for some
$\theta\colon[m]\rightarrow[n]$ and
$\phi\colon[k_{1}+\ldots+k_{n}]\rightarrow[l]$ where $m,n$ and $k_{i}$ are the
lengths of $v$, $c$ and $s(v_{i})$, respectively for $i\leq n$. We are to show
that $dRs(v)$. Notice that
$s(v)=d_{\phi\circ\theta^{\prime}_{k_{1},\ldots,k_{n}}}$ which shows that
$dRs(v)$.

These mappings $R\mapsto\Delta_{R}$ and $\Delta\mapsto R_{\Delta}$ are
inverses of each other which proves the claim. ∎

Since we have bijective correspondence between structure categories and
context structures on an infinite set, we are able to many examples of context
structures.

######  Example 3.5.

Let $V$ be an infinite set and let $x,y,z\in V$ be pairwise different elements
of $V$. Assume that $c$ is a context of $V$ and $v$ a word of $V$. Consider
the following context structures on $V$:

  1. 1.

Let $I$ be a structure monoid.

     * •

There is a context structure $R^{I}$, where $cRv$ if and only if each variable
$x$ in $v$ is in $c$ and expressed $n_{x}$ many times where $n_{x}\in I$. If
$0,3\in I$, then $xyzR^{I}zzzy$.

       * –

We call $R^{\\{0,1\\}}$ the injective context structure and notice that
$cR^{\\{0,1\\}}v$ if and only if each variable in $v$ is expressed at most
once in the context $c$: $xyzR^{\\{0,1\\}}xz$.

       * –

The context structure $R^{\mathbb{N}}$ is called the cartesian context
structure and $cR^{\mathbb{N}}v$ if and only if the variables in $v$ are
expressed in context $c$: $xyzR^{\mathbb{N}}yxyxx$.

       * –

The surjective context structure is defined to be $R^{\\{m\geq 1\\}}$ and
notice $cR^{\\{m\geq 1\\}}v$ if and only if all the variables in $v$ are
expressed in $c$: $xyzR^{\\{m\geq 1\\}}xyyzx$

       * –

The context structure $R^{\\{1\\}}$ is called the bijective context structure
and $cRv$ if and only if $c$ and $v$ are permutations of each other:
$xyzR^{\\{1\\}}yzx$.

     * •

We have a context structure $R_{I}$ which is generated by the condition
$xRx^{n}$ for $n\in I$. Each context structure $R$ satisfies $R_{I}\subset
R\subset R^{I}$ where $I$ is the set consisting $n\in\mathbb{N}$ where
$xRx^{n}$ for $x\in V$.

       * –

The context structures $R_{I}$ for $I=\\{0,1\\}$ and $\\{1\\}$ are called the
strictly increasing and trivial context structures.

     * •

Assume $0\not\in I$. The left surjections of $\Delta^{I}$ correspond to the
context structure $R$ called left surjective $I$-context structure, where
$cRv$ if $cR^{I}v$ and the first appearance of a variable $x$ in $v$ is before
the appearance of the variable $y$ in $v$, if the appearance of $x$ in $c$ is
earlier than the appearance of $y$ in $c$. Consider as an example $xyRxxyyyx$
if $3\in I$ for different $x,y\in V$. Similarly the right surjections of
$\Delta^{I}$ define the right surjective $I$-context structure (the last
appearance of $x$ is earlier than the last appearance of $y$ in $v$ if $x$
appears before $y$ in $c$).

     * •

The following eight context structures are modelable and later we will see
that there are no others.

       * –

Five are attained as follows: $R^{I},R_{I}$ for
$I=\\{0,1\\},\\{1\\},\mathbb{N}$, which corresponds to the injective, strictly
increasing, bijective, trivial and cartesian context structures.

       * –

We attain three more from the surjective context structure $R^{\\{m\geq 1\\}}$
and its substructures defined by left and right surjective context structures.

######  Definition 3.6.

Let $V$ be an infinite set with a context structure $R$. Let $v\in V^{*}$ be a
word. We call a context $c$ a terminal $R$-context of $v$ if $wRc$ is
equivalent with $wRv$ for all contexts $w\in V^{*}$. We will often denote
$c=\overline{v}$.

A context structure $R$ has two different terminal contexts for a word if and
only if $R=R^{I}$ for some structure monoid $I$. This is seen from the fact
that if $v$ has terminal contexts $c$ and $d$, then they are contexts for each
other and the corresponding structure category $\Delta_{R}$ contains a non-
identity bijection and hence $\Delta_{R}=\Delta^{I}$ for some structure monoid
$I$ by Lemma 2.5(3).

######  Theorem 3.7.

Let $V$ be an infinite set. Then there are exactly eight different modelable
context structures $R$ on $V$. Especially, all modelable context structures
$R$ have terminal contexts for all $R$-word.

###### Proof.

We have already seen eight different modelable context structures and each has
a terminal context for each word. We show that there are no others. Assume
that $R$ is a modelable context structure. Let $I$ be the set of
multiplicities of variables in $R$-words. If $0\in I$, then we know by Lemma
2.5(6), that $R$ is either the injective, strictly increasing or cartesian
context structure, all of which are modelable context structures. Assume then
that $0\not\in I$. If $I=\\{1\\}$, then $R$ is either the trivial or bijective
context structure by Lemma 2.5(3). Thus we may assume that $I\neq\\{1\\}$.
This implies that $n\in I$ for some $n>1$. Hence $xRxx^{n-1}$, which implies
that $xRxx$ by modelability of $R$ for some $x\in V$ and hence $2\in I$.
Therefore $I=\mathbb{N}_{1}$. Notice that the surjective context structure
$R^{I}$ is modelable; hence, we may assume that $R\neq R^{I}$.

We will show that $R$ is either the left or right surjective context
structure. Let $x,y\in V$ be different elements. Notice that $xRxx$ and hence
$xyRxyxy$ and thus $xyx$ is an $R$-word by the modelability of $R$. Thus
$xyRxyx$ or $yxRxyx$. We will show that the first case implies that $R$ is the
left surjective context structure and the latter case implies that $R$ is the
right surjective context structure. Since the latter case is similar, we may
assume that $xyRxyx$. Consider the set $S\subset\mathbb{N}$ consisting of
$n\in\mathbb{N}$, where each word $v$ of length at most $n$ holds that $wRv$
if and only if $\overline{v}=w$, where $\overline{v}$ is the left surjective
terminal context of $v$. Notice that $\overline{v}$ contains the variables of
$v$ with the latter repetitions of variables deleted. Since $R$ is balanced
and not the surjective context structure, it holds that each word has at most
a single $R$-context. Hence it suffices to show that $S=\mathbb{N}$. Clearly
$0\in S$. Assume that $n\in S$. We’ll show that $n+1\in S$.

Assume that $wRv$. We will show that $w=\overline{v}$. Now $v=av^{\prime}$ for
some $a\in V$ and $v^{\prime}\in V^{*}$. If $v^{\prime}$ is not a context,
then $wRac$ for some context $c$ and $cRv^{\prime}$ and thus
$w=\overline{ac}=\overline{av}=\overline{v}$. Hence we may assume that
$v^{\prime}$ is a context of the form $w^{\prime}aw^{\prime\prime}$ for some
$w^{\prime},w^{\prime\prime}\in V^{*}$. Now $wRaw^{\prime}aw^{\prime\prime}$
and thus $wRcw^{\prime\prime}$ for $cRaw^{\prime}a$. Since $xyRxyx$, it
follows that $aw^{\prime}Raw^{\prime}a$ and thus $c=aw^{\prime}$. Therefore
$wRaw^{\prime}w^{\prime\prime}$ and thus
$w=aw^{\prime}w^{\prime\prime}=\overline{aw^{\prime}aw^{\prime\prime}}=\overline{v}$.

Next we show that $\overline{v}Rv$. Let $x$ be the last variable expressed in
$\overline{v}$. Let $i$ be the index $x$ is expressed in $v$ for the first
time. Now $v=v_{1}xv_{2}$ where the length of $v_{1}$ is $i-1$. Therefore $x$
is not expressed in $v_{1}$. If $v_{1}$ is the empty word then $v=x^{n+1}$,
which is an $R$-word. Assume that $v_{1}$ is not empty. Now $v_{1}$ and
$xv_{2}$ are $R$-words by induction hypothesis. If either $v_{1}$ or $xv_{2}$
is not a context, then $\overline{v}=\overline{\overline{v_{1}}\text{
}\overline{xv_{2}}}$ is an $R$-context for $v$. Thus we may assume words
$v_{1}$ and $xv_{2}$ are contexts. We attain that $\overline{v}=v_{1}x$. Let
$y$ be the last variable expressed in $v_{1}$ and consider the function
$s\colon\text{Var}(v_{1})\rightarrow V^{*}$, where
$z\mapsto\begin{cases}z,\text{ if }z\not=y\\\ yx,\text{ if }z=y\end{cases}$.
By the induction hypothesis, $v_{1}Rv_{1}v_{2}$. Thus
$v_{1}x=s(v_{1})Rs(v_{1}v_{2})=v_{1}xs(v_{2})$ and thus
$v_{1}xRv_{1}\overline{xs(v_{2})}=v_{1}xv_{2}=v$. Therefore $\overline{v}Rv$.
∎

######  Corollary 3.8.

Let $R$ be a modelable context structure on an infinite set $V$. Denote by
$C_{v}$ the set of contexts of a word $v\in V^{*}$. Then $C_{v^{i}}\subset
C_{w^{i}}$ for $i\leq n$ implies that $C_{v^{1}\cdots v^{n}}\subset
C_{w^{1}\cdots w^{n}}$ for words $v_{i},w_{i}\in V^{*},i\leq n$. Furthermore,
$C_{v^{1}\cdots v^{n}}=C_{v^{\theta(1)}\cdots v^{\theta(m)}}$ for any
surjection $\theta\colon[m]\rightarrow[n]$ in $\Delta_{R}$ and $v^{i}\in
V^{*},i\leq n$.

###### Proof.

Assume that $C_{v^{i}}\subset C_{w^{i}}$ for $v^{i},w^{i}\in V^{*}$ and $i\leq
n$. We show that $C_{v^{1}\cdots v^{n}}\subset C_{w^{1}\ldots w^{n}}$. Let
$wRv^{1}\ldots v^{n}$. Since $R$ is modelable, we have that
$wR\overline{v^{1}}\cdots\overline{v^{n}}$ where $\overline{v^{i}}$ is an
$R$-context for $v^{i}$ for $i\leq n$. Since $\overline{v^{i}}\in C_{v^{i}}$
we have $\overline{v^{i}}\in C_{w^{i}}$ and so $\overline{v^{i}}Rw^{i}$. Since
$wR\overline{v^{1}}\cdots\overline{v^{n}}$ and $\overline{v^{i}}Rw^{i}$, it
follows that $wRw^{1}\ldots w^{n}$ and hence $w\in C_{w^{1}\cdots w^{n}}$.

Let $\theta\colon[m]\rightarrow[n]$ be a surjection in $\Delta_{R}$. Let
$v^{1},\ldots,v^{n}\in V^{*}$. We show that $C_{v^{1}\cdots
v^{n}}=C_{v^{\theta(1)}\cdots v^{\theta(m)}}$. If $R$ is the strictly
increasing, injective, trivial or bijective context structure, then the
equality is clear, since $\theta$ is either an identity or a bijection. Assume
then that $R$ is a balanced context structure. Thus each word of $V$ is an
$R$-word by Theorem 3.7. Notice that

$\overline{v^{1}\cdots v^{n}}=\overline{v^{\theta(1)}\cdots v^{\theta(m)}}$

and hence $C_{v^{1}\cdots v^{n}}=C_{\overline{v^{1}\cdots
v^{n}}}=C_{v^{\theta(1)}\cdots v^{\theta(m)}}$. ∎

######  Definition 3.9 (R–Theory).

Let $\sigma=(S,M,V)$ be a signature with $V$ having a context structure $R$.
We say that a context $c\in V^{*}$ is an $R$-context for a term $t$, if
$sR\tau(t)$. If $t_{1}$ and $t_{2}$ are $\sigma$-terms of type $s$ sharing a
context $v$, then $t_{1}\approx_{v}t_{2}$ is called an $R$-equation. A set of
$R$-equations is called an $R$-theory.

######  Definition 3.10 (Renaming & Substitution).

Let $\sigma=(S,M,V)$ be a signature with a context structure $R$. Let
$v=x_{1}\ldots x_{n}$ be a context. We say that a function $s\colon
Var(v)=\\{x_{1},\ldots,x_{n}\\}\rightarrow$ Term is a renaming of variables in
$v$, if $s$ preserves the types, i.e. $s(x)$ has the same type as $x$ for
$x\in Var(v)$. Let $s$ be a renaming of variables in $v$. We define
$\overline{s}\colon Term_{v}\rightarrow Term$, where

$\overline{s}(t)=\begin{cases}s(t),\text{ if $t\in Var(t)$}\\\ t,\text{ if $t$
is a constant symbol}\\\
f(\overline{s}(t_{1}),\ldots,\overline{s}(t_{n})),\text{ if
$t=f(t_{1},\ldots,t_{n})$}\end{cases},$

where the set Termv consists of those terms $t$, where $Var(t)\subset Var(v).$
We will denote $\overline{s}=s$.

Let $v=v_{1}\cdots v_{n}$ be a context. A triple $(s,(w_{i})_{i\leq n},w)$ is
called an $R$-renaming if $s$ is a renaming of variables in $v$ and the
contexts $w$ and $w_{i}$ are $R$-contexts for $w_{1}\cdots w_{n}$ and
$s(v_{i})$, respectively, for $i\leq n$.

######  Lemma 3.11.

Let $\sigma=(S,M,V)$ be a signature with a context structure $R$. Assume that
$t$ has an $R$-context $v=v_{1}\cdots v_{n}$, where $v_{i}\in V$ for $i\leq
n$. Assume that $(s,w,(w_{i})_{i})$ is an $R$-renaming of variables in $v$.
Then $w$ is an $R$-context for $s(t)$.

###### Proof.

By induction we see that
$\tau(s(t))=\tau(s(v_{\theta(1)}))\cdots\tau(s(v_{\theta(m)}))$ for the
$\theta\colon[m]\rightarrow[n]$ where $\tau(t)=v_{\theta(1)}\cdots
v_{\theta(m)}$. Since we have $wRw_{1}\cdots w_{n}$ and $w_{i}R\tau(s(v_{i}))$
for $i\leq n$, it follows by the third and fourth conditions of context
structures, respectively, that $wR\tau(s(v_{1}))\cdots\tau(s(v_{n}))$ and
$wR\tau(s(v_{\theta(1)}))\cdots\tau(s(v_{\theta(m)}))=\tau(s(t))$. ∎

######  Definition 3.12 (Syntactic deduction).

Let $\sigma$ be a signature with a context structure $R$. Let $E$ be an
$R$-theory. We define the set $D_{E}^{R}=D_{E}=D$ of $R$-deduced equations
from $E$ as the smallest set of $R$-equations satisfying the conditions:

  * •

$E\subset D$.

  * •

$t\approx_{v}t\in D$ for any term $t$ in $R$-context $v$.

  * •

If $t\approx_{v}t^{\prime}\in D$, then $t^{\prime}\approx_{v}t\in D_{E}$.

  * •

If $t_{1}\approx_{v}t_{2},t_{2}\approx_{v}t_{3}\in D$, then
$t_{1}\approx_{v}t_{3}\in D$.

  * •

Let $t_{1}\approx_{v}t_{2}\in D$, where $v=v_{1}\cdots v_{n}$. Let
$(s_{1},w,(w_{i})_{i\leq n})$ and $(s_{2},w,(w_{i})_{i\leq n})$ be
$R$-renamings of $v$ such that $s_{1}(v_{i})\approx_{w_{i}}s_{2}(v_{i})\in
D_{E}$ for $i\leq n$. Then $s_{1}(t_{1})\approx_{w}s_{2}(t_{2})\in D$.

We denote $E\vdash_{R}t_{1}\approx_{v}t_{2}$ if and only if
$t_{1}\approx_{v}t_{2}\in D$. We say that a context structure $R$ is
$\sigma$-deductively complete if for all $R,\sigma$-theories $E\cup\\{\phi\\}$
it holds that $E\vdash_{R}\phi$ if and only if $E\vdash_{\text{Cart}}\phi$,
where Cart is the maximal context structure.

###  3.2 Soundness

For a given signature $\sigma$ with a modelable context structure $R$, we
define models of $R$-theories in any given $\Delta_{R}$-multicategory. We show
that the deductions system $\vdash_{R}$ is sound and complete with respect to
all models in $\Delta_{R}$-multicategories. By soundness and completeness, we
mean the inclusions $D^{R}_{E}\subset\bigcap_{m}\text{True}(m)$ and
$\bigcap_{m}\text{True}(m)\subset D_{E}^{R}$, respectively, where the indexing
is over all $\sigma$-model $m$ in a $\Delta_{R}$-multicategory $C$. Here
$D^{R}_{E}$ means all the equations deduced from $E$ and $\text{True}(m)$ is
the set of all equations true in $m$. Later we see that completeness is
attained for all eight different cases for modelable $R$, but Set-completeness
is attained for balanced-complete $R$ and the cartesian context structures $R$
(six cases).

######  Definition 3.13 (Model).

Let $\sigma=(S,M,V)$ be a signature. Let $C$ be a multi-category. A
$\sigma$-model in $C$ is an association $m$, where

  * •

$m(s)$ is an object of $C$ for each sort $s\in S$. For $a=a_{1}\cdots a_{n}\in
S^{*}$, where $a_{i}\in S$ for $i\leq n$, we define $m(a)=m(a_{1})\cdots
m(a_{n}).$

  * •

$m(f)\colon m(a)\rightarrow m(b)$ is a multi-morphism in $C$ for each morphism
symbol $f\colon a\rightarrow b\in M$.

A morphism of models $m\rightarrow n$ consists of a family $f$ of functions
$f(s)\colon m(s)\rightarrow n(s)$ for each sort $s$ and where the diagram

${m(a)}$${m(b)}$${n(a)}$${n(b)}$$\scriptstyle{m(\alpha)}$$\scriptstyle{f(a)}$$\scriptstyle{f(b)}$$\scriptstyle{n(\alpha)}$

commutes for each morphism symbol $\alpha\colon a\rightarrow b$. Here we
understand the commutativity of the diagram to mean that $f(b)\circ
m(\alpha)=n(\alpha)\circ f(a)$, where $f(a)=(f(a_{1}),\ldots,f(a_{n}))$ for
$a=a_{1}\cdots a_{n}$ and $a_{i}\in S,i\leq n$.

######  Definition 3.14 (Canonical morphisms).

Let $\sigma=(S,M,V)$ be a signature with a context structure $R$. Let $m$ be a
$\sigma$-model in a $\Delta_{R}$–multicategory $C$. Let $v_{1},\ldots v_{n}\in
V$ and $w=v_{\theta(1)}\cdots v_{\theta(m)}$ for a function
$\theta\colon[m]\rightarrow[n]$ in $\Delta_{R}$. We set $m_{v}=m_{v_{1}}\cdots
m_{v_{n}}$ and $m_{v_{i}}=m(a_{i})$ for $v_{i}\colon a_{i}$ and $i\leq n$. We
define a function $m_{v,w,b}\colon C(m_{w},b)\rightarrow C(m_{v},b)$ as
$\theta^{*}_{m_{v},b}$. Instead of writing $m_{v,w,b}(f)$ for a multimorphism
$f\colon m_{w}\rightarrow b$ we use the notation $f*m_{v,w}\colon
m_{v}\rightarrow b$ for the sake of convenience. Even though the function
$m_{v,w}$ is not a morphism in $C$, it behaves very similarly to a canonical
morphism constructed from the natural transformations in a monoidal category
and so we choose to call $m_{v,w}$ a canonical morphism.

######  Lemma 3.15.

Let $m$ be a $\sigma$-model in a $\Delta_{R}$–multicategory $C$ where $R$ is a
context structure on the variables of $\sigma$. Then the following assertions
hold:

  1. 1.

Let $v$ be a context. Then $f*m_{v,v}=f$ for any $f\colon m_{v}\rightarrow b$
in $C$.

  2. 2.

Let $cRv$ and $vRw$. Then $(f*m_{v,w})*m_{c,v}=f*m_{c,w}$ for any $f\colon
m_{w}\rightarrow b$.

  3. 3.

Let $v_{i}Rw_{i}$ for $i\leq n$ and assume that $cRv_{1}\cdots v_{n}$. Let
$f_{i}\colon m_{w_{i}}\rightarrow b_{i}$ for $i\leq n$ and let $g\colon
b_{1}\cdots b_{n}\rightarrow c$ be multimorphisms in $C$. Then

$g\circ(f_{1}*m_{v_{1},w_{1}},\ldots,f_{n}*m_{v_{n},w_{n}})*m_{c,v_{1}\cdots
v_{n}}=(g\circ(f_{1},\ldots,f_{n}))*m_{c,w_{1}\cdots w_{n}}$

  4. 4.

Let $v_{1},\ldots,v_{n}\in V$ and $w,v^{1},\ldots,v^{n}\in V^{*}$ where $w$ is
of length $m$. Assume $v=v_{1}\cdots v_{n}$ is a context. Fix functions
$f\colon m_{v^{i}}\rightarrow m_{v_{i}}$ for $i\leq n$ and $g\colon
w\rightarrow b$. We assume $vRw$. Denote the function
$\theta\colon[m]\rightarrow[n]$ where $w=v_{\theta(1)}\cdots v_{\theta(m)}$.
Then

$(g\circ(f_{\theta(1)},\ldots,f_{\theta(m)}))*m_{c,v^{\theta(1)}\cdots
v^{\theta(m)}}=((g*m_{v,w})\circ(f_{1},\ldots,f_{n}))*m_{c,v^{1}\cdots v^{n}}$

###### Proof.

All parts follow directly from the corresponding axiom of $\Delta_{R}$-action.
So we will show only the last assertion: Denote the length of $v^{i}$ by
$k_{i}\in\mathbb{N}$. Now $m_{v,w}=\theta_{m_{v},*}$ and $m_{c,v^{1}\cdots
v^{n}}=\phi_{*}$ for some $\theta\colon[m]\rightarrow[n]$ and
$\phi\colon[k_{1}+\ldots+k_{n}]\rightarrow[l]$, where $m,n$ and $l$ are the
lengths of $w,v$ and $c$, respectively. Consider the following:

$\displaystyle(g*m_{v,w})\circ(f_{1},\ldots,f_{n})*m_{c,v^{1}\cdots v^{n}}$
$\displaystyle=\phi_{m_{c},*}(\theta_{m_{v},*}(g)\circ(f_{1},\ldots,f_{n}))$
$\displaystyle=\phi_{m_{c},*}((\theta^{\prime}_{k_{1},\ldots,k_{n}})_{v^{1}\cdots
v^{n},*}(g\circ(f_{\theta(1)},\ldots,f_{\theta(m)})))$
$\displaystyle=(\phi\circ\theta^{\prime}_{k_{1},\ldots,k_{n}})_{m_{c},*}(g\circ(f_{\theta(1)},\ldots,f_{\theta(m)}))$
$\displaystyle=g\circ(f_{\theta(1)},\ldots,f_{\theta(m))})*m_{c,v^{\theta(1)}\cdots
v^{\theta(m)}}.$

∎

######  Definition 3.16 (Satisfyiability).

Let $\sigma$ be a signature with a modelable context structure $R$. Let $m$ be
a $\sigma$-model in a $\Delta_{R}$–multicategory $C$. Let $t$ be a term with
an $R$-context $v$. We denote $m_{v}=m(s_{1})\cdots m(s_{n})$ where
$v=x_{1}\ldots x_{n}$ and $x_{i}\colon s_{i}$ for $i\leq n$. We are ready to
define the multi-morphism $m_{v}(t)\colon m_{v}\rightarrow m(b)$ for a term
$t\colon b$ with an $R$-context $v$:

$m_{v}(t)=\begin{cases}id_{b}*m_{v,v_{i}},\text{ if $t=v_{i}$},\\\
m(c)*m_{v,()},\text{ if $t$ is a constant symbol $c$},\\\
(m(f)\circ(m_{w_{1}}(t_{1}),\ldots,m_{w_{k}}(t_{k})))*m_{v,w_{1}\cdots
w_{k}},\text{ if }t=f(t_{1},\ldots,t_{k}),\end{cases}$

where $w_{i}$ is an $R$-context for $t_{i},i\leq n$ and $vRw_{1}\cdots w_{n}$.

The model $m$ is said to satisfy an $R$-equation $t_{1}\approx_{v}t_{2}$ if
$m_{v}(t_{1})=m_{v}(t_{2})$. This is denoted $m\vDash t_{1}\approx_{v}t_{2}$.
We say that $m$ satisfies $R$-theory $E$ if $m$ satisfies all the equations in
$E$ and we denote this by $m\vDash E$.

We defined $m_{v}(f(t_{1},\ldots,t_{n}))=m(f)(m_{w_{1}}(t_{1}),\cdots
m_{w_{n}}(t_{n}))*m_{v,w_{1}\cdots w_{n}}$ where $vRw_{1}\cdots w_{n}$ and
$w_{i}R\tau(t_{i}),i\leq n$. Notice that some contexts $w_{1},\ldots,w_{n}$
satisfying the conditions do exist, since $R$ is a modelable context
structure. Furthermore, this definition is independent of the choice of the
contexts, since we have assumed the existence of terminal contexts for
modelable context structures $R$. In the following lemma, we show the
independence in more detail:

######  Lemma 3.17.

Let $\sigma$ be a signature with a modelable context structure $R$. Let $m$
and be a $\sigma$-model in a $\Delta_{R}$-mulitcategory $C$. Then the
following holds

  1. 1.

Let $t\colon b$ be a term with $R$-contexts $v$ and $w$ where $vRw$. The
multimorphism $m_{v}(t)\colon m_{v}\rightarrow m(b)$ is well defined and
$m_{w}(t)*m_{v,w}=m_{v}(t).$

  2. 2.

Let $v,w$ be $R$-contexts for terms $t_{1}$ and $t_{2}$ and assume that $vRw$.
Then $m_{w}(t_{1})=m_{w}(t_{2})$ implies that $m_{v}(t_{1})=m_{v}(t_{2})$.

  3. 3.

Let $t\colon b$ be a term with an $R$-context $v$. Assume that
$(s,w,(w_{i})_{i\leq n})$ be an $R$-renaming of variables in $v$. Then

$m_{w}(s(t))=m_{v}(t)\circ(m_{w_{1}}(s(v_{1})),\ldots,m_{w_{n}}(s(v_{n})))*m_{w,w_{1}\ldots
w_{n}}$

where $w_{i}=\tau(s(v_{i}))$ for $i\leq n$

###### Proof.

  1. 1.

We can prove both claims simultaneously via induction: The claim clearly holds
for constant and variable terms $t$. Assume that $t=f(t_{1},\ldots,t_{n})$ and
the claim holds for $t_{i},i\leq n$. Let $p_{i}$ be an $R$-terminal context
for $t_{i}$ for $i\leq n$. Notice then that

$\displaystyle
m(f)\circ(m_{v_{1}}(t_{1}),\ldots,m_{v_{n}}(t_{n}))*m_{v,v_{1}\cdots v_{n}}$
$\displaystyle=m(f)\circ(m_{p_{1}}(t_{1})*m_{v_{1},p_{1}},\ldots,m_{p_{n}}(t_{n})*m_{v_{n},p_{n}})*m_{v,v_{1}\cdots
v_{n}}$
$\displaystyle=m(f)\circ(m_{p_{1}}(t_{1}),\cdots,m_{p_{n}}(t_{n}))*m_{v,p_{1}\ldots
p_{n}}$

Since the morphism $m_{v}(t)$ is independent of the choice of contexts
$v_{1},\ldots,v_{n}$, it follows that the morphism $m_{v}(t)$ is uniquely
defined. In the same induction, we notice that

$\displaystyle m_{w}(t)*m_{v,w}$
$\displaystyle=m(f)\circ(m_{p_{1}}(t_{1}),\ldots
m_{p_{n}}(t_{n}))*m_{w,p_{1}\cdots p_{n}})*m_{v,w}$
$\displaystyle=m(f)\circ(m_{p_{1}}(t_{1}),\ldots,m_{p_{n}}(t_{n}))*m_{v,p_{1}\cdots
p_{n}}$ $\displaystyle=m_{w}(t).$

  2. 2.

Assume that $m_{w}(t_{1})=m_{w}(t_{2})$. Now

$\displaystyle m_{v}(t_{1})$ $\displaystyle=m_{w}(t_{1})*m_{v,w}$
$\displaystyle=m_{w}(t_{2})*m_{v,w}$ $\displaystyle=m_{w}(t_{2}).$

  3. 3.

We will show by induction on the structure of $t$ that

$m_{w}(s(t))=m_{v}(t)\circ(m_{w_{1}}(s(v_{1})),\ldots,m_{w_{n}}(s(v_{n})))*m_{w,w_{1}\ldots
w_{n}}.$

If $t=c$ is a constant, then the left-hand side is $m_{w}(s(c))=m(c)*m_{w,()}$
and the right-hand side is

$\displaystyle m_{v}(c)\circ(m_{w_{1}}(s(v_{1})),\ldots,m_{w_{n}}(s(v_{n})))$
$\displaystyle=!_{(),b,*}(m(c))\circ(m_{w_{1}}(s(v_{1})),\ldots,m_{w_{n}}(s(v_{n})))$
$\displaystyle=!^{\prime}_{(),b,*}(m(c))$ $\displaystyle=m(c)*m_{w,()}$

Assume that $t=v_{i}$. The left-hand side becomes
$m_{w}(s(t))=m_{w}(s(v_{i}))$. Denote the function $1\mapsto
i\colon[1]\rightarrow[n]$ as $\phi$. Now the right-hand side is

$\displaystyle
m_{v}(v_{i})\circ(m_{w_{1}}(s(v_{1})),\ldots,m_{w_{n}}(s(v_{n})))*m_{w,w_{1}\cdots
w_{n}}$
$\displaystyle=(id*m_{v,v_{i}})\circ(m_{w_{1}}(s(v_{1})),\ldots,m_{w_{n}}(s(v_{n})))*m_{w,w_{1}\cdots
w_{n}}$ $\displaystyle=(id\circ m_{w_{i}}(s(v_{i})))*m_{w,w_{i}}$
$\displaystyle=m_{w}(s(v_{i})).$

Lastly, assume that $t=f(t_{1},\ldots,t_{k})$. Since $v$ is a context for $t$,
it follows from the assumption that $R$ is a modelable context structure that
$vRv^{1}\cdots v^{k}$ where $v^{i}=v^{i}_{1}\cdots
v^{i}_{\alpha_{i}},v^{i}_{\alpha_{i}}\in V,i\leq k$, is an $R$-terminal
context of $t_{i}$ for $i\leq k$. We notate $w^{i}_{j}=w_{j^{\prime}}$ for the
unique $j^{\prime}$ where $v^{i}_{j}=v_{j^{\prime}}$ for $i\leq k$ and
$j\leq\alpha_{i}$. Notice that since $vRv^{1}_{1}\cdots v^{k}_{\alpha_{k}}$
and $wRw_{1}\cdots w_{n}$, it follows that $wRw^{1}_{1}\cdots w^{k}_{m_{k}}$.
Thus there exists an $R$-terminal context $w^{i}$ for $w^{i}_{1}\cdots
w^{i}_{\alpha_{i}}$ for $i\leq k$ where $wRw^{1}\cdots w^{k}$. Thus
restrictions of $s$ define $R$-renamings of variables
$(s\mid,(w^{i}_{j})_{j\leq\alpha_{i}},w^{i})$ for variables in $v^{i}$. Thus
we may apply the induction hypothesis on terms $t_{i}$ for $i\leq n$. Now

$\displaystyle m_{w}(s(f(t_{1},\ldots,t_{k})))$
$\displaystyle=m_{w}(f(s(t_{1}),\ldots,s(t_{k})))$
$\displaystyle=m(f)\circ(m_{w^{1}}(s(t_{1})),\ldots,m_{w^{k}}(s(t_{k})))*m_{w,w^{1}\cdots
w^{k}}$
$\displaystyle=m(f)\circ(m_{v^{1}}(t_{1})\circ(m_{w^{1}_{1}}(s(v_{1}^{1})),\cdots,m_{w^{1}_{\alpha_{1}}}(s(v^{1}_{\alpha_{1}})))*m_{w^{1},w^{1}_{1}\cdots
w^{1}_{\alpha_{1}}},\ldots,$ $\displaystyle
m_{v^{k}}(t_{k})\circ(m_{w^{k}_{1}}(s(v^{k}_{1})),\ldots,m_{w^{k}_{\alpha_{k}}}(s(v_{\alpha_{k}}^{k})))*m_{w^{k},w^{k}_{1}\cdots
w^{k}_{\alpha_{k}}})*m_{w,w^{1}\cdots w^{k}}$
$\displaystyle=m(f)\circ(m_{v^{1}}(t_{1})\circ(m_{w^{1}_{1}}(s(v_{1}^{1})),\cdots,m_{w^{1}_{\alpha_{1}}}(s(v^{1}_{\alpha_{1}}))),\ldots,$
$\displaystyle
m_{v^{k}}(t_{k})\circ(m_{w^{k}_{1}}(s(v^{k}_{1})),\ldots,m_{w^{k}_{\alpha_{k}}}(s(v_{\alpha_{k}}^{k}))))*m_{w,w^{1}_{1}\cdots
w^{k}_{\alpha_{k}}}$
$\displaystyle=(m(f)\circ(m_{v^{1}}(t_{1}),\ldots,m_{v^{k}}(t_{k})))\circ(m_{w^{1}_{1}}(s(v_{1}^{1})),\ldots,m_{w^{k}_{\alpha_{k}}}(s(v_{\alpha_{k}}^{k})))*m_{w,w^{1}_{1}\ldots
w^{k}_{\alpha_{k}}}$
$\displaystyle=(m(f)\circ(m_{v^{1}}(t_{1}),\ldots,m_{v^{k}}(t_{k}))*m_{v,v^{1}\ldots
v^{k}})\circ(m_{w_{1}}(s(v_{1})),\ldots,m_{w_{n}}(s(v_{n})))*m_{w,w_{1}\cdots
w_{n}}$
$\displaystyle=m_{v}(t)\circ(m_{w_{1}}(s(v_{1})),\ldots,m_{w_{n}}(s(v_{n})))*m_{w,w_{1}\cdots
w_{n}}.$

The second to last equation follows from the Lemma 3.15 (4).

∎

######  Theorem 3.18 (Soundness).

Let $\sigma$ be a signature with a modelable context structure $R$. Consider
the associated structure category $\Delta=\Delta_{R}$. Let $E\cup\\{\phi\\}$
be an $R$-theory. If $E\vdash_{R}\phi$, then $E\vDash_{C}\phi$ for any
$\Delta$-multicategory $C$.

###### Proof.

Let $m\vDash E$ in a $\Delta$-multicategory $C$. Let $T$ be the set
$R$-equations $m$ satisfies. It needs to be shown that $D_{E}\subset T$. We
show this by induction. It is clear that $T$ contains $E$, and satisfies
reflexivity, symmetry and transitivity. We need to see that $T$ is closed
under $R$-substitution: Let $t_{1}\approx_{v}t_{2}\in T$, where $v=v_{1}\cdots
v_{n}$ and $v_{i}\in V$ for $i\leq n,$ and assume that
$(s_{1},w,(w_{i})_{i\leq n})$ and $(s_{2},w,(w_{i})_{i\leq n})$ are
$R$-renamings for $v$. Now by Lemma 3.17

$\displaystyle m_{w}(s_{1}(t_{1}))$
$\displaystyle=m_{v}(t_{1})\circ(m_{w_{1}}(s_{1}(v_{1})),\ldots,m_{w_{n}}(s_{1}(v_{n})))*m_{w,w_{1}\ldots
w_{n}}$
$\displaystyle=m_{v}(t_{2})\circ(m_{w_{1}}(s_{2}(v_{1})),\ldots,m_{w_{n}}(s_{2}(v_{n})))*m_{w,w_{1}\ldots
w_{n}}$ $\displaystyle=m_{w}(s_{2}(t_{2}))$

Thus $s_{1}(t_{1})\approx_{w}s_{2}(t_{2})\in T$. Therefore $D_{E}\subset T$. ∎

###  3.3 Completeness in Sets

We showed that for a given signature $\sigma$ with a modelable context
structure $R$ it holds for any $R$-theory $E$ that
$D^{R}_{E}\subset\text{True}(m)$ for all $m$ models in any
$\Delta_{R}$-multicategory $C$. We will show a strong version of the converse
that there is a single universal model $m$ for $E$ in a
$\Delta_{R}$-multicategory $C$ such that $\text{True}(m)=D^{R}_{E}$. However,
this universal model does not live in the cartesian multicategory of sets. In
this subsection, we are going to show that if $R$ is balanced-complete or the
cartesian context structure, then $D^{R}_{E}$ is exactly the intersection of
True(m) for all models $m$ in the cartesian multicategory of sets. This has
computationally an interesting corollary, that to show $E\vdash\phi$ it
suffices to find a balanced-complete $R$ such that $E\vdash_{R}\phi$.

######  Definition 3.19 (Term-Algebra).

Let $\sigma=(S,M,V)$ be a signature with a modelable context structure $R$.
Let $E$ be an $R$-theory. Denote by $C_{v}$ and $C_{t}$ the set of $R$-context
over a word $v\in V^{*}$ and a $\sigma$-term $t$, respectively. Assume the
first condition of balanced complete context structures for $R$: If
$C_{v_{i}}\subset C_{w_{i}}$ for $i\leq n$, then $C_{v_{1}\cdots v^{n}}\subset
C_{w_{1}\cdots w_{n}}$. We define four different term-algebras $n_{i},m_{i}$
for $i=1,2$ in the cartesian multicategory Set of sets:

  * •

Define $n_{1}(s)=\\{(v,t)\mid t\colon s\text{ is a $\sigma$\textendash term,
$v\in V^{*}$ and $C_{v}\subset C_{t}$}\\}$ and $n_{2}(s)=\\{t\mid t\colon
s\text{ is a $\sigma$\textendash term}\\}$ for a $\sigma$-sort $s$.

  * •

Let $f\colon a\rightarrow b\in M$, where $a=a_{1}\cdots a_{n}$ and $a_{i}\in
S$ for $i\leq n$. We set $n_{i}(f)\colon n_{i}(a)\rightarrow n_{i}(b)$

$n_{1}(f)((v_{1},t_{1}),\ldots,(v_{n},t_{n}))=(v_{1}\cdots
v_{n},f(t_{1},\ldots,t_{n}))\text{ and
}n_{2}(f)(t_{1},\ldots,t_{n})=f(t_{1},\ldots,t_{n})$

for $(v_{j},t_{j})\in n_{1}(a_{i}),j\leq n$ and $i=1,2$. The function
$n_{1}(f)$ is well-defined by the modelability of $R$.

  * •

Let $s\in S$. Set $m_{i}(s)=n_{i}(s)/\sim_{s}^{i}$, where $\sim_{s}^{i}$ is
called the provability relation on $n_{i}(s)$, where
$(v_{1},t_{1})\sim^{1}(v_{2},t_{2})$ if and only if $C_{v_{1}}=C_{v_{2}}$ and
$E\vdash_{R}t_{1}\approx_{w}t_{2}$ for all $w\in C_{v_{1}}$ and
$t_{1}\sim^{2}t_{2}$ if and only $E\vdash_{\text{Cart}}t_{1}\approx_{w}t_{2}$
for some context $w$ containing variables in $t_{1}$ and $t_{2}$.

  * •

We define $m_{i}(f)\colon m_{i}(a)\rightarrow m_{i}(b)$ as the unique function
making the diagram

${n_{i}(a)}$${n_{i}(b)}$${m_{i}(a)}$${m_{i}(b)}$$\scriptstyle{n_{i}(f)}$$\scriptstyle{q_{i}(a)}$$\scriptstyle{q_{i}(b)}$$\scriptstyle{m_{i}(f)}$

commute for a morphism symbol $f\colon a\rightarrow b$. Here we denote the
quotient map $n_{i}(s)\rightarrow m_{i}(s)$ as $q_{i}(s)$ for sorts $s$.

The term algebras $n_{1},n_{2},m_{1},m_{2}$ are called balanced $R$-term
algebra, $R$-term algebra, balanced $E$-term algebra and $E$-term algebra. The
modelability of $R$ guarantees that $m_{1}$ is well-defined.

######  Lemma 3.20.

Let $\sigma=(S,M,V)$ be a signature with a modelable context structure $R$.
Let $n_{1},n_{2}$ be the balanced $R$-term model and the $R$-term model,
respectively. Let $t$ be a term with a cartesian context $v=v_{1}\ldots
v_{n}$, where $v_{i}\in V$ for $i\leq n$. Consider the function
$\theta\colon[m]\rightarrow[n]$ where $\tau(t)=v_{\theta(1)}\cdots
v_{\theta(m)}$. Let $u=((v^{1},u_{1}),\ldots,(v^{n},u_{n}))\in n_{v}$. Denote
the renaming of variables $v_{i}\xmapsto{s}u_{i}$, for $i\leq n$ in $v$. Then

$n_{1,v}(t)(u)=(v^{\theta}\coloneqq v^{\theta(1)}\cdots
v^{\theta(m)},s(t))\text{ and }n_{2,v}(t)(u_{1},\ldots,u_{n})=s(t).$

###### Proof.

The case for $n_{2}$ is similar, so we prove only the case for $n_{1}=n$. We
prove the claim by induction on the structure of the term $t$. If $t=c$ is a
constant, then the right-hand side is $((),c)$. The left-hand side is

$n_{v}(c)(u)=((),c).$

Assume that $t=v_{i}$. The right-hand side is $(v^{i},u_{i})$. The left-hand
side is

$n_{v}(v_{i})((v_{1},u_{1}),\ldots,(v_{n},u_{n}))=(v^{i},u_{i})$

Assume then that $t=f(t_{1},\ldots,t_{k})$ and the claim holds for
$t_{1},\ldots,t_{k}$. Let $\theta_{i}\colon[m_{i}]\rightarrow[n]$ be the
unique function where $\tau(t_{i})=v^{\theta_{i}}$ for $i\leq k$. Notice that
$v^{\theta}=v^{\theta_{1}}\cdots v^{\theta_{k}}$. Now we attain

$\displaystyle n_{v}(t)(u)$
$\displaystyle=n(f)(n_{v}(t_{1})(u),\ldots,n_{v}(t_{k})(u))$
$\displaystyle=n(f)((v^{\theta_{1}},s(t)),\ldots,(v^{\theta_{k}},s(t_{k})))$
$\displaystyle=(v^{\theta_{1}}\cdots
v^{\theta_{k}},f(s(t_{1}),\ldots,s(t_{k})))$
$\displaystyle=(v^{\theta},s(t)).$

∎

######  Lemma 3.21 (Term-naturality).

Let $\sigma$ be a signature with a modelable context structure $R$ and let
$f\colon m\rightarrow n$ be a $\sigma$-model morphism in a
$\Delta_{R}$-multicategory $C$. Let $t\colon b$ be a term with an $R$-context
$v$. Then

${m_{v}}$${m(b)}$${n_{v}}$${n(b)}$$\scriptstyle{m_{v}(t)}$$\scriptstyle{f^{v}}$$\scriptstyle{f(b)}$$\scriptstyle{n_{v}(t)}$

commutes.

###### Proof.

If $t=c$ is a constant, then

$\displaystyle f(b)\circ m_{v}(c)$ $\displaystyle=f(b)\circ(m(c)*m_{v,()})$
$\displaystyle=(f(b)\circ m(c))*m_{v,()}$ $\displaystyle=n(c)*m_{v,()}$
$\displaystyle=(n(c)*n_{v,()})\circ f^{v}$ $\displaystyle=n_{v}(c)\circ f^{v}$

If $t=v_{i}$ is a variable symbol, then denote
$1\xmapsto{\phi}i\colon[1]\rightarrow[n]$ and now

$f(b)\circ m_{v}(v_{i})=f(b)\circ\phi_{*}(id_{b})=\phi_{*}(f(b)\circ
id_{b})=\phi_{*}(f(b))$

and

$n_{v}(v_{i})\circ f^{v}=(\phi_{*}(id_{b}))\circ
f^{v}=(\phi^{\prime}_{1,\ldots,1})_{*}(id_{b}\circ f(b))=\phi_{*}(f(b)).$

Assume then that $t=\alpha(t_{1},\ldots,t_{k})$ and the induction hypothesis
holds for $t_{1}\colon a_{1},\ldots,t_{k}\colon a_{k}$. Let $v^{i}$ be an
$R$-terminal context for $t_{i}$ for $i\leq k$. Now

$\displaystyle f(b)\circ m_{v}(\alpha(t_{1},\ldots,t_{k}))$
$\displaystyle=f(b)\circ m_{v,v^{1}\cdots
v^{n}}(m(\alpha)\circ(m_{v^{1}}(t_{1}),\ldots,m_{v^{k}}(t_{n})))$
$\displaystyle=m_{v,v^{1}\cdots v^{k}}(f(b)\circ
m(\alpha)\circ(m_{v^{1}}(t_{1}),\ldots,m_{v_{k}}(t_{k})))$
$\displaystyle=m_{v,v^{1}\cdots v^{k}}(n(\alpha)\circ(f(a_{1})\circ
m_{v^{1}}(t_{1}),\ldots,f(a_{k})\circ m_{v_{k}}(t_{k})))$
$\displaystyle=m_{v,v^{1}\cdots v^{k}}(n(\alpha)\circ(n_{v^{1}}(t_{1})\circ
f^{v^{1}},\ldots,n_{v^{k}}(t_{k})f^{v^{k}}))$ $\displaystyle=m_{v,v^{1}\cdots
v^{k}}((n(\alpha)\circ(n_{v^{1}}(t_{1}),\cdots n_{v^{k}}(t_{k}))\circ
f^{v^{1}\cdots v^{k}})$ $\displaystyle=m_{v,v^{1}\cdots
v^{k}}(n(\alpha)\circ(n_{v^{1}}(t_{1}),\ldots,n_{v^{k}}(t_{k}))\circ
f^{v^{1}\ldots,v^{k}})$ $\displaystyle=n_{v,v^{1}\cdots
v^{k}}(n(\alpha)\circ(n_{v^{1}}(t_{1}),\ldots,n_{v^{k}}(t_{k})))\circ f^{v}$
$\displaystyle=n_{v}(t)\circ f^{v}.$

∎

######  Theorem 3.22.

Let $\sigma$ be a signature with a modelable context structure $R$. Let $E$ be
an $R$-theory. Denote by $C_{v}$ the set of contexts over a word $v\in V^{*}$.
Then the following holds:

  1. 1.

Let $n$ and $\sim$ be the balanced $R$-term algebra the balanced
$E$-provability relation on $n$, respectively. Denote by $m=n/\sim$ the
balanced $E$-term model. Let $t_{1}\approx_{v}t_{2}$ be an $R$-equation. Then
$m\vDash t_{1}\approx_{v}t_{2}$ if and only if
$E\vdash_{R}t_{1}\approx_{w}t_{2}$ for some $R$-terminal context $w$ for both
$t_{1}$ and $t_{2}$.

  2. 2.

Let $n$ and $\sim$ be the $R$-term algebra and the $E$-provability relation on
$n$, respectively. Let $m$ be the $E$-term model. Let $t_{1}\approx_{v}t_{2}$
be a $\sigma$–equation. Then $m\vDash t_{1}\approx_{v}t_{2}$ if and only if
$t_{1}\sim t_{2}$.

###### Proof.

  1. 1.

Assume first $m_{v}(t_{1})=m_{v}(t_{2})$ for the forwards direction. Now by
Lemmas 3.20 and 3.21

$\displaystyle[(\tau(t_{1}),t_{1})]$
$\displaystyle=[n_{v}(t_{1})((v_{1},v_{1}),\ldots,(v_{n},v_{n}))]$
$\displaystyle=m_{v}(t_{1})([v_{1},v_{1}],\ldots,[v_{n},v_{n}])$
$\displaystyle=m_{v}(t_{2})([v_{1},v_{1}],\ldots,[v_{n},v_{n}])$
$\displaystyle=[n_{v}(t_{2})((v_{1},v_{1}),\ldots,(v_{n},v_{n})]$
$\displaystyle=[(\tau(t_{2}),t_{2})]$

Therefore, $C_{t_{1}}=C_{t_{2}}$ and $E\vdash_{R}t_{1}\approx_{w}t_{2}$ for
all $w\in C_{t_{1}}$. Since $C_{t_{1}}=C_{t_{2}}$ and $v\in C_{t_{1}}$, it
follows that $t_{1}$ and $t_{2}$ have the same variables appearing and hence
they have a common terminal context $w$ and therefore
$E\vdash_{R}t_{1}\approx_{w}t_{2}$.

For the converse, we may assume that $E\vdash_{R}t_{1}\approx_{v}t_{2}$ and
that $t_{1}\approx_{v}t_{2}$ is a balanced equation. Let
$((v^{1},u_{1}),\ldots,(v^{n},u_{n}))\in n_{v}$. Consider the function
$\theta_{i}$, where $\tau(t_{i})=v_{\theta_{i}}$ for $i=1,2$. We show that
$m_{v}(t_{1})([v^{1},u_{1}],\ldots,[v^{n},u_{n}])=m_{v}(t_{2})([v^{1},u_{1}],\ldots,[v^{n},u_{n}])$.
Let $s$ be the renaming $v_{i}\xmapsto{s}u_{i}$ for $i\leq n$. Notice that

$m_{v}(t_{i})([v^{1},u_{1}],\ldots,[v^{n},u_{n}])=[v^{\theta_{i}},s(t_{i})]=[v^{1}\cdots
v^{n},s(t_{i})],$

since $C_{v^{\theta_{i}}}=C_{v^{1}\cdots v^{n}}$ by the Corollary 3.8. Let
$wRv^{1}\cdots v^{n}$. Suffices to show that
$E\vdash_{R}s(t_{1})\approx_{w}s(t_{2})$. Since $R$ is modelable, there exists
contexts $c_{i}$ where $c_{i}Rv^{i}$ for $i\leq n$ and $wRc_{1}\cdots c_{n}$.
Thus $E\vdash_{R}s(v_{i})=u_{i}\approx_{c_{i}}u_{i}=s(v_{i})$ for $i\leq n$
and $E\vdash_{R}t_{1}\approx_{v}t_{2}$. Thus
$E\vdash_{R}s(t_{1})\approx_{w}s(t_{2})$ by the definition of $R$-deduction.
Hence $m_{v}(t_{1})=m_{v}(t_{2})$.

  2. 2.

The proof is similar to the previous part and hence omitted.

∎

######  Theorem 3.23 (Set-Completeness).

Let $\sigma=(S,M,V)$ be a signature with a modelable context structure $R$.
Let $E\cup\\{\phi\\}$ be an $R$-theory. Assume one of the following
assertions:

  1. 1.

The context structure $R$ is balanced, meaning that $cRv$ implies that
$\text{Var}(c)=\text{Var}(v)$.

  2. 2.

The context structure $R$ is the cartesian context structure.

Then

$E\vdash_{R}\phi\text{ if and only if }E\vDash_{\textbf{Set}}\phi$

###### Proof.

Soundness already gives us that $E\vdash_{R}\phi$ implies
$E\vDash_{\textbf{Set}}\phi$.

  1. 1.

Assume that $R$ is balanced-complete. Hence the equation $\phi$ is balanced
and the Theorem 3.22(1) implies the completeness.

  2. 2.

Assume that $R$ is the cartesian context structure and that $E\not\vdash\phi$.
Denote $\phi=t_{1}\approx_{v}t_{2}$. Consider a new signature
$\sigma^{\prime}=(S^{\prime},M^{\prime},V^{\prime})$ and a
$\sigma^{\prime}$-theory $E^{\prime}$, where

$\displaystyle S^{\prime}$ $\displaystyle=\\{s\in
S\mid\text{$\text{Var}(t)\subset\text{Var}(v)$ for some $\sigma$-term $t\colon
s$}\\},$ $\displaystyle M^{\prime}$ $\displaystyle=\\{f\colon a\rightarrow
b\in M\mid a\in S^{\prime*},b\in S\\},$ $\displaystyle V^{\prime}$
$\displaystyle=\\{v\in V\mid v\colon s\text{ for some $s\in
S^{\prime}$}\\}\text{ and }$ $\displaystyle E^{\prime}$
$\displaystyle=\\{t_{1}\approx_{w}t_{2}\in E\mid w\in V^{\prime*}\\}$

Notice that the codomain of a function symbol in $M^{\prime}$ is still in
$S^{\prime}$ which follows from how one constructs terms. Let
$m^{\prime}=m_{E^{\prime}}$ be the $E^{\prime}$-term model. We extend
$m^{\prime}$ to be a $\sigma$-model $m$ by setting

$m(s)=\begin{cases}m^{\prime}(s),\text{ if }s\in S^{\prime}\\\
\emptyset,\text{ if }s\not\in S^{\prime}\end{cases}\text{ and
}m(f)=\begin{cases}m^{\prime}(f)\colon m(a)\rightarrow m(b),\text{ if }f\in
M^{\prime}\\\ \emptyset\colon m(a)\rightarrow m(b),\text{ if }f\not\in
M^{\prime}\end{cases}$

Since $m_{v}(t)=m^{\prime}_{v}(t)$ for any $\sigma^{\prime}$ term $t$ in a
context $v\in V^{\prime*}$, it follows that $m\vDash\psi$ for $\psi\in
E^{\prime}$. The model $m$ satisfies the rest of the equations in $E$ by
vacuity, since $m_{v}$ is the empty set for any $v\in V\setminus V^{\prime}$.
Therefore $m\vDash E$. Assume towards a contradiction that $m\vDash
t_{1}\approx_{v}t_{2}$. Thus $m^{\prime}\vDash t_{1}\approx_{v}t_{2}$ and by
Theorem 3.22(2) $t_{1}\sim t_{2}$, where $\sim$ is the provability relation.
Thus $E^{\prime}\vdash t_{1}\approx_{w}t_{2}$ for some context $w\in
V^{\prime*}$ for $t_{1}$ and $t_{2}$. We define a renaming of variables in $w$
as follows

$x\xmapsto{s}\begin{cases}x,\text{ if }x\text{ is expressed in }v\\\
t_{x},\text{else},\end{cases}$

where $t_{x}$ is a term with the same type as $x$ and $t_{x}$ has its
variables expressed in $v$. Notice that $v$ is a context for
$\tau(s(w_{1}))\cdots\tau(s(w_{n}))$. Therefore, the substitution rule of
deduction yields $E\vdash t_{1}\approx_{v}t_{2}$, which is a contradiction.
Therefore, $m\not\vDash t_{1}\approx_{v}t_{2}$. ∎

######  Theorem 3.24 (Multi-Categorical Meta-Theorem).

Let $\sigma$ be a signature with a modelable context structure $R$. Assume
that $R$ is either balanced or the cartesian context structure. Consider the
associated structure category $\Delta$. Let $E\cup\\{\phi\\}$ be an
$R$-theory. Let $C$ be a $\Delta$-multicategory. Then

$E\vDash_{\textbf{Set}}\phi\text{ implies }E\vDash_{C}\phi.$

###### Proof.

If $E\vDash_{\textbf{Set}}\phi$, then by the Completeness Theorem 3.23
$E\vdash_{R}\phi$, and by the Soundness Theorem 3.18 $E\vDash_{C}\phi$. ∎

The Multicategorical Meta-Theorem applies for $\Delta$-multicategories, where
$\Delta$ is one of the following $6$ structures:

  1. 1.

$\Delta_{\\{1\\}}$ of identities.

  2. 2.

$\Delta^{\\{1\\}}$ of bijections.

  3. 3.

$\Delta_{\mathbb{N}}=\Delta^{\mathbb{N}}$ of all functions.

  4. 4.

$\Delta^{\mathbb{N}_{1}}$ of surjections.

  5. 5.

$\Psi_{N_{1}}$ of left surjections.

  6. 6.

$\Psi^{N_{1}}$ of right surjections.

The structure categories $\Delta_{\\{0,1\\}}$ and $\Delta^{\\{0,1\\}}$
corresponding to strictly increasing maps and injections are do not have an
associated completeness theorem concerning sets. Consider the signature
$\sigma=(S=\\{*\\},M=\\{f\colon**\rightarrow*\\})$ with a theory
$E=\\{f(x,y)\approx_{xyz}x)\\}$. Now $E\vdash f(x,y)\approx_{xy}x$, but
$E\not\vdash_{R}f(x,y)\approx_{xy}x$ where $R$ is either $R^{\\{0,1\\}}$ or
$R_{\\{0,1\\}}$. Let $D=\\{t_{1}\approx_{v}t_{2}\mid\text{if
$\text{Var}(t_{i})=\text{Var}(v)$ for either $i=1,2$, then $t_{1}=t_{2}$}\\}$
be a family of $R$-equations. The family $D$ satisfies the closure properties
of $R$-deduction and $E\subset D$ and thus $D_{E}^{R}\subset D$. Since
$f(x,y)\approx_{xy}x\not\in D$ it follows that
$E\not\vdash_{R}f(x,y)\approx_{xy}x$.

##  4 Categorical completeness

Consider a modelable context structure $R$. At the end of the previous
section, we saw that two of the eight modelable deduction systems $\vdash_{R}$
do not have complete semantics in sets. In this section, we remedy this
problem and show that $\vdash_{R}$ has complete semantics if we permit all the
models in all $\Delta_{R}$-multicategories, not just the ones in sets.

For each $R$-theory $E$, we construct the initial $\Delta_{R}$-multicategory
equipped with model $m\vDash E$. We show that for $m$ it holds that
$D_{E}^{R}=\text{True(m)}$. This result will be called categorical
completeness.

The following theorem is known and very useful as it allows to construct free
algebras.

######  Theorem 4.1.

Let $\sigma=(S,M,V)$ be a signature and let $E$ be a $\sigma$-theory. Then the
forgetful functor
$U\colon\text{Model}(\textbf{Set},E)\rightarrow\textbf{Set}^{S}$ has a left
adjoint.

###### Proof.

Let $A=(A_{s})_{s\in S}$ be a family of sets. We define the typed set
$A\text{-Term}\rightarrow S$ of $A$-terms as follows:

  * •

$a\colon s\in A\text{-Term}$ for $a\in A_{s}$.

  * •

$c:s\in A\text{-Term}$ for $c:s\in M$.

  * •

$f(t_{1},\ldots,t_{n})\colon b\in A\text{-Term}$ for $f\colon a_{0}\cdots
a_{n}\rightarrow b\in M$ and $t_{0}\colon a_{0},\ldots,t_{n}\colon a_{n}\in
A\text{-Term}$.

We define $A$-term model $n$ as follows:

  * •

Set $n(s)=\\{t\colon s\in A\text{-Term}\\}$.

  * •

For $f\colon a_{1}\cdots a_{n}\rightarrow b\in M$ we define

$n(f)\colon n(a_{1}\cdots a_{n})\rightarrow n(b),(t_{1},\ldots,t_{n})\mapsto
f(t_{1},\ldots,t_{n}).$

We define an $E$-model out of $n$ via a $\sigma$-congruence $\sim$ generated
by the pairs of elements $(n_{v}(t_{1})(x),n_{v}(t_{2})(x))$ for all $E\vdash
t_{1}\approx_{v}t_{2}$ and $x\in n_{v}$. As with the provability relation,
$n/\sim$ satisfies the equations in $E$. Furthermore, given any family of
functions $f=(A_{s}\rightarrow p_{s})_{s}$ where $p\vDash E$, $f$ extends
uniquely to a $\sigma$-morphism $\overline{f}\colon n\rightarrow p$. Since $p$
satisfies all the equations deduced from $E$, it follows that $\overline{f}$
extends uniquely along the quotient to a $\sigma$-morphism $m\rightarrow p$.
This proves the claim. ∎

Since left adjoints preserve initial objects, the initial $E$-model $m$
consists of the equivalence classes of pure $\sigma$-terms $t$, which are
$\sigma$-terms where no variable is expressed.

######  Definition 4.2 (Universal model).

Let $\sigma$ be a signature with a modelable context structure $R$. Consider
the signature extended signature $\Sigma$ of $\sigma$ and $R$, defined as
follows:

  * •

The set of $\Sigma$-sorts is $S^{\prime}=S^{*}\times S$.

  * •

For each $b,b_{1},\ldots,b_{n},c\in S,a,a^{1},\ldots,a^{n}\in S^{*},f\colon
a\rightarrow b\in M$ and $\theta\colon[m]\rightarrow[n]$ in $\Delta_{R}$, we
define $\Sigma$–morphism symbols

$\displaystyle\circ_{a^{1},\ldots,a^{n},b_{1},\ldots,b_{n},c}$
$\displaystyle\colon(b_{1}\cdots
b_{n},c)(a^{1},b_{1})\cdots(a^{n},b_{n})\rightarrow(a^{1}\cdots a^{n},c)$
$\displaystyle id_{c}$ $\displaystyle\colon(c,c)$
$\displaystyle\theta_{*,b,c}$ $\displaystyle\colon(b_{\theta(1)}\cdots
b_{\theta(m)},c)\rightarrow(b_{1}\cdots b_{n},c)$ $\displaystyle f$
$\displaystyle\colon(a,b).$

The symbols $\circ,id,\theta_{*,a,b}$ and $f\in M$ are called composition
symbols, identities symbols, $\Delta$-action symbols and the internalized
$\sigma$-symbols, respectively. We will often suppress the indices of the
function symbols. Consider the following theories:

  * •

We define a linear $\Sigma$-theory $\overline{\sigma}$ called the
categorization of $\sigma$ defined as follows:

$\displaystyle\circ(\circ(h,g_{1},\ldots,g_{n}),f^{1}_{1},\ldots,f^{n}_{m_{n}})$
$\displaystyle\approx_{hgf}\circ(h,\circ(g_{1},f^{1}_{1}\ldots
f^{1}_{m_{1}}),\ldots,\circ(g_{n},f^{n}_{1},\ldots,f^{n}_{m_{n}})),$
$\displaystyle\circ(id_{d},h)$ $\displaystyle\approx_{h}h,$
$\displaystyle\circ(h,id_{c_{1}},\ldots,id_{c_{n}})$
$\displaystyle\approx_{h}h,$ $\displaystyle(id_{[n]})_{*,c_{1}\cdots
c_{n},d}(h)$ $\displaystyle\approx_{h}h,$
$\displaystyle(\phi\theta)_{*}(h^{\prime})$
$\displaystyle\approx_{h^{\prime}}\phi_{*}(\theta_{*}(h^{\prime})),$
$\displaystyle\circ(\theta_{*}(h^{\prime}),g_{1},\ldots,g_{n})$
$\displaystyle\approx_{h^{\prime}g}(\theta^{\prime}_{m_{1},\ldots,m_{n}})_{*}(\circ(h^{\prime},g_{\theta(1)},\ldots,g_{\theta(m)})),$
$\displaystyle\circ(h,\theta^{1}_{*}(g_{1}^{\prime}),\ldots,\theta^{n}(g_{n}^{\prime}))$
$\displaystyle\approx_{hg^{\prime}}(\theta^{1}+\ldots+\theta^{n})_{*}(\circ(h,g^{\prime}_{1},\ldots,g^{\prime}_{n}))$

for pairwise different variable symbols

$f^{i}_{j}\colon(a^{i,j},b^{i}_{j}),g_{i}\colon(b^{i}_{1}\cdots
b^{i}_{m_{i}},c_{i}),g_{i}^{\prime}\colon(b^{i}_{\theta^{i}(1)},\ldots,b^{i}_{\theta^{i}(k_{i})},c_{i}),h\colon(c_{1}\ldots
c_{n},d),h^{\prime}\colon(c_{\theta(1)}\cdots c_{\theta(m)},d)$

for $a^{i,j}\in S^{*}$ and $b^{i}_{j},c_{i},d\in S$, where
$i,n,m_{i}\in\mathbb{N}$ and $i\leq n$ and $j\leq m_{i}$ and for functions
$\theta\colon[m]\rightarrow[n],\psi\colon[n]\rightarrow[p]$ and
$\theta^{i}\colon[k_{i}]\rightarrow[m_{i}],$ for $i\leq n$, in $\Delta_{R}$.
Here $hgf$, $h^{\prime}g$ and $hg^{\prime}$ denote the appropriate contexts.

  * •

Let $E$ be an $R$-theory. We define the $\Sigma$-theory $\widetilde{E}$ of
internalized $E$-theory as the set consisting of equations
$N_{v}(t_{1})\approx_{()}N_{v}(t_{2})$ for each $t_{1}\approx_{v}t_{2}\in E$.
Since $R$ is a modelable context structure, each word has a terminal context
by Theorem 3.7. Choose the terminal contexts $\overline{v}$ for each word $v$.
Let $v$ be a context for a term $t\colon b$ and $v=v_{1}\cdots v_{n}$ for
$v_{i}\colon a_{i}\in V,i\leq n$. We can define the pure $\Sigma$-term (has no
variables expressed) $N_{v}(t)\colon(a_{1}\cdots a_{n},b)$ as

$N_{v}(t)=\begin{cases}N_{v,(),b}(c),\text{ if $t=c$ is a constant}\\\
N_{v,v_{i},b}(id_{a_{i}}),\text{ if $t=v_{i}$ for some $i\leq n$}\\\
N_{v,\overline{\tau(t_{1})}\cdots\overline{\tau(t_{k})},b}(\circ(f,N_{\overline{\tau(t_{1})}}(t_{1}),\ldots
N_{\overline{\tau(t_{k})}}(t_{k}))),\text{ if
$t=f(t_{1},\ldots,t_{k})$}\end{cases}$

and $N_{v,w,b}$ is the function symbol $\theta_{*,v,b}$ where
$\theta\colon[m]\rightarrow[n]$ is the unique function in $\Delta_{R}$ where
$w=v_{\theta(1)}\cdots v_{\theta(m)}$. We call the theory
$\overline{E}=\overline{\sigma}\cup\widetilde{E}$ the multicategorical
$E$-theory.

An $\overline{E}$-model in Set corresponds to a $\Delta_{R}$-multicategory
with $S$ as the set of objects and it is equipped with a choice of an
$E$-model. Consider the initial $\overline{E}$–model $C$ in Set and denote by
$m$ the $E$-model in $C$.

######  Lemma 4.3.

Let $\sigma=(S,M,V)$ be a signature with a modelable context structure $R$.
Let $T\colon M\rightarrow N$ be a morphism of $\Delta_{R}$-multicategories.
Then $T$ induces a functor

$\overline{T}\colon Model(M,\sigma)\rightarrow Model(N,\sigma)$

from the $\sigma$-models in $M$ to those in $N$. Furthermore,
$T(m_{v}(t))=\overline{T}(m)_{v}(t)$ for any term $t$ in an $R$-context $v$.
Especially, if $m\vDash_{M}t_{1}\approx_{v}t_{2}$, then
$\overline{T}(m)\vDash_{N}t_{1}\approx_{v}t_{2}$, and in the case $T$ is
faithful, the converse holds.

###### Proof.

Let $m$ be a $\sigma$-model. We define $\overline{T}(m)_{s}=T(m_{s})$ for
$s\in S$ and $\overline{T}(m)(f)=T(m(a))\rightarrow T(m(b))$ for $f\colon
a\rightarrow b\in M$. We set $\overline{T}(\alpha)(s)=T(\alpha(s))\rightarrow
T(m(s))\rightarrow T(n(s))$ for a $\sigma$–morphism $\alpha\colon m\rightarrow
n$ in $M$. Clearly, $\overline{T}$ satisfies the functoriality laws. Let $t$
be a term in an $R$-context $v$. We show that
$T(m_{v}(t))=\overline{T}(m)_{v}(t)$. First notice that
$T(m_{v,w})=\overline{T}(m)_{v,w}$, since $T$ respects the $\Delta$–action on
the multicategories $M$ and $N$. Now

  * •

If $t=c$ is a constant, then
$T(m_{v}(c))=T(m_{v,()}(c))=\overline{T}(m)_{v,()}(c)=\overline{T}(m)_{v}(c))$.

  * •

If $t=v_{i}$ is a variable symbol, then
$T(m_{v}(v_{i}))=T(m_{v,v_{i}}(id))=\overline{T}(m)_{v,v_{i}}(id)=\overline{T}(m)_{v}(v_{i}).$

  * •

Assume that $t=f(t_{1},\ldots,t_{n})$. Denote by $v_{i}$ the terminal context
of $t_{i}$ for $i\leq n$. Now

$\displaystyle T(m_{v}(f(t_{1},\ldots,t_{n})))$
$\displaystyle=T(m_{v,v_{1}\cdots
v_{n}}((m(f)(m_{v_{1}}(t_{1}),\ldots,m_{v_{n}}(t_{n})))))$
$\displaystyle=\overline{T}(m)_{v,v_{1}\cdots
v_{n}}(\overline{T}(m)(f)(\overline{T}(m)_{v_{1}}(t_{1}),\ldots,\overline{T}(m)_{v_{n}}(t_{n}))$
$\displaystyle=\overline{T}(m)_{v}(f(t_{1},\ldots,t_{n}))$

Hence $T(m_{v}(t))=\overline{T}(m)_{v}(t)$. Now if $m$ satisfies an
$R$-equation $t_{1}\approx_{v}t_{2}$, then

$\overline{T}(m)_{v}(t_{1})=T(m_{v}(t_{1}))=T(m_{v}(t_{2}))=\overline{T}(m)_{v}(t_{2}).$

Thus $\overline{T}(m)$ satisfies the equation $t_{1}\approx_{v}t_{2}$.
Similarly with the converse, if $T$ is faithful. ∎

######  Theorem 4.4 (Completeness of the Universal Model).

Let $E$ be an $R,\sigma$-theory, where $R$ is a modelable context structure
and $\sigma=(S,M,V)$. Denote by $\Sigma$ the multicategorically extended
signature of $\sigma$. Let $\overline{\sigma}$ be the categorization theory of
$\sigma$. Let $\overline{E}$ be the multicategorical $E$-theory. Let $C$ be
the initial $\overline{E}$-model and denote by $m$ the $E$-model in $C$. Then
the following claims hold:

  1. 1.

The pair $(C,m)$ defines the initial object in the category of
$\Delta_{R}$–multicategories with a choice of an $E$-model.

  2. 2.

It holds that $E\vdash_{R}\phi$ if and only if $m\vDash\phi$ for any
$R$-equation $\phi$.

###### Proof.

  1. 1.

Let $n\vDash E$ be a model in $\Delta_{R}$-multicategory $D$. Consider the
full submulticategory $C$ of $D$ defined by objects $n_{s}$ for $s\in S$. The
pair $(C,n)$ defines exactly an $\overline{E}$-model. Since the
$\Sigma$-morphisms $C\rightarrow N$ correspond exactly with functors
$C\rightarrow N$ respecting the models $m$ and $n$, it follows that $(C,m)$
defines the initial $\Delta_{R}$-multicategory equipped with a model for $E$.

  2. 2.

The direct holds by soundness. We show the completeness. Notice that the
initial $\overline{E}$-model $C$ is the quotient of the pure $\Sigma$-terms
$A$ according the theory $\overline{E}=\widetilde{E}\cup\overline{\sigma}$.
One attains $C$ up to an isomorphism by first quotienting $A$ with the
congruence generated by $\overline{\sigma}$ and then quotienting by the
congruence generated by $\overline{E}$. Denote by $B$ the quotient of $A$
according to the theory $\overline{\sigma}$. Denote by $b$ the $\sigma$-model
in $B$. Consider the family of relations $\sim=(\sim_{s})_{s\in S}$, where

$\sim_{s}=\\{(b_{v}(t_{1}),b_{v}(t_{2}))\mid
E\vdash_{R}t_{1}\approx_{v}t_{2}\\}\text{ for $s\in S$}$

Notice that $C$ is isomorphic to $B$ quotiented by the congruence generated by
$\sim$. It suffices to show that $\sim$ is a $\Sigma$–congruence on $B$. Let
$n$ be the $\sigma$–term algebra. Thus there exists a functor $F\colon
B\rightarrow\textbf{Set}$ of multicategories mapping the model $b$ to $n$.
Thus for any constant $\Sigma$-term $T\colon(a,b)$, we attain a function
$\overline{T}=F(B_{()}(T))\colon n(a)\rightarrow n(b)$. Notice that by Lemmas
4.3 and 3.20,
$\overline{b_{v}(t)}(v_{1},\ldots,v_{n})=n_{v}(t)(v_{1},\ldots,v_{n})=t$ for
any context $v=v_{1}\cdots v_{n}$ for a $\sigma$-term $t$ where $v_{i}\in
V,i\leq n$. Let $T\colon(a_{1}\cdots a_{n},b)$ be a pure $\Sigma$-term. Let
$v=v_{1}\cdots v_{n}$ be a context where $v_{i}\colon a_{i}$ for $i\leq n$.
Let $t=\overline{T}(v_{1},\ldots,v_{n})$. By induction one sees that $v$ is an
$R$-context for $t$ and $b_{v}(t)=[T]$, where $[T]$ is the equivalence class
of $T$ in $B(a,b)$. Notice that $[b_{v}(t)]=[b_{v^{\prime}}(t^{\prime})]$ if
and only if $v$ and $v^{\prime}$ have the same length,
$v_{i}\xmapsto{s}v_{i}^{\prime},i\leq n$, is a renaming of variables $v$ and
$t^{\prime}=s(t)$. The converse is clear. The direct follows from the fact
that $n_{v}(t)=F(b_{v}(t))=F(b_{v^{\prime}}(t))=n_{v^{\prime}}(t)$ by Lemma
4.3. Now
$t^{\prime}=n_{v}(t^{\prime})(v_{1}^{\prime},\ldots,v_{n}^{\prime})=n_{v}(t)(v_{1}^{\prime},\ldots,v_{n}^{\prime})=s(t)$
by Lemma 3.20. Thus $t^{\prime}=s(t)$. Notice that if $v_{i}\colon a_{i},i\leq
n$ and $v=v_{1}\cdots v_{n}$ is a context and $T_{1},T_{2}\colon(a_{1}\cdots
a_{n},b)$ are pure $\Sigma$-terms, then $[T_{1}]\sim[T_{2}]$ is equivalent to
$E\vdash_{R}\overline{T_{1}}(v_{1},\ldots,v_{n})\approx_{v}\overline{T_{2}}(v_{1},\ldots,v_{n})$.
A direct verification then shows that $\sim$ is a $\Sigma$–congruence on $B$.

∎

##  5 Conclusion

We showed a bijective correspondence between context structures $R$ on an
infinite set $V$ and structure categories $\Delta$. Consider a multi-sorted
signature $\sigma=(S,M,V)$ with a context structure $R$. We developed
$R$-deduction for $R$-theories and showed that if $R$ is a modelable context
structure, then $E\vdash_{R}\phi$ if and only if $E\vDash_{C}\phi$ for all
$\Delta_{R}$-multicategories $C$. The structure categories $\Delta_{R}$
corresponding to modelable context structures are the following:

  1. 1.

$\Delta_{\\{0,1\\}}$ of strictly increasing maps.

  2. 2.

$\Delta^{\\{0,1\\}}$ of injections.

  3. 3.

$\Delta_{\\{1\\}}$ of identities.

  4. 4.

$\Delta^{\\{1\\}}$ of bijections.

  5. 5.

$\Delta_{\mathbb{N}}=\Delta^{\mathbb{N}}$ of all functions.

  6. 6.

$\Delta^{\mathbb{N}_{1}}$ of surjections.

  7. 7.

$\Psi_{N_{1}}$ of left surjections.

  8. 8.

$\Psi^{N_{1}}$ of right surjections.

For the latter six of the eight structure categories $\Delta$, we showed that
the cartesian multicategory of sets gives complete semantics for $R$-deduction
for $R=R_{\Delta}$ and showed a counter-example for the first two. In other
words, $E\vDash_{\textbf{Set}}\phi$ implies $E\vdash_{R}\phi$ for cartesian
context structure $R$ or a balanced and modelable $R$. This has an immediate
corollary called the Multicategorical Meta-Theorem:

$E\vDash_{\textbf{Set}}\phi\text{ implies }E\vDash_{M}\phi$

for all $\Delta_{R}$-multicategories $M$. This Multicategorical Meta-Theorem
allows the transportation of results from the cartesian multicategory of sets
to any other $\Delta_{R}$-multicategory.

There is another application of this work which is more proof-theoretic. If
$E\cup\\{\phi\\}$ is an $R$-theory, where $R$ is a balanced and modelable
context structure. Then $E\vdash_{R}\phi$ if and only $E\vdash\phi$. In other
words, one can potentially change the search space in the quest of finding a
proof for $\phi$ from $E$ without losing all proofs, given that a proof
exists. We also showed that for any modelable context structure $R$ and an
$R$-theory $E$, the theory $E$ can linearized in a certain sense. We may
construct multicategorical signature $\Sigma$ from $\sigma$ and $R$ and
construct a linear $\Sigma$-theory $\overline{E}$ that has the property that
$\overline{E}\vdash T_{1}\approx_{()}T_{2}$ if and only if
$E\vdash_{R}\overline{T_{1}}_{v}\approx_{v}\overline{T_{2}}_{v}$ for all pure
$\Sigma$–terms $T_{1},T_{2}$ having the same type.

## Acknowledgements

This research was supported by a grant from the Fonds de la Recherche
Scientifique - FNRS.

## References

  * [1] M. R. Gould.  Coherence for categorified operadic theories, 2010.
  * [2] F. W. Lawvere.  Functorial semantics of algebraic theories.  Proceedings of the National Academy of Sciences of the United States of America, 50(5):869–872, 1963.
  * [3] T. Leinster.  Higher Operads, Higher Categories.  London Mathematical Society Lecture Note Series. Cambridge University Press, 2004.