# A polynomial-time algorithm for deciding the Hilbert Nullstellensatz over
$\mathbb{Z}_{2}$. A proof of $\mathbf{P}=\mathbf{NP}$ hypothesis

Petar P. Petrov Email<EMAIL_ADDRESS>
(August 28, 2024)

###### Abstract

Let ${\mathbf{P}}$ be the class of polynomial-time decision problems and
$\mathbf{NP}$ be the class of nondeterministic polynomial time decision
problems. We prove the following.

Theorem 3. The classes ${\mathbf{P}}$ and $\mathbf{NP}$ are equivalent. That
is, ${\mathbf{P}}=\mathbf{NP}$.

Theorem 3 gives a positive answer to the question

$\hbox{Does }{\mathbf{P}}=\mathbf{NP}?,$

see S. Cook, The $P$ versus $NP$ problem, Official problem description,
www.claymath.org
/millennium-problems. Crucial for its proof is Theorem 2, from which it
follows that the $\mathbf{NP}$-complete problem of deciding the Hilbert
Nullstellensatz over $\mathbb{Z}_{2}$ belongs to the class ${\mathbf{P}}$.

Theorem 2. There is a constructive algorithm for deciding the Hilbert
Nullstellensatz over $\mathbb{Z}_{2}$, where $\mathbb{Z}_{2}$ is the space of
all complex numbers with integer real and imaginary parts. The number
$s(n,m_{\sigma})$ of basic steps of the algorithm, where $n$ is the number of
variables and $m_{\sigma}$ is the total length of input polynomials, satisfies
the inequality

$\displaystyle s(n,m_{\sigma})$ $\displaystyle\leq$ $\displaystyle
c_{2}\\{m_{\sigma}^{2}\log
m_{\sigma}+\min\\{[m_{\sigma}^{(1)}]^{3},(d_{1})^{3}\\}+\sum_{\ell=1}^{n-2}N^{(l)}\min\\{[m_{\sigma}^{(\ell+1)}]^{2},(d_{\ell+1})^{2})\\}$
$\displaystyle+N^{(n-1)}\min\\{m_{\sigma},d_{n}\\}\\}$

where $c_{2}$ is an absolute constant, $\\{d_{\ell}\\}_{\ell=1}^{n}$ are the
maximal partial degrees in $\\{z_{\ell}\\}_{\ell=1}^{n}$, respectively,
$m_{\sigma}^{(\ell)}$ is the total length of the
$(z_{1},z_{2},\ldots,z_{\ell})$-polynomial coefficients in front of
$z_{\ell+1}^{j}$, $j=0,1,\ldots,d_{\ell+1}$, from all
$(z_{1},z_{2},\ldots,z_{\ell+1})$-sub-monomials, $\ell=1,2,\ldots,n-1$, and
$N^{(\ell)}$ is the number in the natural order of the major
$(z_{1},z_{2},\ldots,z_{\ell})$-sub-monomial, $\ell=1,2,\ldots,n-1$.

Keywords: Complexity classes, P versus NP problem, Completeness, Hilbert
Nullstellensatz.

MSC(2020): 32A08, 68Q15, 68Q17, 68Q25, 68R07, 68R10, 68T20, 90B10, 90C35.

##  1 Introduction

The $\mathbf{P}$ versus $\mathbf{NP}$ problem (Cook [6], Fortnow [7]) is
formulated using the notion of formal computer. The standard way to define the
class $\mathbf{P}$ is through the notion of Turing machine (Turing [18]),
which historically is the first definition of formal computer. Informally,
$\mathbf{P}$ is the class of decision problems, solvable in polynomial time
(PT), that is, in number of steps, bounded by a fixed polynomial of the length
of input. More precisely, the class $\mathbf{P}$ is defined in terms of finite
alphabets and languages. Languages are finite non-empty sets of finite strings
with at least two elements, based on the corresponding alphabet. Having a
Turing machine $M$ and a language, we define by $L(M)$ the set of all strings
of the language acceptable by $M$. These are all (input) strings of the
language, for which $M$ halts in finite number of steps in a fixed state,
called $q_{\hbox{\rm\scriptsize accept}}$. If we restrict ourselves on strings
of length at most $n$ and denote by $T_{M}(n)$ the longest run of $M$ for such
input strings, then we say that M runs in polynomial time (PT) if there exists
a $k$ such that for all n, $T_{M}(n)\leq n^{k}+k$, and define the class
$\mathbf{P}$ as follows:

$\mathbf{P}:=\\{L\leavevmode\nobreak\ |\leavevmode\nobreak\
L=L(M)\hbox{\leavevmode\nobreak\ for some Turing machine M that runs in {\it
PT}}\\}\leavevmode\nobreak\ \hbox{(Cook
\cite[cite]{[\@@bibref{}{Cook2000}{}{}]})}.$

Let us describe more in detail the notion of Turing machine $M$. It deals with
(finite) alphabets $\Gamma$ (including the blank symbol $b$) and subsets
$\Sigma\subset\Gamma$ ($\Sigma$ not containing b), languages $\Gamma^{*}$ and
$\Sigma^{*}$ (finite sets of strings over $\Gamma$ and $\Sigma$,
respectively), and states and configurations (Cook [6]). Let us imagine a tape
head, moving on an infinite tape consisting of cells containing symbols from
$\Gamma$. The way this head is moving on the tape and what is reading/printing
is completely determined by a finite set of states $Q$ and a transition
function $\delta$,

$\delta\,:\,(Q\setminus\\{q_{\hbox{\rm\scriptsize
accept}},q_{\hbox{\rm\scriptsize reject}}\\})\times\Gamma\rightarrow
Q\times\Gamma\times\\{-1,1\\},$

where $\delta(q,s)=(q^{\prime},s^{\prime},h)$ has the interpretation that, if
at a certain step the machine $M$ is in state $q$ with a head, pointing to a
cell containing symbol $s\in\Gamma$, then the transition function $\delta$
decides in a unique way $\delta(q,s)$ to (over)write $s^{\prime}\in\Gamma$
onto the current cell and to move the tape head to the left (if $h=-1$) or to
the right (if $h=1$), choosing thus a unique new state $q^{\prime}$. In the
beginning, the tape stores only a compact (with no blank symbols, or empty)
string $w$ (input data) from $\Sigma^{*}$ and the head is positioned on the
left most symbol of $w$. In this way, $M$ is passing from a state to state
with the help of the transition function $\delta$, in the end finding itself
in one of the following situations - it either halts in one of the two halting
configurations $q_{\hbox{\scriptsize accept}}$ and $q_{\hbox{\scriptsize
reject}}$, or infinitely passes from configuration to configuration. In more
precise words, the set $L(M)$ defined above is the set of all decidable input
strings of $\Sigma^{*}$. That is, there exists a Turing machine $M$ that halts
in $q_{\hbox{\scriptsize accept}}$ for all input strings from $L(M)$. In
addition, $\mathbf{P}$ is the class of all those $L(M)$, for which the halting
accomplishes in a polynomial time.

Next we extend the scope of polynomial-time decision problems $\bf P$ to the
nondeterministic polynomial time class of languages $\mathbf{NP}$, using the
definition of checking relation (Cook [6]). Given finite alphabets $\Sigma$
and $\Sigma_{1}$, a checking relation $R$ is defined as
$R\subseteq\Sigma^{*}\times\Sigma_{1}^{*}$. A language $L_{R}$ over the
alphabet $\Sigma\cup\Sigma_{1}\cup\\{\\#\\}$ is associated with every binary
relation $R$ of this type, where $\\#\notin\Sigma$ and

$L_{R}:=\\{w\\#y\leavevmode\nobreak\ |\leavevmode\nobreak\ R(w,y)\\}.$

######  Definition 1.

A language $L$ over $\Sigma$ is in the class $\mathbf{NP}$, if and only if
there is a $k\in{\mathbb{N}}$ and a polynomial-time checking relation $R$ such
that for all $w\in\Sigma^{*}$,

$w\in L\,\Longleftrightarrow\,\exists y\,\hbox{\,such
that\,}(|y|\leq|w|^{k}\,\hbox{and\,}R(w,y)),$

where $|w|$ and $|y|$ are the lengths of $w$ and $y$, respectively.

Main Problem (Cook [6]).

$\hbox{\rm Does}\leavevmode\nobreak\
\mathbf{P}=\mathbf{NP}\hbox{\,?}\leavevmode\nobreak\ \hbox{\rm}$ (1)

The importance of the Main Problem (1) stems from the remarkable practical
consequences of a constructive proof of $\mathbf{P}=\mathbf{NP}$ in
cryptography (see i.e. Horie and Watanabe [11], De Abishek Kumarasubramanian
and Venkatesan [1]), operations research (see i.e. Robinson[15]), life
sciences (see i.e. Berger and Leighton [3]), etc. In order to prove the
equivalence of the classes $\mathbf{P}$ and $\mathbf{NP}$, we need the
definition of $\mathbf{NP}$-completeness. A notion of
$\mathbf{NP}$-completeness was first introduced by Cook in [5], where it was
shown that several natural problems, including Satisfiability problem (Aho,
Hopcroft and Ullman [2]), 3-SAT problem ([2]) and Subgraph isomorphism problem
(Ullmann [19]), are $\mathbf{NP}$-complete. A year later Karp [12] introduced
the notation $\mathbf{P}$ and $\mathbf{NP}$, which is commonly in use, and
redefined $\mathbf{NP}$-completeness in terms of polynomial-time reducibility,
definition that has become standard. Independently of Cook and Karp, Levin
[13] defined the notion of Universal search problem, similar to the
$\mathbf{NP}$-complete problem, and gave six examples, including
Satisfiability problem. Problems related to the importance of (1), as well as
to the consequences of its solution, were also considered before 1971 (Nash
[14], Hartmanis [9]). The standard definition of $\mathbf{NP}$-completeness is
based on the notion of $p$-reducibility.

######  Definition 2.

Let $L_{i}$ be languages over $\Sigma_{i}$, $i=1,2$. Then
$L_{1}\leq_{\hbox{\scriptsize p}}L_{2}$ or $L_{1}$ is $p$-reducible to $L_{2}$
if and only if there is a polynomial time function
$f\,:\,\Sigma_{1}^{*}\rightarrow\Sigma_{2}^{*}$ such that $x\in
L_{1}\leavevmode\nobreak\ \Longleftrightarrow\leavevmode\nobreak\ f(x)\in
L_{2}$, for all $x\in\Sigma_{1}^{*}$.

######  Definition 3.

A language $L$ is $\mathbf{NP}$-complete if and only if $L$ is in
$\mathbf{NP}$, and $L^{\prime}\leq_{\hbox{\scriptsize p}}L$ for every language
$L^{\prime}$ in $\mathbf{NP}$.

There are hundreds of known $\mathbf{NP}$-complete problems. Their importance
for resolving the Main Problem (1) is based on the following statement (Cook
[6]), and especially on its part (c).

######  Proposition 1.

(a) If $L_{1}\leq_{\hbox{\scriptsize p}}L_{2}$ and $L_{2}\in{\mathbf{P}}$,
then $L_{2}\in{\mathbf{P}}$.

(b) If $L_{1}$ is $\mathbf{NP}$-complete, $L_{2}\in\mathbf{NP}$ and
$L_{1}\leq_{\hbox{\scriptsize p}}L_{2}$, then $L_{2}$ is
$\mathbf{NP}$-complete.

(c) If $L$ is $\mathbf{NP}$-complete and $L\in{\mathbf{P}}$, then
${\mathbf{P}}=\mathbf{NP}$.

In order to use Proposition 1 (c) to give an answer "Yes" to the Main Problem
(1), we are going to consider a particular $\mathbf{NP}$-complete problem,
namely the problem for deciding the Hilbert Nullstellensatz over
${\mathbb{Z}}_{2}$ (Smale [16]). As it is mentioned by Smale [16], there is no
sense to make use of the formal definition of Turing machine for this problem.
From practical point of view, it is much more useful to show existence of a
polynomial-time constructive algorithm for solving it (Cook [6]). Therefore,
in the next section we will introduce our own definitions and notations,
describing a kind of a formal computer, more practically oriented, but
resembling that of a Turing machine.

##  2 Definitions and notations

  * •

Let $n\in{\mathbb{N}}$. In what follows, $c$ will denote different positive
constants.

  * •

$\mathscr{P}_{n}$ will be the set of all complex polynomials of $n$ variables
$\mbox{\boldmath$z$}:=\mbox{\boldmath$z$}^{(n)}:=(z_{1},z_{2},\ldots,z_{n})$.

  * •

Let there be given a sequence of polynomials
$\\{f_{i}\\}_{i=1}^{k}\subset\mathscr{P}_{n}$,
$f_{i}:=f_{i}(\mbox{\boldmath$z$}):=\sum_{\mbox{\scriptsize\boldmath$\alpha$}\in
A_{i}}c_{\mbox{\scriptsize\boldmath$\alpha$}}\mbox{\boldmath$z$}^{\mbox{\scriptsize\boldmath$\alpha$}}\\\
=\sum_{\mbox{\scriptsize\boldmath$\alpha$}\in
A_{i}}c_{\mbox{\scriptsize\boldmath$\alpha$}}\prod_{j=1}^{n}z_{j}^{\alpha_{j}}$,
where
$\\{c_{\mbox{\scriptsize\boldmath$\alpha$}}\\}_{\mbox{\scriptsize\boldmath$\alpha$}\in
A_{i}}$ is the set of non-zero coefficients of $f_{i}$, $i=1,2,\ldots,k$.

  * •

The number of monomials in a polynomial from the sequence
$\\{f_{i}\\}_{i=1}^{k}$ will be denoted by $m_{i}$, $i=1,2,\ldots,k$, and the
total number of monomials by $m_{\sigma}:=\sum_{i=1}^{k}m_{i}$. Let also, for
$j=1,2,\ldots,n$, $d_{j}$ be the maximal degree of $z_{j}$ in all monomials
from $\\{f_{i}\\}_{i=1}^{k}$.

  * •

A basic step will be called one of the following: assignment of a complex
value to a storage cell, carrying out one of the arithmetic operations
$\\{+,-,*,/\\}$, comparison of the (real) values of two storage cells.

  * •

We will be interested in solving identities of the form
$\sum_{i=1}^{k}f_{i}(\mbox{\boldmath$z$})g_{i}(\mbox{\boldmath$z$})\equiv 1$,
where $\\{g_{i}\\}_{i=1}^{k}\subset\mathscr{P}_{n}$,
$g_{i}:=g_{i}(\mbox{\boldmath$z$}):=\sum_{\mbox{\scriptsize\boldmath$\beta$}\in
B_{i}}c_{\mbox{\scriptsize\boldmath$\beta$}}\mbox{\boldmath$z$}^{\mbox{\scriptsize\boldmath$\beta$}}$,
are uknown polynomials. The minimal number of basic steps for finding all
polynomials in a sequence $\\{g_{i}(\mbox{\boldmath$z$})\\}_{i=1}^{k}$ or
proving its non-existence will be denoted by $s(n,m_{\sigma})$.

  * •

Coefficients
$\\{\\{c_{\mbox{\scriptsize\boldmath$\alpha$}}\\}_{\mbox{\scriptsize\boldmath$\alpha$}\in
A_{i}}\\}_{i=1}^{k}$ will be stored in $m_{\sigma}$ records, following for
every $f_{i},\leavevmode\nobreak\ i=1,2,\ldots,k$, the natural order of
monomials (to be explained more precisely in the next section), accompanied by
records of the corresponding exponents ${\mathbf{\alpha}}$.

##  3 Main result

The following theorem provides a criterion for that when two polynomials from
$\mathscr{P}_{n}$ do not have a common zero.

Hilbert Nullstellensatz [over ${\mathbb{C}}$] (Hilbert [10], Smale [16, 17]).
Let there be given a sequence of polynomials
$\\{f_{i}\\}_{i=1}^{k}\subset\mathscr{P}_{n}$. The polynomials
$\\{f_{i}\\}_{i=1}^{k}$ do not possess a common zero
$\zeta\in{\mathbb{C}}^{n}$ if and only if there exists a corresponding
sequence $\\{g_{i}\\}_{i=1}^{k}\subset\mathscr{P}_{n}$ such that

$\sum_{i=1}^{k}f_{i}(\mbox{\boldmath$z$})g_{i}(\mbox{\boldmath$z$})\equiv
1,\leavevmode\nobreak\ \mbox{\boldmath$z$}\in{\mathbb{C}}^{n}.$ (2)

This statement raises naturally the question of how difficult it is to use in
practice the criterion from Hilbert Nullstellensatz over ${\mathbb{C}}$. Is it
possible a decision to be made in a polynomial time, or in other words, does
the decision problem Problem 1 below belong to the class $\mathbf{P}$? The
following conjecture was stated by Smale [16]:

######  Conjecture 1.

There is no polynomial time algorithm for deciding the Hilbert Nullstellensatz
over ${\mathbb{C}}$.

We are going to question this conjecture by exploring the following

######  Problem 1.

Given polynomials $\\{f_{i}\\}_{i=1}^{k}\subset\mathscr{P}_{n}$, check if they
possess a common zero $\zeta\in{\mathbb{C}}^{n}$ and find a upper bound for
the minimal number of basic steps to do this.

Let ${\mathbb{Z}}_{2}$ be the space of all complex numbers with integer real
and imaginary parts. One can also consider the analogue of Problem 1 over
${\mathbb{Z}}_{2}$. Since the latter is $\mathbf{NP}$-complete, it can serve
as a tool for resolving the Main Problem (1):

######  Problem 2.

Given polynomials $\\{f_{i}\\}_{i=1}^{k}$, whose coefficients are in
${\mathbb{Z}}_{2}$, check if they possess a common zero
$\zeta\in({\mathbb{Z}}_{2})^{n}$ and find a upper bound for the minimal number
of basic steps to do this.

The following two theorems present the results from our considerations of
Problems 1 and 2, respectively.

######  Theorem 1.

There is a constructive algorithm for deciding Problem 1. The number
$s(n,m_{\sigma})$ of basic steps of the algorithm satisfies the inequality

$\displaystyle s(n,m_{\sigma})$ $\displaystyle\leq$ $\displaystyle
c_{1}\\{m_{\sigma}^{2}\log
m_{\sigma}+\min\\{[m_{\sigma}^{(1)}]^{3},(d_{1})^{3}\\}+\sum_{\ell=1}^{n-2}N^{(l)}\min\\{[m_{\sigma}^{(\ell+1)}]^{2},(d_{\ell+1})^{2})\\}$
$\displaystyle+N^{(n-1)}\min\\{m_{\sigma},d_{n}\\}\\}$

where $c_{1}$ is an absolute constant, $\\{d_{\ell}\\}_{\ell=1}^{n}$ are the
maximal partial degrees in $\\{z_{\ell}\\}_{\ell=1}^{n}$, respectively,
$m_{\sigma}^{(\ell)}$ is the total length of the
$(z_{1},z_{2},\ldots,z_{\ell})$-polynomial coefficients in front of
$z_{\ell+1}^{j}$, $j=0,1,\ldots,d_{\ell+1}$, from all
$(z_{1},z_{2},\ldots,z_{\ell+1})$-sub-monomials, $\ell=1,2,\ldots,n-1$, and
$N^{(\ell)}$ is the number in the natural order of the major
$(z_{1},z_{2},\ldots,z_{\ell})$-sub-monomial, $\ell=1,2,\ldots,n-1$.

######  Theorem 2.

There is a constructive algorithm for deciding Problem 2. The number
$s(n,m_{\sigma})$ of basic steps of the algorithm satisfies the inequality

$\displaystyle s(n,m_{\sigma})$ $\displaystyle\leq$ $\displaystyle
c_{2}\\{m_{\sigma}^{2}\log
m_{\sigma}+\min\\{[m_{\sigma}^{(1)}]^{3},(d_{1})^{3}\\}+\sum_{\ell=1}^{n-2}N^{(l)}\min\\{[m_{\sigma}^{(\ell+1)}]^{2},(d_{\ell+1})^{2})\\}$
$\displaystyle+N^{(n-1)}\min\\{m_{\sigma},d_{n}\\}\\}$

