# Matrix taxonomy and Bourn localization

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  Institut de Recherche en Mathématique et Physique,
Université catholique de Louvain, Chemin du Cyclotron 2, B 1348 Louvain-la-
Neuve, Belgium Centre for Experimental Mathematics, Department of Mathematical
Sciences, Stellenbosch University, Private Bag X1 Matieland 7602, South Africa

###### Abstract

In a recent paper [13], an algorithm has been presented for determining
implications between a particular kind of category theoretic property
represented by matrices — the so called ‘matrix properties’. In this paper we
extend this algorithm to include matrix properties involving pointedness of a
category, such as the properties of a category to be unital, strongly unital
or subtractive, for example. Moreover, this extended algorithm can also be
used to determine whether a given matrix property is the Bourn localization of
another, thus leading to new characterizations of Mal’tsev, majority and
arithmetical categories. Using a computer implementation of our algorithm, we
can display all such properties given by matrices of fixed dimensions, grouped
according to their Bourn localizations, as well as the implications between
them.

2020 Mathematics Subject Classification: 03B35, 18E13, 18-08, 08B05, 68V20,
03C35 (primary); 68V05, 18A20, 18A35, 18B15, 08C05 (secondary).

Keywords: matrix property, Bourn localization, fibration of points, unital
category, Mal’tsev category, arithmetical category.

## Introduction

In this paper we are concerned with _closedness properties of internal
relations_ [18], which are also simply referred to as ‘matrix properties’. The
term ‘matrix property’ derives itself from the presentation of these
properties, which for our purposes, may always be presented simply as an
extended matrix whose entries are in the set $\\{\ast,x_{1},x_{2},\dots\\}$.
Here the symbols $x_{1},x_{2},\dots$ represent variables, and $\ast$
represents a constant symbol. For instance, the property of a finitely
complete category to be a Mal’tsev category [5, 6] is equivalent to the
requirement that (each binary internal relation in) the category satisfies the
matrix property determined by the matrix

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

An extended matrix, such as the one above, is said to be _non-pointed_ if it
does not contain $\ast$ as an entry. Other examples of categorical properties
which are captured by a non-pointed matrix property include the property of a
category to be a majority category [8] (see also [10]) as well as the property
to be a (finitely complete) arithmetical category [20]. For matrices
containing $\ast$’s, one also needs the category to be pointed in order to
state the corresponding matrix property. Therefore, in general, each extended
matrix whose entries are in the set $\\{\ast,x_{1},x_{2},\dots\\}$ gives rise
to a matrix property on finitely complete pointed categories. In addition to
the restriction to the pointed context of the above mentioned properties, one
can cite the properties to be a unital [4], strongly unital [4] or subtractive
category [17] as examples.

In the literature, it has been shown that some matrix properties follow from a
conjunction of others: a finitely complete category is arithmetical if and
only if it is both Mal’tsev and a majority category (see [13, 7, 8]).
Furthermore, a finitely complete pointed category is strongly unital if and
only if it is unital and subtractive [17]. In the non-pointed context, an
explicit algorithm has been developed in [13] which decides whether a
conjunction of non-pointed matrix properties implies another one; however, the
pointed case was not considered. The first aim of this paper is to treat this
case and give an algorithm for determining whether a conjunction of matrix
properties on finitely complete pointed categories implies another one. In
particular, our algorithm can decide when a single matrix property implies
another. We have implemented this algorithm on a computer in order to get a
picture of the properties induced by matrices of relatively small dimensions
and the implications between them. See for instance Figure 6 representing all
non-equivalent matrix properties of finitely complete pointed categories given
by $4\times 3$ matrices with entries in $\\{\ast,x_{1}\\}$, as well as the
relationships between them.

These algorithms allow one to compute some finite parts of the posets
$\mathsf{Mclex}_{\ast}$ and $\mathsf{Mclex}$, i.e., the posets of collections
of finitely complete pointed categories (respectively finitely complete
categories) defined via matrix properties (respectively non-pointed matrix
properties) and ordered by inclusion. Since each non-pointed matrix property
can be restricted to the pointed context, one has an order-preserving function

$(-)_{\ast}\colon\mathsf{Mclex}\to\mathsf{Mclex}_{\ast}.$

Using the process of ‘Bourn localization’ (introduced in [19] from the ideas
of [4]), we show that this function $(-)_{\ast}$, regarded as a functor
between preorder categories, has a right adjoint

$\mathsf{Loc}\colon\mathsf{Mclex}_{\ast}\to\mathsf{Mclex}.$

This adjunction enables us to prove that, given two non-trivial non-pointed
matrices, one has the implication between the corresponding matrix properties
in the finitely complete context if and only if the analogous implication
holds in the finitely complete pointed context. Moreover, it is shown in [19]
how to effectively compute the Bourn localization of a (pointed) matrix
property. In our displays of the finite subposets of $\mathsf{Mclex}_{\ast}$
computed via the computer, we can thus group together matrix properties with
the same Bourn localization, see e.g. Figure 4. See also Figure 8 which
represents the subposet of $\mathsf{Mclex}_{\ast}$ whose elements are induced
by $3\times 4$ matrices with entries in $\\{\ast,x_{1},x_{2}\\}$ and such that
their Bourn localization is the collection of Mal’tsev categories. This figure
thus gives many more characterizations of Mal’tsev categories via the
fibration of points in the style of [4]. Moreover, in this way, we also get
new characterizations of finitely complete arithmetical categories as well as
majority categories (see Figures 10 and 11).

The paper is organized as follows:

  * •

Section 1 recalls the relevant concepts necessary for the rest of the paper.

  * •

Section 2 deals with the concept of $S$-injectivity as introduced in [13] in
the non-pointed case.

  * •

Section 3 characterizes those matrix properties (in the pointed context) which
determine the collection of categories equivalent to the terminal category
$\mathbf{1}$ and those which determine the collection of all finitely complete
pointed categories.

  * •

Section 4 studies the posets $\mathsf{Mclex}$ and $\mathsf{Mclex}_{\ast}$ and
the adjunction between them given by restriction and Bourn localization.

  * •

Section 5 derives the main result of this paper, which is the algorithm for
determining implications between matrix properties in the finitely complete
pointed context.

  * •

Section 6 presents some of the computer-assisted results which have been
obtained based on the results of the previous sections.

Lastly, we have presented the results of this paper to be mainly self-
contained. However, as our results are heavily based on [13], we encourage the
reader to read the introduction of [13], in order to see our results here in
context.

##  1 Preliminaries

We will sometimes denote a pointed set $(S,\ast)$ simply by $S$ if there is no
ambiguity on the distinguished element $\ast$ of $S$. Given two objects $X$
and $Y$ in a category $\mathbb{C}$, we write as usual $\mathbb{C}(X,Y)$ for
the set of all morphisms $X\to Y$. When the category $\mathbb{C}$ is pointed,
i.e., when it admits a zero object, we will consider this set
$\mathbb{C}(X,Y)$ as a pointed set with the distinguished element being the
zero morphism $X\to Y$. As it is customary, we write
$\mathbb{C}^{\mathsf{op}}$ for the dual of a category $\mathbb{C}$.

Let us fix throughout this paper an infinite sequence
$x_{1},x_{2},x_{3},\dots$ of pairwise distinct variables. Given integers $n>0$
and $m,k\geqslant 0$, we write $\mathsf{matr}_{\ast}(n,m,k)$ for the set of
all $n\times(m+1)$ matrices whose entries are elements of the free pointed set
on $k$-variables $\\{\ast,x_{1},\dots,x_{k}\\}$, and we write
$\mathsf{matr}_{\ast}$ for the union of all such sets. We will display such an
(extended) matrix $M=[x_{ij}]_{i,j}\in\mathsf{matr}_{\ast}(n,m,k)$ by

$\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]$

and refer to the first $m$ columns as the _left columns_ of $M$. The matrix
formed by the left columns of $M$ is called the _left part_ of $M$, and is
denoted by $M_{\mathsf{l}}$. Similarly, the last column of the matrix is
called the _right column_ of $M$ and is denoted by $M_{\mathsf{r}}$. Given a
sequence $((S_{1},\ast_{1}),\dots,(S_{n},\ast_{n}))$ of pointed sets, a _row-
wise interpretation_ of $M$ of _type_
$((S_{1},\ast_{1}),\dots,(S_{n},\ast_{n}))$, is an $n\times(m+1)$ 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 each row of $M$ a specified pointed
function

$f_{i}\colon\\{\ast,x_{1},\dots,x_{k}\\}\to S_{i}$

where ‘pointed’ means as usual that $f_{i}$ is a morphism in the category
$\mathbf{Set}_{\ast}$ of pointed sets, i.e., that $f_{i}(\ast)=\ast_{i}$.
Given a pointed set $(S,\ast)$, an (ordinary) _interpretation_ (i.e., a ‘non-
row-wise’ interpretation) of $M$ of _type_ $(S,\ast)$ is a row-wise
interpretation of $M$ of type $((S,\ast),\dots,(S,\ast))$ for which
$f_{1}=\dots=f_{n}$.

Given $n>0$, an _internal $n$-ary relation (between objects
$C_{1},\dots,C_{n}$)_ in a category $\mathbb{C}$ is given by a jointly
monomorphic span $(r_{i}\colon R\to C_{i})_{1\leqslant i\leqslant n}$, i.e., a
span such that, for any two parallel morphisms $x,y\colon X\to R$ with an
arbitrary domain $X$, if $r_{i}x=r_{i}y$ for all $i\in\\{1,\dots,n\\}$, then
$x=y$. If $C_{1}=\cdots=C_{n}=C$, we say that the $n$-ary relation
$(r_{i}\colon R\to C)_{1\leqslant i\leqslant n}$ is a relation _on_ the object
$C$. When $\mathbb{C}$ has finite products, an internal $n$-ary relation in
$\mathbb{C}$ can also be viewed as a monomorphism $r\colon R\rightarrowtail
C_{1}\times\dots\times C_{n}$, with $r_{i}=\pi_{i}r$, where $\pi_{i}$ denotes
$i$-th product projection $\pi_{i}\colon C_{1}\times\dots\times C_{n}\to
C_{i}$. Up to identification of monomorphisms into an object with ‘subobjects’
of that object, we can say that $n$-ary relations in $\mathbf{Set}_{\ast}$
between the pointed sets $(C_{1},\ast_{1}),\dots,(C_{n},\ast_{n})$ are
(ordinary) _pointed relations_ , i.e., subsets $R\subseteq
C_{1}\times\cdots\times C_{n}$ containing $(\ast_{1},\dots,\ast_{n})$.

Given an internal $n$-ary relation $r$ of domain $R$ between
$C_{1},\dots,C_{n}$ in a pointed category $\mathbb{C}$, a matrix
$M\in\mathsf{matr}_{\ast}(n,m,k)$ and an object $X$ in $\mathbb{C}$, we say
that $r$ is _compatible_ with a 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 $M$ of type $(\mathbb{C}(X,C_{1}),\dots,\mathbb{C}(X,C_{n}))$ when, if
there exist morphisms $u_{1},\dots,u_{m}\colon X\to R$ such that

$\left[\begin{array}[]{c}g_{1j}\\\ \vdots\\\
g_{nj}\end{array}\right]=\left[\begin{array}[]{c}r_{1}u_{j}\\\ \vdots\\\
r_{n}u_{j}\end{array}\right]$

for each $j\in\\{1,\dots,m\\}$, then there exists a morphism $v\colon X\to R$
such that

$\left[\begin{array}[]{c}h_{1}\\\ \vdots\\\
h_{n}\end{array}\right]=\left[\begin{array}[]{c}r_{1}v\\\ \vdots\\\
r_{n}v\end{array}\right].$

Following [18], we say that $r$ is _strictly $M$-closed over $X$_ when it is
compatible with any row-wise interpretation of $M$ of type
$(\mathbb{C}(X,C_{1}),\dots,\mathbb{C}(X,C_{n}))$ and we say that $r$ is
_strictly $M$-closed_ if it is strictly $M$-closed over every object $X$.
Again according to [18], we say that an $n$-ary relation $(r_{i}\colon R\to
C)_{1\leqslant i\leqslant n}$ on an object $C$ is (non-strictly) _$M$ -closed
over_ an object _$X$_ when it is compatible with any interpretation of $M$ of
type $\mathbb{C}(X,C)$ and we say that $r$ is _$M$ -closed_ if it is
$M$-closed over every object $X$.

######  Theorem 1.1.

[18]. Let $n>0$ and $m,k\geqslant 0$ be integers,
$M\in\mathsf{matr}_{\ast}(n,m,k)$ be an extended matrix and $\mathbb{C}$ be a
finitely complete pointed category. The following statement are equivalent:

  * •

every $n$-ary relation in $\mathbb{C}$ is strictly $M$-closed;

  * •

every $n$-ary relation on an object in $\mathbb{C}$ is $M$-closed.

When the equivalent conditions in the above theorem are satisfied, we say that
$\mathbb{C}$ _has $M$-closed relations_.

We recall that a variety of universal algebras $\mathbb{V}$ is pointed if and
only if its theory contains a unique constant term, i.e., the theory of
$\mathbb{V}$ contains a nullary term $\ast$ and for any two such terms $\ast$
and $\ast^{\prime}$, the theorem $\ast=\ast^{\prime}$ holds in the theory. An
$n$-ary internal relation in a pointed variety $\mathbb{V}$ between the
algebras $A_{1},\dots,A_{n}$ is (up to identification of ‘subobjects’ and
‘monomorphisms’) a pointed relation $R\subseteq A_{1}\times\cdots\times A_{n}$
compatible with the operations of $\mathbb{V}$. Given a matrix
$M\in\mathsf{matr}_{\ast}(n,m,k)$, such a relation $R$ is strictly $M$-closed
if and only if for any row-wise interpretation

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

of $M$ of type $(A_{1},\dots,A_{n})$, we have:

$\left\\{\left[\begin{array}[]{c}a_{11}\\\ \vdots\\\
a_{n1}\end{array}\right],\dots,\left[\begin{array}[]{c}a_{1m}\\\ \vdots\\\
a_{nm}\end{array}\right]\right\\}\subseteq
R\quad\Longrightarrow\quad\left[\begin{array}[]{c}a_{1\,m+1}\\\ \vdots\\\
a_{n\,m+1}\end{array}\right]\in R.$

We can characterize pointed varieties of universal algebras with $M$-closed
relations in the following way.

######  Theorem 1.2.

[18]. Let $n>0$ and $m,k\geqslant 0$ be integers,
$M=[x_{ij}]_{i,j}\in\mathsf{matr}_{\ast}(n,m,k)$ be an extended matrix and
$\mathbb{V}$ be a pointed variety of universal algebras with constant term
$\ast$. Then $\mathbb{V}$ has $M$-closed relations if and only if its theory
admits an $m$-ary term $p$ satisfying the equation

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

in the variables $x_{1},\dots,x_{k}$ for any $i\in\\{1,\dots,n\\}$.

