# Partial algebras and implications of (weak) matrix properties

Michael Hoefnagel  Mathematics Division, Department of Mathematical Sciences,
Stellenbosch University, Private Bag X1 Matieland 7602, South Africa Centre
for Experimental Mathematics, Department of Mathematical Sciences,
Stellenbosch University, Private Bag X1 Matieland 7602, South Africa National
Institute for Theoretical and Computational Sciences (NITheCS), South Africa
Pierre-Alain Jacqmin The second author is grateful to the FNRS for its
generous support. Institut de Recherche en Mathématique et Physique,
Université catholique de Louvain, Chemin du Cyclotron 2, B 1348 Louvain-la-
Neuve, Belgium Department of Mathematics, Royal Military Academy, Brussels,
Belgium Centre for Experimental Mathematics, Department of Mathematical
Sciences, Stellenbosch University, Private Bag X1 Matieland 7602, South Africa

###### Abstract

Matrix properties are a type of property of categories which includes the ones
of being Mal’tsev, arithmetical, majority, unital, strongly unital and
subtractive. Recently, an algorithm has been developed to determine
implications $\mathrm{M}\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{N}$ between
them. We show here that this algorithm reduces to construct a partial term
corresponding to $\mathrm{N}$ from a partial term corresponding to
$\mathrm{M}$. Moreover, we prove that this is further equivalent to the
corresponding implication between the weak versions of these properties, i.e.,
the one where only strong monomorphisms are considered instead of all
monomorphisms.

2020 Mathematics Subject Classification: 03B35, 18E13, 08A55, 08B05, 18-08,
18B15, 18A20.

Keywords: matrix property, proof reduction, (weakly) Mal’tsev category,
arithmetical category, majority category, (weakly) unital category.

## Introduction

A pointed variety $\mathbb{V}$ of universal algebras in said to be
_subtractive_ in the sense of [30] if its theory contains a binary term $x-y$
(called a _subtraction_) satisfying the equations

$\begin{cases}x-0=x\\\ x-x=0\end{cases}$ (1)

where $0$ is the unique constant in the theory of $\mathbb{V}$. From such a
term, one can construct a ternary term $p(x,y,z)$ satisfying the equations

$\begin{cases}p(x,x,x)=x\\\ p(x,x,0)=0\\\ p(0,x,x)=0\end{cases}$ (2)

by setting

$p(x,y,z)=x-(y-z).$

Indeed, one can check that

$\begin{cases}p(x,x,x)=x-(x-x)=x-0=x\\\ p(x,x,0)=x-(x-0)=x-x=0\\\
p(0,x,x)=0-(x-x)=0-0=0.\end{cases}$ (3)

In addition, from a subtraction $x-y$, one can also construct a $4$-ary term
$q(x,y,z,w)$ satisfying the equations

$\begin{cases}q(x,0,0,0)=x\\\ q(x,x,y,y)=0\\\ q(x,y,x,y)=0\end{cases}$ (4)

by setting

$q(x,y,z,w)=(x-y)-(z-w).$

To see this, it suffices to compute

$\begin{cases}q(x,0,0,0)=(x-0)-(0-0)=x-0=x\\\ q(x,x,y,y)=(x-x)-(y-y)=0-0=0\\\
q(x,y,x,y)=(x-y)-(x-y)=0.\end{cases}$ (5)

Although these two proofs look very similar, let us now explain a fundamental
difference between them which has deep consequences in Category Theory.

The first proof (the construction of the term $p(x,y,z)$ from the subtraction
$x-y$) can be extended to the context of partial algebras in the following
sense, while the second cannot. Let us consider a pointed set $(A,0)$ equipped
with a _partial subtraction_ , i.e., a partial function $-\colon
A^{2}\dashrightarrow A$ such that the existential equations

$\begin{cases}x-0=^{\mathrm{e}}x\\\ x-x=^{\mathrm{e}}0\end{cases}$

hold, meaning that, for every $a\in A$, both $a-0$ and $a-a$ are defined and
they are equal to $a-0=a$ and $a-a=0$ respectively. For such a _partial
subtractive algebra_ $A$, one can construct the ternary partial operation
$p\colon A^{3}\dashrightarrow A$ by setting $p(x,y,z)=x-(y-z)$ for $x,y,z\in
A$ for which $y-z$ and $x-(y-z)$ are defined (and $p(x,y,z)$ is not defined
for the other triples $(x,y,z)\in A^{3}$). This partial operation satisfies
the existential equations

$\begin{cases}p(x,x,x)=^{\mathrm{e}}x\\\ p(x,x,0)=^{\mathrm{e}}0\\\
p(0,x,x)=^{\mathrm{e}}0\end{cases}$

which can be seen using a proof completely analogous to the one in (3), with
the extra care of checking that every expression which appears is indeed
defined.

For the second proof (i.e., the construction of $q(x,y,z,w)$ from the
subtraction $x-y$), this is no longer the case. One can still define the
$4$-ary partial operation $q\colon A^{4}\dashrightarrow A$ by setting
$q(x,y,z,w)=(x-y)-(z-w)$ exactly for those $x,y,z,w\in A$ for which $x-y$,
$z-w$ and $(x-y)-(z-w)$ are defined, but now the existential equation

$q(x,y,x,y)=^{\mathrm{e}}0$

can no longer be shown to hold in $A$ analogously as in (5) since $x-y$ is in
general not defined for all $x,y\in A$.

Let us now explain the consequences that this difference implies in Category
Theory. Let us first see how the algebraic condition that a pointed variety of
universal algebras has a subtraction in its theory extends to the context of a
finitely complete pointed category. The first thing one can think of is to
require that any object $X$ is naturally equipped with an internal subtraction
$s\colon X^{2}\to X$ satisfying the internal version of the axioms $s(x,0)=x$
and $s(x,x)=0$. However, this is in general too strong of a condition; even
the category of _subtractive algebras_ (i.e., pointed sets equipped with a
subtraction $-$) does not have such an internal operation since $-\colon
A^{2}\to A$ is not a homomorphism in general. The ‘right’ approach has been
proposed in [21] and generalized in [22] to all Mal’tsev conditions of a
similar form to those appearing in (1), (2) and (4). The idea is, instead of
looking at the equations (1) line by line, to look at them ‘components by
components’. In other words, if we write the equations (1) in the form of an
(extended) matrix

$\mathrm{Sub}=\left[\begin{array}[]{cc|c}x&0&x\\\ x&x&0\end{array}\right],$

the columns of this matrix give a condition on the relations in a pointed
variety $\mathbb{V}$. Indeed, writing elements of $A^{2}$ as column vectors,
the ‘matrix condition’ corresponding to $\mathrm{Sub}$ requires that, for any
homomorphic binary relation $R\subseteq A^{2}$ in $\mathbb{V}$, we have

$\left\\{\left[\begin{array}[]{c}a\\\
a\end{array}\right],\,\left[\begin{array}[]{c}0\\\
a\end{array}\right]\right\\}\subseteq
R\quad\implies\quad\left[\begin{array}[]{c}a\\\ 0\end{array}\right]\in R$

for every $a\in A$. Using generalized elements, this condition can be extended
to the context of finitely complete pointed categories. Such a category for
which each binary relation satisfies this condition is called a _subtractive
category_ [21]. Using a similar technique introduced in [22], we can extend
the conditions of having a ternary term $p$ satisfying the equations (2) and
of having a $4$-ary term $q$ satisfying the equations (4) from the pointed
varietal context to the finitely complete pointed context using the matrices

$\mathrm{P}=\left[\begin{array}[]{ccc|c}x&x&x&x\\\ x&x&0&0\\\
0&x&x&0\end{array}\right]$

and

$\mathrm{Q}=\left[\begin{array}[]{cccc|c}x&0&0&0&x\\\ x&x&y&y&0\\\
x&y&x&y&0\end{array}\right]$

respectively. The fact that one can construct a partial term $p$ satisfying
the equations (2) from a partial subtraction is equivalent to the fact that
each subtractive category satisfies the property corresponding to the matrix
$P$, which we denote by
$\mathrm{Sub}\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{P}$. This equivalence is
part of our main Theorem 2.3. In addition, still according to this theorem,
this implication is also equivalent to the implication where the weak versions
of these properties are involved, that is, the properties only requiring that
the strong relations satisfy the matrix properties. Strong relations (or in
general strong monomorphisms) are those which are orthogonal to epimorphisms.
We denote this implication by
$\mathrm{Sub}\Rightarrow_{\mathrm{lex}_{\ast}}^{\mathrm{strong}}\mathrm{P}$,
meaning that any _weakly subtractive category_ has strong $\mathrm{P}$-closed
relations (i.e., has weakly the property corresponding to $\mathrm{P}$).

Besides, as we noted above, the proof that any subtractive variety admits in
its theory a $4$-ary term $q$ satisfying the equations (4) cannot be extended
to the partial algebraic context. We can actually show that, even using
another construction, it is not possible to construct a partial term $q$
satisfying the equations (4) existentially from a partial subtraction. In view
of our Theorem 2.3, this thus means that the implications
$\mathrm{Sub}\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{Q}$ and
$\mathrm{Sub}\Rightarrow_{\mathrm{lex}_{\ast}}^{\mathrm{strong}}\mathrm{Q}$ do
_not_ hold.

The proof of Theorem 2.3 relies on two main ingredients. On one hand, we make
use of the embedding theorem from [19] in which each finitely complete pointed
category satisfying the weak property corresponding to an extended matrix
$\mathrm{M}$ as above is fully faithfully embedded in a power of the category
of partial algebras determined by $\mathrm{M}$. On the other hand, we use the
algorithms developed in [13, 16] to decide whether an implication
$\mathrm{M}\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{N}$ holds for extended
matrices $\mathrm{M}$ and $\mathrm{N}$ as above. Using a computer
implementation of these algorithms, it has been shown in [13] that the
implication $\mathrm{Sub}\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{Q}$ does
indeed _not_ hold (see Figure 8 in that paper), proving in view of our Theorem
2.3 that a partial $4$-ary term $q$ satisfying the equations (4) existentially
cannot be constructed from a partial subtraction.

As classical examples of properties induced by matrices, let us mention the
ones of being _subtractive_ [21], _unital_ [6] and _strongly unital_ [6].
Since our results are also formulated in the non-pointed context, let us also
mention the properties of being _Mal’tsev_ [8, 9], _majority_ [12] and
_arithmetical_ [28, 16]. Among their weak versions, the ones of being _weakly
Mal’tsev_ [26, 27] and _weakly unital_ [26] have already been studied.

The rest of the paper is divided in two sections. In the first one, we
essentially recall the needed concepts and results from the literature. Among
others, we remind the reader with the matrix properties and the algorithms
from [13, 16] to decide implications between them. We also briefly recall the
theory of partial algebras and the embedding theorem established in [19]. In
the second section, we first extend the characterizations found in the
literature of _trivial matrices_ (i.e., those inducing properties that can be
satisfied only by preorders) using the language of partial algebras (Theorem
2.1). We then come to our main theorem (Theorem 2.3) characterizing when a
matrix property (or rather a set of matrix properties) implies another one. As
explained above, we prove that the implication
$\mathrm{M}\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{N}$ is equivalent to
$\mathrm{M}\Rightarrow_{\mathrm{lex}_{\ast}}^{\mathrm{strong}}\mathrm{N}$ and
also to the condition that one can construct a partial term corresponding to
$\mathrm{N}$ from one corresponding to $\mathrm{M}$. A similar
characterization is also established in the non-pointed context. As a
corollary (Corollary 2.7), we also give a characterization of _anti-trivial
matrices_ , i.e., those inducing a property satisfied by any finitely complete
pointed category. Let us finally mention that in all these characterizations,
we also consider the property on a finitely complete (pointed) category
induced by a matrix $\mathrm{M}$ in which only relations in a specified class
of monomorphisms $\mathcal{M}$ are required to be $\mathrm{M}$-closed. This
class $\mathcal{M}$ is asked to be stable under pullbacks, closed under
composition and containing the regular monomorphisms.

##  1 Preliminaries

### Matrix properties

Given integers $n>0$ and $m,k\geqslant 0$, we denote as in [13] by
$\mathrm{matr}_{\ast}(n,m,k)$ the set of (extended) matrices

$\mathrm{M}=\left[\begin{array}[]{ccc|c}x_{11}&\dots&x_{1m}&x_{1\,m+1}\\\
\vdots&&\vdots&\vdots\\\ x_{n1}&\dots&x_{nm}&x_{n\,m+1}\end{array}\right]$

with $n$ rows, $m$ left columns, one right column and whose entries lie in the
set $\\{\ast,x_{1},\dots,x_{k}\\}$ (i.e., the free pointed set on $k$
variables $x_{1},\dots,x_{k}$). Each such matrix
$\mathrm{M}\in\mathrm{matr}_{\ast}(n,m,k)$ determines a property on $n$-ary
(internal) relations $r\colon R\rightarrowtail X_{1}\times\cdots\times X_{n}$
in finitely complete pointed categories $\mathbb{C}$. Such a relation is given
by a subobject of the $n$-fold product $X_{1}\times\cdots\times X_{n}$ and is
represented by a monomorphism $r$. To describe the property determined by
$\mathrm{M}$ on such relations, we need the concept of row-wise
interpretations. Given pointed sets $(S_{1},\ast_{1}),\dots,(S_{n},\ast_{n})$,
a _row-wise interpretation_ of $\mathrm{M}$ of type
$((S_{1},\ast_{1}),\dots,(S_{n},\ast_{n}))$ is an extended matrix

$\left[\begin{array}[]{ccc|c}f_{1}(x_{11})&\dots&f_{1}(x_{1m})&f_{1}(x_{1\,m+1})\\\
\vdots&&\vdots&\vdots\\\
f_{n}(x_{n1})&\dots&f_{n}(x_{nm})&f_{n}(x_{n\,m+1})\end{array}\right]$

whose entries are obtained by applying to the elements of the
$i^{\textrm{th}}$ row of $\mathrm{M}$ (for each $i\in\\{1,\dots,n\\}$) a
_pointed function_
$f_{i}\colon(\\{\ast,x_{1},\dots,x_{k}\\},\ast)\to(S_{i},\ast_{i})$, i.e., a
function $f_{i}\colon\\{\ast,x_{1},\dots,x_{k}\\}\to S_{i}$ such that
$f_{i}(\ast)=\ast_{i}$. Viewing each hom-set $\mathbb{C}(X,Y)$ of a finitely
complete pointed category $\mathbb{C}$ as a pointed set where the
distinguished element is the zero morphism $0\colon X\to Y$, we say that an
$n$-ary relation $r\colon R\rightarrowtail X_{1}\times\cdots\times X_{n}$ in
$\mathbb{C}$ is _strictly $\mathrm{M}$-closed_ [22] if, for any object $Z$ of
$\mathbb{C}$, each row-wise interpretation

$\left[\begin{array}[]{ccc|c}g_{11}&\dots&g_{1m}&h_{1}\\\
\vdots&&\vdots&\vdots\\\ g_{n1}&\dots&g_{nm}&h_{n}\end{array}\right]$

of $\mathrm{M}$ of type $(\mathbb{C}(Z,X_{1}),\dots,\mathbb{C}(Z,X_{n}))$ is
_compatible_ with $r$, i.e., if, for each $j\in\\{1,\dots,m\\}$, the morphism
$(g_{1j},\dots,g_{nj})\colon Z\to X_{1}\times\cdots\times X_{n}$ induced by
the $j^{\textrm{th}}$ left column factors through $r$, then the morphism
$(h_{1},\dots,h_{n})\colon Z\to X_{1}\times\cdots\times X_{n}$ induced by the
right column also factors through $r$.

For a pointed set $(S,\ast)$, a (non-row-wise) _interpretation_ of
$\mathrm{M}$ of type $(S,\ast)$ is a row-wise interpretation of $\mathrm{M}$
of type $((S,\ast),\dots,(S,\ast))$ for which $f_{1}=\dots=f_{n}$. We say that
a relation $r\colon R\rightarrowtail X^{n}$ in $\mathbb{C}$ is _$\mathrm{M}$
-closed_ [22] if, for any object $Z$ of $\mathbb{C}$, each interpretation of
$\mathrm{M}$ of type $\mathbb{C}(Z,X)$ is compatible with $r$.