where $c_{2}$ is an absolute constant and $m_{\sigma}^{(\ell)}$ and
$N^{(\ell)}$ are defined as in Theorem 1.

######  Remark 1.

In Smale [16, Conjecture], it was conjectured also that there is no
polynomial-time algorithm for deciding Problem 2, which is equivalent to a
negative answer $\mathbf{P}\neq\mathbf{NP}$ to the Main Problem (1).

By using Theorem 2, we disprove the conjecture mentioned in Remark 1 and thus,
prove the main result of the paper:

######  Theorem 3.

The classes ${\mathbf{P}}$ and $\mathbf{NP}$ are equivalent. That is,
${\mathbf{P}}=\mathbf{NP}$.

Theorem 3 answers the question (1) of the Main Problem with Yes. Observe that,
the opinion of most of the experts was exactly the opposite. A series of polls
was conducted since 2002, in which the percentage of those voting for
${\mathbf{P}}\neq\mathbf{NP}$ reached 99% in 2019 (see Gasarch [8]).

Proof of Theorem 1. Given a sequence
$\\{f_{i}\\}_{i=1}^{k}\subset\mathscr{P}_{n}$, we will show how to check if
there exists a sequence $\\{g_{i}\\}_{i=1}^{k}\subset\mathscr{P}_{n}$
satisfying (2) (and how to find it, if it exists), estimating simultaneously
the minimal number of steps $s(n,m_{\sigma})$. This will be done by reduction
with respect to the number of variables $n$, followed by induction. Let us
call the problem for doing this a $(n,m_{\sigma})$-problem. Recall that
$m_{\sigma}$ is the total number of monomials $m_{\sigma}=\sum_{i=1}^{k}m_{i}$
in the polynomials $\\{f_{i}\\}_{i=1}^{k}$ and let us explain also what we
mean by natural order in the set of $n$-variate monomials: This means that
amongst two monomials, the one with lower total degree is located to the left
from the other, and if the total degrees of two monomials coincide and
$j\in\\{1,2,\ldots,n\\}$ is the maximal index such that their exponents on the
variables $(z_{1},z_{2},\ldots,z_{j-1})$ coincide, then the one possessing a
higher exponent of $z_{j}$, is located to the left from the other. In this
way, the monomials are ordered as follows:

$1\prec z_{1}\prec z_{2}\prec\cdots\prec z_{n}\prec z_{1}^{2}\prec
z_{1}z_{2}\prec z_{2}^{2}\prec\cdots\prec z_{n-1}z_{n}\prec
z_{n}^{2}\prec\cdots\leavevmode\nobreak\ .$

Reduction) In this first part of the algorithm, the original
$(n,m_{\sigma}^{(n)})$-problem will be reduced to a
$(1,m_{\sigma}^{(1)})$-problem, passing through problems of types
$(\ell-1,m_{\sigma}^{(\ell-1)})$, $\ell=n,n-1,\ldots,3$, where
$m_{\sigma}^{(\ell-1)}\leq m_{\sigma}$ is the total length of the coefficients
$\\{f_{ij}^{(\ell)}(\mbox{\boldmath$z$}^{(\ell-1)})\\}_{i=1}^{k^{(\ell)}}$ in
front of $z_{\ell}^{j}$, $j=0,1,\ldots,d_{\ell}$, $\ell=2,3,\ldots,n$, in all
$(z_{1},z_{2},\ldots,z_{\ell})$-sub-monomials from $\\{f_{i}\\}_{i=1}^{k}$.
Let also $N^{(\ell-1)}$, be the number in the natural order of the major
$(z_{1},z_{2},\ldots,z_{\ell-1})$-sub-monomial, $\ell=2,3,\ldots,n$, in
$\\{f_{i}\\}_{i=1}^{k}$. The unknown polynomials
$\\{g_{ij}^{(\ell)}(\mbox{\boldmath$z$}^{(\ell-1)})\\}_{i=1}^{k^{(\ell)}}$
will be considered as linear combination of all
$(z_{1},z_{2},\ldots,z_{\ell-1})$-monomials in the natural order up to that
with number $N^{(\ell-1)}$, $\ell=2,3,\ldots,n$. Thus, the numbers
$N^{(\ell-1)}$, $\ell=2,3,\ldots,n$, serve as bounds for the total degrees of
$\\{g_{ij}^{(\ell)}(\mbox{\boldmath$z$}^{(\ell-1)})\\}_{i=1}^{k^{(\ell)}}$.
Let us mention here, that estimates for the total degrees of the unknown
polynomials, involving the $n$-th power of the maximal total degree of the
polynomials $\\{f_{i}\\}_{i=1}^{k}$, are obtained in Brownawell [4]. To match
the representations of $\\{g_{ij}^{(\ell)}\\}$, the polynomials
$\\{f_{ij}^{(\ell)}\\}$ will also be considered as linear combination of all
$(z_{1},z_{2},\ldots,z_{\ell-1})$-monomials in the natural order up to that
with number $N^{(\ell-1)}$, taking into account that the missing monomials
have coefficients equal to $0$. The superscript $(\ell)$ of $k$ will be used
only to make the exposition more transparent. In fact, the estimation of the
number of basic steps requires only the quantities $m_{\sigma}^{(\ell)}$ and
the number of variables $n$. Hence, for $\ell=n$,

$f_{i}^{(n)}=\sum_{j=0}^{d_{n}}f_{ij}^{(n)}(\mbox{\boldmath$z$}^{(n-1)})z_{n}^{j},\leavevmode\nobreak\
g_{i}^{(n)}=\sum_{j=0}^{d_{n}}g_{ij}^{(n)}(\mbox{\boldmath$z$}^{(n-1)})z_{n}^{j},\leavevmode\nobreak\
i=1,2,\ldots,k=k^{(n)}.$

######  Remark 2.

During the reduction part of the algorithm, at every level
$\ell=n,n-1,\ldots,2$, non-zero coefficients of the polynomials
$\\{f_{ij}^{(\ell)}(\mbox{\boldmath$z$}^{(\ell-1)})\\}_{i=1}^{k^{(\ell)}}$
will be sorted at the cost of less than or equal to

$cm_{\sigma}^{2}\log m_{\sigma}$ (3)

basic steps. The order of the variables $\\{z_{j}\\}_{j=1}^{n}$ will be
discussed in Remark 5.

The left hand side of (2) is a linear combination of
$1,z_{n},\ldots,z_{n}^{2d_{n}}$. Consequently, the following identities must
be fulfilled in ${\mathbb{C}}^{n-1}$:

$\left(\begin{array}[]{lrc}\sum_{i=1}^{k^{(n)}}f_{i0}^{(n)}g_{i0}^{(n)}&\equiv&1\\\
\sum_{i=1}^{k^{(n)}}f_{i0}^{(n)}g_{i1}^{(n)}+\sum_{i=1}^{k^{(n)}}f_{i1}^{(n)}g_{i0}^{(n)}&\equiv&0\\\
\sum_{i=1}^{k^{(n)}}f_{i0}^{(n)}g_{i2}^{(n)}+\sum_{i=1}^{k^{(n)}}f_{i1}^{(n)}g_{i1}^{(n)}+\sum_{i=1}^{k^{(n)}}f_{i2}^{(n)}g_{i0}^{(n)}&\equiv&0\\\
&\cdots&\nobreak\leavevmode\hfil\\\
\sum_{i=1}^{k^{(n)}}f_{id_{n}}^{(n)}g_{id_{n}}^{(n)}&\equiv&0\end{array}\right)$
(4)