For a given $M\in\mathsf{matr}_{\ast}(n,m,k)$, the collection of all finitely
complete pointed categories with $M$-closed relations is denoted by
$\mathsf{mclex}_{\ast}\\{M\\}$ and is called a _matrix class_ (of finitely
complete pointed categories) in this paper (this notation abbreviates the term
‘matrix class of left exact pointed categories’ in which ‘left exact pointed
category’ is an alternative name for a ‘finitely complete pointed category’).
Note that the word ‘class’ here does not refer to its set-theoretic meaning,
since such a matrix class could not be a class in the set-theoretic sense. By
a _matrix property_ (of a finitely complete pointed category) we mean here the
property to have $M$-closed relations for a given matrix $M$ (as in [16]).

######  Remark 1.3.

Let us warn the reader that the way we display matrices in
$\mathsf{matr}_{\ast}(n,m,k)$ here is slightly different from how they are
displayed in [18, 19] where $0$ is used instead of $\ast$, or from [13] where
integers are used instead of variables and where the right columns have been
omitted. Indeed, in [13], the right column could be made the same for all
matrices without changing the corresponding properties on finitely complete
categories. They could therefore be omitted. In the present paper, the right
column can contain variables and $\ast$’s and thus they cannot, a priori, be
made all the same. This explains why we have to write them explicitly here.
Also, we have preferred $\ast$’s instead of $0$’s not to confuse them with the
$0$’s from [13]. Finally, the choice of variables instead of integers has been
made to stay closer to the original notation as can be found in [18].

We say that a matrix $M\in\mathsf{matr}_{\ast}(n,m,k)$ is _non-pointed_ if it
does not have $\ast$ as one of its entries, and denote the subset of
$\mathsf{matr}_{\ast}$ consisting of all non-pointed matrices by
$\mathsf{matr}$. Borrowing notation from [13], we write $\mathsf{matr}(n,m,k)$
for the set $\mathsf{matr}_{\ast}(n,m,k)\cap\mathsf{matr}$. For a non-pointed
matrix $M$, the notion of a category with $M$-closed relations extends to the
(not necessarily pointed) finitely complete context in the obvious way. As in
[13], we denote by $\mathsf{mclex}\\{M\\}$ the collection of finitely complete
categories with $M$-closed relations. Therefore, for a non-pointed matrix $M$,
$\mathsf{mclex}_{\ast}\\{M\\}$ is the sub-collection of
$\mathsf{mclex}\\{M\\}$ consisting of pointed categories in
$\mathsf{mclex}\\{M\\}$.

By a _matrix set_ we simply mean a subset $S$ of $\mathsf{matr}_{\ast}$. We
denote by $\mathsf{mclex}_{\ast}S$ the collection of all finitely complete
pointed categories which have $M$-closed relations for each matrix $M$ in $S$,
i.e., the intersection $\bigcap_{M\in S}\mathsf{mclex}_{\ast}\\{M\\}$. This
extends the notion of a matrix set from [13] where only matrix sets containing
non-pointed matrices were considered (and up to the change of notation as
explained above). We thus say that a matrix set is _non-pointed_ if it is a
subset of $\mathsf{matr}$. For a non-pointed matrix set $S$, we denote by
$\mathsf{mclex}S$ the collection of all finitely complete categories which
have $M$-closed relations for each matrix $M$ in $S$, i.e., the intersection
$\bigcap_{M\in S}\mathsf{mclex}\\{M\\}$.

######  Example 1.4.

The following table shows on the left some examples of matrices and on the
right the corresponding matrix classes. We denote by $\mathbf{1}$ the category
with a single object and a single morphism. The references indicates where the
corresponding exactness properties have been introduced, possibly in a
different context than that of finitely complete pointed categories.

Extended matrix | Matrix class
---|---
$M=\left[\begin{array}[]{ccc|c}x_{1}&x_{2}&x_{2}&x_{1}\\\ x_{2}&x_{2}&x_{1}&x_{1}\end{array}\right]$ |  (pointed) Mal’tsev categories [5, 6]
$M=\left[\begin{array}[]{ccc|c}x_{2}&x_{1}&x_{1}&x_{1}\\\ x_{1}&x_{2}&x_{1}&x_{1}\\\ x_{1}&x_{1}&x_{2}&x_{1}\end{array}\right]$ |  (pointed) majority categories [8]
$M=\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]$ |  (finitely complete pointed) arithmetical categories [20]
$M=\left[\begin{array}[]{cc|c}x_{1}&\ast&x_{1}\\\ \ast&x_{1}&x_{1}\end{array}\right]$ |  unital categories [4]
$M=\left[\begin{array}[]{ccc|c}x_{1}&\ast&\ast&x_{1}\\\ x_{2}&x_{2}&x_{1}&x_{1}\end{array}\right]$ |  strongly unital categories [4]
$M=\left[\begin{array}[]{cc|c}x_{1}&\ast&x_{1}\\\ x_{1}&x_{1}&\ast\end{array}\right]$ |  subtractive categories [17]
$M=\left[\begin{array}[]{c|c}&x_{1}\end{array}\right]$ |  categories equivalent to $\mathbf{1}$
$M=\left[\begin{array}[]{c|c}&\ast\end{array}\right]$ | all finitely complete pointed categories

######  Example 1.5.

According to Theorem 1.2, the matrix properties in Example 1.4 all determine a
corresponding Mal’tsev condition for pointed varieties of universal algebras.
For instance, the matrix corresponding to the collection of subtractive
categories determines a binary operation $s(x,y)$ which satisfies the
equations $s(x,\ast)=x$ and $s(x,x)=\ast$, i.e., a _subtraction_. On the other
hand, many well known Mal’tsev conditions may be strengthened to a Mal’tsev
condition which is determined by a matrix property. This process has been
described in [13] (see Remark 1.8 therein) and was termed _syntactical
refinement_. To illustrate this process in the pointed context, we consider
the Mal’tsev condition obtained in [9] corresponding to the commutativity of
binary products with coequalizers. For a pointed variety $\mathbb{V}$ (where
$\ast$ is the unique constant symbol) this Mal’tsev condition asserts that
there exists integers $m\geqslant 0$ and $n\geqslant 1$ such that $\mathbb{V}$
admits binary terms $b_{i}(x,y)$ and unary terms $c_{i}(x)$ for each
$1\leqslant i\leqslant m$ and $(m+2)$-ary terms $p_{1},p_{2},\dots,p_{n}$
satisfying the equations:

$\displaystyle p_{1}(x,y,b_{1}(x,y),\dots,b_{m}(x,y))=x,$ $\displaystyle
p_{i}(y,x,b_{1}(x,y),\dots,b_{m}(x,y))=p_{i+1}(x,y,b_{1}(x,y),\dots,b_{m}(x,y))\quad\text{for
each }i\in\\{1,\dots,n-1\\},$ $\displaystyle
p_{n}(y,x,b_{1}(x,y),\dots,b_{m}(x,y))=y,$ $\displaystyle
p_{i}(\ast,\ast,c_{1}(x),\dots,c_{m}(x))=x\quad\text{for each
}i\in\\{1,\dots,n\\}.$

We may strengthen this condition by assuming that $n=1$ and letting $p=p_{1}$,
then the resulting equations reduce to

$\displaystyle p(x,y,b_{1}(x,y),\dots,b_{m}(x,y))$ $\displaystyle=x,$
$\displaystyle p(y,x,b_{1}(x,y),\dots,b_{m}(x,y))$ $\displaystyle=y,$
$\displaystyle p(\ast,\ast,c_{1}(x),\dots,c_{m}(x))$ $\displaystyle=x.$

This condition may be further strengthened by assuming that the terms
$b_{i}(x,y)$ and $c_{i}(x)$ are actually variables so that $m=2$,
$b_{1}(x,y)=x$, $b_{2}(x,y)=y$ and $c_{1}(x)=c_{2}(x)=x$. Doing this reduces
the above equations to

$\displaystyle p(x,y,x,y)$ $\displaystyle=x,$ $\displaystyle p(y,x,x,y)$
$\displaystyle=y,$ $\displaystyle p(\ast,\ast,x,x)$ $\displaystyle=x.$

These equations, in turn, determine a matrix property which is determined by
the matrix

$M=\left[\begin{array}[]{cccc|c}x_{1}&x_{2}&x_{1}&x_{2}&x_{1}\\\
x_{2}&x_{1}&x_{1}&x_{2}&x_{2}\\\ \ast&\ast&x_{1}&x_{1}&x_{1}\\\
\end{array}\right].$

This matrix property is then such that any pointed variety of universal
algebras that satisfies it necessarily has that binary products commute with
coequalizers. This procedure of syntactical refinement can then be applied to
other Mal’tsev conditions which apply to pointed varieties, such as for
instance _anticommutativity_ in the sense of [11] or _normality of
projections_ in the sense of [15]. In the first case, the syntactical
refinement of the Mal’tsev condition appearing in Theorem 3.1 of [11] is only
satisfied by varieties of universal algebras equivalent to the terminal
category $\mathbf{1}$ (i.e., the corresponding matrix is trivial in the sense
of Section 3). In the second case, syntactical refinement of the Mal’tsev
condition appearing in Theorem 3 of [15] yields the matrix

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

whose corresponding Mal’tsev condition on pointed varieties of universal
algebras implies the normality of projections. Using the algorithm presented
in this paper, one can show that the matrix class determined by this matrix is
the collection of subtractive categories, which illustrates the fact that
subtractive categories have normal projections [17].

According to Proposition 1.7 in [19], we know that:

  * •

Given two matrices $M\in\mathsf{matr}_{\ast}(n,m,k)$ and
$N\in\mathsf{matr}_{\ast}(n^{\prime},m,k^{\prime})$ such that every row of $N$
is a row of $M$, then any finitely complete pointed category with $M$-closed
relations also has $N$-closed relations, i.e.,
$\mathsf{mclex}_{\ast}\\{M\\}\subseteq\mathsf{mclex}_{\ast}\\{N\\}$.

  * •

Given two matrices $M\in\mathsf{matr}_{\ast}(n,m,k)$ and
$N\in\mathsf{matr}_{\ast}(n,m^{\prime},k^{\prime})$ such that every left
column of $M$ is a left column of $N$ and the right column of $M$ is the same
as the right column of $N$, then any finitely complete pointed category with
$M$-closed relations also has $N$-closed relations, i.e.,
$\mathsf{mclex}_{\ast}\\{M\\}\subseteq\mathsf{mclex}_{\ast}\\{N\\}$.

It follows immediately from these statements that matrix properties are
invariant under duplication and permutation of left columns and of rows of the
matrices. It is also clear that the matrix property arising from
$M\in\mathsf{matr}_{\ast}(n,m,k)$ is the same as the one arising from $M$
viewed in $\mathsf{matr}_{\ast}(n,m,k^{\prime})$ for any $k^{\prime}\geqslant
k$. It is also evident that matrix properties are invariant under addition of
a left column of $\ast$’s and permutation of the variables $x_{1},\dots,x_{k}$
in a specified row.

The notions of $M$-closedness and strict $M$-closedness have been studied in
[18, 19]. A third type of closedness property has been introduced in [13].
Given a matrix $M\in\mathsf{matr}_{\ast}(n,m,k)$, we say that an internal
$n^{\prime}$-ary relation in a pointed category is _$M$ -sharp_ if it is
strictly $M^{\prime}$-closed under any matrix $M^{\prime}$ obtained from any
selection of $n^{\prime}$ rows from $M$. Note that in this notion, the number
$n$ of rows of $M$ is not required to be exactly $n^{\prime}$; one can have
$n>n^{\prime}$, $n=n^{\prime}$ or $n<n^{\prime}$. By the above remark, a
finitely complete pointed category has $M$-closed relations if and only if
every $n^{\prime}$-ary internal relation in it is $M$-sharp for any positive
integer $n^{\prime}$. We also have a designated concept of an interpretation
for the closedness property of sharpness: given pointed sets
$(S_{1},\ast_{1}),\dots,(S_{n^{\prime}},\ast_{n^{\prime}})$, we define a
_reduction_ of type
$((S_{1},\ast_{1}),\dots,(S_{n^{\prime}},\ast_{n^{\prime}}))$ of a matrix
$M\in\mathsf{matr}_{\ast}(n,m,k)$ to be a row-wise interpretation of type
$((S_{1},\ast_{1}),\dots,(S_{n^{\prime}},\ast_{n^{\prime}}))$ of some matrix
$M^{\prime}\in\mathsf{matr}_{\ast}(n^{\prime},m,k)$ such that every row of
$M^{\prime}$ is a row of $M$, and where duplicate left columns of the row-wise
interpretation have been (possibly) deleted as well as left columns (possibly)
permuted or duplicated. Then an internal $n^{\prime}$-ary relation between the
objects $C_{1},\dots,C_{n^{\prime}}$ in a pointed category $\mathbb{C}$ is
$M$-sharp if and only if it is compatible with every reduction of $M$ of type
$(\mathbb{C}(X,C_{1}),\dots,\mathbb{C}(X,C_{n^{\prime}}))$ (for an arbitrary
object $X$).

######  Example 1.6.

To illustrate the concept of $M$-sharpness, let us consider the matrix

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

from Example 1.4 representing strongly unital categories. A binary relation is
$M$-sharp if it is strictly $M_{ij}$-closed for all $i,j\in\\{1,2\\}$ where

$\begin{array}[]{lr}M_{11}=\left[\begin{array}[]{ccc|c}x_{1}&\ast&\ast&x_{1}\\\
x_{1}&\ast&\ast&x_{1}\end{array}\right]&M_{12}=M=\left[\begin{array}[]{ccc|c}x_{1}&\ast&\ast&x_{1}\\\
x_{2}&x_{2}&x_{1}&x_{1}\end{array}\right]\\\
M_{21}=\left[\begin{array}[]{ccc|c}x_{2}&x_{2}&x_{1}&x_{1}\\\
x_{1}&\ast&\ast&x_{1}\end{array}\right]&M_{22}=\left[\begin{array}[]{ccc|c}x_{2}&x_{2}&x_{1}&x_{1}\\\
x_{2}&x_{2}&x_{1}&x_{1}\end{array}\right].\end{array}$

Since the right column of $M_{11}$ can be found in its left columns (and
analogously for $M_{22}$), any binary relation is strictly $M_{11}$-closed and
strictly $M_{22}$-closed. Hence, a binary relation is $M$-sharp if and only if
it is strictly $M$-closed and strictly $M_{21}$-closed. In the category
$\mathbf{Set}_{\ast}$, let us consider the pointed binary relation

$R=\left\\{\left[\begin{array}[]{c}\ast\\\
\ast\end{array}\right],\left[\begin{array}[]{c}a\\\
\ast\end{array}\right],\left[\begin{array}[]{c}a\\\
a\end{array}\right]\right\\}\subset A^{2}$

on the two-element pointed set $A=\\{\ast,a\\}$. This relation is strictly
$M$-closed since, given two pointed functions
$f_{1},f_{2}\colon\\{\ast,x_{1},x_{2}\\}\to\\{\ast,a\\}$ such that