We denote by $\mathrm{matr}(n,m,k)$ the subset of _non-pointed matrices_ of
$\mathrm{matr}_{\ast}(n,m,k)$, i.e., those matrices not containing $\ast$ as
an entry. For a non-pointed matrix $\mathrm{M}\in\mathrm{matr}(n,m,k)$, we
define analogously as above the concepts of row-wise interpretations of
$\mathrm{M}$ of type $(S_{1},\dots,S_{n})$ and interpretations of $\mathrm{M}$
of type $S$ where $S_{1},\dots,S_{n},S$ are mere sets. This gives rise to the
concepts of _strictly $\mathrm{M}$-closed relations_ $r\colon R\rightarrowtail
X_{1}\times\cdots\times X_{n}$ and of _$\mathrm{M}$ -closed relations_
$r\colon R\rightarrowtail X^{n}$ in a (non necessarily pointed) finitely
complete category $\mathbb{C}$. We also denote by $\mathrm{matr}$ and
$\mathrm{matr}_{\ast}$ the unions

$\mathrm{matr}=\bigcup_{\begin{subarray}{c}n>0\\\ m\geqslant 0\\\ k\geqslant
0\end{subarray}}\mathrm{matr}(n,m,k)\qquad\text{and}\qquad\mathrm{matr}_{\ast}=\bigcup_{\begin{subarray}{c}n>0\\\
m\geqslant 0\\\ k\geqslant 0\end{subarray}}\mathrm{matr}_{\ast}(n,m,k).$

Given a class of monomorphisms $\mathcal{M}$ stable under pullbacks in a
finitely complete category $\mathbb{C}$ (respectively in a finitely complete
pointed category $\mathbb{C}$) and a matrix
$\mathrm{M}\in\mathrm{matr}(n,m,k)$ (respectively
$\mathrm{M}\in\mathrm{matr}_{\ast}(n,m,k)$), we say that $\mathbb{C}$ _has
$\mathrm{M}$-closed $\mathcal{M}$-relations_ if any relation $r\colon
R\rightarrowtail X^{n}$ in $\mathcal{M}$ is $\mathrm{M}$-closed (since
$\mathcal{M}$ is stable under pullbacks, it is in particular closed under pre-
composition with isomorphisms and therefore, a relation is said to be in
$\mathcal{M}$ if one (thus all) representing monomorphism of the relation is
in $\mathcal{M}$). Using (the internal version of) Proposition 1.9 in [22], we
immediately get the following proposition, which slightly generalizes Theorem
2.4 of that paper.

######  Proposition 1.1.

Let $n>0$ and $m,k\geqslant 0$ be integers,
$\mathrm{M}\in\mathrm{matr}(n,m,k)$ (respectively
$\mathrm{M}\in\mathrm{matr}_{\ast}(n,m,k)$), $\mathbb{C}$ a finitely complete
category (respectively a finitely complete pointed category) and $\mathcal{M}$
a class of monomorphisms in $\mathbb{C}$ stable under pullbacks. Then the
following statement are equivalent:

  * •

$\mathbb{C}$ has $\mathrm{M}$-closed $\mathcal{M}$-relations, i.e., any
relation $r\colon R\rightarrowtail X^{n}$ in $\mathcal{M}$ is
$\mathrm{M}$-closed;

  * •

$\mathbb{C}$ has strictly $\mathrm{M}$-closed $\mathcal{M}$-relations, i.e.,
any relation $r\colon R\rightarrowtail X_{1}\times\cdots\times X_{n}$ in
$\mathcal{M}$ is strictly $\mathrm{M}$-closed.

If one takes $\mathcal{M}$ to be the class $\mathcal{M}_{\mathrm{all}}$ of all
monomorphisms, one gets back the notion of (pointed) finitely complete
categories with $\mathrm{M}$-closed relations introduced in [22] and
extensively studied in [13, 14, 15, 16, 17, 23]. Before giving some examples,
let us recall the characterization of (finitary one-sorted) varieties of
universal algebras with $\mathrm{M}$-closed relations. We first remind the
reader that a variety $\mathbb{V}$ is a pointed category if and only if it has
a nullary term $0$ and any two nullary terms are equal in its theory. Note
that, although the notion of $\mathrm{M}$-closed relations is defined via the
columns of $\mathrm{M}$, the characterization of varieties with
$\mathrm{M}$-closed relations reads each row of the matrix as an equation.

######  Theorem 1.2.

[22] Let $n>0$ and $m,k\geqslant 0$ be integers and

$\mathrm{M}=\left[\begin{array}[]{ccc|c}x_{11}&\dots&x_{1m}&x_{1\,m+1}\\\
\vdots&&\vdots&\vdots\\\ x_{n1}&\dots&x_{nm}&x_{n\,m+1}\end{array}\right]$

be a matrix in $\mathrm{matr}(n,m,k)$ (respectively in
$\mathrm{matr}_{\ast}(n,m,k)$), whose entries thus lie in
$\\{x_{1},\dots,x_{k}\\}$ (respectively in $\\{\ast,x_{1},\dots,x_{k}\\}$). A
variety $\mathbb{V}$ (respectively a pointed variety $\mathbb{V}$) has
$\mathrm{M}$-closed ($\mathcal{M}_{\mathrm{all}}$-)relations if and only if
its theory contains an $m$-ary term $p$ such that, for each
$i\in\\{1,\dots,n\\}$, the equation

$p(x_{i1},\dots,x_{im})=x_{i\,m+1}$

holds in $\mathbb{V}$ (where $x_{1},\dots,x_{k}$ are interpreted as different
variables and, in the pointed case, $\ast$ is interpreted as the unique
constant of $\mathbb{V}$).

### Examples

We first focus on examples where $\mathcal{M}=\mathcal{M}_{\mathrm{all}}$. For
the matrix

$\mathrm{Mal}=\left[\begin{array}[]{ccc|c}x_{1}&x_{2}&x_{2}&x_{1}\\\
x_{2}&x_{2}&x_{1}&x_{1}\end{array}\right]$

in $\mathrm{matr}(2,3,2)$, a finitely complete category with
$\mathrm{Mal}$-closed ($\mathcal{M}_{\mathrm{all}}$-)relations is a _Mal’tsev
category_ [9], generalizing the notions of regular Mal’tsev categories [8] and
of Mal’tsev varieties [25] to the left exact context. Making explicit the
definition for this matrix, it turns out that a finitely complete category is
a Mal’tsev category (i.e., has $\mathrm{Mal}$-closed relations) if and only
if, for any binary relation $r\colon R\rightarrowtail X^{2}$ and any pair of
morphisms $z_{1},z_{2}\colon Z\to X$, if the three induced morphisms
$(z_{1},z_{2})$, $(z_{2},z_{2})$ and $(z_{2},z_{1})\colon Z\to X^{2}$ factor
through $r$, so does the morphism $(z_{1},z_{1})\colon Z\to X^{2}$. Using
Proposition 1.1, this is equivalent to the condition that any binary relation
$r\colon R\rightarrowtail X_{1}\times X_{2}$ is _difunctional_ [29], i.e.,
given morphisms $z_{1},z_{2}\colon Z\to X_{1}$ and
$z^{\prime}_{1},z^{\prime}_{2}\colon Z\to X_{2}$ such that the morphisms
$(z_{1},z^{\prime}_{2})$, $(z_{2},z^{\prime}_{2})$ and
$(z_{2},z^{\prime}_{1})\colon Z\to X_{1}\times X_{2}$ factor through $r$, so
does the morphism $(z_{1},z^{\prime}_{1})\colon Z\to X_{1}\times X_{2}$. In
this case, Theorem 1.2 gives back Mal’tsev’s theorem [25], i.e., that a
variety $\mathbb{V}$ of universal algebras is a Mal’tsev category if and only
if there exists a ternary term $p(x,y,z)$ in the theory of $\mathbb{V}$ such
that the identities

$\begin{cases}p(x_{1},x_{2},x_{2})=x_{1}\\\
p(x_{2},x_{2},x_{1})=x_{1}\end{cases}$

hold in $\mathbb{V}$.

If we denote by $\mathrm{Maj}$ the matrix

$\mathrm{Maj}=\left[\begin{array}[]{ccc|c}x_{1}&x_{1}&x_{2}&x_{1}\\\
x_{1}&x_{2}&x_{1}&x_{1}\\\ x_{2}&x_{1}&x_{1}&x_{1}\end{array}\right]$

in $\mathrm{matr}(3,3,2)$, we get the notion of _majority categories_ as
introduced in [12], i.e., finitely complete categories with
$\mathrm{Maj}$-closed relations. A category which is both a majority category
and a Mal’tsev category is called an _arithmetical category_ in [16],
extending the terminology of [28]. These are finitely complete categories with
$\mathrm{Ari}$-closed relations, where $\mathrm{Ari}\in\mathrm{matr}(3,3,2)$
is the matrix

$\mathrm{Ari}=\left[\begin{array}[]{ccc|c}x_{1}&x_{2}&x_{2}&x_{1}\\\
x_{2}&x_{2}&x_{1}&x_{1}\\\ x_{1}&x_{2}&x_{1}&x_{1}\end{array}\right].$

In the pointed context, we consider the matrices

$\mathrm{Uni}=\left[\begin{array}[]{cc|c}x_{1}&\ast&x_{1}\\\
\ast&x_{1}&x_{1}\end{array}\right]$

in $\mathrm{matr}_{\ast}(2,2,1)$ and

$\mathrm{StrUni}=\left[\begin{array}[]{ccc|c}x_{1}&\ast&\ast&x_{1}\\\
x_{2}&x_{2}&x_{1}&x_{1}\end{array}\right]$

in $\mathrm{matr}_{\ast}(2,3,2)$. A finitely complete pointed category with
$\mathrm{Uni}$-closed relations (respectively with $\mathrm{StrUni}$-closed
relations) is a _unital category_ (respectively a _strongly unital category_),
both notions being introduced in [6]. One can also consider the matrix

$\mathrm{Sub}=\left[\begin{array}[]{cc|c}x_{1}&\ast&x_{1}\\\
x_{1}&x_{1}&\ast\end{array}\right]$

in $\mathrm{matr}_{\ast}(2,2,1)$. _Subtractive categories_ (i.e., finitely
complete pointed categories with $\mathrm{Sub}$-closed relations) have been
introduced in [21] where it is shown that a unital subtractive category is
nothing else than a strongly unital category. In order to again illustrate the
definitions of categories with $\mathrm{M}$-closed relations, let us make
explicit the definition of subtractive categories here. A finitely complete
pointed category is subtractive if and only if, for each binary relation
$r\colon R\rightarrowtail X^{2}$ and each morphism $z\colon Z\to X$, if the
two induced morphisms $(z,z)$ and $(0,z)\colon Z\to X^{2}$ factor through $r$,
so does the morphism $(z,0)\colon Z\to X^{2}$. Using Proposition 1.1, this is
equivalent to the condition that for each binary relation $r\colon
R\rightarrowtail X_{1}\times X_{2}$ and every morphisms $z\colon Z\to X_{1}$
and $z^{\prime}\colon Z\to X_{2}$, if the morphisms $(z,z^{\prime})$ and
$(0,z^{\prime})\colon Z\to X_{1}\times X_{2}$ factor through $r$, so does the
morphism $(z,0)\colon Z\to X_{1}\times X_{2}$. In this case, Theorem 1.2 gives
us that a pointed variety $\mathbb{V}$ is a subtractive category if and only
if it is a subtractive variety in the sense of [30], i.e., that its theory
contains a binary term $s(x,y)$ such that the identities

$\begin{cases}s(x,0)=x\\\ s(x,x)=0\end{cases}$

hold in its theory (where $0$ is the unique constant of $\mathbb{V}$).

Another class of monomorphisms $\mathcal{M}$ in a category $\mathbb{C}$ of
interest for this paper is the class $\mathcal{M}_{\mathrm{strong}}$ of
_strong monomorphisms_ , i.e., those monomorphisms $m\colon X\rightarrowtail
Y$ which are orthogonal to every epimorphism, meaning that for each
commutative square made of plain arrows

$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{e}$$\scriptstyle{f}$$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\scriptstyle{d}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{m}$$\textstyle{Y}$

where the top morphism $e\colon A\twoheadrightarrow B$ is an epimorphism,
there is a (unique) dotted diagonal morphism $d\colon B\to X$ retaining the
commutativity of the diagram. This class $\mathcal{M}_{\mathrm{strong}}$ of
strong monomorphisms is stable under pullbacks. As it will be of importance
later, let us also mention that it is closed under composition and that it
contains _regular monomorphisms_ , i.e., equalizers. Categories with
$\mathrm{M}$-closed $\mathcal{M}$-relations have already been considered for
$\mathcal{M}=\mathcal{M}_{\mathrm{strong}}$ and a general $\mathrm{M}$ in [19]
(and implicitly, even for a general $\mathcal{M}$).

_Weakly Mal’tsev categories_ have been introduced in [26, 27] and
characterized in [24]. In the finitely complete context and using the
terminology of the present paper, they can be described as finitely complete
categories with $\mathrm{Mal}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations. They thus form a natural weakening
of the notion of Mal’tsev categories. We can also see this weakening as
follows. From [6], we know that a finitely complete category $\mathbb{C}$ is a
Mal’tsev category if and only if, for all pullbacks