This is the system that we need to solve or disprove. In the reduction section
we will be interested only in the first ($\equiv 1$) identities of systems
like (4). The treatment of the rest ($\equiv 0$) identities will be left for
the next section Induction. As we already mentioned above, passing through
problems of types $(\ell,m_{\sigma}^{(\ell)})$, $\ell=n-1,n-2,\ldots,2$, we
will inevitably arrive at an $(1,m_{\sigma}^{(1)})$ problem:

$\sum_{i=1}^{k}f_{i}^{(1)}(z_{1})g_{i}^{(1)}(z_{1})\equiv
1,\leavevmode\nobreak\
f_{i}^{(1)}(z_{1})=\sum_{u=1}^{d_{1}}a_{ij}z_{1}^{j},\leavevmode\nobreak\
g_{i}^{(1)}(z_{1})=\sum_{j=0}^{d_{1}}b_{ij}z_{1}^{j},\leavevmode\nobreak\
i=1,2,\ldots,k^{(1)}.$

Our goal now is to check if the following system

$\left(\begin{array}[]{lrc}\sum_{i=1}^{k^{(1)}}a_{i0}b_{i0}&=&1\\\
\sum_{i=1}^{k^{(1)}}(a_{i0}b_{i1}+a_{i1}b_{i0})&=&0\\\
\sum_{i=1}^{k^{(1)}}(a_{i0}b_{i2}+a_{i1}b_{i1}+a_{i2}b_{i0})&=&0\\\ \cdots\\\
\sum_{i=1}^{k^{(1)}}a_{id_{1}}b_{id_{1}}&=&0\\\ \end{array}\right)$ (5)

does or does not possess a solution and find it, if it exists. It is a linear
system of $2d_{1}+1$ equations with respect to $k^{(1)}(d_{1}+1)$ unknowns
$\\{b_{ij}\\}_{j=0}^{d_{1}},\leavevmode\nobreak\ i=1,2,\ldots,k^{(1)}$, having
$m_{\sigma}^{(1)}$ non-zero coefficients amongst all
$\\{a_{ij}\\}_{j=0}^{d_{1}},\leavevmode\nobreak\ i=1,2,\ldots,k^{(1)}$.
Consequently, at most $k^{(1)}(d_{1}+1)-(2d_{1}+1)=(k^{(1)}-2)(d_{1}+1)+1$ of
the unknowns could be free, or in other words, the solution, if it exists, is
at most $\\{(k^{(1)}-2)(d_{1}+1)+1\\}$-dimensional linear manifold. Observe
that therefore, $d_{1}$ is the optimal choice for the degree of the unknown
polynomials, since in the lowest non-trivial case $k^{(1)}=2$ the manifold is
of dimension $1$. By using (a modified) Gauss elimination, we will solve the
system or will prove that it does not have a solution. Note that the single
terms in every row are combined in $k^{(1)}$-tuple sums. We take first the
tuple $\\{a_{i0}\\}_{i=1}^{k^{(1)}}$. Going through the equations of the
system, pivot coefficients are chosen from the current tuple
$\\{a_{i0}\\}_{i=1}^{k^{(1)}}$ in ascending order of their first subscript,
until the non-zeros in it are used up. Then we consider the next
$k^{(1)}$-tuple sum from the current equation. If, in our case, there are
$l_{0}$ non-zeros in $\\{a_{i0}\\}_{i=1}^{k^{(1)}}$, at the equation number
$l_{0}+1$ we will consider the $k^{(1)}$-tuple sum
$\sum_{i=1}^{k^{(1)}}a_{i1}b_{i{l_{0}-1}}$ and will look for pivots in
$\\{a_{i1}\\}_{i=1}^{k^{(1)}}$, respectively. If all coefficients in a sum
$\sum_{i=1}^{k^{(1)}}a_{ij_{1}}b_{ij_{2}}$ are zero, this means that none of
the polynomials $\\{f_{i}^{(1)}(z_{1})\\}_{i=1}^{k^{(1)}}$ contains a term
with $z_{1}^{j_{1}}$. If this is true for $j_{1}=0$, the process is terminated
with a result "No solution at Level 1, Equation 1". If not, we solve the
equation number $1$ with respect to one of the unknowns, say $b_{10}$,
representing it in terms of those $\\{b_{i0}\\}_{i=2}^{k^{(1)}}$ such that the
corresponding $a_{i0}$ are non-zero. Then take the next non-zero coefficient
$a_{i_{0}0}$, if any, solve equation number $2$ with respect to $b_{i_{0}1}$
and thus, represent $b_{i_{0}1}$ as a linear function of
$b_{10}=b_{10}(b_{20},\ldots,b_{k^{(1)}0})$, $\\{b_{i0}\\}_{i=2}^{k^{(1)}}$
and $\\{b_{i1}\\}_{i=1}^{k^{(1)}},\leavevmode\nobreak\ i\neq i_{0}$. Let us
suppose that there is not such an $a_{i_{0}0}$. Then we look for non-zeros in
$\\{a_{i1}\\}_{i=1}^{k^{(1)}}$. If all terms in this set are also zero, this
means that the second equation is of the form $a_{10}b_{11}=0$, from where
$b_{11}=0$. Further, the equation number $3$ is under consideration and we do
the same with the sums $\sum_{i=1}^{k^{(1)}}a_{i0}b_{i2}$,
$\sum_{i=1}^{k^{(1)}}a_{i1}b_{i1}$ and $\sum_{i=1}^{k^{(1)}}a_{i2}b_{i0}$,
taken in this order. The manipulation of the third equation is finished again
with one of the same results – either a new unknown is represented as a linear
function of some other unknowns (including $b_{10}$ and for ex. $b_{i_{0}1}$),
or due to luck of sufficiently many non-zero $a_{ij}$’s, some of the next
unknowns is equal to zero. After finishing with all equations, we will have a
set of at most $2d_{1}+1$ unknowns $\\{b_{i_{l}j_{l}}\\}_{l=1}^{l^{*}}$, such
that $b_{i_{1}j_{1}}=b_{i_{1}j_{1}}(\hbox{\it list of variables}(1))$,
$\ldots$ , $b_{i_{l^{*}}j_{l^{*}}}=b_{i_{l^{*}}j_{l^{*}}}(\hbox{\it list of
variables}(l^{*}))$. It is important to realize at this stage, that if the
coefficients of (2) depend linearly on free parameters, any of these
parameters should be equal to $0$. Consequently, we can take $b_{i_{1}j_{1}}$
and substitute by $0$ those of the free parameters, which are in list of
variables$(1)$, set the same for $b_{i_{2}j_{2}}$ (including also the value
$b_{i_{1}j_{1}}$, if it is in list of variables$(2)$), and so on, until we get
to $b_{i_{l^{*}}j_{l^{*}}}$. Thus, if the process is not terminated, the
unique solution of the system (5) will be found. The next step is to find the
polynomials from the upper level systems by using the solution of the
$(1,m_{\sigma}^{(1)})$-problem.

######  Remark 3.

The manipulation of the lowest level linear system (5) takes at most

$c\min\\{(m_{\sigma}^{(1)})^{2},(d_{1})^{2}\\}$ (6)

basic steps.

######  Remark 4.

In order to be used at the next levels, the solution process of (5)

${\mathbf{A}}{\mathbf{b}}=(1,0,\ldots,0)^{t}\leavevmode\nobreak\
\Rightarrow{\mathbf{b}}^{*}={\mathbf{b}}^{*}({\mathbf{A}})$ (7)

should be implemented in a separate module for an arbitrary matrix $A$ with
$2d_{1}+1$ rows and $m_{\sigma}^{(1)}$ non-zero elements, where
$m_{\sigma}^{(1)}$, $d_{1}$, the indeces and the values of the non-zero
elements of $A$ are the parameters of the module.

Induction) Let us consider the system

$\left(\begin{array}[]{lrc}\sum_{i=1}^{k^{(2)}}f_{i0}^{(2)}(z_{1})g_{i0}^{(2)}(z_{1})&\equiv&1\\\
\sum_{i=1}^{k^{(2)}}f_{i0}^{(2)}(z_{1})g_{i1}^{(2)}(z_{1})+\sum_{i=1}^{k^{(2)}}f_{i1}^{(2)}(z_{1})g_{i0}^{(2)}(z_{1})&\equiv&0\\\
\sum_{i=1}^{k^{(2)}}f_{i0}^{(2)}(z_{1})g_{i2}^{(2)}(z_{1})+\sum_{i=1}^{k^{(2)}}f_{i1}^{(2)}(z_{1})g_{i1}^{(2)}(z_{1})+\sum_{i=1}^{k^{(2)}}f_{i2}^{(2)}(z_{1})g_{i0}^{(2)}(z_{1})&\equiv&0\\\
&\cdots&\nobreak\leavevmode\hfil\\\
\sum_{i=1}^{k^{(2)}}f_{id_{2}}^{(2)}(z_{1})g_{id_{2}}^{(2)}(z_{1})&\equiv&0\end{array}\right),$
(8)

that is a consequence of the $(2,m_{\sigma}^{(2)})$-problem

$\sum_{i=1}^{k^{(2)}}f_{i}^{(2)}(z_{1},z_{2})g_{i}^{(2)}(z_{1},z_{2})\equiv
1,$ (9)

as well as (5) is a consequence of the first identity in (8). Polynomials
$\\{g_{i0}^{(2)}\\}_{i=1}^{k^{(2)}}$ are already calculated from (5). Let us
add the first row of (8) to the second one, and then the second one to the
third one, in order to get

$\displaystyle\sum_{i=1}^{k^{(2)}}f_{i0}^{(2)}g_{i0}^{(2)}$
$\displaystyle\equiv$ $\displaystyle 1$ (10)
$\displaystyle\sum_{i=1}^{k^{(2)}}f_{i0}^{(2)}\left[g_{i0}^{(2)}+g_{i1}^{(2)}\right]+\sum_{i=1}^{k^{(2)}}f_{i1}^{(2)}g_{i0}^{(2)}$
$\displaystyle\equiv$ $\displaystyle 1$ (11)
$\displaystyle\sum_{i=1}^{k^{(2)}}f_{i0}^{(2)}\left[g_{i0}^{(2)}+g_{i1}^{(2)}+g_{i2}^{(2)}\right]+\sum_{i=1}^{k^{(2)}}f_{i1}^{(2)}\left[g_{i0}^{(2)}+g_{i1}^{(2)}\right]+\sum_{i=1}^{k^{(2)}}f_{i2}^{(2)}g_{i0}^{(2)}$
$\displaystyle\equiv$ $\displaystyle 1$ (12)

for the first three identities of the system. Identities (11) and (12) are
$(2,m_{\sigma}^{(2)})$-problems, similar to (10). Here is how many steps we
need to solve (11) and find $g_{i1}^{(2)}$. As we know from (6), its solution
is found in at most

$c\min\\{(m_{0;\sigma}^{(1)}+m_{1;\sigma}^{(1)})^{2},(d_{1})^{2}\\}$

basic steps, where $m_{0;\sigma}^{(1)}$ and $m_{1;\sigma}^{(1)}$ are the total
lengths of univariate non-zero polynomials of $z_{1}$ in front of $z_{2}^{0}$
and $z_{2}^{1}$, respectively. We need also at most $N^{(1)}$ steps to find
the new functions $g_{i1}^{(2)}$, if they exist. As usual, if the solution
does not exist, the process is terminated with a message "No solution at Level
2, Identity 2". A similar estimation is valid for the third row. Representing
the rest of the rows in the same way, and summing up the corresponding
estimates for the number of steps yields the following total estimate for
level 2:

$\displaystyle
c\left\\{\sum_{l=0}^{\min\\{(m_{\sigma}^{(2)}),d_{2}\\}}\min\left\\{\left[\sum_{l_{1}=0}^{l}m_{l_{1};\sigma}^{(1)}\right]^{2},(d_{1})^{2}\right\\}+N^{(1)}\min\\{m_{\sigma}^{(2)},d_{2}\\}\right\\}$
$\displaystyle\leq$ $\displaystyle
c\left\\{\min\\{\min\\{(m_{\sigma}^{(2)})^{3},(d_{2})^{3}\\},\min\\{(m_{\sigma}^{(1)})^{3},(d_{1})^{3}\\}\\}+N^{(1)}\min\\{m_{\sigma}^{(2)},d_{2}\\}\right\\}$
$\displaystyle=$ $\displaystyle
c\left\\{\min\\{(m_{\sigma}^{(2)})^{3},(m_{\sigma}^{(1)})^{3},(d_{2})^{3},(d_{1})^{3}\\}+N^{(1)}\min\\{m_{\sigma}^{(2)},d_{2}\\}\right\\}$

Let us also show the corresponding estimate for the system of level $3$, that
is, the system (4) for $n=3$. Observe that, the actual length of that system,
as well as the additional arithmetic operations for finding the new functions
$g_{il}^{(3)}$ from identities number $l+1$, depend only on the parameters
$m_{\sigma}^{(3)}$, $d_{3}$ and $N^{(2)}$. Therefore, using (3),
considerations similar to those for (8) will lead to an expression of the form

$\displaystyle\leq$ $\displaystyle
c\left\\{\min\\{(m_{\sigma}^{(3)})^{4},(m_{\sigma}^{(2)})^{4},(m_{\sigma}^{(1)})^{3},(d_{3})^{4},(d_{2})^{4},(d_{1})^{3}\\}\right.$
$\displaystyle+$
$\displaystyle\left.N^{(1)}\min\\{(m_{\sigma}^{(3)})^{2},(m_{\sigma}^{(2)})^{2},(d_{3})^{2},(d_{2})^{2}\\}+N^{(2)}\min\\{m_{\sigma}^{(3)},d_{3}\\}\right\\}$

Performing in a similar manner induction up to $n$ gives the following
estimate for the total number of basic steps of the process (without counting
sorting operations)