$\left[\begin{array}[]{c}f_{1}(x_{1})\\\
f_{2}(x_{2})\end{array}\right],\left[\begin{array}[]{c}f_{1}(\ast)\\\
f_{2}(x_{2})\end{array}\right],\left[\begin{array}[]{c}f_{1}(\ast)\\\
f_{2}(x_{1})\end{array}\right]\in R,$

one automatically has $f_{2}(x_{1})=f_{2}(x_{2})=\ast$ and therefore

$\left[\begin{array}[]{c}f_{1}(x_{1})\\\ f_{2}(x_{1})\end{array}\right]\in R.$

Moreover, since $R$ is reflexive, we can see that it is (non-strictly)
$M_{21}$-closed. However, $R$ is not strictly $M_{21}$-closed since

$\left[\begin{array}[]{ccc|c}a&a&\ast&\ast\\\ a&\ast&\ast&a\end{array}\right]$

is a row-wise interpretation of $M_{21}$ of type $(A,A)$ whose left columns
are in $R$ but not its right column. Therefore, R is not $M$-sharp which show
that, in general, when the arity $n^{\prime}$ of the relation $R$ on an object
is the same as the number $n$ of rows of the matrix
$M\in\mathsf{matr}_{\ast}$, the condition ‘$R$ is $M$-sharp’ is strictly
stronger than the condition ‘$R$ is strictly $M$-closed’, which is itself
strictly stronger than the condition ‘$R$ is $M$-closed’. Note that when
$n\neq n^{\prime}$, the comparison between $M$-sharpness and (strict)
$M$-closedness does not make sense.

##  2 $S$-injective objects

Given a matrix set $S$ and extending the notions from [13], we call an object
$X$ in a pointed category $\mathbb{C}$ an _$S$ -injective object_ if, for
every matrix $M\in S$, every internal $n$-ary relation on any object in
$\mathbb{C}^{\mathsf{op}}$ is $M$-closed over $X$, where $n$ is the number of
rows of $M$. If $\mathbb{C}$ is finitely cocomplete (i.e., if
$\mathbb{C}^{\mathsf{op}}$ is finitely complete), this is equivalent to
require that, for every matrix $M\in S$, every internal $n$-ary relation in
$\mathbb{C}^{\mathsf{op}}$ is strictly $M$-closed over $X$, where $n$ is the
number of rows of $M$. It is not difficult to see that $S$-injective objects
are closed under all limits that exist in the pointed category. We write
$\mathsf{Inj}_{S}\mathbb{C}$ for the full subcategory of $\mathbb{C}$
consisting of all $S$-injective objects. We say that $\mathbb{C}$ _has enough
$S$-injective objects_ if for any object $C$ in $\mathbb{C}$ there is a
monomorphism $C\rightarrowtail D$ for which $D$ is $S$-injective.

Given a matrix $M=[x_{ij}]_{i,j}\in\mathsf{matr}_{\ast}(n,m,k)$, a pointed
category $\mathbb{C}$ with finite products and finite coproducts, and an
object $X$ in $\mathbb{C}$, we denote by $\pi^{X}_{M_{\mathsf{l}}}$ the
canonical map from the coproduct $nX^{k}$ to the product $X^{m}$ given by the
matrix

$\pi^{X}_{M_{\mathsf{l}}}=\left[\begin{array}[]{ccc}\pi_{x_{11}}&\dots&\pi_{x_{1m}}\\\
\vdots&&\vdots\\\ \pi_{x_{n1}}&\dots&\pi_{x_{nm}}\end{array}\right]$

where $\pi_{\ast}$ stands for the zero morphism $X^{k}\to X$ and
$\pi_{x_{1}},\dots,\pi_{x_{k}}$ stand for the product projections $X^{k}\to
X$. Similarly, we denote by $\pi^{X}_{M_{\mathsf{r}}}$ the canonical map from
the coproduct $nX^{k}$ to $X$ given by the column

$\pi^{X}_{M_{\mathsf{r}}}=\left[\begin{array}[]{c}\pi_{x_{1\,m+1}}\\\
\vdots\\\ \pi_{x_{n\,m+1}}\end{array}\right].$

We say that the category $\mathbb{C}$ has _universal epi-factorizations_ if
every morphism $f$ admits a factorization $f=gh$ via an epimorphism $h$ such
that any similar factorization $f=g^{\prime}h^{\prime}$ with $h^{\prime}$ an
epimorphism yields $h=uh^{\prime}$ for a (necessarily unique) morphism $u$.
Such a factorization is of course unique up to isomorphism and we call it the
_universal epi-factorization_ of $f$. The following theorem is the ‘pointed
version’ of Theorem 2.2 of [13].

######  Theorem 2.1.

Let $n>0$ and $m,k\geqslant 0$ be integers, $M\in\mathsf{matr}_{\ast}(n,m,k)$
be a matrix, $\mathbb{C}$ be a pointed category with finite products, finite
colimits and universal epi-factorizations, and $X$ be an object of
$\mathbb{C}$. Considering the universal epi-factorization
$\pi^{X}_{M_{\mathsf{l}}}=i^{X}_{M_{\mathsf{l}}}r^{X}_{M_{\mathsf{l}}}$ of
$\pi^{X}_{M_{\mathsf{l}}}$, the following statements are equivalent:

  1. (1)

$X$ is $\\{M\\}$-injective.

  2. (2)

Every internal $n$-ary relation in $\mathbb{C}^{\mathsf{op}}$ is strictly
$M$-closed over $X$.

  3. (3)

There exists a morphism $p^{X}_{M}\colon R^{X}_{M_{\mathsf{l}}}\to X$ making
the diagram