$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p_{Y}}$$\scriptstyle{p_{X}}$$\textstyle{Y\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\scriptstyle{r_{Y}}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{l_{X}}$$\textstyle{Z\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{s}$$\scriptstyle{t}$

of split epimorphisms where $fs=1_{Z}=gt$, the induced morphisms
$l_{X}=(1_{X},tf)$ and $r_{Y}=(sg,1_{Y})$ are _jointly strongly epimorphic_ ,
i.e., they do not factorize though a common proper subobject of $P$. Besides,
a finitely complete category is weakly Mal’tsev if and only if for all such
pullbacks, the morphisms $l_{X}$ and $r_{Y}$ are _jointly epimorphic_ , i.e.,
for any pair of morphisms $u,v\colon P\to W$ such that $ul_{X}=vl_{X}$ and
$ur_{Y}=vr_{Y}$ one has $u=v$. The characterization of varieties which form
weakly Mal’tsev categories also gives rise to a Mal’tsev condition but more
complicated than in the case $\mathcal{M}=\mathcal{M}_{\mathrm{all}}$. It has
recently been obtained in [10].

_Weakly unital categories_ have been introduced in [26] as (finitely complete)
pointed categories such that, for any two objects $X,Y$, the induced morphisms
$(1_{X},0)\colon X\rightarrowtail X\times Y$ and $(0,1_{Y})\colon
Y\rightarrowtail X\times Y$ are jointly epimorphic.

$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(1_{X},0)}$$\textstyle{X\times
Y\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p_{Y}}$$\scriptstyle{p_{X}}$$\textstyle{Y\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(0,1_{Y})}$

In [19], they have been characterized as finitely complete pointed categories
with $\mathrm{Uni}$-closed $\mathcal{M}_{\mathrm{strong}}$-relations. For the
comparison, let us mention that unital categories can be described [6] as
finitely complete pointed categories such that, for each pair of objects
$X,Y$, the morphisms $(1_{X},0)$ and $(0,1_{Y})$ are jointly strongly
epimorphic.

In view of the above two examples, categories with $\mathrm{M}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations were also called _categories weakly
with $\mathrm{M}$-closed relations_ in [19].

To conclude this tour of examples, let us mention that, denoting the class of
regular monomorphisms in a category by $\mathcal{M}_{\mathrm{reg}}$, finitely
complete categories with $\mathrm{Mal}$-closed
$\mathcal{M}_{\mathrm{reg}}$-relations are considered in [10]. The class
$\mathcal{M}_{\mathrm{reg}}$ is stable under pullbacks, but in general it
fails to be closed under composition.

### The algorithm for deciding implications of matrix properties

As in [13, 16], we call a _matrix set_ a subset of $\mathrm{matr}_{\ast}$. A
matrix set $S$ is said to be _non-pointed_ if $S\subseteq\mathrm{matr}$. Given
a matrix set $S\subseteq\mathrm{matr}$ (respectively
$S\subseteq\mathrm{matr}_{\ast}$), a finitely complete category $\mathbb{C}$
(respectively a finitely complete pointed category $\mathbb{C}$) and a class
$\mathcal{M}$ of monomorphisms in $\mathbb{C}$ stable under pullbacks, we say
that $\mathbb{C}$ _has $S$-closed $\mathcal{M}$-relations_ if $\mathbb{C}$ has
$\mathrm{M}$-closed $\mathcal{M}$-relations for all $\mathrm{M}$ in $S$.

Extending the notation established in [14], given a non-pointed matrix set
$S\subseteq\mathrm{matr}$ and a matrix $\mathrm{N}\in\mathrm{matr}$, we write
$S\Rightarrow_{\mathrm{lex}}^{\mathrm{all}}\mathrm{N}$, or simply
$S\Rightarrow_{\mathrm{lex}}\mathrm{N}$, if any finitely complete category
with $S$-closed relations has also $\mathrm{N}$-closed relations. The
abbreviation ‘$\mathrm{lex}$’ here stands for ‘left exact’, another name for
‘finitely complete’. Similarly, we write
$S\Rightarrow_{\mathrm{lex}}^{\mathrm{strong}}\mathrm{N}$ to mean that any
finitely complete category with $S$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations has also $\mathrm{N}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations. In the pointed case, i.e., given
$S\subseteq\mathrm{matr}_{\ast}$ and $\mathrm{N}\in\mathrm{matr}_{\ast}$, we
write $S\Rightarrow_{\mathrm{lex}_{\ast}}^{\mathrm{all}}\mathrm{N}$, or simply
$S\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{N}$, to mean that any finitely
complete pointed category with $S$-closed relations has also
$\mathrm{N}$-closed relations. Finally, we write
$S\Rightarrow_{\mathrm{lex}_{\ast}}^{\mathrm{strong}}\mathrm{N}$ if any
finitely complete pointed category with $S$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations has also $\mathrm{N}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations. In all these abbreviations, if
$S=\\{\mathrm{M}\\}$ is a singleton, we sometimes write $\mathrm{M}$ instead
of $\\{\mathrm{M}\\}$, e.g., $\mathrm{M}\Rightarrow_{\mathrm{lex}}\mathrm{N}$
instead of $\\{\mathrm{M}\\}\Rightarrow_{\mathrm{lex}}\mathrm{N}$.

In [16], an algorithm was presented to decide whether
$S\Rightarrow_{\mathrm{lex}}\mathrm{N}$ for a non-pointed matrix set
$S\subseteq\mathrm{matr}$ and a matrix $\mathrm{N}\in\mathrm{matr}$. In [13],
this algorithm was adapted to the pointed context to decide whether
$S\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{N}$ for a matrix set
$S\subseteq\mathrm{matr}_{\ast}$ and a matrix
$\mathrm{N}\in\mathrm{matr}_{\ast}$. Note that, in the original papers [13,
16], it was required that $S$ is finite to be able to implement these
algorithms on a computer. Since this will not be our concern in the present
paper, we can omit this assumption here. Actually, from the results of [13,
16], we can deduce the following (which can also be deduced from the
algorithms recalled below since the number of columns that one can possibly
add to $\mathrm{N}$ is finite).

######  Proposition 1.3.

Given $S\subseteq\mathrm{matr}$ and $\mathrm{N}\in\mathrm{matr}$, one has
$S\Rightarrow_{\mathrm{lex}}\mathrm{N}$ if and only if there is a finite
subset $S^{\prime}\subseteq S$ such that
$S^{\prime}\Rightarrow_{\mathrm{lex}}\mathrm{N}$. Analogously, given
$S\subseteq\mathrm{matr}_{\ast}$ and $\mathrm{N}\in\mathrm{matr}_{\ast}$, one
has $S\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{N}$ if and only if there is a
finite subset $S^{\prime}\subseteq S$ such that
$S^{\prime}\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{N}$.

As they will be needed, let us now recall these algorithms. In each case, the
first step of the algorithm is to deal with trivial matrices. A matrix
$\mathrm{M}\in\mathrm{matr}$ is said to be _trivial_ [16] if every finitely
complete category with $\mathrm{M}$-closed
($\mathcal{M}_{\mathrm{all}}$-)relations is a _preorder_ , i.e., for any two
objects $X,Y$ in the category, there is at most one morphism $X\to Y$.
Similarly, a matrix $\mathrm{M}\in\mathrm{matr}_{\ast}$ is said to be
_trivial_ [13] if every finitely complete pointed category with
$\mathrm{M}$-closed ($\mathcal{M}_{\mathrm{all}}$-)relations is a preorder
(which in that case will contain only one isomorphism class of objects). Since
$\mathrm{matr}\subset\mathrm{matr}_{\ast}$, it is sensible to ask whether
these two definitions agree if $\mathrm{M}\in\mathrm{matr}$. As proved in
[13], they indeed do. In [13, 16], it is shown how to efficiently recognize
whether a matrix is trivial. As this will not be needed here, we do not enter
into the details and refer the interested reader to those papers. However,
some theoretical characterizations from these papers are recalled in Theorem
2.1 where new characterizations are also proved. Given a matrix set
$S\subseteq\mathrm{matr}_{\ast}$, we say that $S$ is _trivial_ if it contains
a trivial matrix.

Now, given a non-pointed non-trivial matrix set $S\subseteq\mathrm{matr}$ and
a matrix $\mathrm{N}\in\mathrm{matr}(n,m,k)$ for integers $n>0$ and
$m,k\geqslant 0$, the algorithm from [16] to decide whether
$S\Rightarrow_{\mathrm{lex}}\mathrm{N}$ says the following:

> Keep expanding the set of left columns of $\mathrm{N}$, until it is not
> possible anymore, with the right column of a row-wise interpretation $B$ of
> type $(\\{x_{1},\dots,x_{k}\\},\dots,\\{x_{1},\dots,x_{k}\\})$ of a matrix
> $\mathrm{M}^{\prime}\in\mathrm{matr}(n,m^{\prime},k^{\prime})$ whose rows
> are rows of a common matrix $\mathrm{M}\in S$ such that the left columns of
> $B$, but not its right column, can be found among the left columns of the
> expending $\mathrm{N}$. One has the implication
> $S\Rightarrow_{\mathrm{lex}}\mathrm{N}$ if and only if the right column of
> $\mathrm{N}$ can be found among the left columns of this expanded
> $\mathrm{N}$.

In the pointed case, given a non-trivial matrix set
$S\subseteq\mathrm{matr}_{\ast}$ and a matrix
$\mathrm{N}\in\mathrm{matr}_{\ast}(n,m,k)$ for integers $n>0$ and
$m,k\geqslant 0$, the algorithm from [13] to decide whether
$S\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{N}$ says the following (where the
pointed set $\\{\ast,x_{1},\dots,x_{k}\\}$ is again considered with $\ast$ as
distinguished element):

> First, add to $\mathrm{N}$ a left column of $\ast$’s. Then, keep expanding
> the set of left columns of $\mathrm{N}$, until it is no more possible, with
> the right column of a row-wise interpretation $B$ of type
> $(\\{\ast,x_{1},\dots,x_{k}\\},\dots,\\{\ast,x_{1},\dots,x_{k}\\})$ of a
> matrix $\mathrm{M}^{\prime}\in\mathrm{matr}_{\ast}(n,m^{\prime},k^{\prime})$
> whose rows are rows of a common matrix $\mathrm{M}\in S$ such that the left
> columns of $B$, but not its right column, can be found among the left
> columns of the expanding $\mathrm{N}$. One has the implication
> $S\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{N}$ if and only if the right
> column of $\mathrm{N}$ can be found among the left columns of this expanded
> $\mathrm{N}$.

### Categories of partial algebras

In Universal Algebra, a _(finitary one-sorted) signature_ $\Sigma$ is a set of
operation symbols $\sigma$, each of them being equipped with an integer
$n\geqslant 0$ called its arity. Given such a signature $\Sigma$ and a set of
variables $X$, we define the set $\mathrm{T}_{\Sigma}(X)$ of _$\Sigma$ -terms
in the variables from $X$_ inductively as follows:

  * •

the elements of $X$ are terms (i.e., $X\subseteq\mathrm{T}_{\Sigma}(X)$);

  * •

given an $n$-ary operation symbol $\sigma\in\Sigma$ and $n$ terms
$t_{1},\dots,t_{n}\in\mathrm{T}_{\Sigma}(X)$, then $\sigma(t_{1},\dots,t_{n})$
is also a term in $\mathrm{T}_{\Sigma}(X)$.

Every element of $\mathrm{T}_{\Sigma}(X)$ is constructed using only those two
rules. A _$\Sigma$ -equation in the variables from $X$_ is then a pair
$(t,t^{\prime})$ of terms in $\mathrm{T}_{\Sigma}(X)$. A _$\Sigma$ -equation_
is then nothing else than a $\Sigma$-equation in the variables from some set
$X$.

For a signature $\Sigma$, a _$\Sigma$ -partial algebra_ $A$ is a set (also
denoted $A$ by abuse of notation) equipped with, for each $n$-ary operation
symbol $\sigma\in\Sigma$, a _partial_ function $\sigma^{A}\colon
A^{n}\dashrightarrow A$, i.e., a (total) function from a subset of $A^{n}$ to
$A$. In a $\Sigma$-partial algebra $A$, each $\Sigma$-term $t$ in the variable
from a set $X$ gives rise to a partial function $t^{A}\colon
A^{X}\dashrightarrow A$ defined inductively as follows:

  * •

if $t\in X$ is a variable, then $t^{A}$ is a total function given by the
corresponding projection $A^{X}\to A\colon(a_{x})_{x\in X}\mapsto a_{t}$;

  * •

if $t=\sigma(t_{1},\dots,t_{n})$ for some $n$-ary $\sigma\in\Sigma$ and
$\Sigma$-terms $t_{1},\dots,t_{n}\in\mathrm{T}_{\Sigma}(X)$, then $t^{A}$ is
defined on the element $(a_{x})_{x\in X}\in A^{X}$ if and only if
$t^{A}_{1},\dots,t^{A}_{n}$ are all defined on $(a_{x})_{x\in X}$ and
$\sigma^{A}$ is defined on $(t_{1}^{A}((a_{x})_{x\in
X}),\dots,t^{A}_{n}((a_{x})_{x\in X}))$, in which case

$t^{A}((a_{x})_{x\in X})=\sigma^{A}(t_{1}^{A}((a_{x})_{x\in
X}),\dots,t^{A}_{n}((a_{x})_{x\in X})).$

Following the terminology from [7], given a $\Sigma$-equation $(t,t^{\prime})$
in the variables from $X$, we say that $A$ satisfies the _existence equation_
$t=^{\mathrm{e}}t^{\prime}$ (or simply that the equation
$t=^{\mathrm{e}}t^{\prime}$ holds in $A$) if $t^{A}((a_{x})_{x\in X})$ and
$t^{\prime A}((a_{x})_{x\in X})$ are both defined for any element
$(a_{x})_{x\in X}\in A^{X}$ and they are equal:

$t^{A}((a_{x})_{x\in X})=t^{\prime A}((a_{x})_{x\in X}).$

Although there are other kind of equations that can be defined for partial
algebras, in this paper we will only consider existence equations.

Given a pair $(\Sigma,E)$ where $\Sigma$ is a signature and $E$ a set of
existence $\Sigma$-equations, a _$(\Sigma,E)$ -partial algebra_ is
$\Sigma$-partial algebra which satisfies all equations of $E$. A homomorphism
$f\colon A\to B$ of $(\Sigma,E)$-partial algebras is a (total) function
$f\colon A\to B$ such that, for each $n$-ary operation symbol
$\sigma\in\Sigma$ and every $a_{1},\dots,a_{n}\in A$, if
$\sigma^{A}(a_{1},\dots,a_{n})$ is defined in $A$, then
$\sigma^{B}(f(a_{1}),\dots,f(a_{n}))$ is defined in $B$ and the equality

$f(\sigma^{A}(a_{1},\dots,a_{n}))=\sigma^{B}(f(a_{1}),\dots,f(a_{n}))$ (6)

holds. These form the category $\mathsf{Part}(\Sigma,E)$ of
$(\Sigma,E)$-partial algebras. All small limits in such a category of partial
algebras exist and are computed as in the category $\mathsf{Set}$ of sets and
functions. More specifically, given a small category $\mathbb{J}$ and a
diagram $D\colon\mathbb{J}\to\mathsf{Part}(\Sigma,E)$, the limit of $D$ is
constructed as the set

$L=\\{(a_{J}\in D(J))_{J\in\mathbb{J}}\,|\,D(j)(a_{J})=a_{J^{\prime}}\,\forall
j\colon J\to J^{\prime}\in\mathbb{J}\\}$

and, given any $n$-ary $\sigma\in\Sigma$,

$\sigma^{L}((a_{1J})_{J\in\mathbb{J}},\dots,(a_{nJ})_{J\in\mathbb{J}})$

is defined if and only if $\sigma^{D(J)}(a_{1J},\dots,a_{nJ})$ is defined for
all object $J\in\mathbb{J}$, and is equal in that case to

$\sigma^{L}((a_{1J})_{J\in\mathbb{J}},\dots,(a_{nJ})_{J\in\mathbb{J}})=(\sigma^{D(J)}(a_{1J},\dots,a_{nJ}))_{J\in\mathbb{J}}.$

The legs of the limit are just the projections. Let us also mention that these
categories of partial algebras are _essentially algebraic_ [1, 2], i.e.,
_locally presentable_ [11]. As we will need it later on, for a matrix set
$S\subseteq\mathrm{matr}$ and a matrix $\mathrm{N}\in\mathrm{matr}$
(respectively a matrix set $S\subseteq\mathrm{matr}_{\ast}$ and a matrix
$\mathrm{N}\in\mathrm{matr}_{\ast}$), we write
$S\Rightarrow_{\mathrm{ess\,\,alg}}^{\mathrm{strong}}\mathrm{N}$ (respectively
$S\Rightarrow_{\mathrm{ess\,\,alg}_{\ast}}^{\mathrm{strong}}\mathrm{N}$) to
mean that any essentially algebraic category (respectively essentially
algebraic pointed category) with $S$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations has also $\mathrm{N}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations.

Inspired by Theorem 1.2, we now give our main example of a category of partial
algebras. Given a matrix set $S\subseteq\mathrm{matr}$ (respectively
$S\subseteq\mathrm{matr}_{\ast}$), we consider the signature $\Sigma^{S}$
which is constituted of, for each $\mathrm{M}\in S$ with $m$ left columns, an
$m$-ary operation symbol $p^{\mathrm{M}}$ (respectively, the signature
$\Sigma_{\ast}^{S}$ which is constituted of a nullary operation symbol $0$
and, for each $\mathrm{M}\in S$ with $m$ left columns, an $m$-ary operation
symbol $p^{\mathrm{M}}$). The set $E^{S}$ (respectively $E_{\ast}^{S}$) is
constituted by one existence equation for each row of each $\mathrm{M}\in S$,
namely

$p^{\mathrm{M}}(x_{i1},\dots,x_{im})=^{\mathrm{e}}x_{i\,m+1}$

in the variables from $\\{x_{1},\dots,x_{k}\\}$ for the $i^{\textrm{th}}$ row
of $\mathrm{M}$ if this row is

$\left[\begin{array}[]{ccc|c}x_{i1}&\dots&x_{im}&x_{i\,m+1}\end{array}\right]$

where the $x_{ij}$’s are in $\\{x_{1},\dots,x_{k}\\}$ (respectively, in the
pointed case, the $x_{ij}$’s are in $\\{\ast,x_{1},\dots,x_{k}\\}$ and in this
case $\ast$ is interpreted as $0$ in the above equation; we moreover add
$0=^{\mathrm{e}}0$ to $E_{\ast}^{S}$ to force $0$ to be defined). We denote
the category of $(\Sigma^{S},E^{S})$-partial algebras (respectively of
$(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebras) by $\mathsf{Part}^{S}$
(respectively by $\mathsf{Part}_{\ast}^{S}$).

In the pointed case $S\subseteq\mathrm{matr}_{\ast}$, for each $\mathrm{M}\in
S$, since $\mathrm{M}$ has at least one row, this implies that the existence
equation

$p^{\mathrm{M}}(0,\dots,0)=^{\mathrm{e}}0$

holds in any $(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebra. This shows
that, in the pointed case, the category $\mathsf{Part}_{\ast}^{S}$ is pointed.

Let us remark that for a non-pointed $S\subseteq\mathrm{matr}$ which contains
a matrix $\mathrm{M}$ with no left columns, $p^{\mathrm{M}}$ is then a
constant term and $p^{\mathrm{M}}=^{\mathrm{e}}x$ is an equation of $E^{S}$.
This equation means that, for any element $a$ of a
$(\Sigma^{S},E^{S})$-partial algebra $A$, $p^{\mathrm{M}}$ is defined and
equal to $a$. This does _not_ prevent $A$ to be empty. In that case,
$\mathsf{Part}^{S}$ is thus a preorder with exactly two isomorphism classes of
objects.

As it will useful later on, for a set $X$, we denote by $\mathrm{T}^{S}(X)$
(respectively by $\mathrm{T}_{\ast}^{S}(X)$) the set of terms
$\mathrm{T}_{\Sigma^{S}}(X)$ (respectively
$\mathrm{T}_{\Sigma_{\ast}^{S}}(X)$). If $S=\\{\mathrm{M}\\}$ is a singleton,
we make the usual abbreviations
$\Sigma^{\mathrm{M}}:=\Sigma^{\\{\mathrm{M}\\}}$,
$\Sigma_{\ast}^{\mathrm{M}}:=\Sigma_{\ast}^{\\{\mathrm{M}\\}}$,
$E^{\mathrm{M}}:=E^{\\{\mathrm{M}\\}}$,
$E_{\ast}^{\mathrm{M}}:=E_{\ast}^{\\{\mathrm{M}\\}}$,
$\mathsf{Part}^{\mathrm{M}}:=\mathsf{Part}^{\\{\mathrm{M}\\}}$,
$\mathsf{Part}_{\ast}^{\mathrm{M}}:=\mathsf{Part}_{\ast}^{\\{\mathrm{M}\\}}$,
$\mathrm{T}^{\mathrm{M}}(X):=\mathrm{T}^{\\{\mathrm{M}\\}}(X)$ and
$\mathrm{T}_{\ast}^{\mathrm{M}}(X):=\mathrm{T}_{\ast}^{\\{\mathrm{M}\\}}(X)$.
The categories $\mathsf{Part}^{\mathrm{M}}$ and
$\mathsf{Part}_{\ast}^{\mathrm{M}}$ have been introduced in [19]. We conclude
this subsection by mentioning an important property of
$\mathsf{Part}^{\mathrm{M}}$ and $\mathsf{Part}_{\ast}^{\mathrm{M}}$, that we
will generalize to the case of a matrix set in the next subsection.

######  Proposition 1.4.

[19] Let $\mathrm{M}\in\mathrm{matr}$ (respectively
$\mathrm{M}\in\mathrm{matr}_{\ast}$). The category
$\mathsf{Part}^{\mathrm{M}}$ (respectively
$\mathsf{Part}_{\ast}^{\mathrm{M}}$) has $\mathrm{M}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations (in general, it does _not_ have
$\mathrm{M}$-closed $\mathcal{M}_{\mathrm{all}}$-relations).

### Free partial algebras

Let us now fix two matrix sets $S^{\prime}\subseteq S\subseteq\mathrm{matr}$
(respectively $S^{\prime}\subseteq S\subseteq\mathrm{matr}_{\ast}$). We denote
by
$\mathrm{U}^{S,S^{\prime}}\colon\mathsf{Part}^{S}\to\mathsf{Part}^{S^{\prime}}$
(respectively
$\mathrm{U}_{\ast}^{S,S^{\prime}}\colon\mathsf{Part}_{\ast}^{S}\to\mathsf{Part}_{\ast}^{S^{\prime}}$)
the corresponding forgetful functor. In view of the description of small
limits in categories of partial algebras recalled above, this functor
preserves these small limits. Moreover, it is easy to construct its left
adjoint. Given a $(\Sigma^{S^{\prime}},E^{S^{\prime}})$-partial algebra $A$
(respectively a $(\Sigma_{\ast}^{S^{\prime}},E_{\ast}^{S^{\prime}})$-partial
algebra $A$), we distinguish two cases to construct the universal
$(\Sigma^{S},E^{S})$-partial algebra $\mathrm{F}^{S,S^{\prime}}(A)$
(respectively the universal $(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebra
$\mathrm{F}_{\ast}^{S,S^{\prime}}(A)$):

  * •

In this first case, we suppose that $A$ has at least two elements but there is
no $(\Sigma^{S},E^{S})$-partial algebra (respectively
$(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebra) with at least two elements
(i.e., $S$ is trivial anticipating the equivalences of Theorem 2.1). In that
case, $\mathrm{F}^{S,S^{\prime}}(A)$ (respectively
$\mathrm{F}_{\ast}^{S,S^{\prime}}(A)$) is the terminal object, that is, it has
exactly one element and any $m$-ary operation symbol of $\Sigma^{S}$
(respectively of $\Sigma_{\ast}^{S}$) is defined on the unique element of
$\mathrm{F}^{S,S^{\prime}}(A)^{m}$ (respectively of
$\mathrm{F}_{\ast}^{S,S^{\prime}}(A)^{m}$). The reflection of $A$ along
$\mathrm{U}^{S,S^{\prime}}$ (respectively along
$\mathrm{U}_{\ast}^{S,S^{\prime}}$) is then given by the unique function
$A\to\mathrm{U}^{S,S^{\prime}}(\mathrm{F}^{S,S^{\prime}}(A))$ (respectively
$A\to\mathrm{U}_{\ast}^{S,S^{\prime}}(\mathrm{F}_{\ast}^{S,S^{\prime}}(A))$).

  * •

Otherwise, $\mathrm{F}^{S,S^{\prime}}(A)$ (respectively
$\mathrm{F}_{\ast}^{S,S^{\prime}}(A)$) is obtained by keeping the same
underlying $(\Sigma^{S^{\prime}},E^{S^{\prime}})$-partial algebra $A$
(respectively the same underlying
$(\Sigma_{\ast}^{S^{\prime}},E_{\ast}^{S^{\prime}})$-partial algebra $A$) and
defining, for each $\mathrm{M}\in{S\setminus S^{\prime}}$, $p^{\mathrm{M}}$
only where it is required by the existence equations related to $\mathrm{M}$.
It is not hard to see that, in this case, these definitions do not contradict
each other. The identity function
$A\to\mathrm{U}^{S,S^{\prime}}(\mathrm{F}^{S,S^{\prime}}(A))$ (respectively
$A\to\mathrm{U}_{\ast}^{S,S^{\prime}}(\mathrm{F}_{\ast}^{S,S^{\prime}}(A))$)
gives the reflection of $A$ along $\mathrm{U}^{S,S^{\prime}}$ (respectively
$\mathrm{U}_{\ast}^{S,S^{\prime}}$).

We have therefore an adjunction
$\mathrm{F}^{S,S^{\prime}}\dashv\mathrm{U}^{S,S^{\prime}}$ (respectively
$\mathrm{F}_{\ast}^{S,S^{\prime}}\dashv\mathrm{U}_{\ast}^{S,S^{\prime}}$).
Moreover, we can see from the above construction of the left adjoint that, if
$S$ is not trivial, this adjunction is actually a _co-reflection_ , i.e., the
unit is an isomorphism. If $S^{\prime}=\emptyset$ is empty,
$\mathsf{Part}^{S^{\prime}}$ is (equivalent to) the category $\mathsf{Set}$ of
sets (respectively $\mathsf{Part}_{\ast}^{S^{\prime}}$ is (equivalent to) the
category $\mathsf{Set}_{\ast}$ of pointed sets). We therefore have a left
adjoint $\mathrm{F}^{S}:=\mathrm{F}^{S,\emptyset}$ (respectively
$\mathrm{F}_{\ast}^{S}:=\mathrm{F}_{\ast}^{S,\emptyset}$) for the forgetful
functor
$\mathrm{U}^{S}:=\mathrm{U}^{S,\emptyset}\colon\mathsf{Part}^{S}\to\mathsf{Set}$
(respectively
$\mathrm{U}_{\ast}^{S}:=\mathrm{U}_{\ast}^{S,\emptyset}\colon\mathsf{Part}_{\ast}^{S}\to\mathsf{Set}_{\ast}$).

It is a classical result that right adjoints preserves strong monomorphisms
(see e.g. Proposition 4.3.9 in [5]). We therefore immediately have the
following.

######  Proposition 1.5.

Let $S^{\prime}\subseteq S\subseteq\mathrm{matr}$ (respectively
$S^{\prime}\subseteq S\subseteq\mathrm{matr}_{\ast}$) be two matrix sets. The
forgetful functor
$\mathrm{U}^{S,S^{\prime}}\colon\mathsf{Part}^{S}\to\mathsf{Part}^{S^{\prime}}$
(respectively
$\mathrm{U}_{\ast}^{S,S^{\prime}}\colon\mathsf{Part}_{\ast}^{S}\to\mathsf{Part}_{\ast}^{S^{\prime}}$)
preserves strong monomorphisms.

Due to this proposition, we can extend Proposition 1.4 to matrix sets.

######  Proposition 1.6.

Let $S\subseteq\mathrm{matr}$ (respectively $S\subseteq\mathrm{matr}_{\ast}$)
be a matrix set. The category $\mathsf{Part}^{S}$ (respectively
$\mathsf{Part}^{S}_{\ast}$) has $S$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations.

###### Proof.

Let $\mathrm{M}\in S\cap\mathrm{matr}_{\ast}(n,m,k)$ for integers $n>0$ and
$m,k\geqslant 0$. Let also $r\colon R\rightarrowtail X^{n}$ be a
$\mathcal{M}_{\mathrm{strong}}$-relation in $\mathsf{Part}^{S}$ (respectively
in $\mathsf{Part}_{\ast}^{S}$) and

$\left[\begin{array}[]{ccc|c}g_{11}&\dots&g_{1m}&h_{1}\\\
\vdots&&\vdots&\vdots\\\ g_{n1}&\dots&g_{nm}&h_{n}\end{array}\right]$

be an interpretation of $\mathrm{M}$ of type $\mathsf{Part}^{S}(Z,X)$
(respectively of type $\mathsf{Part}_{\ast}^{S}(Z,X)$) such that, for each
$j\in\\{1,\dots,m\\}$, the morphism $(g_{1j},\dots,g_{nj})\colon Z\to X^{n}$
factors through $r$. We must show that the morphism $(h_{1},\dots,h_{n})\colon
Z\to X^{n}$ also factors through $r$, i.e., that the pullback $r^{\prime}$ of
$r$ along $(h_{1},\dots,h_{n})$ is an isomorphism. Since the forgetful functor
$\mathrm{U}^{S,\mathrm{M}}:=\mathrm{U}^{S,\\{\mathrm{M}\\}}$ (respectively
$\mathrm{U}_{\ast}^{S,\mathrm{M}}:=\mathrm{U}_{\ast}^{S,\\{\mathrm{M}\\}}$)
preserves limits and strong monomorphisms, and since
$\mathsf{Part}^{\mathrm{M}}$ (respectively
$\mathsf{Part}_{\ast}^{\mathrm{M}}$) has $\mathrm{M}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations by Proposition 1.4, we know that
$\mathrm{U}^{S,\mathrm{M}}(r^{\prime})$ (respectively
$\mathrm{U}_{\ast}^{S,\mathrm{M}}(r^{\prime})$) is an isomorphism. This thus
means that $r^{\prime}$ is surjective and, being a
$\mathcal{M}_{\mathrm{strong}}$-relation, it is an isomorphism. ∎

### Closed sub-partial algebras

Given a signature $\Sigma$ and a set $E$ of existence $\Sigma$-equations, the
monomorphisms in $\mathsf{Part}(\Sigma,E)$ are exactly the injective
homomorphisms. A _sub-partial algebra_ of a $(\Sigma,E)$-partial algebra $B$
is thus given by a $(\Sigma,E)$-partial algebra $A$ where the underlying set
of $A$ is included in that of $B$ and such that, for any $n$-ary operation
symbol $\sigma\in\Sigma$ and any $a_{1},\dots,a_{n}\in A$, if
$\sigma^{A}(a_{1},\dots,a_{n})$ is defined in $A$, then
$\sigma^{B}(a_{1},\dots,a_{n})$ is defined in $B$ and
$\sigma^{B}(a_{1},\dots,a_{n})=\sigma^{A}(a_{1},\dots,a_{n})$. Note that in
general, if $\sigma^{B}(a_{1},\dots,a_{n})$ is defined in $B$, there is no
reason for which $\sigma^{A}(a_{1},\dots,a_{n})$ is defined in $A$. A sub-
partial algebra for which this reverse implication holds is said to be
_closed_ [18]. More generally, a homomorphism $f\colon A\to B$ in
$\mathsf{Part}(\Sigma,E)$ is said to be _closed_ if, for each $n$-ary
operation symbol $\sigma\in\Sigma$ and every $a_{1},\dots,a_{n}\in A$, if
$\sigma^{B}(f(a_{1}),\dots,f(a_{n}))$ is defined in $B$, then
$\sigma^{A}(a_{1},\dots,a_{n})$ is defined in $A$ (and therefore the identity
(6) holds).

Let us recall from [19] that in most cases, closed monomorphisms in
$\mathsf{Part}^{\mathrm{M}}$ and $\mathsf{Part}_{\ast}^{\mathrm{M}}$ coincide
with strong monomorphisms.

######  Proposition 1.7.

[19] For a matrix $\mathrm{M}\in\mathrm{matr}_{\ast}$, closed monomorphisms in
$\mathsf{Part}_{\ast}^{\mathrm{M}}$ coincide with strong monomorphisms. For a
matrix $\mathrm{M}\in\mathrm{matr}$, strong monomorphisms in
$\mathsf{Part}^{\mathrm{M}}$ are closed monomorphisms and the converse is true
if there exists a partial algebra in $\mathsf{Part}^{\mathrm{M}}$ with at
least two elements.

The condition that $\mathsf{Part}^{\mathrm{M}}$ contains a partial algebra
with at least two elements in the above proposition will be rephrased as
‘$\mathrm{M}$ is not trivial’, see the equivalence (12)$\Leftrightarrow$(19)
in Theorem 2.1.

Using a similar same proof than in [19], we can generalize the above
proposition to the case of matrix sets, giving rise to the following where we
use Theorem 2.1 by anticipation to reformulate the condition.

######  Proposition 1.8.

For a matrix set $S\subseteq\mathrm{matr}_{\ast}$, closed monomorphisms in
$\mathsf{Part}_{\ast}^{S}$ coincide with strong monomorphisms. For a non-
pointed matrix set $S\subseteq\mathrm{matr}$, strong monomorphisms in
$\mathsf{Part}^{S}$ are closed monomorphisms and the converse is true if $S$
is not trivial.

### The embedding theorem

We now recall the embedding theorem from [19] which will be of crucial
importance in the proof of our results. The notation
$\mathbb{C}^{\mathrm{op}}$ stands for the dual of the category $\mathbb{C}$
and, for a category $\mathbb{D}$, the notation
$\mathbb{D}^{\mathbb{C}^{\mathrm{op}}}$ denotes the category of functors
$\mathbb{C}^{\mathrm{op}}\to\mathbb{D}$ and natural transformations between
them.

######  Theorem 1.9.

[19] Given a matrix $\mathrm{M}\in\mathrm{matr}$ (respectively
$\mathrm{M}\in\mathrm{matr}_{\ast}$), a small finitely complete category
$\mathbb{C}$ (respectively a small finitely complete pointed category
$\mathbb{C}$) and $\mathcal{M}$ a class of monomorphisms in $\mathbb{C}$
stable under pullbacks, closed under composition and containing the regular
monomorphisms, if $\mathbb{C}$ has $\mathrm{M}$-closed
$\mathcal{M}$-relations, then there exists a fully faithful embedding
$\varphi\colon\mathbb{C}\hookrightarrow(\mathsf{Part}^{\mathrm{M}})^{\mathbb{C}^{\mathrm{op}}}$
(respectively
$\varphi\colon\mathbb{C}\hookrightarrow(\mathsf{Part}_{\ast}^{\mathrm{M}})^{\mathbb{C}^{\mathrm{op}}}$)
which preserves and reflects finite limits and such that, for every
monomorphism $f\in\mathcal{M}$ and every object $X\in\mathbb{C}$,
$\varphi(f)_{X}$ is a closed monomorphism in $\mathsf{Part}^{\mathrm{M}}$
(respectively in $\mathsf{Part}_{\ast}^{\mathrm{M}}$).

The embedding $\varphi$ can be constructed as a factorization of the Yoneda
embedding
$\mathrm{Y}\colon\mathbb{C}\hookrightarrow\mathsf{Set}^{\mathbb{C}^{\mathrm{op}}}$
(respectively
$\mathrm{Y}_{\ast}\colon\mathbb{C}\hookrightarrow\mathsf{Set}_{\ast}^{\mathbb{C}^{\mathrm{op}}}$)
through the functor $(\mathrm{U}^{\mathrm{M}})^{\mathbb{C}^{\mathrm{op}}}$
(respectively $(\mathrm{U}_{\ast}^{\mathrm{M}})^{\mathbb{C}^{\mathrm{op}}}$)
induced by post-composition with
$\mathrm{U}^{\mathrm{M}}:=\mathrm{U}^{\\{\mathrm{M}\\},\emptyset}$
(respectively with
$\mathrm{U}_{\ast}^{\mathrm{M}}:=\mathrm{U}_{\ast}^{\\{\mathrm{M}\\},\emptyset}$).

$\textstyle{(\mathsf{Part}^{\mathrm{M}})^{\mathbb{C}^{\mathrm{op}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\mathrm{U}^{\mathrm{M}})^{\mathbb{C}^{\mathrm{op}}}}$$\textstyle{\mathbb{C}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi}$$\scriptstyle{\mathrm{Y}}$$\textstyle{\mathsf{Set}^{\mathbb{C}^{\mathrm{op}}}}$
$\textstyle{(\mathsf{Part}_{\ast}^{\mathrm{M}})^{\mathbb{C}^{\mathrm{op}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\mathrm{U}_{\ast}^{\mathrm{M}})^{\mathbb{C}^{\mathrm{op}}}}$$\textstyle{\mathbb{C}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi}$$\scriptstyle{\mathrm{Y}_{\ast}}$$\textstyle{\mathsf{Set}_{\ast}^{\mathbb{C}^{\mathrm{op}}}}$

Given a matrix set $S\subseteq\mathrm{matr}$ (respectively
$S\subseteq\mathrm{matr}_{\ast}$), the category $\mathsf{Part}^{S}$
(respectively $\mathsf{Part}_{\ast}^{S}$) together with the forgetful functors
$\mathrm{U}^{S}$ and $\mathrm{U}^{S,\mathrm{M}}$ for each $\mathrm{M}\in S$
(respectively $\mathrm{U}_{\ast}^{S}$ and $\mathrm{U}_{\ast}^{S,\mathrm{M}}$
for each $\mathrm{M}\in S$) has the universal property of the limit of the
diagram constituted of one occurrence of $\mathsf{Set}$ (respectively of
$\mathsf{Set}_{\ast}$) and, for each $\mathrm{M}\in S$, the forgetful functor
$\mathrm{U}^{\mathrm{M}}$ (respectively $\mathrm{U}_{\ast}^{\mathrm{M}}$) to
that occurrence of $\mathsf{Set}$ (respectively of $\mathsf{Set}_{\ast}$).

$\textstyle{\mathsf{Part}^{S}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathrm{U}^{S,\mathrm{M}}}$$\scriptstyle{\mathrm{U}^{S,\mathrm{M}^{\prime}}}$$\scriptstyle{\mathrm{U}^{S}}$$\textstyle{\mathsf{Part}^{\mathrm{M}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathrm{U}^{\mathrm{M}}}$$\textstyle{\cdots}$$\textstyle{\cdots}$$\textstyle{\mathsf{Part}^{\mathrm{M}^{\prime}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathrm{U}^{\mathrm{M}^{\prime}}}$$\textstyle{\mathsf{Set}}$
$\textstyle{\mathsf{Part}_{\ast}^{S}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathrm{U}_{\ast}^{S,\mathrm{M}}}$$\scriptstyle{\mathrm{U}_{\ast}^{S,\mathrm{M}^{\prime}}}$$\scriptstyle{\mathrm{U}_{\ast}^{S}}$$\textstyle{\mathsf{Part}_{\ast}^{\mathrm{M}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathrm{U}_{\ast}^{\mathrm{M}}}$$\textstyle{\cdots}$$\textstyle{\cdots}$$\textstyle{\mathsf{Part}_{\ast}^{\mathrm{M}^{\prime}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathrm{U}_{\ast}^{\mathrm{M}^{\prime}}}$$\textstyle{\mathsf{Set}_{\ast}}$

In view of this, the above embedding theorem immediately generalizes for a
matrix set as follows.

######  Theorem 1.10.

Given a matrix set $S\subseteq\mathrm{matr}$ (respectively
$S\subseteq\mathrm{matr}_{\ast}$), a small finitely complete category
$\mathbb{C}$ (respectively a small finitely complete pointed category
$\mathbb{C}$) and $\mathcal{M}$ a class of monomorphisms in $\mathbb{C}$
stable under pullbacks, closed under composition and containing the regular
monomorphisms, if $\mathbb{C}$ has $S$-closed $\mathcal{M}$-relations, then
there exists a fully faithful embedding
$\varphi\colon\mathbb{C}\hookrightarrow(\mathsf{Part}^{S})^{\mathbb{C}^{\mathrm{op}}}$
(respectively
$\varphi\colon\mathbb{C}\hookrightarrow(\mathsf{Part}_{\ast}^{S})^{\mathbb{C}^{\mathrm{op}}}$)
which preserves and reflects finite limits, such that, for every monomorphism
$f\in\mathcal{M}$ and every object $X\in\mathbb{C}$, $\varphi(f)_{X}$ is a
closed monomorphism in $\mathsf{Part}^{S}$ (respectively in
$\mathsf{Part}_{\ast}^{S}$) and which makes the diagram

$\textstyle{(\mathsf{Part}^{S})^{\mathbb{C}^{\mathrm{op}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\mathrm{U}^{S})^{\mathbb{C}^{\mathrm{op}}}}$$\textstyle{\mathbb{C}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi}$$\scriptstyle{\mathrm{Y}}$$\textstyle{\mathsf{Set}^{\mathbb{C}^{\mathrm{op}}}}$

respectively

$\textstyle{(\mathsf{Part}_{\ast}^{S})^{\mathbb{C}^{\mathrm{op}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\mathrm{U}_{\ast}^{S})^{\mathbb{C}^{\mathrm{op}}}}$$\textstyle{\mathbb{C}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi}$$\scriptstyle{\mathrm{Y}_{\ast}}$$\textstyle{\mathsf{Set}_{\ast}^{\mathbb{C}^{\mathrm{op}}}}$

commute.

##  2 Main results

We can now state and prove our results reinforcing the links between
categories of partial algebras and matrix properties involving a general class
$\mathcal{M}$ of monomorphisms.

### Trivial matrix sets

Let us start by studying trivial matrix sets. We extend here the
characterizations of trivial matrices that can already be found in [13, 15,
16]. In addition of recalling some known characterizations, we add many new
ones. We however omit to recall here many other characterizations found in
those papers which allow to effectively recognize when a matrix is trivial. In
the following theorem, $\mathsf{Bool}$ denotes the category of Boolean
algebras and $\mathsf{1}$ denotes the category with a unique object and the
identity on it as unique morphism. A category is said to be _regular_ [3] if
it has finite limits, coequalizers of kernel pairs and such that regular
epimorphisms are stable under pullbacks. Note that the following theorem can
be used with $S=\\{\mathrm{M}\\}$ a singleton, giving rise to some
characterizations of trivial matrices (instead of trivial matrix sets), some
of those already appearing in [13, 15, 16].

######  Theorem 2.1.

For a matrix set $S\subseteq\mathrm{matr}_{\ast}$ , the following conditions
are equivalent:

  1. (1)

every finitely complete pointed category with $S$-closed relations is
equivalent to the single morphism category $\mathsf{1}$;

  2. (2)

$S$ is trivial, that is, $S$ contains a trivial matrix $\mathrm{M}$, i.e.,
such that every finitely complete pointed category with $\mathrm{M}$-closed
relations is equivalent to the single morphism category $\mathsf{1}$;

  3. (3)

every finitely complete pointed category with $S$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations is equivalent to the single morphism
category $\mathsf{1}$;

  4. (4)

for every finitely complete pointed category $\mathbb{C}$ and every class
$\mathcal{M}$ of monomorphisms in $\mathbb{C}$ stable under pullbacks, closed
under composition, containing all regular monomorphisms and such that
$\mathbb{C}$ has $S$-closed $\mathcal{M}$-relations, $\mathbb{C}$ is
equivalent to the single morphism category $\mathsf{1}$;

  5. (5)

any regular pointed category with $S$-closed relations is equivalent to the
single morphism category $\mathsf{1}$;

  6. (6)

any essentially algebraic pointed category with $S$-closed relations is
equivalent to the single morphism category $\mathsf{1}$;

  7. (7)

any pointed variety with $S$-closed relations is equivalent to the single
morphism category $\mathsf{1}$, i.e., the equation $x=0$ holds in its theory
for a constant term $0$;

  8. (8)

$\mathsf{Part}_{\ast}^{S}$ is equivalent to the single morphism category
$\mathsf{1}$;

  9. (9)

every $(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebra has exactly one
element;

  10. (10)

$\mathsf{Set}_{\ast}^{\mathrm{op}}$ does _not_ have $S$-closed relations.

If $S\subseteq\mathrm{matr}$ is non-pointed, these are further equivalent to
the following conditions:

  1. (11)

every finitely complete category with $S$-closed relations is a preorder;

  2. (12)

$S$ contains a trivial matrix $\mathrm{M}$, i.e., such that every finitely
complete category with $\mathrm{M}$-closed relations is a preorder;

  3. (13)

every finitely complete category with $S$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations is a preorder;

  4. (14)

for every finitely complete category $\mathbb{C}$ and every class
$\mathcal{M}$ of monomorphisms in $\mathbb{C}$ stable under pullbacks, closed
under composition, containing all regular monomorphisms and such that
$\mathbb{C}$ has $S$-closed $\mathcal{M}$-relations, $\mathbb{C}$ is a
preorder;

  5. (15)

any regular category with $S$-closed relations is a preorder;

  6. (16)

any essentially algebraic category with $S$-closed relations is a preorder;

  7. (17)

any variety with $S$-closed relations is a preorder, i.e., the equation $x=y$
holds in its theory;

  8. (18)

$\mathsf{Part}^{S}$ is a preorder;

  9. (19)

every $(\Sigma^{S},E^{S})$-partial algebra has at most one element;

  10. (20)

$\mathsf{Set}^{\mathrm{op}}$ does _not_ have $S$-closed relations;

  11. (21)

$\mathsf{Bool}$ does _not_ have $S$-closed relations.

###### Proof.

We first consider the general case where $S\subseteq\mathrm{matr}_{\ast}$. The
implication (2)$\Rightarrow$(1) is obvious while (1)$\Rightarrow$(10) follows
from the fact that $\mathsf{Set}_{\ast}^{\mathrm{op}}$ is not equivalent to
$\mathsf{1}$. If (10) holds, $S$ contains a matrix $\mathrm{M}$ for which
$\mathsf{Set}_{\ast}^{\mathrm{op}}$ does not have $\mathrm{M}$-closed
relations. Using Theorem 3.1 in [13], this means that $\mathrm{M}$ is trivial.
We have therefore already proved the equivalences
(1)$\Leftrightarrow$(2)$\Leftrightarrow$(10). The implication
(4)$\Rightarrow$(3) follows from the fact that the class of strong
monomorphisms in a category is stable under pullbacks, closed under
composition and contains regular monomorphisms. The implications
(3)$\Rightarrow$(1)$\Rightarrow$(5) are obvious, as well as
(5)$\Rightarrow$(7) since varieties of universal algebras form regular
categories. Since essentially algebraic categories are complete and varieties
are essentially algebraic categories, the implications
(1)$\Rightarrow$(6)$\Rightarrow$(7) are also straightforward. Concerning the
implication (7)$\Rightarrow$(9), suppose $A$ is a
$(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebra. Note that $A$ cannot be
empty since $0$ needs to be defined in $A$. For each matrix $\mathrm{M}\in S$
with $m$ left columns, the $m$-ary operation symbol
$p^{\mathrm{M}}\in\Sigma_{\ast}^{\mathrm{M}}$ can be extended to a total
operation $(p^{\mathrm{M}})^{A}$ on $A$ by defining it to be $0$ on any
$m$-tuple in $A^{m}$ on which it is not yet defined. Doing so, $A$ becomes a
total $(\Sigma_{\ast}^{S},E_{\ast}^{S})$-algebra. Using Theorem 1.2, the
variety of total $(\Sigma_{\ast}^{S},E_{\ast}^{S})$-algebras has $S$-closed
relations. If (7) holds, this means that $A$ as a unique element, proving the
implication (7)$\Rightarrow$(9). To prove the equivalence
(9)$\Leftrightarrow$(8), it suffices to notice that any
$(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebra $A$ with a unique element
is isomorphic to the terminal object of $\mathsf{Part}_{\ast}^{S}$ since $0$
has to be defined as well as $(p^{\mathrm{M}})^{A}(0,\dots,0)$ for each
$\mathrm{M}\in S$. We conclude the first part of the proof with the
implication (9)$\Rightarrow$(4). Let us suppose (9) holds and let $\mathbb{C}$
be a finitely complete pointed category and $\mathcal{M}$ a class of
monomorphisms in $\mathbb{C}$ stable under pullbacks, closed under
composition, containing all regular monomorphisms and such that $\mathbb{C}$
has $S$-closed $\mathcal{M}$-relations. We shall prove that $\mathbb{C}$ is
equivalent to $\mathsf{1}$. Since $\mathbb{C}$ has a terminal object, it is
not empty and thus it remains to prove that given any two objects $X,Y$ in
$\mathbb{C}$, $0$ is the unique morphism $X\to Y$. If $\mathbb{C}$ is a small
category, one can use the Embedding Theorem 1.10 to obtain a fully faithful
embedding
$\varphi\colon\mathbb{C}\hookrightarrow(\mathsf{Part}_{\ast}^{S})^{\mathbb{C}^{\mathrm{op}}}$.
If there were two different morphisms $f,g\colon X\to Y$, then
$\varphi(f)\neq\varphi(g)$ and so $\varphi(f)_{Z}\neq\varphi(g)_{Z}$ for some
object $Z\in\mathbb{C}^{\mathrm{op}}$. However, this is not possible since
$\mathsf{Part}_{\ast}^{S}$ is supposed to be equivalent to $\mathsf{1}$. If
$\mathbb{C}$ is not small, one can extract from the proof of the Embedding
Theorem 1.9 in [19] a $(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebraic
structure on $\mathbb{C}(X,Y)$ and conclude by (9) that it contains only the
zero morphism.

Let us now suppose that $S\subseteq\mathrm{matr}$. The equivalence
(20)$\Leftrightarrow$(21) can be found in [15] while the equivalence
(2)$\Leftrightarrow$(12) is established in [13]. The remaining implications
are proved similarly as above except that (20)$\Rightarrow$(12) follows now
from Theorem 2.3 in [16] and (18)$\Rightarrow$(19) can be proved as follows.
For any element $a$ in a $(\Sigma^{S},E^{S})$-partial algebra $A$, one has
that, for each $\mathrm{M}\in S$, $(p^{\mathrm{M}})^{A}(a,\dots,a)$ is defined
and equal to $a$ (since $\mathrm{M}$ has at least one row). Such an element
thus determines a morphism from the terminal $(\Sigma^{S},E^{S})$-partial
algebra to $A$, sending the unique element in the domain to $a$. If
$\mathsf{Part}^{S}$ is a preorder, this implies that $A$ cannot have more than
one element. ∎

In [13, 16], for a matrix set $S\subseteq\mathrm{matr}$ (respectively
$S\subseteq\mathrm{matr}_{\ast}$), we denoted by $\mathrm{mclex}S$
(respectively by $\mathrm{mclex}_{\ast}S$) the collection of finitely complete
(respectively finitely complete pointed) categories with $S$-closed relations.
Similarly, we denote here by $\mathrm{mclex}^{\mathrm{strong}}S$ (respectively
$\mathrm{mclex}_{\ast}^{\mathrm{strong}}S$) the collection of finitely
complete (respectively finitely complete pointed) categories with $S$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations.

######  Remark 2.2.

Let $\mathrm{M}\in\mathrm{matr}(n,m,k)$ for integers $n>0$ and $m,k\geqslant
0$. If $m=0$, then $\mathrm{M}$ is automatically trivial and
$\mathrm{mclex}\\{\mathrm{M}\\}$ is the collection of categories equivalent to
$\mathsf{1}$. If $\mathrm{M}$ is trivial but $m>0$,
$\mathrm{mclex}\\{\mathrm{M}\\}$ is then the bigger collection of finitely
complete preorders. Trivial matrix sets determine thus two different
collections of categories when looking at
$\mathcal{M}=\mathcal{M}_{\mathrm{all}}$. Although the equivalence
(11)$\Leftrightarrow$(13) holds in the above theorem, trivial matrix sets
determine only one collection of categories when looking at
$\mathcal{M}=\mathcal{M}_{\mathrm{strong}}$. Indeed, if $S$ is trivial,
$\mathrm{mclex}^{\mathrm{strong}}S$ is always the collection of finitely
complete preorders. This is due to the fact that in finitely complete
preorders, $\mathcal{M}_{\mathrm{strong}}$ is the class of isomorphisms and
therefore they all have $S$-closed $\mathcal{M}_{\mathrm{strong}}$-relations
even if $S$ contains a matrix with no left columns. This distinction
disappears in the pointed case because if $S\subseteq\mathrm{matr}_{\ast}$ is
a trivial matrix set, both $\mathrm{mclex}_{\ast}S$ and
$\mathrm{mclex}_{\ast}^{\mathrm{strong}}S$ are the collection of categories
equivalent to $\mathsf{1}$.

### Implications of matrix properties

We now come to our main result.

######  Theorem 2.3.

Let $S\subseteq\mathrm{matr}_{\ast}$ be a matrix set and
$\mathrm{N}\in\mathrm{matr}_{\ast}$ be a matrix such that $\mathrm{N}$ has
$m\geqslant 0$ left columns. The following conditions are equivalent:

  1. (1)

$S\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{N}$;

  2. (2)

$S\Rightarrow_{\mathrm{lex}_{\ast}}^{\mathrm{strong}}\mathrm{N}$;

  3. (3)

$S\Rightarrow_{\mathrm{ess\,\,alg}_{\ast}}^{\mathrm{strong}}\mathrm{N}$;

  4. (4)

for every finitely complete pointed category $\mathbb{C}$ and every class
$\mathcal{M}$ of monomorphisms in $\mathbb{C}$ stable under pullbacks, closed
under composition and containing all regular monomorphisms, if $\mathbb{C}$
has $S$-closed $\mathcal{M}$-relations, then it has also $\mathrm{N}$-closed
$\mathcal{M}$-relations;

  5. (5)

$\mathsf{Part}_{\ast}^{S}$ has $\mathrm{N}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations;

  6. (6)

there exists an $m$-ary term
$q\in\mathrm{T}_{\ast}^{S}(\\{y_{1},\dots,y_{m}\\})$ such that, for any
$(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebra $A$, $q^{A}\colon
A^{m}\dashrightarrow A$ makes $A$ a
$(\Sigma_{\ast}^{\mathrm{N}},E_{\ast}^{\mathrm{N}})$-partial algebra.

Moreover, if $S\subseteq\mathrm{matr}$, $\mathrm{N}\in\mathrm{matr}$ and
$m>0$, these are further equivalent to the following conditions:

  1. (7)

$S\Rightarrow_{\mathrm{lex}}\mathrm{N}$;

  2. (8)

$S\Rightarrow_{\mathrm{lex}}^{\mathrm{strong}}\mathrm{N}$;

  3. (9)

$S\Rightarrow_{\mathrm{ess\,\,alg}}^{\mathrm{strong}}\mathrm{N}$;

  4. (10)

for every finitely complete category $\mathbb{C}$ and every class
$\mathcal{M}$ of monomorphisms in $\mathbb{C}$ stable under pullbacks, closed
under composition and containing all regular monomorphisms, if $\mathbb{C}$
has $S$-closed $\mathcal{M}$-relations, then it has also $\mathrm{N}$-closed
$\mathcal{M}$-relations;

  5. (11)

$\mathsf{Part}^{S}$ has $\mathrm{N}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations;

  6. (12)

there exists an $m$-ary term $q\in\mathrm{T}^{S}(\\{y_{1},\dots,y_{m}\\})$
such that, for any $(\Sigma^{S},E^{S})$-partial algebra $A$, $q^{A}\colon
A^{m}\dashrightarrow A$ makes $A$ a
$(\Sigma^{\mathrm{N}},E^{\mathrm{N}})$-partial algebra.

###### Proof.

We first consider the general case where $S\subseteq\mathrm{matr}_{\ast}$ and
$\mathrm{N}\in\mathrm{matr}_{\ast}$. To fix dimensions, we suppose that
$\mathrm{N}\in\mathrm{matr}_{\ast}(n,m,k)$ for integers $n>0$ and
$m,k\geqslant 0$. The implications (4)$\Rightarrow$(1) and (4)$\Rightarrow$(2)
are obvious since the classes $\mathcal{M}_{\mathrm{all}}$ and
$\mathcal{M}_{\mathrm{strong}}$ in any finitely complete category are closed
under composition, stable under pullbacks and contain all regular
monomorphisms. The implication (2)$\Rightarrow$(3) is trivial since
essentially algebraic categories are complete. The implication
(3)$\Rightarrow$(5) follows immediately from Proposition 1.6 and the fact that
$\mathsf{Part}_{\ast}^{S}$ is an essentially algebraic pointed category. To
prove the implication (5)$\Rightarrow$(4), let us suppose that
$\mathsf{Part}_{\ast}^{S}$ has $\mathrm{N}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations and let us consider a finitely
complete pointed category $\mathbb{C}$ and a class of monomorphisms
$\mathcal{M}$ in $\mathbb{C}$ as in (4). We suppose that $\mathbb{C}$ has
$S$-closed $\mathcal{M}$-relations and we must show it has $\mathrm{N}$-closed
$\mathcal{M}$-relations. Let $r\colon R\rightarrowtail X^{n}$ be a relation in
$\mathcal{M}$, $Z$ be an object of $\mathbb{C}$ and

$\left[\begin{array}[]{ccc|c}g_{11}&\dots&g_{1m}&h_{1}\\\
\vdots&&\vdots&\vdots\\\ g_{n1}&\dots&g_{nm}&h_{n}\end{array}\right]$

be an interpretation of $\mathrm{N}$ of type $\mathbb{C}(Z,X)$. We suppose
that, for each $j\in\\{1,\dots,m\\}$, the morphism
$(g_{1j},\dots,g_{nj})\colon Z\to X^{n}$ factors through $r$ and we must show
that $(h_{1},\dots,h_{n})\colon Z\to X^{n}$ also factors through $r$. If
$\mathbb{C}$ is a small category, by the Embedding Theorem 1.10, there exists
a fully faithful embedding
$\varphi\colon\mathbb{C}\hookrightarrow(\mathsf{Part}_{\ast}^{S})^{\mathbb{C}^{\mathrm{op}}}$
which preserves and reflects finite limits and such that, for every
monomorphism $f\in\mathcal{M}$ and every object $A\in\mathbb{C}$,
$\varphi(f)_{A}$ is a closed monomorphism in $\mathsf{Part}_{\ast}^{S}$. By
Proposition 1.8, $\varphi(r)_{A}$ is a strong relation for every object
$A\in\mathbb{C}$. Since $\mathsf{Part}_{\ast}^{S}$ is supposed to have
$\mathrm{N}$-closed $\mathcal{M}_{\mathrm{strong}}$-relations, this means that
$\varphi((h_{1},\dots,h_{n}))_{A}$ factors through $\varphi(r)_{A}$ for every
$A\in\mathbb{C}$. Therefore, the pullback of $\varphi(r)$ along
$\varphi((h_{1},\dots,h_{n}))$ is an isomorphism since each of its component
is. Thus, since $\varphi$ is fully faithful and preserves finite limits, the
pullback of $r$ along $(h_{1},\dots,h_{n})$ is $\mathbb{C}$ is an isomorphism,
proving that $(h_{1},\dots,h_{n})$ factors through $r$. If $\mathbb{C}$ is not
small, a similar argument can still be applied. Indeed, looking at the proof
in [19] of Theorem 1.9, we can still construct
$(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebraic structures on
$\mathbb{C}(Z,X)$, $\mathbb{C}(Z,X^{n})$ and $\mathbb{C}(Z,R)$. This can be
done in such a way that $\mathbb{C}(Z,X^{n})$ is isomorphic as
$(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebra to the $n$-fold power of
$\mathbb{C}(Z,X)$ via the canonical isomorphism
$\mathbb{C}(Z,X^{n})\cong\mathbb{C}(Z,X)^{n}$ and such that composition with
$r$ gives a closed monomorphism
$\mathbb{C}(Z,R)\rightarrowtail\mathbb{C}(Z,X^{n})$. We can thus see
$\mathbb{C}(Z,R)$ as a closed sub-partial algebra of $\mathbb{C}(Z,X)^{n}$
containing $(g_{1},\dots,g_{n})\in\mathbb{C}(Z,X)^{n}$ if and only if the
morphism $(g_{1},\dots,g_{n})\colon Z\to X^{n}$ factors through $r$. By
Proposition 1.8, this thus defines a strong $n$-ary relation in
$\mathsf{Part}_{\ast}^{S}$. Therefore this relation is $\mathrm{N}$-closed by
assumption. Considering the free $(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial
algebra $\mathrm{F}_{\ast}^{S}(\\{\ast,x\\})$ on the one element set (notice
that $\\{\ast,x\\}$ is the free pointed set on the one element set $\\{x\\}$),
we get an interpretation

$\left[\begin{array}[]{ccc|c}g^{\prime}_{11}&\dots&g^{\prime}_{1m}&h^{\prime}_{1}\\\
\vdots&&\vdots&\vdots\\\
g^{\prime}_{n1}&\dots&g^{\prime}_{nm}&h^{\prime}_{n}\end{array}\right]$

of $\mathrm{N}$ of type
$\mathsf{Part}_{\ast}^{S}(\mathrm{F}_{\ast}^{S}(\\{\ast,x\\}),\mathbb{C}(Z,X))$
where $g^{\prime}_{ij}(x)=g_{ij}$ and $h^{\prime}_{i}(x)=h_{i}$ for all
$i\in\\{1,\dots,n\\}$ and $j\in\\{1,\dots,m\\}$. Since $(g_{1j},\dots,g_{nj})$
factors through $r$ for each $j\in\\{1,\dots,m\\}$, we know that the morphisms
$(g^{\prime}_{1j},\dots,g^{\prime}_{nj})\colon\mathrm{F}_{\ast}^{S}(\\{\ast,x\\})\to\mathbb{C}(Z,X)^{n}$
factor through $\mathbb{C}(Z,R)$. We conclude from this that
$(h^{\prime}_{1},\dots,h^{\prime}_{n})$ also factors through $\mathbb{C}(Z,R)$
meaning that $(h_{1},\dots,h_{n})$ factors through $r$ as required. We have
therefore already proved the implications
(2)$\Leftrightarrow$(3)$\Leftrightarrow$(4)$\Leftrightarrow$(5)$\Rightarrow$(1).

Let us now prove (1)$\Rightarrow$(6). If $S$ is trivial, by the equivalence
(2)$\Leftrightarrow$(9) of Theorem 2.1, it suffices to choose $q$ to be the
constant term $0$. If $S$ is not trivial, we rely on the algorithm to decide
$S\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{N}$ from [13] recalled in Section
1. We denote the entries of the matrix $\mathrm{N}$ as in

$\mathrm{N}=\left[\begin{array}[]{ccc|c}x_{11}&\dots&x_{1m}&x_{1\,m+1}\\\
\vdots&&\vdots&\vdots\\\ x_{n1}&\dots&x_{nm}&x_{n\,m+1}\end{array}\right]$

where the $x_{ij}$’s belong to $\\{\ast,x_{1},\dots,x_{k}\\}$. To each left
column $c$ of $\mathrm{N}$ (the original ones and the ones added by the
algorithm), we associate an $m$-ary term
$q_{c}\in\mathrm{T}_{\ast}^{S}(\\{y_{1},\dots,y_{m}\\})$ such that, for each
$i\in\\{1,\dots,n\\}$, the equation

$q_{c}(x_{i1},\dots,x_{im})=^{\mathrm{e}}c_{i}$

holds in any $(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebra, where $c_{i}$
is the $i^{\textrm{th}}$ entry of $c$ and $\ast$ is interpreted as $0$. For
the $j^{\textrm{th}}$ original left column $c^{j}$ of $\mathrm{N}$ (for
$j\in\\{1,\dots,m\\}$), we simply let $q_{c^{j}}$ be $y_{j}$. For the first
added column $c^{j+1}$ of $\ast$’s, we take $q_{c^{j+1}}$ to be the term $0$.
Now, suppose at some point of the algorithm, we have defined $q_{c}$ for all
the left columns of the current $\mathrm{N}$ and we are adding the right
column $c^{B,m^{\prime}+1}$ of a row-wise interpretation $B$ of type
$(\\{\ast,x_{1},\dots,x_{k}\\},\dots,\\{\ast,x_{1},\dots,x_{k}\\})$ of a
matrix $\mathrm{M}^{\prime}\in\mathrm{matr}_{\ast}(n,m^{\prime},k^{\prime})$
whose rows are rows of a common matrix $\mathrm{M}\in
S\cap\mathrm{matr}_{\ast}(n^{\prime},m^{\prime},k^{\prime})$ (for integers
$n^{\prime}>0$, $m^{\prime},k^{\prime}\geqslant 0$) and such that the left
columns $c^{B,j}$ of $B$ (for each $j\in\\{1,\dots,m^{\prime}\\}$), but not
its right column $c^{B,m^{\prime}+1}$, can be found among the left columns of
$\mathrm{N}$. We then define

$q_{c^{B,m^{\prime}+1}}=p^{\mathrm{M}}(q_{c^{B,1}},\dots,q_{c^{B,m^{\prime}}}).$

For $i\in\\{1,\dots,n\\}$, the $i^{\textrm{th}}$ row of $B$ is of the form

$\left[\begin{array}[]{ccc|c}f(x^{\prime}_{i^{\prime}1})&\dots&f(x^{\prime}_{i^{\prime}m^{\prime}})&f(x^{\prime}_{i^{\prime}\,m^{\prime}+1})\end{array}\right]$

for a pointed function
$f\colon\\{\ast,x_{1},\dots,x_{k^{\prime}}\\}\to\\{\ast,x_{1},\dots,x_{k}\\}$
and an $i^{\prime}\in\\{1,\dots,n^{\prime}\\}$ and where

$\left[\begin{array}[]{ccc|c}x^{\prime}_{i^{\prime}1}&\dots&x^{\prime}_{i^{\prime}m^{\prime}}&x^{\prime}_{i^{\prime}\,m^{\prime}+1}\end{array}\right]$

is the $i^{\prime\textrm{th}}$ row of $\mathrm{M}$. Thus, in any
$(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial algebra, the equations

$\displaystyle c^{B,m^{\prime}+1}_{i}$
$\displaystyle=^{\mathrm{e}}f(x^{\prime}_{i^{\prime}\,m^{\prime}+1})$
$\displaystyle=^{\mathrm{e}}p^{\mathrm{M}}(f(x^{\prime}_{i^{\prime}1}),\dots,f(x^{\prime}_{i^{\prime}m^{\prime}}))$
$\displaystyle=^{\mathrm{e}}p^{\mathrm{M}}(c^{B,1}_{i},\dots,c^{B,m^{\prime}}_{i})$
$\displaystyle=^{\mathrm{e}}p^{\mathrm{M}}(q_{c^{B,1}}(x_{i1},\dots,x_{im}),\dots,q_{c^{B,m^{\prime}}}(x_{i1},\dots,x_{im}))$
$\displaystyle=^{\mathrm{e}}q_{c^{B,m^{\prime}+1}}(x_{i1},\dots,x_{im})$

hold, completing the construction of the $q_{c}$’s. But this immediately
proves (1)$\Rightarrow$(6) since, if
$S\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{N}$ holds, the algorithm says that
the right column of $\mathrm{N}$ has been added by the algorithm to its left
columns.

To conclude the first list of equivalences, it remains to show
(6)$\Rightarrow$(5). Supposing (6), we get a forgetful functor
$U\colon\mathsf{Part}_{\ast}^{S}\to\mathsf{Part}_{\ast}^{\mathrm{N}}$. In view
of the construction of small limits in categories of partial algebras, it is
routine to show that $U$ preserves them. In order to prove (5), let us
consider a strong monomorphism $r\colon R\rightarrowtail X^{n}$ in
$\mathsf{Part}_{\ast}^{S}$, a $(\Sigma_{\ast}^{S},E_{\ast}^{S})$-partial
algebra $Z$ and an interpretation

$\left[\begin{array}[]{ccc|c}g_{11}&\dots&g_{1m}&h_{1}\\\
\vdots&&\vdots&\vdots\\\ g_{n1}&\dots&g_{nm}&h_{n}\end{array}\right]$

of $\mathrm{N}$ of type $\mathsf{Part}_{\ast}^{S}(Z,X)$. Let us suppose that
for each $j\in\\{1,\dots,m\\}$, the morphism $(g_{1j},\dots,g_{nj})\colon Z\to
X^{n}$ factors through $r$. Since by Proposition 1.4,
$\mathsf{Part}_{\ast}^{\mathrm{N}}$ has $\mathrm{N}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations, applying the functor $U$, we get
that

$(U(h_{1}),\dots,U(h_{n}))\colon U(Z)\to U(X)^{n}$

(which is (isomorphic to) $U((h_{1},\dots,h_{n}))\colon U(Z)\to U(X^{n})$)
factors through $U(r)$. Therefore, the pullback $r^{\prime}$ of $r$ along
$(h_{1},\dots,h_{n})$ is sent by $U$ to an isomorphism, and so it is
bijective. So $r^{\prime}$ is an epimorphism which, being a pullback of the
strong monomorphism $r$, is also a strong monomorphism. It is thus an
isomorphism, which shows that $(h_{1},\dots,h_{n})$ factors through $r$ as
desired.

Let us now consider the case where $S\subseteq\mathrm{matr}$,
$\mathrm{N}\in\mathrm{matr}$ and $m>0$. The equivalence
(1)$\Leftrightarrow$(7) has been proved in [13] using the assumption $m>0$.
The other equivalences can be proved analogously as in the pointed case above.
For the proof of (11)$\Rightarrow$(10), we separate it in two cases. It is
analogous to the one of (5)$\Rightarrow$(4) if $S$ is not trivial (to be able
to apply Proposition 1.8). If $S$ is trivial, (10) is always true since $m>0$
(see Theorem 2.1 and Remark 2.2). For the implication (7)$\Rightarrow$(12), it
is analogous to (1)$\Rightarrow$(6) if $S$ is not trivial. If $S$ is trivial,
since $m>0$ and in view of the equivalence (2)$\Leftrightarrow$(19) of Theorem
2.1, one can choose $q$ to be the term $y_{1}$. ∎

######  Remark 2.4.

Let us now say a word on the case where $S\subseteq\mathrm{matr}$,
$\mathrm{N}\in\mathrm{matr}$ and $m=0$ in the above theorem. Using Theorem 2.1
and Remark 2.2, the statements (1), (2), (3), (4), (5), (6), (8), (9) and (11)
of Theorem 2.3 are in that case all equivalent to the condition that $S$ is
trivial. Besides, the statements (7), (10) and (12) of Theorem 2.3 are in that
case equivalent to the condition that $S$ contains a matrix with no left
columns.

######  Open question 2.5.

We leave open the question whether the statements of Theorem 2.3 are further
equivalent to $S\Rightarrow_{\mathrm{ess\,\,alg}_{\ast}}\mathrm{N}$ (in the
general case) and to $S\Rightarrow_{\mathrm{ess\,\,alg}}\mathrm{N}$ (in the
case $S\subseteq\mathrm{matr}$, $\mathrm{N}\in\mathrm{matr}$ and $m>0$) with
the obvious meaning of these notations. The fact that we have been unable yet
to prove or disprove this reduction is closely linked with the fact that we do
not know yet if the property of being Mal’tsev (or having $\mathrm{M}$-closed
relations for a general matrix $\mathrm{M}$) is stable under the pro-
completion of a finitely complete (pointed) category, see [20].

As a consequence of Theorem 2.3, one can now write proofs of implications of
matrix properties in another way. In [13, 16], lex-tableaux and
$\text{lex}_{\ast}$-tableaux were used to represent such proofs. For instance,
if $\mathrm{Ari}$ and $\mathrm{Maj}$ are the arithmetical and majority
matrices from Section 1, a proof of the implication
$\mathrm{Ari}\Rightarrow_{\mathrm{lex}}\mathrm{Maj}$ can been displayed as the
following lex-tableau:

$\begin{array}[]{ccc|c||ccc|c}x_{1}&x_{2}&x_{2}&x_{1}&x_{1}&x_{1}&x_{2}&x_{1}\\\
x_{2}&x_{2}&x_{1}&x_{1}&x_{1}&x_{2}&x_{1}&x_{1}\\\
x_{1}&x_{2}&x_{1}&x_{1}&x_{2}&x_{1}&x_{1}&x_{1}\\\ \hline\cr
x_{2}&x_{1}&x_{1}&x_{2}&x_{2}&&&\\\ x_{1}&x_{1}&x_{2}&x_{2}&x_{2}&&&\\\
x_{1}&x_{2}&x_{1}&x_{1}&x_{1}&&&\\\ \hline\cr
x_{1}&x_{2}&x_{2}&x_{1}&x_{1}&&&\\\ x_{2}&x_{2}&x_{1}&x_{1}&x_{1}&&&\\\
x_{1}&x_{1}&x_{1}&x_{1}&x_{1}&&&\\\ \end{array}$

The first block on the left represents the matrix $\mathrm{Ari}$, while the
first block on the right represents the matrix $\mathrm{Maj}$. Below each
horizontal line, a step of the algorithm to decide
$\mathrm{Ari}\Rightarrow_{\mathrm{lex}}\mathrm{Maj}$ is displayed. So, for the
second block, a row-wise interpretation of a matrix whose rows are rows of
$\mathrm{Ari}$ (the matrix $\mathrm{Ari}$ itself in this case) is drawn, where
each left column belongs to the left columns of $\mathrm{Maj}$ but not its
right column. On the right, this right column is added to the extended
$\mathrm{Maj}$. In the third block, again a row-wise interpretation of
$\mathrm{Ari}$ is displayed on the left and its right column is added to the
extended $\mathrm{Maj}$ on the right. Since this is the right column of
$\mathrm{Maj}$, this concludes the proof of
$\mathrm{Ari}\Rightarrow_{\mathrm{lex}}\mathrm{Maj}$.

One can transform this proof into a ternary term
$q\in\mathrm{T}^{\mathrm{Ari}}(\\{y_{1},y_{2},y_{3}\\})$ proving the
implication $\mathrm{Ari}\Rightarrow_{\mathrm{lex}}\mathrm{Maj}$ via the
equivalence (7)$\Leftrightarrow$(12) of Theorem 2.3. To extract this term $q$
from the above lex-tableau, one follows the proof of (7)$\Rightarrow$(12),
analogous to the proof of (1)$\Rightarrow$(6). To the first three left columns
of $\mathrm{Maj}$, one associates the variables $y_{1},y_{2},y_{3}$
respectively. To the first added column

$\left[\begin{array}[]{c}x_{2}\\\ x_{2}\\\ x_{1}\end{array}\right]$

one associates the term $p(y_{3},y_{1},y_{2})$ where $p=p^{\mathrm{Ari}}$ is
the term from $\mathrm{Ari}$, i.e., partial algebras in
$\mathsf{Part}^{\mathrm{Ari}}$ satisfy the equations

$\begin{cases}p(x_{1},x_{2},x_{2})=^{\mathrm{e}}x_{1}\\\
p(x_{2},x_{2},x_{1})=^{\mathrm{e}}x_{1}\\\
p(x_{1},x_{2},x_{1})=^{\mathrm{e}}x_{1}.\end{cases}$ (7)

Finally, the term $q$, corresponding to the second added column is

$q(y_{1},y_{2},y_{3})=p(y_{2},p(y_{3},y_{1},y_{2}),y_{3}).$

At each step, the term is obtained applying $p$ to the terms corresponding to
the left columns of the row-wise interpretation. To prove
$\mathrm{Ari}\Rightarrow_{\mathrm{lex}}\mathrm{Maj}$ it is actually enough to
check that, from the equations (7), one has the equations

$q(x_{1},x_{1},x_{2})=^{\mathrm{e}}p(x_{1},p(x_{2},x_{1},x_{1}),x_{2})=^{\mathrm{e}}p(x_{1},x_{2},x_{2})=^{\mathrm{e}}x_{1},$
$q(x_{1},x_{2},x_{1})=^{\mathrm{e}}p(x_{2},p(x_{1},x_{1},x_{2}),x_{1})=^{\mathrm{e}}p(x_{2},x_{2},x_{1})=^{\mathrm{e}}x_{1}$

and

$q(x_{2},x_{1},x_{1})=^{\mathrm{e}}p(x_{1},p(x_{1},x_{2},x_{1}),x_{1})=^{\mathrm{e}}p(x_{1},x_{1},x_{1})=^{\mathrm{e}}x_{1}$

corresponding to the matrix $\mathrm{Maj}$.

Since both rows of $\mathrm{Mal}$ appear in $\mathrm{Ari}$, it is
straightforward to prove $\mathrm{Ari}\Rightarrow_{\mathrm{lex}}\mathrm{Mal}$
using the above term proofs. As shown in [16], one also has
$\\{\mathrm{Maj},\mathrm{Mal}\\}\Rightarrow_{\mathrm{lex}}\mathrm{Ari}$. In
the language of terms, this can be done by considering

$q(x,y,z)=p^{\mathrm{Mal}}(x,p^{\mathrm{Maj}}(z,x,y),z)$

where $p^{\mathrm{Mal}}$ and $p^{\mathrm{Maj}}$ are terms satisfying the
existence equations from $\mathrm{Mal}$ and $\mathrm{Maj}$ respectively. This
term $q$ indeed satisfies the existence equations from $\mathrm{Ari}$ since

$q(x,y,y)=^{\mathrm{e}}p^{\mathrm{Mal}}(x,p^{\mathrm{Maj}}(y,x,y),y)=^{\mathrm{e}}p^{\mathrm{Mal}}(x,y,y)=^{\mathrm{e}}x$
$q(y,y,x)=^{\mathrm{e}}p^{\mathrm{Mal}}(y,p^{\mathrm{Maj}}(x,y,y),x)=^{\mathrm{e}}p^{\mathrm{Mal}}(y,y,x)=^{\mathrm{e}}x$
$q(x,y,x)=^{\mathrm{e}}p^{\mathrm{Mal}}(x,p^{\mathrm{Maj}}(x,x,y),x)=^{\mathrm{e}}p^{\mathrm{Mal}}(x,x,x)=^{\mathrm{e}}x.$

We have thus re-proved that an arithmetical category is the same thing as a
Mal’tsev majority category. By the equivalence (8)$\Leftrightarrow$(12) of
Theorem 2.3, this also shows that a finitely complete category is _weakly
arithmetical_ (i.e., has $\mathrm{Ari}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations) if and only if it is _weakly
Mal’tsev_ (i.e., has $\mathrm{Mal}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations) and _weakly majority_ (i.e., has
$\mathrm{Maj}$-closed $\mathcal{M}_{\mathrm{strong}}$-relations).

To give an example in the pointed case, let us mention that in [13] we have
shown that the matrix $\mathrm{StrUni}$ is equivalent to the matrix

$\mathrm{StrUni}^{\prime}=\left[\begin{array}[]{ccc|c}x_{1}&x_{1}&\ast&x_{1}\\\
\ast&\ast&x_{1}&x_{1}\\\ x_{1}&\ast&x_{1}&\ast\end{array}\right]$

in the sense that
$\mathrm{StrUni}\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{StrUni}^{\prime}$ and
$\mathrm{StrUni}^{\prime}\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{StrUni}$.
Let us re-prove it here using (partial) terms. The term $p(x,y,z)$
corresponding to $\mathrm{StrUni}$ is associated to the equations

$\begin{cases}p(x,0,0)=^{\mathrm{e}}x\\\ p(y,y,x)=^{\mathrm{e}}x\end{cases}$
(8)

while the term $q(x,y,z)$ corresponding to $\mathrm{StrUni}^{\prime}$ is
associated to the equations

$\begin{cases}q(x,x,0)=^{\mathrm{e}}x\\\ q(0,0,x)=^{\mathrm{e}}x\\\
q(x,0,x)=^{\mathrm{e}}0.\end{cases}$ (9)

From a term $p(x,y,z)$ satisfying the equations (8), we can construct the term

$q(x,y,z)=p(z,p(x,y,0),y)$

satisfying the equations (9). Indeed,

$\begin{cases}q(x,x,0)=^{\mathrm{e}}p(0,p(x,x,0),x)=^{\mathrm{e}}p(0,0,x)=^{\mathrm{e}}x\\\
q(0,0,x)=^{\mathrm{e}}p(x,p(0,0,0),0)=^{\mathrm{e}}p(x,0,0)=^{\mathrm{e}}x\\\
q(x,0,x)=^{\mathrm{e}}p(x,p(x,0,0),0)=^{\mathrm{e}}p(x,x,0)=^{\mathrm{e}}0\end{cases}$

already proving
$\mathrm{StrUni}\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{StrUni}^{\prime}$.
For the other implication, from a term $q(x,y,z)$ satisfying the equations
(9), we can construct the term

$p(x,y,z)=q(q(y,0,x),q(y,0,x),z)$

satisfying the equations (8). Indeed,

$\begin{cases}p(x,0,0)=^{\mathrm{e}}q(q(0,0,x),q(0,0,x),0)=^{\mathrm{e}}q(x,x,0)=^{\mathrm{e}}x\\\
p(y,y,x)=^{\mathrm{e}}q(q(y,0,y),q(y,0,y),x)=^{\mathrm{e}}q(0,0,x)=^{\mathrm{e}}x\end{cases}$

proving
$\mathrm{StrUni}^{\prime}\Rightarrow_{\mathrm{lex}_{\ast}}\mathrm{StrUni}$.

######  Remark 2.6.

Let us make clear that in the above proofs, _partial_ terms are considered. It
was shown in [16] that matrix implications are context sensitive. In
particular, given matrices $\mathrm{M},\mathrm{N}\in\mathrm{matr}$, if one
proves that any variety with $\mathrm{M}$-closed relations has
$\mathrm{N}$-closed relations, this does _not_ imply that
$\mathrm{M}\Rightarrow_{\mathrm{lex}}\mathrm{N}$ in general. An example of
this phenomenon has already been shown in the Introduction. Let us show here
an example in the non-pointed context. We consider the matrices

$\mathrm{Cube}^{\Delta^{*}}_{3}=\left[\begin{array}[]{ccccc|c}x_{1}&x_{1}&x_{1}&x_{2}&x_{2}&x_{1}\\\
x_{1}&x_{2}&x_{2}&x_{1}&x_{1}&x_{1}\\\
x_{2}&x_{1}&x_{2}&x_{1}&x_{2}&x_{1}\end{array}\right]$

and

$\mathrm{Edge}_{3}=\left[\begin{array}[]{cccc|c}x_{2}&x_{2}&x_{1}&x_{1}&x_{1}\\\
x_{2}&x_{1}&x_{2}&x_{1}&x_{1}\\\
x_{1}&x_{1}&x_{1}&x_{2}&x_{1}\end{array}\right].$

It has been shown in [16] (using a computer implementation of the algorithm,
see Figure 2 in [16]) that
$\mathrm{Edge}_{3}\Rightarrow_{\mathrm{lex}}\mathrm{Cube}^{\Delta^{*}}_{3}$
but
$\mathrm{Cube}^{\Delta^{*}}_{3}\nRightarrow_{\mathrm{lex}}\mathrm{Edge}_{3}$
(i.e., the implication
$\mathrm{Cube}^{\Delta^{*}}_{3}\Rightarrow_{\mathrm{lex}}\mathrm{Edge}_{3}$
does _not_ hold). However, it was shown in [4] that varieties with
$\mathrm{Cube}^{\Delta^{*}}_{3}$-closed relations also have
$\mathrm{Edge}_{3}$-closed relations. According to Theorem 1.2, a variety
$\mathbb{V}$ has $\mathrm{Cube}^{\Delta^{*}}_{3}$-closed relations if and only
if its theory has a $5$-ary term $p$ satisfying the equations

$\begin{cases}p(x_{1},x_{1},x_{1},x_{2},x_{2})=x_{1}\\\
p(x_{1},x_{2},x_{2},x_{1},x_{1})=x_{1}\\\
p(x_{2},x_{1},x_{2},x_{1},x_{2})=x_{1}.\end{cases}$

Such a term has been called a _$\Delta^{*}$ -special cube term_ in [4],
explaining the notation $\mathrm{Cube}^{\Delta^{*}}_{3}$. Analogously, a
variety $\mathbb{V}$ has $\mathrm{Edge}_{3}$-closed relations if and only if
its theory has a $4$-ary term $q$ satisfying the equations

$\begin{cases}q(x_{2},x_{2},x_{1},x_{1})=x_{1}\\\
q(x_{2},x_{1},x_{2},x_{1})=x_{1}\\\
q(x_{1},x_{1},x_{1},x_{2})=x_{1}.\end{cases}$

Such a term has been called a _$3$ -edge term_ in [4], justifying the notation
$\mathrm{Edge}_{3}$. Although
$\mathrm{Cube}^{\Delta^{*}}_{3}\nRightarrow_{\mathrm{lex}}\mathrm{Edge}_{3}$,
it was shown in [4] that one can construct a $3$-edge term $q$ from a
$\Delta^{*}$-special cube term $p$ as follows:

$q(x,y,z,w)=p(p(y,z,z,w,w),z,p(x,z,z,z,z),w,p(x,w,z,w,z)).$

One can indeed compute

$\displaystyle q(x_{2},x_{2},x_{1},x_{1})$
$\displaystyle=p(p(x_{2},x_{1},x_{1},x_{1},x_{1}),x_{1},p(x_{2},x_{1},x_{1},x_{1},x_{1}),x_{1},p(x_{2},x_{1},x_{1},x_{1},x_{1}))$
$\displaystyle=x_{1},$ $\displaystyle q(x_{2},x_{1},x_{2},x_{1})$
$\displaystyle=p(p(x_{1},x_{2},x_{2},x_{1},x_{1}),x_{2},p(x_{2},x_{2},x_{2},x_{2},x_{2}),x_{1},p(x_{2},x_{1},x_{2},x_{1},x_{2}))$
$\displaystyle=p(x_{1},x_{2},x_{2},x_{1},x_{1})$ $\displaystyle=x_{1}$

and

$\displaystyle q(x_{1},x_{1},x_{1},x_{2})$
$\displaystyle=p(p(x_{1},x_{1},x_{1},x_{2},x_{2}),x_{1},p(x_{1},x_{1},x_{1},x_{1},x_{1}),x_{2},p(x_{1},x_{2},x_{1},x_{2},x_{1}))$
$\displaystyle=p(x_{1},x_{1},x_{1},x_{2},x_{2})$ $\displaystyle=x_{1}.$

However, this proof does _not_ extend to the partial context since in that
case $p(x_{2},x_{1},x_{1},x_{1},x_{1})$ in the first equation, and so
$q(x_{2},x_{2},x_{1},x_{1})$, are not defined in general.

Another consequence of Theorem 2.3 is that one can completely describe the
posets of collections of categories of the form
$\mathrm{mclex}^{\mathrm{strong}}\\{\mathrm{M}\\}$ or
$\mathrm{mclex}_{\ast}^{\mathrm{strong}}\\{\mathrm{M}\\}$ for matrices
$\mathrm{M}$ of relatively small dimensions. We consider these posets ordered
by inclusion. These posets are almost isomorphic to the ones where we consider
$\mathcal{M}_{\mathrm{all}}$ instead of $\mathcal{M}_{\mathrm{strong}}$, the
only difference concerns trivial matrices (see Remarks 2.2 and 2.4). One can
thus use a computer implementation of the algorithms recalled in Section 1 to
describe these posets. Several of these posets have been displayed in [13, 16]
for the case $\mathcal{M}_{\mathrm{all}}$. For instance, derived from Figure 1
in [13], here is the Hasse diagram of the poset of collections of categories
of the form $\mathrm{mclex}_{\ast}^{\mathrm{strong}}\\{\mathrm{M}\\}$ where
$\mathrm{M}$ runs among the matrices in $\mathrm{matr}_{\ast}(2,3,2)$.

$\textstyle{\\{\text{all finitely complete pointed
categories}\\}}$$\textstyle{\\{\text{weakly unital
categories}\\}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\\{\text{weakly
subtractive
categories}\\}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\\{\text{weakly
strongly unital
categories}\\}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\\{\text{weakly
Mal'tsev pointed
categories}\\}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\\{\text{categories
equivalent to
}\mathsf{1}\\}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

In that diagram, a weakly unital category (respectively a weakly subtractive
category, a weakly strongly unital category or a weakly Mal’tsev pointed
category) is a finitely complete pointed category with $\mathrm{M}$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations where
$\mathrm{M}=\mathrm{Uni},\mathrm{Sub},\mathrm{StrUni},\mathrm{Mal}$
respectively.

To conclude, let us mention that if one takes $S=\\{[x_{1}|x_{1}]\\}$ in
Theorem 2.3, one obtains the following description of anti-trivial matrix
sets. Extending the terminology from [13, 16], we say that a matrix set
$S\subseteq\mathrm{matr}_{\ast}$ is _anti-trivial_ if all finitely complete
pointed categories have $S$-closed relations.

######  Corollary 2.7.

For a matrix set $S\subseteq\mathrm{matr}_{\ast}$, the following conditions
are equivalent:

  1. (1)

$S$ is anti-trivial, i.e., all finitely complete pointed categories have
$S$-closed relations;

  2. (2)

all matrices $\mathrm{M}$ in $S$ are anti-trivial in the sense of [13], i.e.,
all finitely complete pointed categories have $\mathrm{M}$-closed relations;

  3. (3)

all finitely complete pointed categories have $S$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations;

  4. (4)

all essentially algebraic pointed categories have $S$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations;

  5. (5)

for every finitely complete pointed category $\mathbb{C}$ and every class
$\mathcal{M}$ of monomorphisms in $\mathbb{C}$ stable under pullbacks,
$\mathbb{C}$ has $S$-closed $\mathcal{M}$-relations;

  6. (6)

$\mathsf{Set}_{\ast}$ has $S$-closed relations;

  7. (7)

for all matrices $\mathrm{M}\in S$, all the entries of the right column of
$\mathrm{M}$ are $\ast$’s or this right column of $\mathrm{M}$ can be found
among its left columns.

Moreover, if $S\subseteq\mathrm{matr}$, these are further equivalent to the
following conditions:

  1. (8)

all finitely complete categories have $S$-closed relations;

  2. (9)

all matrices $\mathrm{M}$ in $S$ are anti-trivial in the sense of [16], i.e.,
all finitely complete categories have $\mathrm{M}$-closed relations;

  3. (10)

all finitely complete categories have $S$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations;

  4. (11)

all essentially algebraic categories have $S$-closed
$\mathcal{M}_{\mathrm{strong}}$-relations;

  5. (12)

for every finitely complete category $\mathbb{C}$ and every class
$\mathcal{M}$ of monomorphisms in $\mathbb{C}$ stable under pullbacks,
$\mathbb{C}$ has $S$-closed $\mathcal{M}$-relations;

  6. (13)

$\mathsf{Set}$ has $S$-closed relations;

  7. (14)

for all matrices $\mathrm{M}\in S$, the right column of $\mathrm{M}$ can be
found among its left columns.

###### Proof.

Let us first note that the equivalences
(2)$\Leftrightarrow$(6)$\Leftrightarrow$(7) have been proved in [13].
Moreover, if $S\subseteq\mathrm{matr}$, (2)$\Leftrightarrow$(9) has been shown
also in [13] while (9)$\Leftrightarrow$(13)$\Leftrightarrow$(14) were proved
in [16]. In addition, we remark that (1)$\Leftrightarrow$(2) and
(8)$\Leftrightarrow$(9) if $S\subseteq\mathrm{matr}$ are obvious. In view of
that, we can suppose without loss of generality that $S=\\{\mathrm{N}\\}$ for
some $\mathrm{N}\in\mathrm{matr}_{\ast}$.

Now, note that if $\mathrm{N}\in\mathrm{matr}$ and $\mathrm{N}$ has no left
columns, all statements in the theorem are obviously false (and thus
equivalent), so that we can exclude this case without loss of generality. Now
it suffices to apply Theorem 2.3 with $S^{\prime}=\\{[x_{1}|x_{1}]\\}$; it is
straightforward to show that each of its equivalent conditions becomes
(equivalent to) the statements listed above. For statements (6) (respectively
(13)), it is easy to see that $\mathsf{Part}_{\ast}^{S^{\prime}}$
(respectively $\mathsf{Part}^{S^{\prime}}$) for that $S^{\prime}$ is
equivalent to $\mathsf{Set}_{\ast}$ (respectively to $\mathsf{Set}$) and any
monomorphism is strong in those categories. Statements (5) and (12) many seem
stronger than those coming from Theorem 2.3 due to the conditions on
$\mathcal{M}$, but they can still be easily seen to be implied by (7) and (14)
respectively. ∎

## References

  * [1] J. Adámek, H. Herrlich and J. Rosický, Essentially equational categories, Cah. Topol. Géom. Différ. Catég. 29 (1988), 175–192.
  * [2] J. Adámek and J. Rosický, Locally presentable and accessible categories, London Math. Soc. 189 (1994).
  * [3] M. Barr, P. A. Grillet and D.H. van Osdol, Exact categories and categories of sheaves, Lect. Notes Math. 236 (1971).
  * [4] J. Berman, P. Idziak, P. Marković, R. McKenzie, M. Valeriote and R. Willard, Varieties with few subalgebras of powers, Trans. Am. Math. Soc. 362 (2010), 1445–1473.
  * [5] F. Borceux, Handbook of Categorical Algebra 1, Encycl. Math. Appl. (Cambridge Uni. Press) 50 (1994).
  * [6] D. Bourn, Mal’cev categories and fibration of pointed objects, Appl. Categ. Struct. 4 (1996), 307–327.
  * [7] P. Burmeister, Algebraic theory of quasivarieties of heterogeneous partial algebras, Stud. Log. 78 (2004), 129–153.
  * [8] A. Carboni, J. Lambek and M.C. Pedicchio, Diagram chasing in Mal’cev categories, J. Pure Appl. Algebra 69 (1991), 271–284.
  * [9] A. Carboni, M.C. Pedicchio and N. Pirovano, Internal graphs and internal groupoids in Mal’cev categories, CMS Conf. Proc. 13 (1992), 97–109.
  * [10] N. Egner, P.-A. Jacqmin and N. Martins-Ferreira, A syntactic characterization of weakly Mal’tsev categories, to appear in Theory Appl. Categ..
  * [11] P. Gabriel and P. Ulmer, Lokal präsentierbare Kategorien, Lect. Notes Math. 221 (1971).
  * [12] M. Hoefnagel, Majority categories, Theory Appl. Categ. 34 (2019), 249–268.
  * [13] M. Hoefnagel and P.-A. Jacqmin, Matrix taxonomy and Bourn localization, Appl. Categ. Struct. 30 (2022), 1305–1340.
  * [14] M. Hoefnagel and P.-A. Jacqmin, When a matrix condition implies the Mal’tsev property, arXiv:2208.09516v1.
  * [15] M. Hoefnagel and P.-A. Jacqmin, A note on the atomicity of arithmeticity, submitted for publication in Theory Appl. Categ..
  * [16] M. Hoefnagel, P.-A. Jacqmin and Z. Janelidze, The matrix taxonomy of finitely complete categories, Theory Appl. Categ. 38 (2022), 737–790.
  * [17] M. Hoefnagel, P.-A. Jacqmin, Z. Janelidze and E. van der Walt, On binary matrix properties, to appear in Quaest. Math..
  * [18] H. Höft, A characterization of strong homomorphisms, Coll. Math. 28 (1973), 189–193.
  * [19] P.-A. Jacqmin, Partial algebras and embedding theorems for (weakly) Mal’tsev categories and matrix conditions, Cahiers Topologie Géom. Différentielle Catég. 60 (2019), 365–403.
  * [20] P.-A. Jacqmin and Z. Janelidze, On stability of exactness properties under the pro-completion, Advances in Mathematics 377 (2021), 107484.
  * [21] Z. Janelidze, Subtractive categories, Appl. Categ. Struct. 13 (2005), 343–350.
  * [22] Z. Janelidze, Closedness properties of internal relations I: A unified approach to Mal’tsev, unital and subtractive categories, Theory Appl. Categ. 16 (2006), 236–261.
  * [23] Z. Janelidze, Closedness properties of internal relations II: Bourn localization, Theory Appl. Categ. 16 (2006), 262–282.
  * [24] Z. Janelidze and N. Martins-Ferreira, Weakly Mal’tsev categories and strong relations, Theory Appl. Categ. 27 (2012), 65–79.
  * [25] A.I. Mal’tsev, On the general theory of algebraic systems, Mat. Sbornik 35 (1954), 3–20 (in Russian); English translation: Amer. Math. Soc. Trans. 27 (1963), 125–142.
  * [26] N. Martins-Ferreira, Low-dimensional internal categorical structures in weakly Mal’cev sesquicategories, PhD Thesis, University of Cape Town (2008).
  * [27] N. Martins-Ferreira, Weakly Mal’cev categories, Theory Appl. Categ. 21 (2008), 91–117.
  * [28] M.C. Pedicchio, Arithmetical categories and commutator theory, Appl. Categ. Structures 4 (1996), 297–305.
  * [29] J. Riguet, Relations binaires, fermetures, correspondances de Galois, Bull. Soc. Math. France 76 (1948), 114–155.
  * [30] A. Ursini, On subtractive varieties, I, Algebra Universalis 31 (1994), 204–222.

Email: |<EMAIL_ADDRESS>
---|---
|<EMAIL_ADDRESS>