$\displaystyle\leq$ $\displaystyle
c\left\\{\min\\{(m_{\sigma}^{(n)})^{n+1},(m_{\sigma}^{(n-1)})^{n+1},\ldots,(m_{\sigma}^{(1)})^{3},(d_{n})^{n+1},(d_{n-1})^{n+1},\ldots,(d_{1})^{3}\\}\right.$
(14)
$\displaystyle+N^{(1)}\min\\{(m_{\sigma}^{(n)})^{n},(m_{\sigma}^{(n-1)})^{n}\ldots,(m_{\sigma}^{(2)})^{2},(d_{n})^{n},(d_{n-1})^{n},\ldots,(d_{2})^{2}\\}$
$\displaystyle+\cdots$
$\displaystyle+\left.N^{(n-1)}\min\\{m_{\sigma}^{(n)},d_{n}\\}\right\\}.$

Consequently, combining (3) and (14), it follows for every $n\geq 1$ that

$\displaystyle s(n,m_{\sigma})$ $\displaystyle\leq$ $\displaystyle
c\\{m_{\sigma}^{2}\log
m_{\sigma}+\min\\{[m_{\sigma}^{(1)}]^{3},(d_{1})^{3}\\}+\sum_{\ell=1}^{n-2}N^{(l)}\min\\{[m_{\sigma}^{(\ell+1)}]^{2},(d_{\ell+1})^{2})\\}$
$\displaystyle+N^{(n-1)}\min\\{m_{\sigma},d_{n}\\}\\}$

Theorem 1 is proved. $\Box$

######  Remark 5.

It is clear now, that in the beginning the variables $\\{z_{j}\\}_{j=1}^{n}$
can be sorted so, that the expression in the outer curly brackets in (3) to be
minimal.

######  Remark 6.

In order to keep the number of basic steps in the frames of the upper bound
(3), system solution processes at any level $\ell$, $\ell=2,3,\ldots,n-1$,
should also be implemented in separate modules, similarly to the case $\ell=1$
(see Remark 4). Note though, that these modules are to be prepared "on the
fly" and should be normally quite ordinary in size, since their size depends
rather on the total input length $m_{\sigma}$ than on the number of variables
$n$.

Proof of Theorem 2. The proof follows that of Theorem 1 with the only
difference that we use ${\mathbb{Q}}_{2}$-arithmetic and at every division-
step normalize the result to a simple fraction. This can only lead to an
increase of $c_{1}$ with a factor that comes from the application of the
Euclidean algorithm, which is bound by a constant multiple of $\max_{1\leq
i\leq k}\max_{\mbox{\scriptsize\boldmath$\alpha$}\in
A_{i}}\log|c_{\mbox{\scriptsize\boldmath$\alpha$}}|$. $\Box$

Proof of Theorem 3. It follows from Proposition 1 (c), Theorem 2 and the fact
that the Hilbert Nullstellensatz over ${\mathbb{Z}}_{2}$ is an
$\mathbf{NP}$-complete problem. $\Box$

######  Remark 7.

Obviously, the values of the constants $c_{1}$ and $c_{2}$ in Theorems 1 and
2, respectively, lie within some ordinary limits. More precise estimates for
them are not subject of this paper and can be obtained empirically by applying
the corresponding algorithms to polynomials of different degrees and with
different numbers of non-zero coefficients.

######  Remark 8.

Note that the aim of the present paper is to validate theoretically the
existence of the algorithms from Theorems 1 and 2, to explain their complexity
and milestones, but not to present precise descriptions of them.

## References

  * [1] D. De Abishek Kumarasubramanian and R. Venkatesan, Inversion attacks on secure hash functions using SAT solvers, in Theory and Applications of Satisfiability Testing – SAT 2007, J. Marques-Silva and K. A. Sakallah, eds., Lecture Notes in Computer Science, vol. 4501, Springer, Berlin, Heidelberg, 2007, 377–382.
  * [2] A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Boston, 1974.
  * [3] B. Berger and T. Leighton, Protein Folding in the Hydrophobic-Hydrophilic (HP) Model is NP-Complete, J. Comput. Biol., 5 (2009), 27–40.
  * [4] W. Brownawell, Bounds for the degrees in the Nullstellensatz, Ann. Math. 126 (1987), 577–591.
  * [5] S. Cook, The complexity of theorem-proving procedures, in Conference Record of Third Annual ACM Symposium on Theory of Computing, ACM, New York, 1971, 151–158.
  * [6] S. Cook, The $P$ versus $NP$ problem, Official problem description, www.claymath.org
/millennium-problems/p-vs-np-problem.

  * [7] L. Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, Princeton University Press, Princeton, 2013.
  * [8] W. I. Gasarch, Guest Column: The Third P=?NP Poll, ACM SIGACT News 50 (2019), 38–59.
  * [9] J. Hartmanis, Gödel, von Neumann and the P =? NP problem, EATCS Bulletin 38 (1989), 101–107.
  * [10] D. Hilbert, Uber die vollen Invariantensysteme, Math. Ann. 42 (1893), 313–-373.
  * [11] S. Horie and O. Watanabe, Hard instance generation for SAT, in Algorithms and Computation – ISAAC 1997, H. W.Leong, H. Imai and S. Jain, eds., Lecture Notes in Computer Science, vol. 1350, Springer Berlin, Heidelberg, 1997, 22–31.
  * [12] R.M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 1972, 85–103.
  * [13] L. Levin, Universal search problems (in Russian), Problemy Peredachi Informatsii 9:3 (1973), 115–116. English translation in B. A. Trakhtenbrot, A survey of Russian approaches to Perebor (brute-force search) algorithms, IEEE Ann. Hist. Comput. 6 (1984), 384–400.
  * [14] J. Nash, Letters from John Nash, NSA, www.nsa.gov/Portals/70/documents/news-features/declassified-documents/nash-letters/nash_letters1.pdf, 2012.
  * [15] J. Robinson, On the Hamiltonian game (a traveling salesman problem), Research Memorandum RM-303, The RAND Corporation, Santa Monica, California, 1949.
  * [16] S. Smale, Mathematical problems for the next century, Lecture given on the occasion of 60th birthday of W. I. Arnold, www-users.cse.umn.edu/$\sim$mille003/smale_problems.ps, The Fields Institute for Research in Mathematical Sciences, University of Toronto, Toronto, 1997.
  * [17] S. Smale, Mathematical problems for the next century, Math. Intell. 20 (1998), 7–15.
  * [18] A. Turing, On computable numbers with an application to the entscheidnungsproblem, Proc. London Math. Soc. 42 (1936), 230–265.
  * [19] J. R. Ullmann, An algorithm for subgraph isomorphism, J. ACM 23 (1976), 31–42.


# The monotone-light factorization for 2-categories via 2-preorders

João J. Xarez  CIDMA - Center for Research and Development in Mathematics and
Applications, Department of Mathematics, University of Aveiro, Portugal.
<EMAIL_ADDRESS>
###### Abstract.

It is shown that the reflection $2Cat\rightarrow 2Preord$ of the category of
all 2-categories into the category of 2-preorders determines a monotone-light
factorization system on $2Cat$ and that the light morphisms are precisely the
2-functors faithful on 2-cells with respect to the vertical structure. In
order to achieve such result it was also proved that the reflection
$2Cat\rightarrow 2Preord$ has stable units, a stronger condition than
admissibility in categorical Galois theory, and that the 2-functors surjective
both on horizontally and on vertically composable triples of 2-cells are the
effective descent morphisms in $2Cat$.

###### Key words and phrases:

Monotone-light factorization, 2-categories

###### 2020 Mathematics Subject Classification:

18A32,18E50,18N10

##  1\. Introduction

###  1.1. The process of stabilization and localization

The classical monotone-light factorization is due to S. Eilenberg [3] and G.
T. Whyburn [14]. It consists of a pair
$(\mathcal{E^{{}^{\prime}}},\mathcal{M^{*}})$ of classes of morphisms in the
category $CompHaus$ of compact Hausdorff spaces, such that any continuous map
$f$ of compact Hausdorff spaces factorizes as $f=m\circ e$, with
$e\in\mathcal{E^{{}^{\prime}}}$ (the class of monotone maps, i.e., those who
have totally disconnected fibres) and $m\in\mathcal{M^{*}}$ (the class of
light maps, i.e., those whose fibres are connected).

This factorization system $(\mathcal{E^{{}^{\prime}}},\mathcal{M^{*}})$ may be
obtained from another (reflective) factorization system
$(\mathcal{E},\mathcal{M})$ on $CompHaus$ by a process of simultaneous
stabilization and localization. That is: beginning with the reflector
$I:CompHaus\rightarrow Stone$ (the category of Stone spaces), whose right
adjoint $H$ is a full inclusion, there is an associated (reflective)
factorization system $(\mathcal{E},\mathcal{M})$; then, we take the largest
subclass $\mathcal{E^{{}^{\prime}}}$ of $\mathcal{E}$ which is stable under
pullbacks, and take $\mathcal{M^{*}}$ to be the class of morphisms which are
obtained by localizing $\mathcal{M}$ ($m\in\mathcal{M^{*}}$ if there is any
surjective map $p$ such that the pullback $p^{*}(m)$ along $p$ is in
$\mathcal{M}$).

The process of last paragraph was studied in general in [1], beginning with a
reflection $H\vdash I:\mathbb{C}\rightarrow\mathbb{X}$, and the surjective
maps $p$ used in the localization were generalized to morphisms
$p:E\rightarrow B$ such that the pullback functor
$p^{*}:\mathbb{C}/B\rightarrow\mathbb{C}/E$ is monadic, called effective
descent morphisms (e.d.m.) in Grothendieck (basic-fibrational) descent theory.

In that paper [1] some examples were given in which this process actually
achieves a new factorization system
$(\mathcal{E^{{}^{\prime}}},\mathcal{M^{*}})$ (non-trivial because
$\mathcal{E^{{}^{\prime}}}\neq\mathcal{E}\Leftrightarrow\mathcal{M}\neq\mathcal{M^{*}}$).
This is a quite rare phenomenon, since the pair
$(\mathcal{E^{{}^{\prime}}},\mathcal{M^{*}})$ usually fails to be a
factorization system. When $(\mathcal{E^{{}^{\prime}}},\mathcal{M^{*}})$ is in
fact a factorization system (whose definition can be found in [4], and nicely
exposed with other insights in [1]), obtained by simultaneous stabilization
and localization, it is to be called monotone-light as in [1], paying tribute
to that first example referred to above.

An interesting feature of this process is its connection to categorical Galois
theory (see [5]). If the reflection $I\dashv H$ is semi-left-exact (in the
sense of [2]), also called admissible in categorical Galois theory, then
$\mathcal{M^{*}}$ is the class of coverings in the sense of that theory (being
$Spl(E,p)$ the full subcategory of $\mathbb{C}/B$, determined by the coverings
over $B$ split by the monadic extension $(E,p)$, the fundamental theorem of
categorical Galois theory says that $Spl(E,p)$ has an algebraic description).

###  1.2. Past and present work

In [11], it was presented a new non-trivial example of the process above, for
the reflection $Cat\rightarrow Preord$ of the category of all categories into
the category of all preordered sets, where the coverings are the faithful
functors.

Now, in this paper, it will be proved that also the reflection
$2Cat\rightarrow 2Preord$ of the category of all 2-categories into the
category of all 2-preorders has a non-trivial monotone-light factorization,
where the coverings are the 2-functors which are faithful vertically with
respect to 2-cells.

Notice that both reflections have stable units (in the sense of [2]; a
stronger condition than semi-left-exactness), which is crucial to the proof in
association with the fact that there are enough e.d.m. with domain in the
subcategory.

The needed characterization of e.d.m. in $2Cat$ is given in this paper,
obtained in a completely analogous way as the characterization of e.d.m. in
$Cat$ was done in [6]. These characterizations depend on the embedding of
$Cat$ and $2Cat$ in the obvious presheaf categories.

###  1.3. Future work: prospects

This paper is intended to be a first step in showing that the monotone-light
factorization in [11] can be extended to higher category theory.

In particular, we hope to achieve the same results for n-categories in general
(and to $\omega$-categories) in a similar way, embedding n-categories in
categories of presheaves, if feasible.

We also believe, for the moment, that the good context for extending our
results to higher category theory will be that of $\mathcal{V}$-categories.
Remark that, considering $\mathcal{V}=Set$ the category of sets and then
iterating one obtains n-categories. Of course, this opens the possibility of
doing so for $\mathcal{V}$ other than the category of sets. We would be very
interested, for instance, to apply these future results to the following open
problem: is there a monotone-light factorization for semigroups via
semilattices (see [7] and [10])?

Remark finally that, because of the characterization given in this paper for
the e.d.m in $2Cat$ (cf. 4.1), we are driven to present the following
conjecture about the nature of e.d.m. for n-categories (n$\geq 1$), which may
be helpful in related future work.

Conjecture: a n-functor is an e.d.m. in the category of all n-categories if
and only if it is surjective both on vertically composable triples of n-cells,
and on horizontally composable triples of k-cells, for every
$k\in\\{2,...,n\\}$.

Similarly, we could present other obvious conjectures. Some concerning the
classes of morphisms of categorical Galois theory characterized in this paper,
and even of other important classes of morphisms not treated here, since we
were not exhaustive.

##  2\. The category of all 2-categories

Consider the category $2Cat$, with objects all 2-categories and whose
morphisms are the 2-functors (see [9, §XII.3]). Its definition is going to be
stated in a way that suits our purposes. In order to do so, some intermediate
structures need to be defined previously.

First, consider the category $\mathbb{P}$ generated by the following
precategory diagram,
$P_{2}$$r$$m$$q$$P_{1}$$c$$e$$d$$P_{0}$

in which

$d\circ e=1_{P_{0}}=c\circ e,\ d\circ m=d\circ q,\ c\circ m=c\circ r\ and\
c\circ q=d\circ r,$

where $1_{P_{0}}$ stands for the identity morphism of $P_{0}$ (see [1, §4.1]).

A precategory is an object in the category of presheaves
$\hat{\mathbb{P}}=Set^{\mathbb{P}}$, that is, any functor
$P:\mathbb{P}\rightarrow Set$ to the category of sets.