$\textstyle{X^{m}}$$\textstyle{nX^{k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r^{X}_{M_{\mathsf{l}}}}$$\scriptstyle{\pi^{X}_{M_{\mathsf{r}}}}$$\scriptstyle{\pi^{X}_{M_{\mathsf{l}}}}$$\textstyle{R^{X}_{M_{\mathsf{l}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i^{X}_{M_{\mathsf{l}}}}$$\scriptstyle{p^{X}_{M}}$$\textstyle{X}$

commute.

###### Proof.

As mentioned above, the equivalence (1)$\Leftrightarrow$(2) holds because
$\mathbb{C}$ is finitely cocomplete. To prove the implication
(1)$\Rightarrow$(3), we consider the epimorphism $r^{X}_{M_{\mathsf{l}}}\colon
nX^{k}\twoheadrightarrow R^{X}_{M_{\mathsf{l}}}$ as an $n$-ary relation in
$\mathbb{C}^{\mathsf{op}}$. We also consider the interpretation of $M$ of type
$\mathbb{C}^{\mathsf{op}}(X,X^{k})=\mathbb{C}(X^{k},X)$ given by the pointed
function $f\colon\\{\ast,x_{1},\dots,x_{k}\\}\to\mathbb{C}(X^{k},X)$ defined
by $f(x_{i})=\pi_{x_{i}}$, the $i$-th projection $X^{k}\to X$, for each
$i\in\\{1,\dots,k\\}$. Since $\pi^{X}_{M_{\mathsf{l}}}$ factorizes through
$r^{X}_{M_{\mathsf{l}}}$ and since this relation is $M$-closed over $X$ in
$\mathbb{C}^{\mathsf{op}}$, we know that $\pi^{X}_{M_{\mathsf{r}}}$ must also
factorize through $r^{X}_{M_{\mathsf{l}}}$.

It remains to prove the implication (3)$\Rightarrow$(1). Let us consider an
$n$-ary internal relation on an object $C$ in $\mathbb{C}^{\mathsf{op}}$,
viewed as an epimorphism $r\colon nC\twoheadrightarrow R$ in $\mathbb{C}$. Let
us also consider an interpretation of $M$ of type
$\mathbb{C}^{\mathsf{op}}(X,C)=\mathbb{C}(C,X)$ given by a pointed function
$f\colon\\{\ast,x_{1},\dots,x_{k}\\}\to\mathbb{C}(C,X)$. This function $f$
induces a morphism $g\colon C\to X^{k}$ such that $\pi_{x_{i}}g=f(x_{i})$ for
each $i\in\\{1,\dots,k\\}$. We denote by $ng\colon nC\to nX^{k}$ the $n$-fold
coproduct of the morphism $g$. Given a factorisation of
$\pi^{X}_{M_{\mathsf{l}}}\circ ng$ through $r$ as in

|
---|---
$\textstyle{X^{m}}$$\textstyle{nX^{k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pi^{X}_{M_{\mathsf{r}}}}$$\scriptstyle{\pi^{X}_{M_{\mathsf{l}}}}$$\textstyle{nC\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r}$$\scriptstyle{ng}$$\textstyle{X}$$\textstyle{R\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

we must show that $\pi^{X}_{M_{\mathsf{r}}}\circ ng$ also factors through $r$.
Considering the pushout of $r$ along $ng$,

$\textstyle{nC\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r}$$\scriptstyle{ng}$$\textstyle{nX^{k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r^{\prime}}$$\textstyle{R\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{R^{\prime}\ignorespaces}$

it suffices to show that $\pi^{X}_{M_{\mathsf{r}}}$ factors through
$r^{\prime}$ under the assumption that $\pi^{X}_{M_{\mathsf{l}}}$ does.

$\textstyle{X^{m}}$$\textstyle{nX^{k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r^{\prime}}$$\scriptstyle{\pi^{X}_{M_{\mathsf{r}}}}$$\scriptstyle{\pi^{X}_{M_{\mathsf{l}}}}$$\textstyle{R^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X}$

Since $\pi^{X}_{M_{\mathsf{l}}}=i^{X}_{M_{\mathsf{l}}}r^{X}_{M_{\mathsf{l}}}$
is a universal epi-factorization, there exists a morphism $u\colon
R^{\prime}\to R^{X}_{M_{\mathsf{l}}}$ such that
$ur^{\prime}=r^{X}_{M_{\mathsf{l}}}$. The required morphism $R^{\prime}\to X$
is then given by the composite $p^{X}_{M}u$. ∎

We will later need the following result, which is the direct adaptation to the
pointed context of Theorem 3.1 in [13], itself coming from the ideas of [21].
The proof being analogous to the one in [13], we omit it here.

######  Theorem 2.2.

Let $\mathbb{C}$ be a pointed category having finite limits and finite
colimits and where every morphism factorizes as an epimorphism followed by an
equalizer. Consider two matrix sets $S\subseteq T$. If $\mathbb{C}$ has enough
$T$-injective objects, then $\mathsf{Inj}_{S}\mathbb{C}$ is the largest full
subcategory of $\mathbb{C}$ among those that contain all $T$-injective
objects, are closed under finite limits, and whose dual categories have
$M$-closed relations for every $M\in S$.

##  3 Trivial and anti-trivial matrices

A matrix $M\in\mathsf{matr}_{\ast}$ is said to be _trivial_ if the matrix
class $\mathsf{mclex}_{\ast}\\{M\\}$ consists exactly of those categories
which are equivalent to $\mathbf{1}$, the single morphism category. Since
those categories belong to $\mathsf{mclex}_{\ast}\\{N\\}$ for all
$N\in\mathsf{matr}_{\ast}$, one has
$\mathsf{mclex}_{\ast}\\{M\\}\subseteq\mathsf{mclex}_{\ast}\\{N\\}$ for any
trivial matrix $M$ and any matrix $N$. This section is devoted to the proof of
Theorem 3.1 which characterizes trivial matrices. In view of that theorem and
of Theorem 2.3 in [13], we know that a non-pointed matrix
$M\in\mathsf{matr}\subset\mathsf{matr}_{\ast}$ is trivial in our sense if and
only if it is trivial in the sense of [13], i.e., if and only if any finitely
complete category with $M$-closed relations is a preorder (see Corollary 3.2).

Given a matrix $M=[x_{ij}]_{i,j}\in\mathsf{matr}_{\ast}(n,m,k)$ and an integer
$i\in\\{1,\dots,n\\}$, we denote by $R_{M_{i}}$ the kernel relation on the set
$\\{1,\dots,m\\}$ induced by the left part of the $i$-th row of $M$ seen as a
map $\\{1,\dots,m\\}\to\\{\ast,x_{1},\dots,x_{k}\\}$, i.e.,

$j\,R_{M_{i}}\,j^{\prime}\,\,\Leftrightarrow\,\,x_{ij}=x_{ij^{\prime}}.$

Given $i,i^{\prime}\in\\{1,\dots,n\\}$, we denote by
$R^{\ast}_{M_{i,i^{\prime}}}$ the equivalence relation on the set
$\\{1,\dots,m\\}$ defined by

$j\,R^{\ast}_{M_{i,i^{\prime}}}\,j^{\prime}\,\,\Leftrightarrow\,\,(j=j^{\prime})\text{
or }((x_{i,j}=\ast\text{ or }x_{i^{\prime},j}=\ast)\text{ and
}(x_{i,j^{\prime}}=\ast\text{ or }x_{i^{\prime},j^{\prime}}=\ast))$

We also consider the equivalence relation $R_{M_{i}}\vee
R_{M_{i^{\prime}}}\vee R^{\ast}_{M_{i,i^{\prime}}}$ given by the join of the
three equivalence relations $R_{M_{i}}$, $R_{M_{i^{\prime}}}$ and
$R^{\ast}_{M_{i,i^{\prime}}}$. Finally, given a pointed set $(Y,\ast)$, we say
that $M$ is _functional in $(Y,\ast)$_ if, given
$i,i^{\prime}\in\\{1,\dots,n\\}$ and two pointed functions

$f_{i},f_{i^{\prime}}\colon\\{\ast,x_{1},\dots,x_{k}\\}\to Y$

such that $f_{i}(x_{ij})=f_{i^{\prime}}(x_{i^{\prime}j})$ for all
$j\in\\{1,\dots,m\\}$, one has
$f_{i}(x_{i\,m+1})=f_{i^{\prime}}(x_{i^{\prime}\,m+1})$. Using Theorem 2.1
with $\mathbb{C}=\mathbf{Set}_{\ast}$ and $X=(Y,\ast)$, since
$R^{X}_{M_{\mathsf{l}}}$ is in that case the image of
$\pi^{(Y,\ast)}_{M_{\mathsf{l}}}$, it is not difficult to see that $M$ is
functional in $(Y,\ast)$ if and only if $(Y,\ast)$ is an $\\{M\\}$-injective
object in $\mathbf{Set}_{\ast}$.

######  Theorem 3.1.

Given integers $n>0$ and $m,k\geqslant 0$ and a matrix
$M=[x_{ij}]_{i,j}\in\mathsf{matr}_{\ast}(n,m,k)$, the following conditions are
equivalent:

  1. (1)

$M$ is not a trivial matrix.

  2. (2)

$\mathbf{Set}_{\ast}^{\mathsf{op}}$ has $M$-closed relations.

  3. (3)

The following three conditions are all satisfied:

     * •

every row of $M$ whose right entry is $x_{i\,m+1}\neq\ast$ contains
$x_{i\,m+1}$ as one of its left entries,

     * •

given $i,i^{\prime}\in\\{1,\dots,n\\}$ and $j,j^{\prime}\in\\{1,\dots,m\\}$
such that $i\neq i^{\prime}$ and

$x_{ij}=x_{i\,m+1}\neq\ast\neq x_{i^{\prime}j^{\prime}}=x_{i^{\prime}\,m+1},$

then $j\,R_{M_{i}}\vee R_{M_{i^{\prime}}}\vee
R^{\ast}_{M_{i,i^{\prime}}}\,j^{\prime}$,

     * •

given $i,i^{\prime}\in\\{1,\dots,n\\}$ and $j\in\\{1,\dots,m\\}$ such that
$x_{ij}=x_{i\,m+1}\neq\ast=x_{i^{\prime}\,m+1}$, there exists
$j^{\prime}\in\\{1,\dots,m\\}$ such that $j\,R_{M_{i}}\vee
R_{M_{i^{\prime}}}\vee R^{\ast}_{M_{i,i^{\prime}}}\,j^{\prime}$ and either
$x_{ij^{\prime}}=\ast$ or $x_{i^{\prime}j^{\prime}}=\ast$.

  4. (4)

$M$ does not have a reduction of type $(\\{\ast,x_{1}\\})$ or
$(\\{\ast,x_{1}\\},\\{\ast,x_{1}\\})$ given by any of the following four
matrices:

$\left[\begin{array}[]{c|c}&x_{1}\end{array}\right],\quad\left[\begin{array}[]{c|c}\ast&x_{1}\end{array}\right],\quad\left[\begin{array}[]{c|c}x_{1}&x_{1}\\\
x_{1}&\ast\end{array}\right],\quad\left[\begin{array}[]{cc|c}x_{1}&\ast&x_{1}\\\
x_{1}&\ast&\ast\end{array}\right].$

  5. (5)

$M$ is functional in every pointed set.

  6. (6)

$M$ is functional in a two element pointed set.

  7. (7)

$M$ is functional in a pointed set having at least two elements.

###### Proof.

The implications (5)$\Rightarrow$(6)$\Rightarrow$(7) are obvious. Let us show
(7)$\Rightarrow$(4). Suppose (4) does not hold and let $(Y,\ast)$ be a pointed
set and $y\in Y$ with $y\neq\ast$. If

$\left[\begin{array}[]{c|c}&x_{1}\end{array}\right]\quad\left(\text{respectively
}\left[\begin{array}[]{c|c}\ast&x_{1}\end{array}\right],\quad\left[\begin{array}[]{c|c}x_{1}&x_{1}\\\
x_{1}&\ast\end{array}\right],\text{ or
}\left[\begin{array}[]{cc|c}x_{1}&\ast&x_{1}\\\
x_{1}&\ast&\ast\end{array}\right]\right)$

is a reduction of $M$, so is

$\left[\begin{array}[]{c|c}&y\\\
&\ast\end{array}\right]\quad\left(\text{respectively
}\left[\begin{array}[]{c|c}\ast&y\\\
\ast&\ast\end{array}\right],\quad\left[\begin{array}[]{c|c}y&y\\\
y&\ast\end{array}\right],\text{ or }\left[\begin{array}[]{cc|c}y&\ast&y\\\
y&\ast&\ast\end{array}\right]\right)$

showing that $M$ is not functional in $(Y,\ast)$.

Let us now prove (4)$\Rightarrow$(3). Suppose (3) does not hold and let us
show that (4) does not hold neither. If $m=0$, this means that $M$ has a row
with $x_{i\,m+1}\neq\ast$ as right entry (and empty left part) and therefore
$M$ admits

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

as a reduction. If $m>0$ and $M$ has a row whose right entry is
$x_{i\,m+1}\neq\ast$ but for which $x_{i\,m+1}$ is not a left entry, then

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

is a reduction of $M$. If the second condition of (3) is not satisfied, there
exist $i,i^{\prime}\in\\{1,\dots,n\\}$ and $j,j^{\prime}\in\\{1,\dots,m\\}$
such that $i\neq i^{\prime}$ and $x_{ij}=x_{i\,m+1}\neq\ast\neq
x_{i^{\prime}j^{\prime}}=x_{i^{\prime}\,m+1}$ but where $j\,R_{M_{i}}\vee
R_{M_{i^{\prime}}}\vee R^{\ast}_{M_{i,i^{\prime}}}\,j^{\prime}$ does not hold.
By definition of $R^{\ast}_{M_{i,i^{\prime}}}$, up to swapping $(i,j)$ with
$(i^{\prime},j^{\prime})$, we can suppose without loss of generality that if
$x_{ij^{\prime\prime}}=\ast$ or $x_{i^{\prime}j^{\prime\prime}}=\ast$ for some
$j^{\prime\prime}\in\\{1,\dots,m\\}$, then $j\,R_{M_{i}}\vee
R_{M_{i^{\prime}}}\vee R^{\ast}_{M_{i,i^{\prime}}}\,j^{\prime\prime}$ does not
hold neither. The columns of $M$ can then be divided into two disjoint sets:
the $j^{\prime\prime}$-th column will be in the first set if $j\,R_{M_{i}}\vee
R_{M_{i^{\prime}}}\vee R^{\ast}_{M_{i,i^{\prime}}}\,j^{\prime\prime}$ and in
the second set otherwise. Interpreting, in the $i$-th and the $i^{\prime}$-th
rows of $M$, each entry in the first set of columns as $x_{1}$ and the other
ones as $\ast$, this guarantees that $M$ admits

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

as a reduction. Suppose now the third condition of (3) is not satisfied with
$i,i^{\prime}\in\\{1,\dots,n\\}$ and $j\in\\{1,\dots,m\\}$ such that
$x_{ij}=x_{i\,m+1}\neq\ast=x_{i^{\prime}\,m+1}$. If there is no $\ast$ in the
left part of the $i$-th and $i^{\prime}$-th rows of $M$, it admits

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

as a reduction. Otherwise, there exists $j^{\prime}\in\\{1,\dots,m\\}$ such
that either $x_{ij^{\prime}}=\ast$ or $x_{i^{\prime}j^{\prime}}=\ast$. By
assumption, we know that $j\,R_{M_{i}}\vee R_{M_{i^{\prime}}}\vee
R^{\ast}_{M_{i,i^{\prime}}}\,j^{\prime}$ does not hold. Dividing the columns
of $M$ in two sets and considering the interpretation as above, we also get
that $M$ admits

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

as a reduction.

Next, we prove (3)$\Rightarrow$(5). Suppose (5) does not hold. We can thus
find a pointed set $(Y,\ast)$, $i,i^{\prime}\in\\{1,\dots,n\\}$ and two
pointed functions $f_{i},f_{i^{\prime}}\colon\\{\ast,x_{1},\dots,x_{k}\\}\to
Y$ such that $f_{i}(x_{ij})=f_{i^{\prime}}(x_{i^{\prime}j})$ for all
$j\in\\{1,\dots,m\\}$ but $f_{i}(x_{i\,m+1})\neq
f_{i^{\prime}}(x_{i^{\prime}\,m+1})$. If $i=i^{\prime}$, then the first
condition of (3) gets violated. Let us thus suppose that $i\neq i^{\prime}$.
We can see that, if $j_{1},j_{2}\in\\{1,\dots,m\\}$ satisfy
$j_{1}\,R_{M_{i}}\vee R_{M_{i^{\prime}}}\vee
R^{\ast}_{M_{i,i^{\prime}}}\,j_{2}$, then
$f_{i}(x_{ij_{1}})=f_{i}(x_{ij_{2}})=f_{i^{\prime}}(x_{i^{\prime}j_{1}})=f_{i^{\prime}}(x_{i^{\prime}j_{2}})$.
Since we cannot have $x_{i\,m+1}=x_{i^{\prime}\,m+1}=\ast$, we can also
suppose without loss of generality that $x_{i\,m+1}\neq\ast$. Not to violate
the first condition of (3), there should exist $j\in\\{1,\dots,m\\}$ such that
$x_{ij}=x_{i\,m+1}$. If $x_{i^{\prime}\,m+1}\neq\ast$, then, again not to
contradict the first condition of (3), there exists
$j^{\prime}\in\\{1,\dots,m\\}$ such that
$x_{i^{\prime}j^{\prime}}=x_{i^{\prime}\,m+1}$. But since
$f_{i}(x_{ij})=f_{i}(x_{i\,m+1})\neq
f_{i^{\prime}}(x_{i^{\prime}\,m+1})=f_{i^{\prime}}(x_{i^{\prime}j^{\prime}})$,
one cannot have $j\,R_{M_{i}}\vee R_{M_{i^{\prime}}}\vee
R^{\ast}_{M_{i,i^{\prime}}}\,j^{\prime}$, violating the second condition of
(3). If $x_{i^{\prime}\,m+1}=\ast$, not to contradict the third condition of
(3), there exists $j^{\prime}\in\\{1,\dots,m\\}$ such that $j\,R_{M_{i}}\vee
R_{M_{i^{\prime}}}\vee R^{\ast}_{M_{i,i^{\prime}}}\,j^{\prime}$ and either
$x_{ij^{\prime}}=\ast$ or $x_{i^{\prime}j^{\prime}}=\ast$. By our remark
above, this means that
$f_{i}(x_{i\,m+1})=f_{i}(x_{ij})=f_{i}(x_{ij^{\prime}})=f_{i^{\prime}}(x_{i^{\prime}j^{\prime}})=\ast=f_{i^{\prime}}(x_{i^{\prime}\,m+1})$,
leading to a contradiction. We have therefore already proved the equivalences
(3)$\Leftrightarrow$(4)$\Leftrightarrow$(5)$\Leftrightarrow$(6)$\Leftrightarrow$(7).

Since $\mathbf{Set}_{\ast}^{\mathsf{op}}$ is not equivalent to the single
morphism category, the implication (2)$\Rightarrow$(1) is straightforward from
the definition of a trivial matrix. To prove (5)$\Rightarrow$(2), it suffices
to recall that $M$ is functional in a pointed set $(Y,\ast)$ exactly when
$(Y,\ast)$ is an $\\{M\\}$-injective object in $\mathbf{Set}_{\ast}$, i.e.,
when internal $n$-ary relations in $\mathbf{Set}_{\ast}^{\mathsf{op}}$ are
$M$-closed over $(Y,\ast)$. It remains now to prove (1)$\Rightarrow$(4). We
suppose that (4) does not hold and we consider a finitely complete pointed
category $\mathbb{C}$ with $M$-closed relations. If $M$ has
$\left[\begin{array}[]{c|c}&x_{1}\end{array}\right]$ or
$\left[\begin{array}[]{c|c}\ast&x_{1}\end{array}\right]$ as a reduction, then,
for an arbitrary object $C$ in $\mathbb{C}$, the identity morphism $C\to C$
must factors through the subobject $0\rightarrowtail C$ where $0$ is the zero
object of $\mathbb{C}$, proving that $C$ is itself a zero object. If $M$
admits

$\left[\begin{array}[]{c|c}x_{1}&x_{1}\\\
x_{1}&\ast\end{array}\right]\quad\text{or}\quad\left[\begin{array}[]{cc|c}x_{1}&\ast&x_{1}\\\
x_{1}&\ast&\ast\end{array}\right]$

as a reduction, then the morphism $(1_{C},0)\colon C\to C\times C$ induced by
the identity on an object $C$ and the zero morphism $C\to C$ should factors
through the diagonal $(1_{C},1_{C})\colon C\rightarrowtail C\times C$ proving
again that $1_{C}$ is the zero morphism and thus $C$ is a zero object. This
proves that $\mathbb{C}$ is equivalent to $\mathbf{1}$ and thus $M$ is a
trivial matrix. ∎

The equivalence (1)$\Leftrightarrow$(3) of this theorem, in the case where $M$
is a non-pointed matrix, reduces to the characterization of trivial matrices
in the sense of [13] (i.e., non-pointed matrices $M$ for which any finitely
complete category in $\mathsf{mclex}\\{M\\}$ is a preorder). One thus has the
following corollary.

######  Corollary 3.2.

A non-pointed matrix $M\in\mathsf{matr}$ is trivial (in the sense of the
present paper) if and only if it is trivial in the sense of [13].

Let us now turn our attention to anti-trivial matrices. A matrix
$M\in\mathsf{matr}_{\ast}$ is said to be _anti-trivial_ if all finitely
complete pointed categories have $M$-closed relations. The following theorem
characterizes anti-trivial matrices. We invite the reader to compare the
equivalence (1)$\Leftrightarrow$(2) of it with the equivalence
(1)$\Leftrightarrow$(2) of Theorem 3.1.

######  Theorem 3.3.

The following conditions on a matrix $M\in\mathsf{matr}_{\ast}$ are
equivalent:

  1. (1)

$M$ is anti-trivial.

  2. (2)

$\mathbf{Set}_{\ast}$ has $M$-closed relations.

  3. (3)

All the entries of the right column of $M$ are $\ast$’s or this right column
of $M$ can be found among its left columns.

###### Proof.

The implication (1)$\Rightarrow$(2) follows immediately from the definition of
anti-trivial matrices. For the implication (2)$\Rightarrow$(3), if
$M\in\mathsf{matr}_{\ast}(n,m,k)$, we consider the $n$-ary pointed relation
$R$ on the pointed set $\\{\ast,x_{1},\dots,x_{k}\\}$ formed by the left
columns of $M$ and the column made of $n$ many $\ast$’s. If
$\mathbf{Set}_{\ast}$ has $M$-closed relations, $R$ should also contain the
right column of $M$, which implies (3). Finally, the implication
(3)$\Rightarrow$(1) follows from the definition of $M$-closedness. ∎

Again, the equivalence (1)$\Leftrightarrow$(3) of the above theorem, in the
case where $M$ is a non-pointed matrix, reduces to the characterization of
anti-trivial matrices in the sense of [13] (i.e., non-pointed matrices $M$ for
which any finitely complete category is in $\mathsf{mclex}\\{M\\}$). One thus
has the following corollary.

######  Corollary 3.4.

A non-pointed matrix $M\in\mathsf{matr}$ is anti-trivial (in the sense of the
present paper) if and only if it is anti-trivial in the sense of [13].

##  4 The posets $\mathsf{Mclex}$ and $\mathsf{Mclex}_{\ast}$ and Bourn
localizations

In [13], we studied the collection $\mathsf{Mclex}$ of collections
$\mathsf{mclex}\\{M\\}$ of finitely complete categories given by non-pointed
matrices $M\in\mathsf{matr}$. In a similar way, we introduce here the
collection $\mathsf{Mclex}_{\ast}$ of collections
$\mathsf{mclex}_{\ast}\\{M\\}$ for matrices $M\in\mathsf{matr}_{\ast}$. We
regard $\mathsf{Mclex}$ and $\mathsf{Mclex}_{\ast}$ as posets with the order
given by inclusion. We have an order-preserving function

$(-)_{\ast}\colon\mathsf{Mclex}\to\mathsf{Mclex}_{\ast}$

given by intersection with the collection of pointed categories, i.e., for a
non-pointed matrix $M$, $(-)_{\ast}$ sends $\mathsf{mclex}\\{M\\}$ to
$\mathsf{mclex}_{\ast}\\{M\\}$.

In order to describe a right adjoint to this function (seen as a functor
between preorder categories), we need to recall the concept of Bourn
localizations. Let $\mathbb{C}$ be a given finitely complete category. A
_point_ in $\mathbb{C}$ is a pair of morphisms $(p\colon A\twoheadrightarrow
I,s\colon I\rightarrowtail A)$ such that the composite $ps$ is $1_{I}$, the
identity on $I$. A morphism of points
$(p,s)\rightarrow(p^{\prime},s^{\prime})$ is a pair of morphisms $(u\colon
A\rightarrow A^{\prime},v\colon I\rightarrow I^{\prime})$ in $\mathbb{C}$ such
that $vp=p^{\prime}u$ and $us=s^{\prime}v$.

$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{u}$$\scriptstyle{p}$$\textstyle{A^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p^{\prime}}$$\textstyle{I\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{v}$$\scriptstyle{s}$$\textstyle{I^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{s^{\prime}}$

This forms the category $\mathsf{Pt}(\mathbb{C})$ of points of $\mathbb{C}$.
Together with this category, we have a forgetful functor

$\displaystyle\pi\colon\quad\,\mathsf{Pt}(\mathbb{C})$
$\displaystyle\longrightarrow\mathbb{C}$
$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p}$$\textstyle{I\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{s}$
$\displaystyle\longmapsto I$ $\displaystyle(u,v)$ $\displaystyle\longmapsto v$

called the _fibration of points_ [3]. Given an object $I$ in $\mathbb{C}$, the
fibre of $\pi$ over $I$ is denoted by $\mathsf{Pt}_{I}(\mathbb{C})$ and
consists of the subcategory of $\mathsf{Pt}(\mathbb{C})$ of points and
morphisms mapped by $\pi$ to $I$ and $1_{I}$ respectively. Each such fibre is
a finitely complete pointed category, the zero object being the point
$(1_{I},1_{I})$. Using the terminology recalled in Example 1.4, D. Bourn
showed in [4] that the following statements are equivalent:

  * •

$\mathbb{C}$ is a Mal’tsev category;

  * •

for all objects $I$ of $\mathbb{C}$, the fibre $\mathsf{Pt}_{I}(\mathbb{C})$
is unital;

  * •

for all objects $I$ of $\mathbb{C}$, the fibre $\mathsf{Pt}_{I}(\mathbb{C})$
is strongly unital;

  * •

for all objects $I$ of $\mathbb{C}$, the fibre $\mathsf{Pt}_{I}(\mathbb{C})$
is a Mal’tsev category.

In [17], Z. Janelidze showed that these conditions are also equivalent to

  * •

for all objects $I$ of $\mathbb{C}$, the fibre $\mathsf{Pt}_{I}(\mathbb{C})$
is subtractive.

As in [19], for a collection $\mathcal{C}$ of finitely complete pointed
categories, we denote by $\mathsf{Loc}(\mathcal{C})$ the _Bourn localization_
of $\mathcal{C}$, i.e., the collection of finitely complete categories
$\mathbb{C}$ for which, given any object $I$ in $\mathbb{C}$, the category
$\mathsf{Pt}_{I}(\mathbb{C})$ is in $\mathcal{C}$. Given a non-pointed matrix
$M=[x_{ij}]_{i,j}\in\mathsf{matr}(n,m,k)$ and a variable $x$ among
$x_{1},x_{2},x_{3},\dots$, we denote by $M[x\to\ast]$ the matrix in
$\mathsf{matr}_{\ast}(n,m,k)$ obtained by replacing each occurrence of $x$ in
$M$ by $\ast$. We say that the pair $(M,x)$ is _admissible_ if there exists a
left column of $M$

$\left[\begin{array}[]{c}x_{1j}\\\ \vdots\\\ x_{nj}\end{array}\right]$

such that, for each $i\in\\{1,\dots,n\\}$, if there is a
$j^{\prime}\in\\{1,\dots,m+1\\}$ such that $x_{ij^{\prime}}=x$, then
$x_{ij}=x$. The following theorem generalizes the above mentioned results from
[4] and [17].

######  Theorem 4.1.

[19]. Given a non-pointed matrix $M\in\mathsf{matr}$ and a variable $x$ among
$x_{1},x_{2},x_{3},\dots$ for which the pair $(M,x)$ is admissible, one has

$\mathsf{mclex}\\{M\\}=\mathsf{Loc}(\mathsf{mclex}_{\ast}\\{M[x\to\ast]\\}).$

In particular, this theorem shows that for a non-pointed matrix
$M\in\mathsf{matr}(n,m,k)$, one has

$\mathsf{mclex}\\{M\\}=\mathsf{Loc}(\mathsf{mclex}_{\ast}\\{M\\})$

provided that $m>0$. If $m=0$, $\mathsf{mclex}\\{M\\}$ is the collection of
categories equivalent to $\mathbf{1}$ and
$\mathsf{Loc}(\mathsf{mclex}_{\ast}\\{M\\})$ is the collection of finitely
complete preorders. So, in any case, one has at least the inclusion
$\mathsf{mclex}\\{M\\}\subseteq\mathsf{Loc}(\mathsf{mclex}_{\ast}\\{M\\})$.
Moreover, given a (pointed) matrix $N\in\mathsf{matr}_{\ast}(n,m,k)$, Theorem
4.1 implies that

$\mathsf{Loc}(\mathsf{mclex}_{\ast}\\{N\\})=\mathsf{mclex}\\{N_{\mathsf{loc}}\\}$

where $N_{\mathsf{loc}}\in\mathsf{matr}(n,m+1,k+1)$ is obtained from $N$ by
first adding a left column of $\ast$’s and then replace all $\ast$’s by
$x_{k+1}$. Bourn localizations thus induce an order-preserving function

$\mathsf{Loc}\colon\mathsf{Mclex}_{\ast}\to\mathsf{Mclex}$

sending $\mathsf{mclex}_{\ast}\\{N\\}$ to
$\mathsf{Loc}(\mathsf{mclex}_{\ast}\\{N\\})$. It is easy to see that this
function gives a right adjoint to
$(-)_{\ast}\colon\mathsf{Mclex}\to\mathsf{Mclex}_{\ast}$, i.e., that

$\mathsf{mclex}\\{M\\}\subseteq\mathsf{Loc}(\mathsf{mclex}_{\ast}\\{N\\})\Longleftrightarrow\mathsf{mclex}_{\ast}\\{M\\}\subseteq\mathsf{mclex}_{\ast}\\{N\\}$

holds for any non-pointed matrix $M$ and any (pointed) matrix $N$. Indeed,
supposing
$\mathsf{mclex}\\{M\\}\subseteq\mathsf{Loc}(\mathsf{mclex}_{\ast}\\{N\\})$ and
given a finitely complete pointed category $\mathbb{C}$ with $M$-closed
relations, we know that all fibres $\mathsf{Pt}_{I}(\mathbb{C})$ have
$N$-closed relations. Taking $I$ to be a zero object of $\mathbb{C}$ gives a
category which is isomorphic to $\mathbb{C}$ which thus has $N$-closed
relations. The converse inclusion follows immediately from
$\mathsf{mclex}\\{M\\}\subseteq\mathsf{Loc}(\mathsf{mclex}_{\ast}\\{M\\})$.

$\textstyle{\mathsf{Mclex}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(-)_{\ast}}$$\textstyle{\mathsf{Mclex}_{\ast}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{Loc}}$$\scriptstyle{\top}$

In addition, this right adjoint is also ‘almost a left inverse’ of
$(-)_{\ast}$ in the sense that
$\mathsf{mclex}\\{M\\}=\mathsf{Loc}(\mathsf{mclex}_{\ast}\\{M\\})$ holds for
any non-pointed matrix $M$ with at least one left column. Therefore, if $M$
and $M^{\prime}$ are two non-pointed matrices such that
$\mathsf{mclex}_{\ast}\\{M\\}\subseteq\mathsf{mclex}_{\ast}\\{M^{\prime}\\}$,
then
$\mathsf{mclex}\\{M\\}\subseteq\mathsf{Loc}(\mathsf{mclex}_{\ast}\\{M^{\prime}\\})$
and thus either $\mathsf{mclex}\\{M\\}\subseteq\mathsf{mclex}\\{M^{\prime}\\}$
or $\mathsf{mclex}\\{M\\}$ is the collection of all finitely complete
preorders and $\mathsf{mclex}\\{M^{\prime}\\}$ is the collection of all
categories equivalent to $\mathbf{1}$. This discussion leads us to the
following theorem.

######  Theorem 4.2.

Let $S$ and $U$ be non-pointed matrix sets such that $U$ does not contain any
matrix with no left columns. Then one has
$\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}U$ if and only if
$\mathsf{mclex}S\subseteq\mathsf{mclex}U$.

Let us immediately note that, if $S$ is the singleton consisting of the
trivial matrix
$\left[\begin{array}[]{c|c}x_{2}&x_{1}\end{array}\right]\in\mathsf{matr}(1,1,2)$
and $U$ is the singleton consisting of the trivial matrix
$\left[\begin{array}[]{c|c}&x_{1}\end{array}\right]\in\mathsf{matr}(1,0,1)$,
one has that $\mathsf{mclex}U=\mathsf{mclex}_{\ast}S=\mathsf{mclex}_{\ast}U$
is the collection of all categories equivalent to $\mathbf{1}$ while
$\mathsf{mclex}S$ is the collection of all finitely complete preorders.
Therefore, $\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}U$ holds but
$\mathsf{mclex}S\subseteq\mathsf{mclex}U$ does not. In other words, the
function $(-)_{\ast}$ is not injective but is not far from being it, i.e., for
two non-pointed matrices $M$ and $M^{\prime}$, one has

$\mathsf{mclex}_{\ast}\\{M\\}=\mathsf{mclex}_{\ast}\\{M^{\prime}\\}\Longleftrightarrow(\mathsf{mclex}\\{M\\}=\mathsf{mclex}\\{M^{\prime}\\}\text{
or }(M\text{ and }M^{\prime}\text{ are trivial matrices})).$

We know from [13] that $\mathsf{Mclex}$ is infinite but countable. In view of
the above properties of the function $(-)_{\ast}$, we can deduce that
$\mathsf{Mclex}_{\ast}$ is also infinite and it is not hard to see that it is
also countable. On the other hand, it is proved in [13] that $\mathsf{Mclex}$
is a meet semi-lattice with the meet operation being given by the intersection
of the corresponding collections of categories. It seems the same argument
cannot be transposed to the pointed context and we therefore leave as an open
question whether finite conjunctions of matrix properties of finitely complete
pointed categories are again matrix properties, and the question whether
$\mathsf{Mclex}_{\ast}$ is a meet semi-lattice.

Given integers $n>0$ and $m,k\geqslant 0$, we have denoted in [13] by
$\mathsf{Mclex}[n,m,k]$ the restriction of the poset $\mathsf{Mclex}$ to those
$\mathsf{mclex}\\{M\\}$ given by non-pointed matrices
$M\in\mathsf{matr}(n,m,k)$. Adapting this notation, we denote by
$\mathsf{Mclex}_{\ast}[n,m,k]$ the restriction of $\mathsf{Mclex}_{\ast}$ to
those matrix classes $\mathsf{mclex}_{\ast}\\{M\\}$ given by matrices
$M\in\mathsf{matr}_{\ast}(n,m,k)$. Obviously, each of these posets is finite.
For very small values of the parameters $n,m,k$, in view of Theorems 3.1 and
3.3, we can have a complete description of these posets:

  * •

$\mathsf{Mclex}_{\ast}[n,m,0]$ contains only the collection of all finitely
complete pointed categories.

  * •

When $k>0$,
$\mathsf{Mclex}_{\ast}[n,0,k]=\mathsf{Mclex}_{\ast}[n,1,k]=\mathsf{Mclex}_{\ast}[1,m,k]$
has exactly two matrix classes given by the collection of all finitely
complete pointed categories and the collection of categories equivalent to
$\mathbf{1}$.

In view of this, we will call a matrix class (of finitely complete pointed
categories) _degenerate_ if it is determined by a trivial matrix or an anti-
trivial matrix. That is, the degenerate matrix classes are the following two:

  * •

the matrix class given by trivial matrices, i.e., the collection of categories
equivalent to $\mathbf{1}$, or in other words, the bottom element of the poset
$\mathsf{Mclex}_{\ast}$;

  * •

the matrix class given by anti-trivial matrices, i.e., the collection of all
finitely complete pointed categories, or in other words, the top element of
the poset $\mathsf{Mclex}_{\ast}$.

######  Remark 4.3.

Since the left adjoint $(-)_{\ast}$ preserves the top element, we know that
the collection of all finitely complete pointed categories is the only element
of $\mathsf{Mclex}_{\ast}$ sent by $\mathsf{Loc}$ to the top element of
$\mathsf{Mclex}$, i.e., the collection of all finitely complete categories.
Similarly, in view of Theorem 3.1, it is not hard to see that given a non-
trivial matrix $N$, the non-pointed matrix $N_{\mathsf{loc}}$ is also non-
trivial and thus the bottom element of $\mathsf{Mclex}_{\ast}$ is the only
element being mapped by $\mathsf{Loc}$ to the collection of finitely complete
preorders, i.e., the unique atom of $\mathsf{Mclex}$. Let us also notice that,
given a non-pointed matrix $M$ with at least one left column, in view of the
counit of the adjunction $(-)_{\ast}\dashv\mathsf{Loc}$, the matrix class
$\mathsf{mclex}_{\ast}\\{M\\}$ is the smallest element of
$\mathsf{Mclex}_{\ast}$ whose Bourn localization is $\mathsf{mclex}\\{M\\}$.

######  Remark 4.4.

Given integers $n>0$ and $m,k\geqslant 0$, we know that the Bourn localization
of a matrix class $\mathsf{mclex}_{\ast}\\{N\\}$ for a matrix
$N\in\mathsf{matr}_{\ast}(n,m,k)$ is given by
$\mathsf{mclex}\\{N_{\mathsf{loc}}\\}$, where
$N_{\mathsf{loc}}\in\mathsf{matr}(n,m+1,k+1)$. The function $\mathsf{Loc}$
therefore restricts as an order-preserving function

$\mathsf{Loc}\colon\mathsf{Mclex}_{\ast}[n,m,k]\twoheadrightarrow\mathsf{Mclex}[n,m+1,k+1]$

(denoted in the same way by abuse of notation). Moreover, in view of the
construction of $N_{\mathsf{loc}}$ from $N$, it is easy to see that this
function is actually surjective.

Let us notice that a matrix $M\in\mathsf{matr}_{\ast}(n,m,k)$ with $n>0$ and
$m,k\geqslant 0$ (i.e., a $n\times(m+1)$ matrix with entries in
$\\{\ast,x_{1},\dots,x_{k}\\}$) can have at most $(k+1)^{n}$ different left
columns. One of these columns is the right column of $M$, whose presence makes
$M$ anti-trivial. Among those $(k+1)^{n}$ possibilities for the left columns
of $M$, there is also the column of $\ast$’s. If this column is the right
column, $M$ is again anti-trivial. If the column of $\ast$’s belongs to the
left of $M$, one can remove it without changing the corresponding matrix
class. Therefore, one has the inclusion

$\mathsf{Mclex}_{\ast}[n,m,k]\subseteq\mathsf{Mclex}_{\ast}[n,(k+1)^{n}-2,k]$

for all $n,k>0$ and $m\geqslant 0$. Applying Remark 4.4 here, we know that
$\mathsf{Loc}$ restricts to a surjective function

$\mathsf{Loc}\colon\mathsf{Mclex}_{\ast}[n,(k+1)^{n}-2,k]\twoheadrightarrow\mathsf{Mclex}[n,(k+1)^{n}-1,k+1]$

where, as shown in [13], $\mathsf{Mclex}[n,(k+1)^{n}-1,k+1]$ contains all
elements of $\mathsf{Mclex}$, different from the bottom element, and induced
by a non-pointed matrix with $n$ rows and $k+1$ variables. Moreover, if a
matrix $M\in\mathsf{matr}_{\ast}(n,m,k)$ has the left entries of its $i$-th
row consisting of $m$ different variables, then, for any
$i^{\prime}\in\\{1,\dots,n\\}$, the equivalence relation $R_{M_{i}}\vee
R_{M_{i^{\prime}}}\vee R^{\ast}_{M_{i,i^{\prime}}}$ used in Theorem 3.1 is
nothing but $R_{M_{i^{\prime}}}$. In view of this and of that theorem, it is
easy to prove that such a matrix induces a degenerate matrix class
$\mathsf{mclex}_{\ast}\\{M\\}$. This proves that

$\mathsf{Mclex}_{\ast}[n,m,k]\subseteq\mathsf{Mclex}_{\ast}[n,m,m-1]$

for all $n>0$, $m>1$ and $k\geqslant 0$. In addition, if $M$ is a non-trivial
matrix in $\mathsf{matr}_{\ast}(n,m,m-1)$, up to permutation of variables, we
can assume that the right column is only made of $x_{1}$’s and $\ast$’s. There
are $m^{m}$ different rows with $x_{1}$ as right entry, to which we can
subtract the $(m-1)^{m}$ rows which does not contain $x_{1}$ on the left (in
view of Theorem 3.1). There are also $m^{m}$ different rows with $\ast$ as a
right entry, to which we can remove the row of $\ast$’s which does not
influence the corresponding matrix class (see for instance our algorithm in
the next section). The matrix class induced by $M$ is thus the same as the
matrix class determined by a matrix made of a maximum of $2m^{m}-(m-1)^{m}-1$
rows. This observation leads to the fact that the inclusion

$\mathsf{Mclex}_{\ast}[n,m,k]\subseteq\mathsf{Mclex}_{\ast}[2m^{m}-(m-1)^{m}-1,m,m-1]$

holds for all $n>0$, $m>1$ and $k\geqslant 0$.

##  5 The algorithm

Theorem 4.2 shows that, to decide whether
$\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}U$ for finite non-pointed
matrix sets $S$ and $U$, it is equivalent, in non-trivial cases, to use the
algorithm of [13] which decide whether
$\mathsf{mclex}S\subseteq\mathsf{mclex}U$. In this section, we present an
analogue algorithm for the case where $S$ and $U$ are not necessarily non-
pointed. In order to do so, adapting the ideas of [13], themselves based on
the ideas of [8], let us now study $S$-injective objects in the category of
$n$-ary pointed relations. For each non-zero natural number $n$, we consider
the category $\mathbf{Rel}_{\ast}^{n}$ whose objects are triples $(X,\ast,R)$
where $(X,\ast)$ is a pointed set and $R$ is an $n$-ary pointed relation on
$X$ (i.e., a subset $R\subseteq X^{n}$ containing $(\ast,\dots,\ast)$), and
whose morphisms $(X,\ast,R)\to(X^{\prime},\ast^{\prime},R^{\prime})$ are
relation-preserving pointed functions, i.e., functions $f\colon X\to
X^{\prime}$ such that $f(\ast)=\ast^{\prime}$ and such that there exists a
(necessarily unique) dashed morphism rendering the diagram

$\textstyle{R\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{R^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X^{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f^{n}}$$\textstyle{X^{\prime\,n}}$

commutative. The forgetful functor
$\mathbf{Rel}_{\ast}^{n}\to\mathbf{Set}_{\ast}$ is a topological functor (see
e.g. [2]) and therefore $\mathbf{Rel}_{\ast}^{n}$ is a complete and cocomplete
pointed category. Moreover, the limit/colimit of a diagram in
$\mathbf{Rel}_{\ast}^{n}$ has as its underlying pointed set the limit/colimit
of the underlying diagram in $\mathbf{Set}_{\ast}$, equipped with the
largest/smallest pointed relation making the canonical projections/inclusions
relation-preserving. It is then not difficult to see that, given a matrix
$M\in\mathsf{matr}_{\ast}$, an object $(X,\ast,R)$ of
$\mathbf{Rel}_{\ast}^{n}$ is an $\\{M\\}$-injective object if and only if $M$
is functional in the pointed set $(X,\ast)$ and $R$ is $M$-sharp. This is
because, if we consider the diagram in Theorem 2.1 applied to $(X,\ast,R)$ in
$\mathbf{Rel}_{\ast}^{n}$, we have that $M$ functional in the pointed set
$(X,\ast)$ and $R$ is $M$-sharp if and only if the pointed function
$p^{X}_{M}$ exists and is a morphism in $\mathbf{Rel}_{\ast}^{n}$, i.e., is
relation-preserving. Furthermore, when $M$ is not a trivial matrix, we can
drop ‘$M$ is functional in $(X,\ast)$’ by virtue of Theorem 3.1, i.e.,
$(X,\ast,R)$ is $\\{M\\}$-injective if and only if $R$ is $M$-sharp. We can
also see that for a matrix set $S$, the category
$\mathsf{Inj}_{S}\mathbf{Rel}_{\ast}^{n}$ forms a full reflective subcategory
of $\mathbf{Rel}_{\ast}^{n}$. Given an object $(X,\ast,R)$ in
$\mathbf{Rel}_{\ast}^{n}$, its reflection
$f\colon(X,\ast,R)\to(X^{\prime},\ast^{\prime},R^{\prime})$ in the subcategory
$\mathsf{Inj}_{S}\mathbf{Rel}_{\ast}^{n}$ is obtained as follows:

  * •

If $S$ contains a trivial matrix, then $(X^{\prime},\ast^{\prime},R^{\prime})$
is the zero object of $\mathbf{Rel}_{\ast}^{n}$, i.e.,
$X^{\prime}=\\{\ast^{\prime}\\}$ and $R^{\prime}=\\{\ast^{\prime}\\}^{n}$, and
the function $f$ is the unique function $f\colon X\to\\{\ast^{\prime}\\}$.

  * •

If $S$ does not contain a trivial matrix, then
$(X^{\prime},\ast^{\prime})=(X,\ast)$, the function $f$ is the identity
function $f=1_{X}$ and $R^{\prime}\subseteq X^{n}$ is the intersection of all
relations containing $R$ as a subrelation and which are $M$-sharp for each
matrix $M$ in $S$.

Thus, a colimit of a small diagram in
$\mathsf{Inj}_{S}\mathbf{Rel}_{\ast}^{n}$ can be obtained by applying the
construction above to the colimit of the same diagram in
$\mathbf{Rel}_{\ast}^{n}$. In particular, each
$(\mathsf{Inj}_{S}\mathbf{Rel}_{\ast}^{n})^{\mathsf{op}}$ is a finitely
complete pointed category. These remarks together with Theorem 2.2 bring us to
the following result:

######  Theorem 5.1.

Consider two matrix sets $S$ and $U$. If for any non-zero natural number $n$,
every $n$-ary pointed relation $R$ on any pointed set $(X,\ast)$ that is
$M$-sharp for every matrix $M$ in $S$ is $N$-closed for every matrix $N$ in
$U$ having $n$ rows, then every finitely complete pointed category that has
$M$-closed relations for every $M$ in $S$ also has $N$-closed relations for
every $N$ in $U$, i.e.,
$\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}U$. The converse is also
true when no matrix in $S$ is trivial.

###### Proof.

Assume first that for any integer $n>0$, every $n$-ary pointed relation $R$ on
any pointed set $(X,\ast)$ that is $M$-sharp for every matrix $M$ in $S$ is
$N$-closed for every matrix $N$ in $U$ with $n$ rows. Consider a finitely
complete pointed category $\mathbb{C}$ that has $M$-closed relations for every
$M$ in $S$. Then every internal relation in $\mathbb{C}$ is $M$-sharp for each
$M\in S$. Considering a matrix $N\in U$ with $n$ rows, an $n$-ary internal
relation $r\colon R\rightarrowtail C^{n}$ on an object $C$ in $\mathbb{C}$ and
an arbitrary object $Y$, we need to prove that $r$ is $N$-closed over $Y$.
These induce an $n$-ary relation $R^{\prime}$ on the pointed set
$\mathbb{C}(Y,C)$ for which $g_{1},\dots,g_{n}\colon Y\to C$ are related if
and only if there exists a (necessarily unique) morphism $v\colon Y\to R$ such
that $r_{i}v=g_{i}$ for each $i\in\\{1,\dots,n\\}$. It is then easy to see
that $R^{\prime}$ is an (ordinary) $n$-ary pointed relation which is $M$-sharp
for each $M\in S$. Our assumption gives then that $R^{\prime}$ is $N$-closed,
which implies that the internal relation $r$ on $C$ is $N$-closed over $Y$.

Now assume that every finitely complete pointed category that has $M$-closed
relations for every $M$ in $S$ also has $N$-closed relations for every $N$ in
$U$. Suppose also that no matrix in $S$ is trivial. Then no matrix in $U$ can
be trivial as well since, by Theorem 3.1, $\mathbf{Set}_{\ast}^{\mathsf{op}}$
belongs to $\mathsf{mclex}_{\ast}S$ and thus to $\mathsf{mclex}_{\ast}U$. For
each positive $n$, consider the full subcategory
$\mathsf{Inj}_{U}\mathbf{Rel}_{\ast}^{n}$ of $\mathbf{Rel}_{\ast}^{n}$
consisting of $U$-injective objects. We will now apply Theorem 2.2 to the
category $\mathbb{C}=\mathbf{Rel}_{\ast}^{n}$. Let $T$ be the set of all non-
trivial matrices. For any pointed set $(X,\ast)$, the relation $X^{n}$ is
clearly $M$-sharp for every matrix $M$. So the object $(X,\ast,X^{n})$ is a
$T$-injective object in $\mathbf{Rel}_{\ast}^{n}$. For any object $(X,\ast,R)$
in $\mathbf{Rel}_{\ast}^{n}$, there is a monomorphism into such object —
namely, the inclusion $(X,\ast,R)\rightarrowtail(X,\ast,X^{n})$. By Theorem
2.2 we then get that $\mathsf{Inj}_{U}\mathbf{Rel}_{\ast}^{n}$ is the largest
full subcategory of $\mathbf{Rel}_{\ast}^{n}$ having the following properties:
it contains all $T$-injective objects, it is closed under finite limits and
its dual category has $N$-closed relations for every $N$ in $U$. By Theorem
2.2 again, the subcategory $\mathsf{Inj}_{S}\mathbf{Rel}_{\ast}^{n}$ of
$\mathbf{Rel}_{\ast}^{n}$ consisting of all $S$-injective objects has similar
properties: it contains all $T$-injective objects, it is closed under finite
limits and its dual category has $M$-closed relations for every $M$ in $S$.
The assumption that every finitely complete pointed category having $M$-closed
relations for every $M$ in $S$ has $N$-closed relations for every $N$ in $U$
gives that $\mathsf{Inj}_{S}\mathbf{Rel}_{\ast}^{n}$ must be a subcategory of
$\mathsf{Inj}_{U}\mathbf{Rel}_{\ast}^{n}$ (note that, from the paragraph
before the theorem, we know that the duals of these categories are finitely
complete pointed). So, for any non-zero natural number $n$, every $n$-ary
pointed relation $R$ on any pointed set $(X,\ast)$ that is $M$-sharp for every
matrix $M$ in $S$ is also $N$-sharp for every matrix $N$ in $U$. In
particular, this means that every such relation is $N$-closed for every matrix
$N$ in $U$ having $n$ rows. ∎

From the proof of Theorem 5.1 we can extract the following theorem, which says
that in order to prove an implication between matrix properties (in the
finitely complete pointed context), one only needs to produce a proof for a
single particular category.

######  Theorem 5.2.

Let $S$ be a matrix set and let $N\in\mathsf{matr}_{\ast}$ be a matrix with
$n$ rows. The following statements are equivalent:

  1. (1)

$\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}\\{N\\}$.

  2. (2)

The category $(\mathsf{Inj}_{S}\mathbf{Rel}_{\ast}^{n})^{\mathsf{op}}$, which
belongs to $\mathsf{mclex}_{\ast}S$, also belongs to
$\mathsf{mclex}_{\ast}\\{N\\}$.

(Notice that in the case where $S$ contains a trivial matrix, both statements
are true and the result thus also holds in that case.)

We now come to the following question. Given a matrix set $S$ and a matrix
$N\in\mathsf{matr}_{\ast}(n,m,k)$, how to decide whether every $n$-ary pointed
relation $R$ on any pointed set $(X,\ast)$ that is $M$-sharp for every matrix
$M$ in $S$ is $N$-closed? Let us denote by $\mathsf{col}_{\ast}(N)$ the
$n$-ary pointed relation on $\\{\ast,x_{1},\dots,x_{k}\\}$ containing exactly
the left columns of $N$ and $(\ast,\dots,\ast)$. Let us denote by
$\mathsf{col}_{\ast}^{S}(N)$ the intersection of all $n$-ary relations on
$\\{\ast,x_{1},\dots,x_{k}\\}$ that contain $\mathsf{col}_{\ast}(N)$ as a
subrelation and that are $M$-sharp for all $M$ in $S$. It is certainly pointed
and $M$-sharp for all $M$ in $S$. Therefore, if every $n$-ary pointed relation
on any pointed set $(X,\ast)$ that is $M$-sharp for every matrix $M$ in $S$ is
$N$-closed, then the right column $N_{\mathsf{r}}$ of $N$ belongs to
$\mathsf{col}_{\ast}^{S}(N)$. The converse is also true: If
$N_{\mathsf{r}}\in\mathsf{col}_{\ast}^{S}(N)$, then every $n$-ary pointed
relation $R$ on any pointed set $(X,\ast)$ that is $M$-sharp for every matrix
$M$ in $S$ is $N$-closed. To see this, consider an interpretation

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

of $N$ of type $(X,\ast)$ such that every left column of the interpretation
belongs to $R$. Let this interpretation be given by a pointed map
$f\colon\\{\ast,x_{1},\dots,x_{k}\\}\to X$. Then the inverse image $f^{-1}(R)$
of $R$ along $f$ will be a pointed relation on $\\{\ast,x_{1},\dots,x_{k}\\}$
that is $M$-sharp for every $M$ in $S$. Indeed, every reduction of each $M$ of
type $(\\{\ast,x_{1},\dots,x_{k}\\},\dots,\\{\ast,x_{1},\dots,x_{k}\\})$ whose
left columns belong to $f^{-1}(R)$ will have a further reduction by applying
$f$ to its entries, whose left columns belong to $R$. Then, since $R$ is
$M$-sharp, $f$ of the right column of the reduction will be in $R$, which
means the right column of the reduction will be in $f^{-1}(R)$. Now, since
$f^{-1}(R)$ is $M$-sharp for every $M$ in $S$ and since it contains
$\mathsf{col}_{\ast}(N)$, it must also contain $\mathsf{col}_{\ast}^{S}(N)$.
The fact that $N_{\mathsf{r}}\in\mathsf{col}_{\ast}^{S}(N)$ will now give that
the right column of the above interpretation of $N$ belongs to $R$. So Theorem
5.1 has the following consequence.

######  Corollary 5.3.

Consider two matrix sets $S$ and $U$. If
$N_{\mathsf{r}}\in\mathsf{col}_{\ast}^{S}(N)$ for every matrix $N$ in $U$,
then $\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}U$. The converse is
also true when no matrix in $S$ is trivial.

Note that $\mathsf{col}_{\ast}^{S}(N)$ is necessarily finite (it is a subset
of $\\{\ast,x_{1},\dots,x_{k}\\}^{n}$, when
$N\in\mathsf{matr}_{\ast}(n,m,k)$). When $S$ is finite, we can build
$\mathsf{col}_{\ast}^{S}(N)$ in finitely many steps as follows. For a given
pointed relation $R\subseteq\\{\ast,x_{1},\dots,x_{k}\\}^{n}$, we consider the
pointed relation $S(R)\subseteq\\{\ast,x_{1},\dots,x_{k}\\}^{n}$ containing
exactly $R$ and the right columns of each row-wise interpretation $B$ of type
$(\\{\ast,x_{1},\dots,x_{k}\\},\dots,\\{\ast,x_{1},\dots,x_{k}\\})$ of each
matrix $M^{\prime}\in\mathsf{matr}_{\ast}(n,m^{\prime},k^{\prime})$ whose rows
are rows of a common matrix $M$ in $S$ such that the left columns of $B$
belong to $R$. The number of all possible such $B$’s is finite (as $S$ is
finite), so $S(R)$ can be built from $R$ in finitely many steps. It is easy to
see that if $R\subseteq\mathsf{col}_{\ast}^{S}(N)$ then also
$S(R)\subseteq\mathsf{col}_{\ast}^{S}(N)$. Now, starting with
$R=\mathsf{col}_{\ast}(N)$, we can build a chain of proper subset inclusions

$\mathsf{col}_{\ast}(N)\subset S(\mathsf{col}_{\ast}(N))\subset
SS(\mathsf{col_{\ast}}(N))\subset\dots\subset SS\dots
S(\mathsf{col_{\ast}}(N))$

until $S(R)$ for the last set $R$ in the chain is equal to $R$. When this
happens, $R$ will be $M$-sharp for every $M$ in $S$, and hence
$R=\mathsf{col}_{\ast}^{S}(N)$. The chain does terminate after some finitely
many steps because each of the sets in the chain are subsets of the finite set
$\\{\ast,x_{1},\dots,x_{k}\\}^{n}$.

From the results above we can readily extract an algorithm for deciding
$\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}U$, when $S$ and $U$ are
finite matrix sets. Note that the results did not give full characterization
of $\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}U$ when $S$ contains a
trivial matrix, however, when $S$ contains a trivial matrix, one always has
$\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}U$.

The combined algorithm which deals with both the trivial and non-trivial
matrices is then the following. To decide whether
$\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}U$ where $S$ and $U$ are
finite matrix sets, do the following:

Step 1.

If $S$ contains a trivial matrix (i.e., if $S$ contains a matrix which does
not satisfies the three conditions in (3) of Theorem 3.1), then terminate the
process with positive decision for
$\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}U$.

Step 2.

For each matrix $N\in\mathsf{matr}_{\ast}(n,m,k)$ in $U$ do the following.
First expand the left part of $N$ with a column of $\ast$’s. Then, keep
expanding the left part of $N$, until it is impossible to expand it further,
with right columns of those row-wise interpretations $B$ of type
$(\\{\ast,x_{1},\dots,x_{k}\\},\dots,\\{\ast,x_{1},\dots,x_{k}\\})$ of each
matrix $M^{\prime}\in\mathsf{matr}_{\ast}(n,m^{\prime},k^{\prime})$ whose rows
are rows of a common matrix $M$ in $S$ such that the left columns of $B$, but
not its right column, can be found in the left part of $N$. If the expanded
left part of $N$ does not contain the right column of $N$, then terminate the
process with negative decision for
$\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}U$.

Step 3.

Reaching this step means that the process has not been terminated in the
previous steps. Then the process completes with positive decision for
$\mathsf{mclex}_{\ast}S\subseteq\mathsf{mclex}_{\ast}U$.

We conclude this section by recalling from [13] (and Theorem 4.2) that, given
two matrices $M$ and $N$, the above algorithm _cannot_ be used to prove that
any pointed variety of universal algebras with $M$-closed relations has
$N$-closed relations. In general, this statement is weaker than the statement
$\mathsf{mclex}_{\ast}\\{M\\}\subseteq\mathsf{mclex}_{\ast}\\{N\\}$. Actually,
the statement
$\mathsf{mclex}_{\ast}\\{M\\}\subseteq\mathsf{mclex}_{\ast}\\{N\\}$ is, in
general, even stronger than the statement that any regular [1] well-powered
pointed category with $M$-closed relations has $N$-closed relations. However,
it is shown in [12] that if $M$ is non-pointed and $N$ is the matrix from
Example 1.4 determining Mal’tsev categories, this distinction disappears. We
refer the reader to [14] for a link of this case with the matrix class of
majority categories.

##  6 Computer-assisted results

A computer implementation of our algorithm allows us to get a complete
description of the posets $\mathsf{Mclex}_{\ast}[n,m,k]$ for relatively small
values of $n,m,k$. We present those results in this section.