If
$Q_{2}$$r^{\prime}$$m^{\prime}$$q^{\prime}$$Q_{1}$$c^{\prime}$$e^{\prime}$$d^{\prime}$$Q_{0}$

is another precategory diagram, then a triple $(f_{2},f_{1},f_{0})$ with
$f_{2}:P_{2}\rightarrow Q_{2}$, $f_{1}:P_{1}\rightarrow Q_{1}$ and
$f_{0}:P_{0}\rightarrow Q_{0}$, will be called a precategory morphism diagram
provided the following equations hold: $f_{0}\circ d=d^{\prime}\circ f_{1},\
f_{0}\circ c=c^{\prime}\circ f_{1},\ f_{1}\circ e=e^{\prime}\circ f_{0},\
f_{1}\circ q=q^{\prime}\circ f_{2},f_{1}\circ m=m^{\prime}\circ f_{2},\
f_{1}\circ r=r^{\prime}\circ f_{2}.$

Secondly, consider the category $2\mathbb{P}$ generated by the following
2-precategory diagram,

\begin{picture}(200.0,120.0)\par\put(0.0,70.0){$hvP_{2}$}
\put(55.0,90.0){\vector(1,0){70.0}}\put(55.0,75.0){\vector(1,0){70.0}}\put(55.0,60.0){\vector(1,0){70.0}}
\put(70.0,65.0){$hr\times hr$}\put(70.0,78.0){$hm\times
hm$}\put(70.0,95.0){$hq\times hq$} \put(148.0,70.0){$vP_{2}$}
\put(185.0,90.0){\vector(1,0){70.0}}\put(255.0,75.0){\vector(-1,0){70.0}}\put(185.0,60.0){\vector(1,0){70.0}}
\put(200.0,65.0){$hc\times hc$}\put(200.0,78.0){$he\times
he$}\put(200.0,95.0){$hd\times hd$} \put(260.0,70.0){$P_{0}$}
\par\par\par\put(-55.0,35.0){$vr\times
vr$}\put(-15.0,60.0){\vector(0,-1){40.0}}\put(-12.0,35.0){$vm\times
vm$}\put(15.0,60.0){\vector(0,-1){40.0}}\put(42.0,35.0){$vq\times
vq$}\put(40.0,60.0){\vector(0,-1){40.0}}
\par\put(120.0,35.0){$vr$}\put(135.0,60.0){\vector(0,-1){40.0}}\put(140.0,35.0){$vm$}\put(160.0,60.0){\vector(0,-1){40.0}}\put(165.0,35.0){$vq$}\put(180.0,60.0){\vector(0,-1){40.0}}
\par\put(270.0,35.0){$1_{P_{0}}$}\put(265.0,60.0){\vector(0,-1){40.0}}
\par\par\par\par\put(0.0,0.0){$hP_{2}$}
\put(55.0,20.0){\vector(1,0){70.0}}\put(55.0,5.0){\vector(1,0){70.0}}\put(55.0,-10.0){\vector(1,0){70.0}}
\put(80.0,-5.0){$hr$}\put(80.0,8.0){$hm$}\put(80.0,25.0){$hq$}
\put(148.0,0.0){$2P_{1}$}
\put(185.0,20.0){\vector(1,0){70.0}}\put(255.0,5.0){\vector(-1,0){70.0}}\put(185.0,-10.0){\vector(1,0){70.0}}
\put(210.0,-5.0){$hc$}\put(210.0,8.0){$he$}\put(210.0,25.0){$hd$}
\put(260.0,0.0){$P_{0}$}\put(300.0,0.0){$(2.1)$}
\par\par\par\put(-55.0,-35.0){$vc\times
vc$}\put(-15.0,-10.0){\vector(0,-1){40.0}} \put(-9.0,-35.0){$ve\times
ve$}\put(15.0,-50.0){\vector(0,1){40.0}} \put(42.0,-35.0){$vd\times
vd$}\put(40.0,-10.0){\vector(0,-1){40.0}}
\par\put(120.0,-35.0){$vc$}\put(135.0,-10.0){\vector(0,-1){40.0}}
\put(140.0,-35.0){$ve$}\put(160.0,-50.0){\vector(0,1){40.0}}
\put(165.0,-35.0){$vd$}\put(180.0,-10.0){\vector(0,-1){40.0}}
\par\put(270.0,-35.0){$1_{P_{0}}$}\put(265.0,-10.0){\vector(0,-1){40.0}}
\par\par\par\par\put(0.0,-70.0){$P_{2}$}
\put(55.0,-50.0){\vector(1,0){70.0}}\put(55.0,-65.0){\vector(1,0){70.0}}\put(55.0,-80.0){\vector(1,0){70.0}}
\put(80.0,-75.0){$r$}\put(80.0,-62.0){$m$}\put(80.0,-45.0){$q$}
\put(148.0,-70.0){$P_{1}$}
\put(185.0,-50.0){\vector(1,0){70.0}}\put(255.0,-65.0){\vector(-1,0){70.0}}\put(185.0,-80.0){\vector(1,0){70.0}}
\put(210.0,-75.0){$c$}\put(210.0,-62.0){$e$}\put(210.0,-45.0){$d$}
\put(260.0,-70.0){$P_{0}$\hskip 10.0pt} \par\end{picture}

$hvP_{2}$$hr\times hr$$hm\times hm$$hq\times hq$$vP_{2}$$hc\times hc$$he\times
he$$hd\times hd$$P_{0}$

$vr\times vr$$vm\times vm$$vq\times vq$

$vr$$vm$$vq$

$1_{P_{0}}$

$hP_{2}$$hr$$hm$$hq$$2P_{1}$$hc$$he$$hd$$P_{0}$$(2.1)$

$vc\times vc$$ve\times ve$$vd\times vd$

$vc$$ve$$vd$

$1_{P_{0}}$

$P_{2}$$r$$m$$q$$P_{1}$$c$$e$$d$$P_{0}$

in which:

  * •

each one of the three horizontal diagrams (upwards, $P$, $hP$ and $hvP$) is a
precategory diagram;

  * •

each one of the three vertical diagrams (from the left to the right, $vhP$,
$vP$ and the trivial $P_{0}$) is a precategory diagram;

  * •

$(vc\times vc,vc,1_{P_{0}})$, $(ve\times ve,ve,1_{P_{0}})$, $(vd\times
vd,vd,1_{P_{0}})$, $(vr\times vr,vr,1_{P_{0}})$, $(vm\times vm,vm,1_{P_{0}})$,
$(vq\times vq,vq,1_{P_{0}})$ are all six precategory morphism diagrams
(equivalently, $(hq\times hq,hq,q)$, $(hm\times hm,hm,m)$, $(hr\times
hr,hr,r)$, $(hd\times hd,hd,d)$, $(he\times he,he,e)$, $(hc\times hc,hc,c)$
are all six precategory morphism diagrams).

Notice that the names given to objects and morphisms in $(2.1)$ are arbitrary,
being so chosen in order to relate to the following last definition of section
2 (for instance, $vq\times vq$ will denote the morphism uniquely determined by
a pullback diagram).

The category $2Cat$ of all 2-categories is the full subcategory of
$\hat{2\mathbb{P}}=Set^{2\mathbb{P}}$, determined by its objects
$C:2\mathbb{P}\rightarrow Set$ such that the image by $C$ of each horizontal
and vertical precategory diagram in $(2.1)$ is a category. That is, for
instance, in the case of the bottom horizontal precategory diagram in $(2.1)$:

the commutative square

$C(P_{1})$$C(P_{2})$$C(P_{0})$$C(P_{1})$$Cr$$Cq$$Cc$$(2.2)$$Cd$

is a pullback diagram in $Set$;

the associative and unit laws hold for the operation $Cm$, that is, the
following respective diagrams commute in $Set$,

$C(P_{2})$$C(P_{2})\times_{C(P_{1})}C(P_{2})$$C(P_{1})$,$C(P_{2})$$Cr\times
Cm$$Cm\times Cq$$Cm$$(2.3)$$Cm$

\begin{picture}(300.0,80.0)\par\put(-60.0,50.0){$C(P_{0})\times_{C(P_{0})}C(P_{1})$}\put(20.0,45.0){\vector(0,-1){30.0}}\put(42.0,55.0){\vector(1,0){70.0}}
\put(230.0,55.0){\vector(-1,0){70.0}}
\par\put(0.0,0.0){$C(P_{1})$}\put(25.0,25.0){$pr_{2}$}
\put(42.0,3.0){\vector(1,0){70.0}} \put(50.0,60.0){$Ce\times
1_{C(P_{1})}$}\put(60.0,10.0){$1_{C(P_{1})}$}
\par\put(120.0,0.0){$C(P_{1})$}\put(120.0,50.0){$C(P_{2})$}\put(245.0,0.0){$C(P_{1})$\hskip
10.0pt}\put(235.0,50.0){$C(P_{1})\times_{C(P_{0})}C(P_{0})$}
\par\put(145.0,25.0){$Cm$}\put(170.0,60.0){$1_{C(P_{1})}\times
Ce$}\put(270.0,25.0){$pr_{1}$\hskip 20.0pt$(2.4)$}
\put(190.0,10.0){$1_{C(P_{1})}$} \par\put(230.0,3.0){\vector(-1,0){70.0}}
\put(140.0,45.0){\vector(0,-1){30.0}}\put(265.0,45.0){\vector(0,-1){30.0}}
\end{picture}

$C(P_{0})\times_{C(P_{0})}C(P_{1})$

$C(P_{1})$$pr_{2}$$Ce\times 1_{C(P_{1})}$$1_{C(P_{1})}$

$C(P_{1})$$C(P_{2})$$C(P_{1})$$C(P_{1})\times_{C(P_{0})}C(P_{0})$

$Cm$$1_{C(P_{1})}\times Ce$$pr_{1}$$(2.4)$$1_{C(P_{1})}$

It would be a long and trivial calculation to check that there is an
isomorphism between the category of all 2-categories (in the sense of [9,
§XII.3]) and the full subcategory of $\hat{2\mathbb{P}}$ just defined. Notice
that: the requirement that the horizontal composite of two vertical identities
is itself a vertical identity is encoded in diagram $(2.1)$ in the
commutativity of the square $hm\circ(ve\times ve)=ve\circ m$ ; the interchange
law, which relates the vertical and the horizontal composites of 2-cells, is
encoded in diagram $(2.1)$ in the commutativity of the square
$vm\circ(hm\times hm)=hm\circ(vm\times vm)$.

##  3\. Internal categories and limits

In section 2, if the category $Set$ of sets is replaced by any category
$\mathcal{C}$ with pullbacks, then one obtains the definition of
$2Cat(\mathcal{C})$, the category of internal 2-categories in $\mathcal{C}$.

In this section 3, the goal is to show that the category of all 2-categories
$2Cat$ is closed under limits in the presheaves category
$\hat{2\mathbb{P}}=Set^{2\mathbb{P}}$. The following Lemmas 3.1 and 3.2 give
some well known facts about limits of internal categories, which will
translate into internal 2-categories, and finally into 2-categories in the
special case of $\mathcal{C}=Set$.

In what follows, $Cat(\mathcal{C})$ will denote the category of internal
categories in $\mathcal{C}$, that is, the full subcategory of the category of
functors $\mathcal{C}^{\mathbb{P}}$, determined by all the functors
$C:\mathbb{P}\rightarrow\mathcal{C}$ such that the diagram $(2.2)$ is a
pullback diagram in $\mathcal{C}$ and the diagrams $(2.3)$ and $(2.4)$ commute
in $\mathcal{C}$ ($\mathbb{P}$ is of course the category defined in section
2).

######  Lemma 3.1.

Let $\mathcal{C}$ be a category with pullbacks.

Then, $Cat(\mathcal{C})$ is closed under pullbacks in
$\mathcal{C}^{\mathbb{P}}$, where pullbacks exist and are calculated
pointwise.

######  Lemma 3.2.

Let $\mathcal{C}$ be a category with pullbacks.

If $\mathbb{I}$ is a discrete category (that is, a set) and $\mathcal{C}$ has
all limits $\mathbb{I}\rightarrow\mathcal{C}$, then $Cat(\mathcal{C})$ is
closed under all limits $\mathbb{I}\rightarrow Cat(\mathcal{C})$ in
$\mathcal{C}^{\mathbb{P}}$, where limits
$\mathbb{I}\rightarrow\mathcal{C}^{\mathbb{P}}$ exist and are calculated
pointwise.

######  Corollary 3.1.

If $\mathcal{C}$ has all limits then $2Cat(\mathcal{C})$ is closed under
limits in the functor category $\mathcal{C}^{2\mathbb{P}}$, where all limits
exist and are calculated pointwise.

In particular, for $\mathcal{C}=Set$, $2Cat$ is closed under limits in
$\hat{2\mathbb{P}}=Set^{2\mathbb{P}}$.

###### Proof.

The proof follows from the fact that limits are calculated pointwise in
$\mathcal{C}^{2\mathbb{P}}$, and that a category with pullbacks and all
products has all limits, and from Lemmas 3.1 and 3.2. ∎

##  4\. Effective descent morphisms in 2Cat

Consider again the category of all categories $Cat$ and its full inclusion in
the category of precategories $\hat{\mathbb{P}}=Set^{\mathbb{P}}$.

A functor $p:\mathbb{E}\rightarrow\mathbb{B}$ is an effective descent morphism
(e.d.m.)111Also called a monadic extension in categorical Galois theory. in
$Cat$ if and only if it is surjective on composable triples of morphisms. The
proof of this statement can be found in [6, Proposition 6.2]. In a completely
analogous way, the class of effective descent morphisms in $2Cat$ is going to
be given in the following Proposition 4.1.

######  Proposition 4.1.

A 2-functor $2p:2\mathbb{E}\rightarrow 2\mathbb{B}$ is an e.d.m. in the
category of all 2-categories $2Cat$ if and only if it is surjective both on
horizontally composable triples of 2-cells and on vertically composable
triples of 2-cells.