Before displaying these results, we describe how we chose to represent the
matrix classes in the display. For each matrix class
$\mathcal{C}\in\mathsf{Mclex}_{\ast}$, and for each choice of integers $n>0$
and $m,k\geqslant 0$, consider the set $\mathcal{C}_{n,m,k}$ of all matrices
$M$ such that $\mathcal{C}=\mathsf{mclex}_{\ast}\\{M\\}$ and
$M\in\mathsf{matr}_{\ast}(n^{\prime},m^{\prime},k^{\prime})$ for some
$n^{\prime}\leqslant n$, $m^{\prime}\leqslant m$ and $k^{\prime}\leqslant k$.
Now consider the subset $\mathcal{C}^{\mathsf{R}}_{n,m,k}$ of
$\mathcal{C}_{n,m,k}$ consisting of those matrices that have minimal number of
rows; the subset $\mathcal{C}^{\mathsf{RC}}_{n,m,k}$ of
$\mathcal{C}^{\mathsf{R}}_{n,m,k}$ consisting of those matrices that have
minimal number of columns and the subset $\mathcal{C}^{\mathsf{RCV}}_{n,m,k}$
of $\mathcal{C}^{\mathsf{RC}}_{n,m,k}$ consisting of those matrices whose
entries lie in $\\{\ast,x_{1},\dots,x_{v}\\}$ for the smallest possible $v$.
We then view each matrix in $\mathcal{C}^{\mathsf{RCV}}_{n,m,k}$ as a sequence
of elements from $\\{x_{1},\dots,x_{k},\ast\\}$ by juxtaposing the transpose
of each column next to each other, starting with the right column and
continuing with the left columns from left to right. We order these matrices
using the lexicographical ordering coming from this way of displaying matrices
and from the order $x_{1}<\dots<x_{k}<\ast$. A matrix will be called an
_$(n,m,k)$ -canonical_ matrix if it is the smallest element of
$\mathcal{C}^{\mathsf{RCV}}_{n,m,k}$ under this ordering for some
$\mathcal{C}\in\mathsf{Mclex}_{\ast}$. It is easy to see that any matrix
$M\in\mathsf{matr}_{\ast}(n^{\prime},m^{\prime},k^{\prime})$ which is
$(n,m,k)$-canonical for some $n\geqslant n^{\prime}$, $m\geqslant m^{\prime}$
and $k\geqslant k^{\prime}$ is also
$(n^{\prime},m^{\prime},k^{\prime})$-canonical. In this section, we will
however see that, for the matrix class of strongly unital categories (see
Example 1.4), the $(2,3,2)$-canonical matrix is not the same as the
$(3,3,1)$-canonical matrix. In the following lemma, we again consider that the
set of possible entries of a matrix is ordered via $x_{1}<\dots<x_{k}<\ast$.

######  Lemma 6.1.

Let $n>0$ and $m,k\geqslant 0$ be integers and $M$ an $(n,m,k)$-canonical
matrix. The following properties hold for $M$:

  * •

There exist integers $a,b\geqslant 0$ such that the right column of $M$
consists of $a$ many $x_{1}$’s followed by $b$ many $\ast$’s.

  * •

$M$ has no duplicate rows or left columns.

  * •

Each left column of $M$ contains at least one variable (i.e., an entry
different from $\ast$).

  * •

The left columns of $M$ are lexicographically ordered.

  * •

The first $a$ rows of $M$ are lexicographically ordered.

  * •

The last $b$ rows of $M$ are lexicographically ordered.

  * •

For each of the first $a$ rows of $M$ and for each $1<i<j\leqslant k$, if
$x_{j}$ appears in the left part of the row, then so does $x_{i}$ and the
first occurrence of $x_{j}$ appears after the first occurrence of $x_{i}$.

  * •

For each of the last $b$ rows of $M$ and for each $1\leqslant i<j\leqslant k$,
if $x_{j}$ appears in the left part of the row, then so does $x_{i}$ and the
first occurrence of $x_{j}$ appears after the first occurrence of $x_{i}$.

The proof of this lemma is similar to the proof of Lemma 4.1 in [13].

###### Proof.

This follows easily from the fact that, given a matrix in some
$\mathsf{matr}_{\ast}(n^{\prime},m^{\prime},k^{\prime})$, one can, without
changing the corresponding matrix property, do the following:

  * •

in each row, permute the variables $x_{1},\dots,x_{k^{\prime}}$;

  * •

permute the rows and the left columns;

  * •

delete the duplicated rows and left columns;

  * •

delete a left column which contains only $\ast$’s.∎

We now show the computations of the posets $\mathsf{Mclex}_{\ast}[n,m,k]$ for
various values of the parameters $n,m,k$ obtained by the computer. When
displaying such a poset $\mathsf{Mclex}_{\ast}[n,m,k]$, we represent each
matrix class by the $(n,m,k)$-canonical matrix giving rise to the considered
matrix class. This matrix will be represented by a gird where the right column
of the matrix is highlighted in gray and where each variable $x_{i}$ has been
represented by its index $i$. An arrow from a matrix $M$ to a matrix $N$
represents the inclusion
$\mathsf{mclex}_{\ast}\\{M\\}\subseteq\mathsf{mclex}_{\ast}\\{N\\}$. We do not
draw an arrow if it can be obtained by a path of arrows (we thus display the
reflexive and transitive reduction of the poset).

We start with Figure 1 which represents the poset
$\mathsf{Mclex}_{\ast}[2,3,2]$. According to our convention, the bottom
element of that poset is the matrix class generated by the trivial matrix
$\left[\begin{array}[]{c|c}&x_{1}\end{array}\right]$, i.e., the collection of
categories equivalent to $\mathbf{1}$. The top element is the matrix class
generated by the anti-trivial matrix
$\left[\begin{array}[]{c|c}&\ast\end{array}\right]$, i.e., the collection of
all finitely complete pointed categories. In view of Example 1.4, the matrix
on the left of the second row (from the top) represents the collection of
subtractive categories and the matrix on the right of the second row represent
the collection of unital categories. The matrix in the third row represents
the collection of strongly unital categories and the matrix in the fourth row
represents the collection of pointed Mal’tsev categories. This poset already
illustrates a result from [17], where it is shown that a finitely complete
pointed category is strongly unital if and only if it is subtractive and
unital. This situation is somehow special as we recall that in general we do
not know whether the intersection of two matrix classes is again a matrix
class. It also illustrates that pointed Mal’tsev categories are in particular
strongly unital, which was shown in [4]. We also computed the posets
$\mathsf{Mclex}_{\ast}[2,14,3]$ and $\mathsf{Mclex}_{\ast}[2,10,4]$ which are
both equal to $\mathsf{Mclex}_{\ast}[2,3,2]$. We therefore conjecture that
Figure 1 shows all matrix classes induced by two-row matrices, although we
have not been able to formally prove it yet.

Figure 1: Hasse diagram of the poset $\mathsf{Mclex}_{\ast}[2,3,2]$.

We then tackle the problem to compute all matrix classes induced by matrices
with two left columns. In view of the discussion at the end of Section 4, it
is enough to compute the poset $\mathsf{Mclex}_{\ast}[6,2,1]$, which becomes
an easy task for the computer. The results are displayed in Figure 2. Let us
notice that all matrices represented there have at most three rows, which
indicates that the bound of $2m^{m}-(m-1)^{m}-1$ from Section 4 might be far
from optimal.

Figure 2: Hasse diagram of the poset $\mathsf{Mclex}_{\ast}[6,2,1]$.

Our next display is Figure 3 which represents the poset
$\mathsf{Mclex}_{\ast}[3,6,1]$. Since $6=(1+1)^{3}-2$, this poset contains all
matrix classes generated by a matrix with three rows and one variable. The
blue boxes group together the matrix classes which have same Bourn
localization in $\mathsf{Mclex}$, i.e., same image under
$\mathsf{Loc}\colon\mathsf{Mclex}_{\ast}\to\mathsf{Mclex}$. The words
appearing in some of these boxes indicate the common Bourn localization of the
matrix classes appearing in each of these boxes (see Example 1.4). These
conventions will be used also in subsequent figures as well. By a _minority
category_ , we mean here a finitely complete category which has $M$-closed
relations for the non-pointed matrix

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

extending the notion of a variety of universal algebras with a minority term.
It can be easily proved using our algorithm (see below) that the first matrix
in the eighth row (from the top) of Figure 3 represents the matrix class of
strongly unital categories, represented by another matrix in the third row of
Figure 1 (which means in particular that the $(2,3,2)$-canonical matrix for
this matrix class is not the same as the $(3,6,1)$-canonical matrix). This
leads to the following remark.

######  Remark 6.2.

The collection of strongly unital categories is