###### Proof.

(if:)

Let $2p:2\mathbb{E}\rightarrow 2\mathbb{B}$ be surjective on triples of
composable 2-cells (both horizontally and vertically). Then, $2p$ is an e.d.m.
in $\hat{2\mathbb{P}}=Set^{2\mathbb{P}}$, since the effective descent
morphisms in a category of presheaves are simply those surjective pointwise
(which, of course, is implied by either surjectivity on triples of composable
2-cells). Hence, the following instance of [6, Corollary 3.9] can be applied:

if $2p:2\mathbb{E}\rightarrow 2\mathbb{B}$ in $2Cat$ is an e.d.m. in
$\hat{2\mathbb{P}}=Set^{2\mathbb{P}}$ then $2p$ is an e.d.m. in $2Cat$ if and
only if , for every pullback square

$2\mathbb{E}$$2\mathbb{D}$$2\mathbb{B}$$2A$$(4.1)$$2p$

in $\hat{2\mathbb{P}}=Set^{2\mathbb{P}}$ such that $2\mathbb{D}$ is in $2Cat$,
then also $2A$ is in $2Cat$.

Since the pullback square $(4.1)$ is calculated pointwise (cf. Corollary 3.1),
it induces six other pullback squares in $\hat{\mathbb{P}}=Set^{\mathbb{P}}$,
corresponding to the three rows $P$, $hP$ and $hvP$, and the three columns
$vhP$, $vP$ and $P_{0}$, in the 2-precategory diagram $(2.1)$.

The fact that $2p$ is surjective on triples of composable 2-cells (both
horizontally and vertically) implies that its six restrictions (to the six
rows and columns $2\mathbb{E}(P)$, $2\mathbb{E}(hP)$, $2\mathbb{E}(hvP)$,
$2\mathbb{E}(vhP)$, $2\mathbb{E}(vP)$ and $2\mathbb{E}(P_{0})$) are surjective
on triples of composable morphisms in $Cat$, as it is easy to check. Hence,
these six restrictions are effective descent morphisms in $Cat$. Therefore,
$2A$ must always be a 2-category, provided so is $2\mathbb{D}$.

(only if:)

Let’s now prove the converse, that if $2p:2\mathbb{E}\rightarrow 2\mathbb{B}$
is not surjective on vertically composable triples or on horizontally
composable triples of 2-cells, then it is not an effective descent morphism.

Suppose first that $2p:2\mathbb{E}\rightarrow 2\mathbb{B}$ is not surjective
on horizontally composable triples of 2-cells, that is, there is a triple

\begin{picture}(0.0,20.0)\par\put(50.0,0.0){$0$}\put(100.0,0.0){$1$}
\put(150.0,0.0){$2$}\put(200.0,0.0){$3$}
\par\put(60.0,12.0){\vector(1,0){35.0}}\put(60.0,-6.0){\vector(1,0){35.0}}
\put(110.0,12.0){\vector(1,0){35.0}}\put(110.0,-6.0){\vector(1,0){35.0}}
\put(160.0,12.0){\vector(1,0){35.0}}\put(160.0,-6.0){\vector(1,0){35.0}}
\par\put(73.0,0.0){$\Downarrow$}\put(80.0,0.0){$\beta_{01}$}
\put(123.0,0.0){$\Downarrow$}\put(130.0,0.0){$\beta_{12}$}
\put(173.0,0.0){$\Downarrow$}\put(180.0,0.0){$\beta_{23}$}
\par\par\end{picture}

$0$$1$$2$$3$

$\Downarrow$$\beta_{01}$$\Downarrow$$\beta_{12}$$\Downarrow$$\beta_{23}$

in $2\mathbb{B}$, and there is not a triple

\begin{picture}(0.0,20.0)\par\put(50.0,0.0){$0$}\put(100.0,0.0){$1$}
\put(150.0,0.0){$2$}\put(200.0,0.0){$3$}
\par\put(60.0,12.0){\vector(1,0){35.0}}\put(60.0,-6.0){\vector(1,0){35.0}}
\put(110.0,12.0){\vector(1,0){35.0}}\put(110.0,-6.0){\vector(1,0){35.0}}
\put(160.0,12.0){\vector(1,0){35.0}}\put(160.0,-6.0){\vector(1,0){35.0}}
\par\put(73.0,0.0){$\Downarrow$}\put(80.0,0.0){$\varepsilon_{1}$}
\put(123.0,0.0){$\Downarrow$}\put(130.0,0.0){$\varepsilon_{2}$}
\put(173.0,0.0){$\Downarrow$}\put(180.0,0.0){$\varepsilon_{3}$}
\par\par\end{picture}

$0$$1$$2$$3$

$\Downarrow$$\varepsilon_{1}$$\Downarrow$$\varepsilon_{2}$$\Downarrow$$\varepsilon_{3}$

in $2\mathbb{E}$, such that $2p(\varepsilon_{1})=\beta_{01}$,
$2p(\varepsilon_{2})=\beta_{12}$ and $2p(\varepsilon_{3})=\beta_{23}$.

Consider the 2-category $h\mathbf{4}$ generated by the following diagram,

\begin{picture}(0.0,20.0)\par\put(50.0,0.0){$0$}\put(100.0,0.0){$1$}
\put(150.0,0.0){$2$}\put(200.0,0.0){$3$\ .}
\par\put(60.0,12.0){\vector(1,0){35.0}}\put(60.0,-6.0){\vector(1,0){35.0}}
\put(110.0,12.0){\vector(1,0){35.0}}\put(110.0,-6.0){\vector(1,0){35.0}}
\put(160.0,12.0){\vector(1,0){35.0}}\put(160.0,-6.0){\vector(1,0){35.0}}
\par\par\put(73.0,0.0){$\Downarrow$}\put(80.0,0.0){$\alpha_{01}$}
\put(123.0,0.0){$\Downarrow$}\put(130.0,0.0){$\alpha_{12}$}
\put(173.0,0.0){$\Downarrow$}\put(180.0,0.0){$\alpha_{23}$}
\par\par\end{picture}

$0$$1$$2$$3$.

$\Downarrow$$\alpha_{01}$$\Downarrow$$\alpha_{12}$$\Downarrow$$\alpha_{23}$

Then, consider also the presheaf $h\mathbf{4}^{n.a.}:2\mathbb{P}\rightarrow
Set$, which has the same objects (0-cells), the same morphisms (1-cells), and
the same six non-identity 2-cells $\alpha_{ij}$, $0\leq i<j\leq 3$ as
$h\mathbf{4}$, plus a new 2-cell $\alpha^{\prime}_{03}:0\rightarrow 3$, with
the horizontal composition of 2-cells being as follows:
$\alpha_{12}\circ\alpha_{01}=\alpha_{02}$,
$\alpha_{23}\circ\alpha_{12}=\alpha_{13}$,
$\alpha_{23}\circ\alpha_{02}=\alpha_{03}$ and
$\alpha_{13}\circ\alpha_{01}=\alpha^{\prime}_{03}$ (with
$\alpha^{\prime}_{03}\neq\alpha_{03}$, which destroys the horizontal
associativity). Hence, one can call $h\mathbf{4}^{n.a.}$ a horizontally non-
associative 2-category, in the sense that the images of the precategory
diagrams $P$, $vP$ are categories, the image of the commutative square
$hc\circ hq=hd\circ hr$ is a pullback diagram, the unit laws hold for the
image of $hP$, but the image of $hm$ is not associative (cf. diagram (2.1)).

Now, if one takes $2A=h\mathbf{4}^{n.a.}$ and $2A\rightarrow 2\mathbb{B}$ to
be the morphism $\varphi$ determined by $\varphi\alpha_{ij}=\beta_{ij}$,
$0\leq i<j\leq 3$, and $\varphi\alpha^{\prime}_{03}=\beta_{03}$, then the
pullback $2\mathbb{D}$ is a 2-category; and therefore $2p$ is not an effective
descent morphism, because it is not surjective on horizontal triples. In fact,
$2\mathbb{D}$ would not be a 2-category only if there was a triple of 2-cells

\begin{picture}(0.0,20.0)\par\par\put(60.0,12.0){\vector(1,0){55.0}}\put(60.0,-6.0){\vector(1,0){55.0}}
\put(130.0,12.0){\vector(1,0){55.0}}\put(130.0,-6.0){\vector(1,0){55.0}}
\put(200.0,12.0){\vector(1,0){55.0}}\put(200.0,-6.0){\vector(1,0){55.0}}
\par\par\put(73.0,0.0){$\Downarrow$}\put(80.0,0.0){$(\varepsilon_{1},\alpha_{1})$}
\put(143.0,0.0){$\Downarrow$}\put(150.0,0.0){$(\varepsilon_{2},\alpha_{2})$}
\put(213.0,0.0){$\Downarrow$}\put(220.0,0.0){$(\varepsilon_{3},\alpha_{3})$}
\par\par\end{picture}

$\Downarrow$$(\varepsilon_{1},\alpha_{1})$$\Downarrow$$(\varepsilon_{2},\alpha_{2})$$\Downarrow$$(\varepsilon_{3},\alpha_{3})$

in $2\mathbb{D}$ such that

$((\varepsilon_{3},\alpha_{3})\circ(\varepsilon_{2},\alpha_{2}))\circ(\varepsilon_{1},\alpha_{1})\neq(\varepsilon_{3},\alpha_{3})\circ((\varepsilon_{2},\alpha_{2})\circ(\varepsilon_{1},\alpha_{1}))$,222Since
pullbacks are calculated componentwise in a category of presheaves, and that
the proof of Lemma 3.1 is made by considering the associative and unit laws
independently (cf. above (2.2), (2.3) and (2.4)).

which would imply $\alpha_{1}=\alpha_{01}$, $\alpha_{2}=\alpha_{12}$ and
$\alpha_{3}=\alpha_{23}$, and so, contrary to the hypothesis, $2p$ would be
surjective on horizontally composable triples of 2-cells.

The proof that if $2p:2\mathbb{E}\rightarrow 2\mathbb{B}$ is not surjective on
vertically composable triples of 2-cells, then it is not an effective descent
morphism, can be made “mutatis mutandis” using the 2-category $v\mathbf{4}$ in
the following Example 4.1.

∎

######  Example 4.1.

It is obvious that the coproduct $\coprod$ of 2-categories is just the
disjoint union, as for categories.

Let $v\mathbf{4}$ and $h\mathbf{4}$ be the 2-categories generated by the
following two diagrams, respectively:

\begin{picture}(60.0,40.0)\par\par\put(0.0,0.0){$0$}\put(50.0,0.0){$1$}
\par\put(70.0,0.0){;}
\par\put(10.0,30.0){\vector(1,0){35.0}}\put(10.0,12.0){\vector(1,0){35.0}}
\put(10.0,-6.0){\vector(1,0){35.0}}\put(10.0,-24.0){\vector(1,0){35.0}}
\par\put(23.0,18.0){$\Downarrow$}\put(23.0,0.0){$\Downarrow$}
\put(23.0,-18.0){$\Downarrow$} \par\put(150.0,0.0){$0$}\put(200.0,0.0){$1$}
\put(250.0,0.0){$2$}\put(300.0,0.0){$3$} \par\put(320.0,0.0){.}
\par\put(160.0,12.0){\vector(1,0){35.0}}\put(160.0,-6.0){\vector(1,0){35.0}}
\put(210.0,12.0){\vector(1,0){35.0}}\put(210.0,-6.0){\vector(1,0){35.0}}
\put(260.0,12.0){\vector(1,0){35.0}}\put(260.0,-6.0){\vector(1,0){35.0}}
\par\put(173.0,0.0){$\Downarrow$}\put(223.0,0.0){$\Downarrow$}\put(273.0,0.0){$\Downarrow$}
\par\par\end{picture}

$0$$1$

;

$\Downarrow$$\Downarrow$$\Downarrow$

$0$$1$$2$$3$

.

$\Downarrow$$\Downarrow$$\Downarrow$

Consider, for each 2-category $2\mathbb{B}$, the 2-category

$2\mathbb{E}=(\coprod_{i\in I}v\mathbf{4})\coprod(\coprod_{j\in
J}h\mathbf{4}),$

such that $I$ is the set of all vertically composable triples of 2-cells in
$2\mathbb{B}$, and $J$ is the set of all horizontally composable triples of
2-cells in $2\mathbb{B}$.

Then, there is an e.d.m. $2p:2\mathbb{E}\rightarrow 2\mathbb{B}$ which
projects the corresponding copy of $v\mathbf{4}$ and $h\mathbf{4}$ to every
$i\in I$ and every $j\in J$, respectively.

As another option, let

$2\mathbb{E}=\coprod_{k\in I\cup J}vh\mathbf{4},$

with $vh\mathbf{4}$ the 2-category333Remark that $v\mathbf{4}$, $h\mathbf{4}$
and $vh\mathbf{4}$ are really 2-preorders as defined just below at the
beginning of the following section 5. generated by the following diagram,

##  5\. The reflection of 2-categories into 2-preorders has stable units and a
monotone-light factorization

Let $2Preord$ be the full subcategory of $2Cat$ determined by the objects
$C:2\mathbb{P}\rightarrow Set$ such that $Cvd$ and $Cvc$ are jointly monic
(cf. diagram $(2.1)$), that is,

$C(vP_{2})$$Cvr$$Cvm$$Cvq$$C(2P_{1})$$Cvc$$Cve$$Cvd$$C(P_{1})$$(5.1)$

is a preordered set.

There is a reflection

$H\vdash
I:2Cat$$2Preord$,$(5.2)$$a$$b$$a$$b$,$f$$g$$\mapsto$$f$$g$$\Downarrow$$\theta$$\Downarrow$$\leq$

which identifies all 2-cells which have the same domain and codomain for the
vertical composition. That is, the reflector $I$ takes the middle vertical
category $C(vP)$ (cf. diagram $(5.1)$) to its image by the well known
reflection $Cat\rightarrow Preord$ from categories into preordered sets (see
[11]).

Many of the results in [13] are going to be stated again, with small
improvements in their presentation444The reader could easily bring these small
improvements to the paper [13]. In fact, although they are stated here in the
particular case of the reflection from $2Cat$ into $2Preord$, they are
completely general., in order to prove that the reflection $H\vdash
I:2Cat\rightarrow 2Preord$ has stable units (in the sense of [2]).

###  5.1. Ground structure

Consider the adjunction $H\vdash I:2Cat\rightarrow 2Preord$, described just
above in $(5.2)$, with unit $\eta:1_{2Cat}\rightarrow HI$.

  * •

$2Cat$ has pullbacks (in fact, it has all limits - see Corollary 3.1).

  * •

$H$ is a full inclusion of $2Preord$ in $2Cat$, that is, $I$ is a reflection
of a category with pullbacks into a full subcategory.

  * •

Consider also the forgetful functor $U:2Cat\rightarrow 2RGrph$, where $2RGrph$
is the presheaves category $Set^{2\mathbb{G}}$, with $2\mathbb{G}$ the
category generated by the following 2-reflexive graph diagram,

\begin{picture}(200.0,30.0)\par\put(28.0,0.0){$2P_{1}$}
\put(65.0,20.0){\vector(1,0){70.0}}\put(135.0,5.0){\vector(-1,0){70.0}}\put(65.0,-10.0){\vector(1,0){70.0}}
\put(90.0,-5.0){$hc$}\put(90.0,8.0){$he$}\put(90.0,25.0){$hd$}
\put(140.0,0.0){$P_{0}$}
\par\put(0.0,-35.0){$vc$}\put(15.0,-10.0){\vector(0,-1){40.0}}
\put(20.0,-35.0){$ve$}\put(40.0,-50.0){\vector(0,1){40.0}}
\put(45.0,-35.0){$vd$}\put(60.0,-10.0){\vector(0,-1){40.0}}
\par\put(150.0,-35.0){$1_{P_{0}}$}\put(145.0,-10.0){\vector(0,-1){40.0}}
\par\put(28.0,-70.0){$P_{1}$}
\put(65.0,-50.0){\vector(1,0){70.0}}\put(135.0,-65.0){\vector(-1,0){70.0}}\put(65.0,-80.0){\vector(1,0){70.0}}
\put(90.0,-75.0){$c$}\put(90.0,-62.0){$e$}\put(90.0,-45.0){$d$}
\put(140.0,-70.0){$P_{0}$\hskip 10.0pt} \par\end{picture}

$2P_{1}$$hc$$he$$hd$$P_{0}$

$vc$$ve$$vd$

$1_{P_{0}}$

$P_{1}$$c$$e$$d$$P_{0}$

satisfying the same equations as in the 2-precategory diagram $(2.1)$.

  * •

$\mathcal{E}$ denotes the class of all morphisms
$(2g_{1},g_{1},g_{0}):G\rightarrow H$ of $2RGrph$ which are bijections on
objects and on arrows, and surjections on 2-cells (that is,
$g_{0}:G(P_{0})\rightarrow H(P_{0})$ and $g_{1}:G(P_{1})\rightarrow H(P_{1})$
are bijections, and $2g_{1}:G(2P_{1})\rightarrow H(2P_{1})$ is a surjection).

  * •

$\mathcal{T}=\\{T\\}$ is a singular set, with $T$ the 2-preorder generated by
the diagram
\begin{picture}(95.0,30.0)\par\par\put(0.0,0.0){$a$}\put(50.0,0.0){$a^{\prime}$}
\par\put(70.0,0.0){$(5.3)$}
\par\put(10.0,12.0){\vector(1,0){35.0}}\put(23.0,17.0){$h$}
\put(10.0,-6.0){\vector(1,0){35.0}}\put(23.0,-17.0){$h^{\prime}$}
\par\put(23.0,0.0){$\Downarrow$}\put(32.0,0.0){$\leq$} \par\par\end{picture}

$a$$a^{\prime}$

$(5.3)$

$h$$h^{\prime}$

$\Downarrow$$\leq$

,

that is, a 2-preorder with two objects, two non-identity arrows and only one
non-identity (both horizontally and vertically) 2-cell.

Then, the following four conditions are satisfied.

  1. (a)

$U$ preserves pullbacks (in fact, it preserves all limits).

  2. (b)

$\mathcal{E}$ is pullback stable in $2RGrph$, and if $g^{\prime}\circ g$ is in
$\mathcal{E}$ so is $g^{\prime}$, provided $g$ is in $\mathcal{E}$.555In [13],
it was also demanded in (b) that $\mathcal{E}$ is closed under composition,
which is not needed. We take this opportunity to correct that redundancy in
[13].

  3. (c)

Every map $U\eta_{C}:U(C)\rightarrow UHI(C)$ belongs to $\mathcal{E}$, $C\in
2Cat$ (this is also obvious).

  4. (d) 666This item is rephrased from [13], in a way that seems to us now more easily understandable. Remark also that the diagram $(5.4)$ is simplified, suppressing one morphism $UH(T)\rightarrow UH(T)$, which can be the identity. We take this opportunity to correct that other redundancy.

Let $g:N\rightarrow M$ be any morphism of $2Preord$ such that
$UHg:UH(N)\rightarrow UH(M)$ is in $\mathcal{E}$.

If,

there is one morphism $f:A\rightarrow UH(N)$ of $2RGrph$ in $\mathcal{E}$

such that,

for all morphisms $c:T\rightarrow M$ in $2Preord$

($T$ as defined in (5.3)),

there is a commutative diagram as below

then

$g:N\rightarrow M$ is an isomorphism in $2Preord$.

It remains to show that the statement in (d) is true, which is trivial, since
if $g:N\rightarrow M$ is in $\mathcal{E}$, seen as a morphism of $2RGrph$,
then $g$ must be an isomorphism in $2Preord$ by the uniqueness of the 2-cells
in $N$ and in $M$.

###  5.2. Stable units

Using the fact that a ground structure holds (which guarantees the validity of
Theorems 2.1 and 2.2 in [13]), it will be possible to show that $H\vdash
I:2Cat\rightarrow 2Preord$ is an admissible reflection in the sense of
categorical Galois theory (cf. [5]) or, equivalently, semi-left-exact in the
sense of [2]. Furthermore, it will be shown, always using the results in [13],
that the reflection $H\vdash I:2Cat\rightarrow 2Preord$ satisfies the stronger
condition of having stable units.

######  Definition 5.1.

Consider any morphism $\mu:T\rightarrow HI(C)$ from $T$ ($\in\mathcal{T}$; cf.
$(5.3)$), for some $C\in 2Cat$.

The connected component of the morphism $\mu$ is the pullback
$C_{\mu}=C\times_{HI(C)}T$ in the following pullback square

where $\eta_{C}$ is the unit morphism of $C$ in the reflection $H\vdash
I:2Cat\rightarrow 2Preord$, and $T$ is identified with $H(T)$.

######  Theorem 5.1.

The reflection $H\vdash I:2Cat\rightarrow 2Preord$ is semi-left-exact.

###### Proof.

According to Theorem 2.1 in [13], one has to show that
$I\pi_{2}^{\mu}:I(C_{\mu})\rightarrow I(T)$ is an isomorphism, for every
connected component $C_{\mu}$.

If $\mu($$a$$a^{\prime}$$h$$h^{\prime}$$\Downarrow$$\leq$$)=\
$$c$$c^{\prime}$,$k$$k^{\prime}$$\Downarrow$$\leq$ then,

since $U\eta_{C}\in\mathcal{E}$ (identity on objects and morphisms, and
surjection on 2-cells), the pullback $C_{\mu}$ is the 2-category generated by
the diagram

$(c,a)$$(c^{\prime},a^{\prime})$$(k,h)$$(k^{\prime},h^{\prime})$$\Downarrow$$(\theta_{r},\leq)$

,

with $\theta_{r}\in Hom_{C(vP)}(k,k^{\prime})=\\{\theta_{r}\ |\ r\in R\\}$,
the set $R$ indexing all the 2-cells $\theta_{r}$ in $C$ with vertical domain
$k:c\rightarrow c^{\prime}$ and vertical codomain $k^{\prime}:c\rightarrow
c^{\prime}$.

Hence, $I(C_{\mu})\cong T$.∎

######  Theorem 5.2.

The reflection $H\vdash I:2Cat\rightarrow 2Preord$ has stable units.

###### Proof.

According to Theorem 2.2 in [13], one has to show that
$I(C_{\mu}\times_{T}D_{\nu})\cong T$, for every pair of connected components
$C_{\mu}$, $D_{\nu}$, where $C_{\mu}\times_{T}D_{\nu}$ is the pullback object
in any pullback of the form

where $\pi_{2}^{\mu}$ and $\pi_{2}^{\nu}$ are the second projections in
pullback diagrams of the form $(5.5)$.

According to the previous Theorem 5.1, one can suppose (up to isomorphism)
that $C_{\mu}=\ $$c$$c^{\prime}$$k$$k^{\prime}$$\Downarrow$$\theta_{r}$, $r\in
R$, and $D_{\nu}=\ $$d$$d^{\prime}$$l$$l^{\prime}$$\Downarrow$$\delta_{s}$,

$s\in S$ (the identity morphisms and the identity 2-cells are not displayed);
the sets $R$ and $S$ indexing respectively all the 2-cells $\theta_{r}$ in $C$
with vertical domain $k:c\rightarrow c^{\prime}$ and vertical codomain
$k^{\prime}:c\rightarrow c^{\prime}$, and all the 2-cells $\delta_{s}$ in $D$
with vertical domain $l:d\rightarrow d^{\prime}$ and vertical codomain
$l^{\prime}:d\rightarrow d^{\prime}$.

Hence, $C_{\mu}\times_{T}D_{\nu}=\
$$(c,d)$$(c^{\prime},d^{\prime})$$(k,l)$$(k^{\prime},l^{\prime})$$\Downarrow$$(\theta_{r},\delta_{s})$,
$(r,s)\in R\times S$, and so it is obvious that
$I(C_{\mu}\times_{T}D_{\nu})\cong\
$$a$$a^{\prime}$.$h$$h^{\prime}$$\Downarrow$$\leq$
∎

###  5.3. Monotone-light factorization for 2-categories via 2-preorders

######  Theorem 5.3.

The reflection $H\vdash I:2Cat\rightarrow 2Preord$ does have a monotone-light
factorization.

###### Proof.

The statement is a consequence of the central result of [1] (cf. Corollary 6.2
in [12]), because $H\vdash I$ has stable units (cf. Theorem 5.2) and for every
$2\mathbb{B}\in 2Cat$ there is an e.d.m. $2p:2\mathbb{E}\rightarrow
2\mathbb{B}$ with $2\mathbb{E}\in 2Preord$ (cf. Example 4.1).

∎

In the following section 6, it will be proved that the monotone-light
factorization system is not trivial. That is, it does not coincide with the
reflective factorization system associated to the reflection of $2Cat$ into
$2Preord$.

##  6\. Vertical and stably-vertical 2-functors

In this section, it will be given a characterization of the class of vertical
morphisms $\mathcal{E}_{I}$ in the reflective factorization system
$(\mathcal{E}_{I},\mathcal{M}_{I})$, and of the class of the stably-vertical
morphisms $\mathcal{E}^{\prime}_{I}$
($\subseteq\mathcal{E}_{I}$)777$\mathcal{E}^{\prime}_{I}$ is the largest
subclass of $\mathcal{E}_{I}$ stable under pullbacks. The terminologies
“vertical morphisms” and “stably-vertical morphisms” were introduced in [8].
in the monotone-light factorization system
$(\mathcal{E}^{\prime}_{I},\mathcal{M}^{*}_{I})$, both associated to the
reflection $2Cat\rightarrow 2Preord$. Then, since $\mathcal{E}^{\prime}_{I}$
is a proper class of $\mathcal{E}_{I}$, one concludes that
$(\mathcal{E}^{\prime}_{I},\mathcal{M}^{*}_{I})$ is a non-trivial monotone-
light factorization system.

Consider a 2-functor $f:A\rightarrow B$, which is obviously determined by the
three functions $f_{0}:A(P_{0})\rightarrow B(P_{0})$,
$f_{1}:A(P_{1})\rightarrow B(P_{1})$ and $2f_{1}:A(2P_{1})\rightarrow
B(2P_{1})$ (cf. diagram $(2.1)$), so that we may make the identification
$f=(2f_{1},f_{1},f_{0})$.

######  Proposition 6.1.

A 2-functor $f=(2f_{1},f_{1},f_{0}):A\rightarrow B$ belongs to the class
$\mathcal{E}_{I}$ of vertical 2-functors if and only if the following two
conditions hold:

  1. (1)

$f_{0}$ and $f_{1}$ are bijections;

  2. (2)

for every two elements $h$ and $h^{\prime}$ in $A(P_{1})$, if
$Hom_{B(vP)}(f_{1}h,f_{1}h^{\prime})$ is nonempty then so is
$Hom_{A(vP)}(h,h^{\prime})$.

###### Proof.

The 2-functor $f=(2f_{1},f_{1},f_{0})$ belongs to $\mathcal{E}_{I}$ if and
only if $If$ is an isomorphism (cf. [1, §3.1]), that is, $If_{0}$, $If_{1}$,
and $I2f_{1}$ are bijections. Since $If_{0}=f_{0}$ and $If_{1}=f_{1}$, the
fact that $f\in\mathcal{E}_{I}$ implies and is implied by (1) and (2) is
trivial.

∎

######  Proposition 6.2.

A 2-functor $f=(2f_{1},f_{1},f_{0}):A\rightarrow B$ belongs to the class
$\mathcal{E}^{\prime}_{I}$ of stably-vertical 2-functors if and only if the
following two conditions hold:

  1. (1)