$\mathsf{mclex}_{\ast}\left\\{\left[\begin{array}[]{ccc|c}x_{1}&\ast&\ast&x_{1}\\\
x_{2}&x_{1}&x_{2}&x_{1}\end{array}\right]\right\\}=\mathsf{mclex}_{\ast}\left\\{\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]\right\\}.$

In order to illustrate the algorithm, let us display some tableaux that
represent the proof of each inclusion of the above equality. These tableaux
will be called _$\text{lex}_{\ast}$ -tableaux_ (analogously to the ‘lex-
tableaux’ from [13], where as usual ‘lex’ abbreviates ‘left exact’, a synonym
of ‘finitely complete’). A proof of the inclusion

$\mathsf{mclex}_{\ast}\left\\{\left[\begin{array}[]{ccc|c}x_{1}&\ast&\ast&x_{1}\\\
x_{2}&x_{1}&x_{2}&x_{1}\end{array}\right]\right\\}\subseteq\mathsf{mclex}_{\ast}\left\\{\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]\right\\}$

can be represented by the $\text{lex}_{\ast}$-tableau

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

where the double vertical line separates the two given matrices. In such a
tableau, the matrix class induced by the matrix in the top left is being
proved to be included in the matrix class induced by the matrix in the top
right. The columns below the first horizontal line and on the right of the
double vertical line are being added to the left columns of the second matrix
by the algorithm. In the first step (just below the first horizontal line), we
add a column of $\ast$’s as required by the algorithm. Then, the added columns
come from row-wise interpretations of the first matrix; these row-wise
interpretations are represented on the left of the double vertical line.
Reaching the right column of the second matrix in the last step proves the
desired inclusion of matrix classes. The following $\text{lex}_{\ast}$-tableau

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

represents a proof of

$\mathsf{mclex}_{\ast}\left\\{\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]\right\\}\subseteq\mathsf{mclex}_{\ast}\left\\{\left[\begin{array}[]{ccc|c}x_{1}&\ast&\ast&x_{1}\\\
x_{2}&x_{1}&x_{2}&x_{1}\end{array}\right]\right\\}.$

Figure 3 illustrates the characterization of Mal’tsev categories in terms of
the fibration of points from [4] and [17] recalled in Section 4. From Remark
4.4, we know that $\mathsf{Loc}$ restricts to a surjective order-preserving
function
$\mathsf{Loc}\colon\mathsf{Mclex}_{\ast}[3,6,1]\twoheadrightarrow\mathsf{Mclex}[3,7,2]$
where $\mathsf{Mclex}[3,7,2]$ has been displayed in Figure 2 of [13] and
contains all $\mathsf{mclex}\\{M\\}$ for a non-pointed matrix $M$ with three
rows, two variables and at least one left column. Therefore, we can recover
from Figure 3 of the present paper that $\mathsf{Mclex}[3,7,2]$ has $13$
elements (represented by the $13$ blue boxes). Moreover, since $\mathsf{Loc}$
is an order preserving function, we know that an arrow in Figure 3 displayed
from a matrix in some box to a matrix in another box induces an arrow in the
same direction between the corresponding elements of $\mathsf{Mclex}[3,7,2]$.
However, Figure 3 does not contain all the information about
$\mathsf{Mclex}[3,7,2]$ as $\mathsf{Loc}$ does not reflect the order. For
instance, any finitely complete arithmetical category is a minority category,
but no arrow in Figure 3 indicates this implication. The ‘missing arrow’
appears in Figure 4.

Figure 3: Hasse diagram of the poset $\mathsf{Mclex}_{\ast}[3,6,1]$.

Let us now consider Figure 4 which represents $\mathsf{Mclex}_{\ast}[3,3,2]$.
This figures illustrates Remark 4.3 since each non-pointed matrix represented
in that figure is the bottom element of the subposet of
$\mathsf{Mclex}_{\ast}$ formed by the blue box containing it. Moreover, the
top element of $\mathsf{Mclex}_{\ast}$ is the only one in its blue box and
similarly for the bottom element of $\mathsf{Mclex}_{\ast}$.

Figure 4: Representation of the poset $\mathsf{Mclex}_{\ast}[3,3,2]$.

We have also been able to compute $\mathsf{Mclex}_{\ast}[3,m,2]$ for
$m\leqslant 6$, but $\mathsf{Mclex}_{\ast}[3,4,2]$ is already too big to
reasonably fit on one page. We have instead produced Figure 5 displaying the
size of these posets.

$\begin{array}[]{|r|c|c|c|c|c|c|c|}\hline\cr m=&0&1&2&3&4&5&6\\\
\hline\cr|\mathsf{Mclex}_{\ast}[3,m,2]|=&2&2&8&42&217&1137&5100\\\
\hline\cr\end{array}$

Figure 5: Size of $\mathsf{Mclex}_{\ast}[3,m,2]$ for $m\leqslant 6$.

Figure 6 displays the poset $\mathsf{Mclex}_{\ast}[4,3,1]$. As we can see,
even when considering one variable matrices, the poset can quickly get
complex.

Figure 6: Hasse diagram of the poset $\mathsf{Mclex}_{\ast}[4,3,1]$.

We have also computed the posets $\mathsf{Mclex}_{\ast}[4,m,1]$ for any value
of $m$. However, for $m=4$, this poset already contains $156$ elements and
cannot be represented with enough readability on a single page. We have
instead displayed the size of these posets on Figure 7. Let us remark here
that the matrix classes of unital, strongly unital and subtractive categories
respectively are elements of $\mathsf{Mclex}_{\ast}[4,14,1]$, while the matrix
classes of Mal’tsev, majority, arithmetical and minority pointed categories
respectively are not elements of $\mathsf{Mclex}_{\ast}[4,14,1]$.

$0$$5$$10$$15$$0$$1{,}000$$2{,}000$$3{,}000$$4{,}000$$m$$|\mathsf{Mclex}_{\ast}[4,m,1]|$

$0$$2$$4$$6$$8$$10$$12$$14$$16$$0$$200$$400$$600$$800$$m$$|\mathsf{Mclex}_{\ast}[4,m,1]|-|\mathsf{Mclex}_{\ast}[4,m-1,1]|$

$\begin{array}[]{|r|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline\cr
m=&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14+\\\
\hline\cr|\mathsf{Mclex}_{\ast}[4,m,1]|=&2&2&8&48&156&453&1066&1953&2841&3502&3822&3957&4007&4023&4027\\\
\hline\cr\end{array}$

Figure 7: Size of $\mathsf{Mclex}_{\ast}[4,m,1]$.

We conclude the paper with the representation of some subposets of some
$\mathsf{Mclex}_{\ast}[n,m,k]$ formed by elements with the same Bourn
localization. We start with Figure 8 which displays the subposet of
$\mathsf{Mclex}_{\ast}[3,4,2]$ formed by matrix classes whose Bourn
localization is the collection of Mal’tsev categories. The analogous poset
defined by replacing $\mathsf{Mclex}_{\ast}[3,4,2]$ with
$\mathsf{Mclex}_{\ast}[3,5,2]$ contains $268$ elements and is too big to be
reasonably displayed on a single page. As we already know from Remark 4.3, the
matrix class of Mal’tsev pointed categories is the bottom element of this
subposet of $\mathsf{Mclex}_{\ast}[3,4,2]$. The two maximal elements of this
subposet are the matrix classes of unital and subtractive categories. They
intersection (i.e., the matrix class of strongly unital categories) is
represented by the left matrix in the seventh row of that figure. Figure 8
gives thus many more characterizations of Mal’tsev categories in terms of the
fibres of the fibration of points in the style of [4, 17].

Figure 8: Hasse diagram of the subposet of $\mathsf{Mclex}_{\ast}[3,4,2]$
formed by matrix classes whose Bourn localization is the collection of
Mal’tsev categories.

Figure 9 represents the subposet of $\mathsf{Mclex}_{\ast}[4,14,1]$ formed by
matrix classes whose Bourn localization is the collection of Mal’tsev
categories. Since the matrix class of pointed Mal’tsev categories does not
belong to $\mathsf{Mclex}_{\ast}[4,14,1]$, it is not represented on this
figure. The bottom element of this subposet of $\mathsf{Mclex}_{\ast}[4,14,1]$
is the matrix class of strongly unital categories, represented here by its
$(3,3,1)$-canonical matrix. Again, the two maximal elements of this subposet
are the matrix classes of unital and subtractive categories. Let us remark
that, in both Figures 8 and 9, the number of elements between the matrix class
of strongly unital categories and the matrix class of unital categories is
much bigger than the number of elements between the matrix class of strongly
unital categories and the matrix class of subtractive categories. We can also
observe that, although we considered all matrix classes in
$\mathsf{Mclex}_{\ast}[4,14,1]$ whose Bourn localization is the collection of
Mal’tsev categories, they are all represented by matrices with at most seven
left columns.

Figure 9: Hasse diagram of the subposet of $\mathsf{Mclex}_{\ast}[4,14,1]$
formed by matrix classes whose Bourn localization is the collection of
Mal’tsev categories.

There are $123$ matrix classes in $\mathsf{Mclex}_{\ast}[3,6,2]$ whose Bourn
localization is the collection of finitely complete arithmetical categories,
which is too many to draw them on a single page with enough readability.
Instead, we show in Figure 10 the subposet of $\mathsf{Mclex}_{\ast}[3,5,2]$
formed by those matrix classes whose Bourn localization is the collection of
finitely complete arithmetical categories. As expected, the bottom element of
this subposet is the matrix class of arithmetical finitely complete pointed
categories. There are only four matrix classes in
$\mathsf{Mclex}_{\ast}[4,14,1]$ whose Bourn localization is the collection of
finitely complete arithmetical categories. Since they can all be represented
by a matrix in $\mathsf{matr}_{\ast}(4,3,1)$, they appear in the same blue box
in Figure 6.

Figure 10: Hasse diagram of the subposet of $\mathsf{Mclex}_{\ast}[3,5,2]$
formed by matrix classes whose Bourn localization is the collection of
(finitely complete) arithmetical categories.

Figure 11 represents the subposet of $\mathsf{Mclex}_{\ast}[3,5,2]$ formed by
matrix classes whose Bourn localization is the collection of majority
categories. The subposet of $\mathsf{Mclex}_{\ast}[3,6,2]$ defined analogously
having $89$ elements, we choose not to represent it here for the sake of
readability. The subposet of $\mathsf{Mclex}_{\ast}[4,14,1]$ formed by matrix
classes whose Bourn localization is the collection of majority categories has
only $3$ elements and is displayed in Figure 12. Notice that all the matrix
classes appearing there are represented by a matrix with at most four left
columns.

Figure 11: Hasse diagram of the subposet of $\mathsf{Mclex}_{\ast}[3,5,2]$
formed by matrix classes whose Bourn localization is the collection of
majority categories. Figure 12: Hasse diagram of the subposet of
$\mathsf{Mclex}_{\ast}[4,14,1]$ formed by matrix classes whose Bourn
localization is the collection of majority categories.

We have found very few matrix classes whose Bourn localization is the
collection of minority categories. There is only one which belongs to
$\mathsf{Mclex}_{\ast}[4,14,1]$: it is represented by a matrix in
$\mathsf{matr}_{\ast}(3,2,1)$ in Figure 6. There are $12$ which belong to
$\mathsf{Mclex}_{\ast}[3,6,2]$ and the corresponding poset has been
represented in Figure 13. As we can notice, all these matrix classes actually
belong to $\mathsf{Mclex}_{\ast}[3,5,2]$.

Figure 13: Hasse diagram of the subposet of $\mathsf{Mclex}_{\ast}[3,6,2]$
formed by matrix classes whose Bourn localization is the collection of
minority categories.

### Acknowledgments

The authors would like to warmly thank Zurab Janelidze for interesting
discussions on the topic presented here. They are also grateful to the
anonymous referee for his/her remarks to improve the reader’s experience. The
first author is grateful to the National Graduate Academy for Mathematical and
Statistical Sciences (NGA(MaSS)) for its generous financial support. The
second author also acknowledges the FNRS for its generous support.

### Data availability

Data sharing not applicable to this article as no datasets were generated or
analysed during the current study.

## References

  * [1] M. Barr, P.A. Grillet and D.H. van Osdol, Exact categories and categories of sheaves, Springer Lect. Notes Math. 236 (1971).
  * [2] F. Borceux, Handbook of Categorical Algebra 2, Encyclopedia of Mathematics and Its Applications, Cambridge University Press (1994).
  * [3] D. Bourn, Normalization equivalence, kernel equivalence and affine categories, Springer Lect. Notes Math. 1488 (1991), 43–62.
  * [4] D. Bourn, Mal’cev categories and fibration of pointed objects, Appl. Categ. Struct. 4 (1996), 307–327.
  * [5] A. Carboni, J. Lambek and M.C. Pedicchio, Diagram chasing in Mal’cev categories, J. Pure Appl. Algebra 69 (1991), 271–284.
  * [6] A. Carboni, M.C. Pedicchio and N. Pirovano, Internal graphs and internal groupoids in Mal’cev categories, CMS Conf. Proc. 13 (1992), 97–109.
  * [7] M. Gran, D. Rodelo and I. Tchoffo Nguefeu, Facets of congruence distributivity in Goursat categories, J. Pure Appl. Algebra 224 (2020), 106380.
  * [8] M. Hoefnagel, Majority categories, Theory Appl. Categ. 34 (2019), 249–268.
  * [9] M. Hoefnagel, Products and coequalizers in pointed categories, Theory Appl. Categ. 34 (2019), 1386–1400.
  * [10] M. Hoefnagel, Characterizations of majority categories, Appl. Categ. Struct. 28 (2020), 113–134.
  * [11] M. Hoefnagel, Anticommutativity and the triangular lemma, Algebra Universalis 82 (2021).
  * [12] M. Hoefnagel and P.-A. Jacqmin, When a matrix condition implies the Mal’tsev property, in preparation.
  * [13] M. Hoefnagel, P.-A. Jacqmin and Z. Janelidze, The matrix taxonomy of finitely complete categories, Theory Appl. Categ. 38 (2022), 737–790.
  * [14] M. Hoefnagel, P.-A. Jacqmin, Z. Janelidze and E. van der Walt, On binary matrix properties, submitted to Quaestiones Mathematicae.
  * [15] Z. Janelidze, Characterization of pointed varieties of universal algebras with normal projections, Theory Appl. Categ. 11 (2003), 212–214.
  * [16] Z. Janelidze, Normal product projections, subtractive categories, and elementary term conditions in universal and categorical algebra, PhD thesis, Tbilisi State University (2005).
  * [17] Z. Janelidze, Subtractive categories, Appl. Categ. Struct. 13 (2005), 343–350.
  * [18] 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.
  * [19] Z. Janelidze, Closedness properties of internal relations II: Bourn localization, Theory Appl. Categ. 16 (2006), 262–282.
  * [20] M.C. Pedicchio, Arithmetical categories and commutator theory, Appl. Categ. Structures 4 (1996), 297–305.
  * [21] T. Weighill, Mal’tsev objects, $R_{1}$-spaces and ultrametric spaces, Theory Appl. Categ. 32 (2017), 1485–1500.

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