$f_{0}$ and $f_{1}$ are bijections;

  2. (2)

for every two elements $h$ and $h^{\prime}$ in $A(P_{1})$, $f$ induces a
surjection $Hom_{A(vP)}(h,h^{\prime})\rightarrow
Hom_{B(vP)}(f_{1}h,f_{1}h^{\prime})$ ($f$ is a “full functor on 2-cells”).

###### Proof.

As every pullback $g^{*}(f)=\pi_{1}:C\times_{B}A\rightarrow C$ in $2Cat$ of
$f$ along any 2-functor $g:C\rightarrow B$ is calculated pointwise, and
$(2f_{1},f_{1}):A(vP)\rightarrow B(vP)$ is a stably-vertical functor for the
reflection $Cat\rightarrow Preord$, that is, $f_{1}$ is a bijection and
$(2f_{1},f_{1})$ is a full functor (cf. Propositions 4.4 and 3.2 in [11]),
then (1) and (2) imply that $g^{*}(f)$ belongs to $\mathcal{E}_{I}$ (cf. last
Proposition 6.1).

Hence, $f\in\mathcal{E}^{\prime}_{I}$ if (1) and (2) hold.

If $f\in\mathcal{E}^{\prime}_{I}$, then $f\in\mathcal{E}_{I}$
($\mathcal{E}^{\prime}_{I}\subseteq\mathcal{E}_{I}$), and therefore (1) holds.

Suppose now that (2) does not hold, so that there is $\theta:f_{1}h\rightarrow
f_{1}h^{\prime}$ not in the image of $f$, and consider the 2-category $C$
generated by the diagram
$b$$b^{\prime}$$f_{1}h$$f_{1}h^{\prime}$$\Downarrow$$\theta$, and let $g$ be
the inclusion of $C$ in $B$. Then, $C\times_{B}A\cong$
$b$$b^{\prime}$$f_{1}(h)$$f_{1}(h^{\prime})$, with no non-identity 2-cells,
and so $g^{*}(f)$ is not in $\mathcal{E}_{I}$.

Hence, if $f\in\mathcal{E}^{\prime}_{I}$ then (1) and (2) must hold.∎

It is evident that $\mathcal{E}^{\prime}_{I}$ is a proper class of
$\mathcal{E}_{I}$, therefore the monotone-light factorization system
$(\mathcal{E}^{\prime}_{I},\mathcal{M}^{*}_{I})$ is non-trivial
($\neq(\mathcal{E}_{I},\mathcal{M}_{I})$).

##  7\. Trivial coverings for 2-categories via 2-preorders

A 2-functor $f:A\rightarrow B$ belongs to the class $\mathcal{M}_{I}$ of
trivial coverings (with respect to the reflection $H\vdash I:2Cat\rightarrow
2Preord$) if and only if the following square

$B$$A$$I(B)$$I(A)$$f$$\eta_{A}$$If$$(7.1)$$\eta_{B}$

is a pullback diagram, where $\eta_{A}$ and $\eta_{B}$ are unit morphisms for
the reflection $H\vdash I:2Cat\rightarrow 2Preord$ (cf. [2, Theorem 4.1]).

Since the pullback (as any limit) is calculated pointwise in $2Cat$ (cf.
Corollary 3.1), then $f\in\mathcal{M}_{I}$ if and only if the following seven
squares are pullbacks, corresponding to the seven pointwise components of
$\eta_{A}$ and of $\eta_{B}$ (cf. diagram $(2.1)$):

$B(P_{i})$$A(P_{i})$$I(B)(P_{i})$$I(A)(P_{i})$$f_{P_{i}}$$\eta_{A(P_{i})}$$If_{P_{i}}$($D_{i}$)$(i=0,1,2);$$\eta_{B(P_{i})}$

$B(2P_{1})$$A(2P_{1})$$I(B)(2P_{1})$$I(A)(2P_{1})$$f_{2P_{1}}$$\eta_{A(2P_{1})}$$If_{2P_{1}}$;($2D$)$\eta_{B(2P_{1})}$

$B(vP_{2})$$A(vP_{2})$$I(B)(vP_{2})$$I(A)(vP_{2})$$f_{vP_{2}}$$\eta_{A(vP_{2})}$$If_{vP_{2}}$;($vD$)$\eta_{B(vP_{2})}$

$B(hP_{2})$$A(hP_{2})$$I(B)(hP_{2})$$I(A)(hP_{2})$$f_{hP_{2}}$$\eta_{A(hP_{2})}$$If_{hP_{2}}$;($hD$)$\eta_{B(hP_{2})}$

$B(hvP_{2})$$A(hvP_{2})$$I(B)(hvP_{2})$.$I(A)(hvP_{2})$$f_{hvP_{2}}$$\eta_{A(hvP_{2})}$$If_{hvP_{2}}$($hvD$)$\eta_{B(hvP_{2})}$

The three first squares $(D_{i})$ $(i=0,1,2)$ are pullbacks since
$\eta_{A(P_{i})}$ and $\eta_{B(P_{i})}$ are identity maps for $i=0,1,2$ (cf.
diagram $(2.1)$ and the definition of the reflection $H\vdash
I:2Cat\rightarrow 2Preord$ in $(5.2)$).

Notice that if diagram $(2.1)$ is restricted to the (vertical) precategory
diagram $vP$, one obtains from $(7.1)$ the following square in $Cat$, with
unit morphisms of the reflection of all categories into preorders
$Cat\rightarrow Preord$ (cf. [11]),

$B(vP)$$A(vP)$$I(B)(vP)$.$I(A)(vP)$$f_{vP}$$\eta_{A(vP)}$$If_{vP}$$(7.2)$$\eta_{B(vP)}$

It is known (cf. [11, Proposition 3.1]) that this square is a pullback in
$Cat$ if and only if, for every two objects $h$ and $h^{\prime}$ in $A(P_{1})$
with $Hom_{A(2P_{1})}(h,h^{\prime})$ nonempty, the map

$Hom_{A(2P_{1})}(h,h^{\prime})\rightarrow
Hom_{B(2P_{1})}(f_{1}h,f_{1}h^{\prime})$

induced by $f$ is a bijection.

A necessary condition for the 2-functor $f$ to be a trivial covering was just
stated; the following Lemma 7.1 will help to show that this necessary
condition is also sufficient in next Proposition 7.1.

######  Lemma 7.1.

Consider the following commutative parallelepiped

$B_{2}$$\eta_{B,2}$$r^{B}$$q^{B}$$B_{1}$$\eta_{B,1}$$d^{B}$$c^{B}$$B_{0}$$\eta_{B,0}$$f_{2}$$f_{1}$$f_{0}$$A_{2}$$\eta_{A,2}$$r^{A}$$q^{A}$$A_{1}$$\eta_{A,1}$$d^{A}$$c^{A}$$A_{0}$$\eta_{A,0}$$I(B)_{2}$$Ir^{B}$$Iq^{B}$$I(B)_{1}$$Id^{B}$$Ic^{B}$$I(B)_{0}$$If_{2}$$If_{1}$$If_{0}$$I(A)_{2}$$Ir^{A}$$Iq^{A}$$I(A)_{1}$$Id^{A}$$Ic^{A}$$I(A)_{0}$$(7.3)$

where the five squares $c^{A}q^{A}=d^{A}r^{A}$, $c^{B}q^{B}=d^{B}r^{B}$,
$Ic^{A}Iq^{A}=Id^{A}Ir^{A}$, $If_{0}\eta_{A,0}=\eta_{B,0}f_{0}$ and
$If_{1}\eta_{A,1}=\eta_{B,1}f_{1}$ are pullbacks.

Then, the square $If_{2}\eta_{A,2}=\eta_{B,2}f_{2}$ is also a pullback.888The
notation used in diagram $(7.3)$ is arbitrary, being so chosen in order to
make the application of Lemma 7.1 in this section more easily understandable.

###### Proof.

The proof is obtained by an obvious diagram chase. ∎

######  Proposition 7.1.

A 2-functor $f:A\rightarrow B$ is a trivial covering for the reflection
$H\vdash I:2Cat\rightarrow 2Preord$ (in notation, $f\in\mathcal{M}_{I}$) if
and only if, for every two objects $h$ and $h^{\prime}$ in $A(P_{1})$ with
$Hom_{A(2P_{1})}(h,h^{\prime})$ nonempty, the map

$Hom_{A(2P_{1})}(h,h^{\prime})\rightarrow
Hom_{B(2P_{1})}(f_{1}h,f_{1}h^{\prime})$

induced by $f$ is a bijection.

###### Proof.

In the considerations just above, it was showed that the statement warrants
that the squares $(2D)$ and $(vD)$ are pullbacks, adding to the fact that
$(D_{0})$, $(D_{1})$ and $(D_{2})$ are all three pullbacks.

Then, $(hD)$ and $(hvD)$ must also be pullbacks according to Lemma 7.1. ∎

##  8\. Coverings for 2-categories via 2-preorders

A 2-functor $f:A\rightarrow B$ belongs to the class $\mathcal{M}^{*}_{I}$ of
coverings (with respect to the reflection $H\vdash I:2Cat\rightarrow 2Preord$)
if there is some effective descent morphism (also called monadic extension in
categorical Galois theory) $p:C\rightarrow B$ in $2Cat$ with codomain $B$ such
that the pullback $p^{*}(f):C\times_{B}A\rightarrow C$ of $f$ along $p$ is a
trivial covering ($p^{*}(f)\in\mathcal{M}_{I}$).

The following Lemma 8.1 can be found in [11, Lemma 4.2], in the context of the
reflection of categories into preorders, but for 2-categories via 2-preorders
the proof is exactly the same, since the same conditions hold (cf. Theorem 5.2
and Example 4.1). The next Proposition 8.1 characterizes the coverings for
2-categories via 2-preorders.

######  Lemma 8.1.

A 2-functor $f:A\rightarrow B$ in $2Cat$ is a covering (for the reflection
$H\vdash I:2Cat\rightarrow 2Preord$) if and only if, for every 2-functor
$\varphi:X\rightarrow B$ over $B$ from any 2-preorder $X$, the pullback
$X\times_{B}A$ of $f$ along $\varphi$ is also a 2-preorder.

######  Proposition 8.1.

A 2-functor $f:A\rightarrow B$ in $2Cat$ is a covering (for the reflection
$H\vdash I:2Cat\rightarrow 2Preord$) if and only if it is faithful vertically
with respect to 2-cells, that is, for every pair of morphisms $g$ and
$g^{\prime}$, the map

$Hom_{A(2P_{1})}(g,g^{\prime})\rightarrow
Hom_{B(2P_{1})}(f_{1}g,f_{1}g^{\prime})$

induced by $f$ is an injection.

###### Proof.

Consider again the 2-preorder $T$ generated by the diagram
$a$$a^{\prime}$.$h$$h^{\prime}$$\Downarrow$$\leq$

If $f$ is not faithful vertically with respect to 2-cells, then, by including
$T$ in $B$, one could obtain a pullback $T\times_{B}A$ that is not a preorder.

Therefore, $f$ is not a covering, by the previous Lemma 8.1.

Reciprocally, consider any 2-functor $\varphi:X\rightarrow B$ such that $X$ is
a 2-preorder.

If $f$ is faithful (vertically with respect to 2-cells), then the pullback
$X\times_{B}A$ is a 2-preorder, given the nature of $X$. Hence, $f$ is a
covering, by the previous Lemma 8.1.

∎

## Acknowledgement

This work was supported by The Center for Research and Development in
Mathematics and Applications (CIDMA) through the Portuguese Foundation for
Science and Technology

(FCT - Fundação para a Ciência e a Tecnologia),

references UIDB/04106/2020 and UIDP/04106/2020.

## References

  * [1] Carboni, A., Janelidze, G., Kelly, G. M., Paré, R. On localization and stabilization for factorization systems. App. Cat. Struct. 5, (1997) 1–58.
  * [2] Cassidy, C., Hébert, M., Kelly, G. M. Reflective subcategories, localizations and factorization systems. J. Austral. Math. Soc. 38A (1985) 287–329.
  * [3] Eilenberg, S. Sur les transformations continues d’espaces métriques compacts. Fundam. Math. 22 (1934) 292–296.
  * [4] Freyd, P. J., Kelly, G. M. Categories of continuous funtors I, J. Pure App. Algebra 2 (1972) 169–191.
  * [5] Janelidze, G. Pure Galois theory in categories, J. Algebra 132 (1990) 270–286.
  * [6] Janelidze, G., Sobral, M., Tholen, W. Beyond Barr Exactness: Effective Descent Morphisms in Categorical Foundations. Special Topics in Order, Topology, Algebra and Sheaf Theory, Cambridge University Press, 2004\.
  * [7] Janelidze, G., Laan, V., Márki, L. Limit preservation properties of the greatest semilattice image functor, Internat. J. Algebra Comput. 18(5) (2008), 853–867.
  * [8] Janelidze, G., Tholen, W. Functorial factorization, well-pointedness and separability, J. Pure App. Algebra 142 (1999) 99–130.
  * [9] Mac Lane, S. Categories for the Working Mathematician, 2nd ed., Springer, 1998.
  * [10] Xarez, I. A. Reflections of Universal Algebras into Semilattices, their Galois Theories and Related Factorization Systems, University of Aveiro, Ph.D. Thesis, 2013.
  * [11] Xarez, J. J. The monotone-light factorization for categories via preorders. Galois theory, Hopf algebras and semiabelian Categories, 533–541, Fields Inst. Commun., 43, Amer. Math. Soc., Providence, RI, 2004.
  * [12] Xarez, J. J. Internal monotone-light factorization for categories via preorders, Theory Appl. Categories 13 (2004) 235–251.
  * [13] Xarez, J. J. Generalising Connected Components, J. Pure Appl. Algebra, 216, Issues 8-9(2012), 1823–1826.
  * [14] Whyburn, G. T. Non-alternating transformations. Amer. J. Math. 56 (1934) 294–302.