Fuzzy Presheaves are Quasitoposes

Aloïs Rosset  0000-0002-7841-2318
Roy Overbeek 0000-0003-0569-0947
Jörg Endrullis

Aloïs Rosset, Roy Overbeek and Jörg Endrullis

Vrije Universiteit Amsterdam, Amsterdam, The Netherlands

{a.rosset, r.overbeek<EMAIL_ADDRESS>
Quasitoposes encompass a wide range of structures, including various categories of graphs.
They have proven to be a natural setting for reasoning about the metatheory of algebraic graph rewriting.
In this paper we propose and motivate the notion of fuzzy presheaves, which generalises fuzzy sets and fuzzy graphs.
We prove that fuzzy presheaves are rm-adhesive quasitoposes, proving our recent conjecture for fuzzy graphs.
Furthermore, we show that simple fuzzy graphs categories are quasitoposes.

The algebraic graph transformation tradition uses category theory to define graph rewriting formalisms.
The categorical approach enables rewriting a large variety of structures,
and allows meta-properties to be studied in uniform ways, such as concurrency, parallelism, termination, and confluence.
Different formalisms have been developed and studied since 1973, such as
DPO [14],
SPO [22],
DPU [4],
SqPO [13],
AGREE [11],
PBPO [12], and

The study of meta-properties on a categorical level has given new motivation to study existing concepts, such as quasitoposes [43], and has given rise to new ones, such as different notions of adhesivity [20, 21].
Quasitoposes are categories with rich structure.
They encompass many examples of particular interest in computer science [19].
They have moreover been proposed as a natural setting for non-linear rewriting [5].
In addition, they provide a unifying setting: we have shown that  subsumes DPO, SqPO, AGREE and PBPO in quasitoposes <cit.>.[We moreover conjecture that  subsumes SPO in quasitoposes <cit.>.]

Fuzzy sets generalise the usual notion of sets by allowing elements to have membership values in the unit interval [44] or more generally in a poset [16].
Similarly, fuzzy graphs [26] and fuzzy Petri nets [10, 38] have been defined by allowing elements to have membership values.
Having a range of possible membership is used in artificial intelligence for example to express a degree of certainty or strength of a connection.
In graph rewriting, it can be used to restrict matching [26, 34, 33, 35].
We have recently shown that for fuzzy graphs, where we see the membership value as a label, the order structure on the labelling set lends itself well for implementing relabelling mechanics and type hierarchies [30, 31].
These features have proved useful, for example, for  faithfully modelling linear term rewriting with graph rewriting [27].

In this paper, we do the following.

* We propose the notion of a fuzzy presheaf, which is a presheaf endowed pointwise with a membership function, generalising fuzzy sets and fuzzy graphs.

* We show that fuzzy presheaf categories are rm-adhesive quasitoposes, when the membership values are taken in a complete Heyting algebra (<ref>).
We obtain as a corollary the known result that fuzzy sets form a quasitopos, prove our conjecture that fuzzy graph form a quasitopos [31], and as a new results that fuzzy sets, graphs, hypergraphs and other fuzzy presheaves are rm-adhesive quasitoposes.

* We examine the related question whether simple fuzzy graphs form a quasitopos.
Because simple graphs are not presheaves (nor rm-adhesive), our main theorem cannot be applied.
However, we show that (directed and undirected) simple fuzzy graphs are quasitoposes by using the notion of separated elements.

An immediate practical application of our result is that the termination technique [29], recently developed for rm-adhesive quasitoposes is applicable to rewriting fuzzy presheaves. In addition, it follows that our already mentioned subsumption result for  holds for fuzzy presheaf categories <cit.>.

The paper is structured as follows.
<ref> introduces preliminary definitions of presheaves, Heyting algebra and quasitoposes.
<ref> proves that fuzzy presheaves are quasitoposes.
<ref> proves that fuzzy presheaves are rm-adhesive.
<ref> looks at examples and applications.
<ref> establishes that simple fuzzy graph categories are also quasitoposes.
<ref> discusses future work and concludes.

§ PRELIMINARIES

We assume the reader is familiar with basic notions of category theory
[2, 23].
In this section, we recall basic definitions about fuzzy sets, presheaves, graphs, Heyting algebra and quasitoposes and fix notation concerning the Yoneda embedding, regular monomorphisms and subobjects.

Let $I$ be a locally small category.
The contravariant $\Hom$-functor
${I(-,i) : \opcat{I} \to \Set}$ is defined
on objects $j \in \opcat{I}$ as the set of $I$-morphisms $I(j,i)$, and
on $\opcat{I}$-morphisms $\opcat{\kappa}: j \rightarrow k$ (i.e. $\kappa: k \rightarrow j$ in $I$) as the precomposition
\(
I(j,i) \xrightarrow{- \circ \kappa} I(k,i):
\;
(j \xrightarrow{\iota} i)
\ \xmapsto \ \
(k \xrightarrow{\kappa} j \xrightarrow{\iota} i).
\)

Let $I$ be a locally small category.
The (contravariant) Yoneda embedding $y : I \to \PresheafDefault$ is defined
on objects $y(i \in I) = I(-,i)$ as the contravariant $\Hom$-functor, and
on morphisms $y(j \xrightarrow{\iota} i)$ as the natural transformation that postcomposes by $\iota$,
i.e., for every $k \in I$:

\[
I(k,j) \xrightarrow{\iota \circ -} I(k,i):
\;
(k \xrightarrow{\kappa} j)
\ \xmapsto \ \
(k \xrightarrow{\kappa} j \xrightarrow{\iota} i).
\]

Given a poset $(\labels,\leq)$, an $\labels$-fuzzy set is a pair $(A,\alpha)$ consisting of a set $A$ and a membership function $\alpha:A \to \labels$.
A morphism $f:(A,\alpha) \to (B,\beta)$ of fuzzy sets is a function $f:A \to B$ such that $\alpha \leq \beta f$, i.e., $\alpha(a) \leq \beta f (a)$ for all $a \in A$.
They form the category $\FuzzySetDefault$.
Membership functions are represented in grey.
We express that $\alpha \leq \beta f$ by the diagram on the right, which we call $\leq$-commuting.

[column sep=2mm, row sep=5mm,ampersand replacement=&]
A &  & B

["α"', color=gray, from=1-1, to=2-2]
["β", color=gray, from=1-3, to=2-2]
["f", from=1-1, to=1-3]
["≤"description, color=gray, draw=none, from=1-2, to=2-2,pos=0.4]

A presheaf on a category $I$ is a functor $F : \opcat{I} \to \Set$.
A morphism of presheaves is a natural transformation between functors.
The category of presheaves on $I$ is denoted by $\PresheafDefault$ or $\PresheafHatDefault$.

A graph $A$ consists of a set of vertices $A(V)$, a set of edges $A(E)$, and source and target functions $A(s),A(t) : A(E) \to A(V)$.
A graph homomorphism $f : A \to B$ is a pair of functions $f_V : A(V) \to B(V)$ and $f_E : A(E) \to B(E)$ respecting sources and targets, i.e., $(B(s),B(t)) \cdot f_E = (f_V \times f_V) \cdot (A(s),A(t))$.
They form the category $\Graph$, which is in fact the presheaf category on
\(
\opcat{I} =
\smash{\begin{tikzcd}[ampersand replacement=\&]
\ar[r, "s"{description}, shift left=3pt]
\ar[r, "t"{description}, shift right=3pt]
\& V
\end{tikzcd}}
\).

A fuzzy graph $(A,\alpha)$ consists of a graph $A$ and two membership functions $\alpha_V : A(V) \to \labels(V)$, and $\alpha_E : A(E) \to \labels(E)$, where $\labels(V)$ and $\labels(E)$ are posets.
A fuzzy graph homomorphism $f:(A,\alpha) \to (B,\beta)$ is a graph homomorphism $f : A \to B$ such that $\alpha_V \leq \beta_V f_V$ and $\alpha_E \leq \beta_E f_E$.
They form the category $\FuzzyGraph$.

Some authors require that fuzzy graphs satisfy $\labels(V) = \labels(E)$ and $\alpha_E(e) \leq \alpha_V(s(e)) \meet \alpha_V (t(e))$ for all edges $e \in A(E)$ [37].
For survey works on fuzzy graphs, see e.g. [25, 32].

A monomorphism $m : A \mono B$ is called regular, and denoted $m : A \regmono B$, if it is the equaliser of some  pair of parallel morphisms $B \rightrightarrows C$.

Monomorphisms into an object $C$ form a class denoted $\MonoClass(C)$.
There is a preorder on this class: $m \leq m'$ if there exists $u$ such that $m = m'u$.
The equivalence relation $m \simeq m' \defeq (m \leq m' \; \meet \; m \geq m')$ is equivalent to having $m = m'u$ for some isomorphism $u$.
The equivalence classes are the subobjects of $C$.
If each representative of a subobject is a special kind of monomorphism, for instance a regular monomorphism, then we talk of regular subobjects.

[column sep=2mm, row sep=5mm,ampersand replacement=&]
A && B

& C &
[from=1-1, to=2-2, tail, "m"']
[from=1-1, to=1-3, dotted, "u"]
[from=1-3, to=2-2, tail, "m'"]

Let $\cat{C}$ be a category with finite limits, and $\mathcal{M}$ be a class of monomorphisms.
An $\mathcal{M}$-subobject classifier in $\cat{C}$ is a monomorphism $\true : 1 \mono \Omega$ such that for every monomorphism $m : A \mono B$ in $\mathcal{M}$, there exists a unique $\chi_A : B \to \Omega$ such that
the diagram on the right is a pullback square.
When unspecified, $\mathcal{M}$ is all monomorphisms.

[column sep=5mm, row sep=5mm,ampersand replacement=&]
A & 1

B & Ω[from=1-1, to=1-2, "!"]
[from=1-1, to=2-1, tail, "m"']
[from=1-2, to=2-2, ""]
[from=2-1, to=2-2, "χ_A"']
[from=1-1, to=2-2, "⌟"anchor=center, pos=0.125, draw=none]

A category $\cat{C}$ is cartesian closed if it has finite products and any two objects $A,B \in \cat{C}$ have an exponential object $B^A \in \cat{C}$.
In more details, there must exist a functor $-^A : \cat{C} \to \cat{C}$ that is right adjoint to the product functor:
\(
- \times A \dashv -^A.
% \begin{tikzcd}
%     - \times A: \cat{C}  & \cat{C} : -^A .
%     \ar[from=1-1, to=1-2, shift right=1.3]
%     \ar[from=1-1, to=1-2, phantom, "\scriptscriptstyle\bot"]
%     \ar[from=1-2, to=1-1, shift right=1.3]
% \end{tikzcd}
\)
A category $\cat{C}$ is locally cartesian closed if all its slice categories $\cat{C}/C$ are cartesian closed.

We recall some order theory definitions.

* A lattice is a poset $(\labels, \leq)$ that has a binary join $\join$ and binary meet $\meet$.

* A lattice is bounded if it has a greatest element $\top$ and a least element $\bot$.

* A lattice is complete if all its subsets have both a join and a meet.

* A Heyting algebra is a bounded lattice with, for all elements $a$ and $b$, an element $a \Rightarrow b$ such that for all $c$

\begin{equation} \label{eq:heyting_algebra_cartesian_closed}
a \meet b \leq c \iff a \leq b \Rightarrow c
\end{equation}

We can view a poset/lattice/Heyting algebra as a category where for any two elements $a,b$ there is at most one morphism from $a$ to $b$, denoted $a \leq b$.[
See e.g. <cit.>, <cit.>, or <cit.>.
Meet and join correspond to binary product and coproduct.
Least and greatest elements correspond to initial and a terminal objects.
A bounded lattice is thus finitely bicomplete.
A lattice is complete in the usual sense if and only if it is complete as a category.[
Note that completeness and cocompleteness are equivalent for lattices <cit.>.
Heyting algebras are cartesian closed categories because (<ref>) is the $\Hom$-set adjunction requirement asking $a \Rightarrow b$ to be an exponential object.
The counit of the adjunction tells us that we have modus ponens <cit.>:

\begin{equation} \label{eq:heyting_algebra_modus_ponens}
a \meet (a \Rightarrow b) = a \meet b.
\end{equation}

A category is a quasitopos if

* every finite limit and finite colimit exists,

* it has a regular-subobject classifier, and

* it is locally cartesian closed.

The definition of quasitopos is sometimes stated with the requirement of having a strong-subobject classifier, see e.g. <cit.> or <cit.>.
Both definitions are equivalent, since in any category, a regular monomorphism is strong, and conversely, asking for strong-subobjects to be classified makes them necessarily regular <cit.>.

§ FUZZY PRESHEAVES ARE QUASITOPOSES

We introduce the notion of a fuzzy presheaf, which generalises fuzzy sets and fuzzy graphs.
This allows to obtain in only one definition the additional concepts of fuzzy undirected graphs, fuzzy hypergraphs, fuzzy k-uniform hypergraphs, and plenty more.
For examples see <ref>.

Given a category $I$ and a family of posets $(\labels(i),\leq)_{i \in I}$, an $\labels$-fuzzy presheaf is a pair $(A,\alpha)$ consisting of a presheaf $A : \opcat{I} \to \Set$ and a membership function $\alpha : A \to \labels$, or to be more precise, a family of functions $\alpha_i : A(i) \to \labels(i)$ for each $i \in I$.
A morphism of $\labels$-fuzzy presheaves $f : (A,\alpha) \to (B,\beta)$ is a natural transformation $f :A \to B$ such that $\alpha \leq \beta f$, i.e., $\alpha_i \leq \beta_i f_i$ for all $i \in I$.
They form a category $\FuzzyPresheafDefault$.

Note that by taking each $\labels(i)$ to be a singleton set, we retrieve the usual definition of presheaf.

One can strenghten <ref> by requiring, for each $j \xrightarrow{\iota} i$ in $\I$, a poset morphism $\labels(\iota) : \labels(i) \to \labels(j)$ such that the diagram on the right $=$-commutes or $\leq$-commutes.
\(
\opcat{I} =
\smash{\begin{tikzcd}[ampersand replacement=\&]
\ar[r, "s"{description}, shift left=3pt]
\ar[r, "t"{description}, shift right=3pt]
\& V
\end{tikzcd}}
\), asking for $\labels(E) = \labels(V)$, for $\labels(s)=\labels(t)=\id{}$, and for $\leq$-commutation gives the fuzzy graphs as in <ref>.

[ampersand replacement=&, sep=normal]
A(i) & A(j)

(i) & (j)
[from=1-1, to=1-2, "A(ι)"]
[from=1-1, to=2-1, color=gray, "α_i"']
[from=1-2, to=2-2, color=gray, "α_j"]
[from=2-1, to=2-2, color=gray, "(ι)"']
[from=1-1, to=2-2, color=gray, "=  or  ≤"description, draw=none]

The rest of this section is dedicated to proving the next theorem.

If $I$ is a small category and $(\labels(i))_{i \in I}$ is a family of complete Heyting algebras, then $\FuzzyPresheafDefault$ is a quasitopos.

In the rest of this section $I$ is a small category and $\mathcal{L} = \big( \mathcal{L}(i) \big)_{i \in I}$ is a family of complete Heyting algebras.
We give a brief high-level overview of the proof.
We tackle the properties of being a quasitopos one by one (<ref>):

* <ref>:
Finite limits and colimits exist for presheaves, and it suffices to combine them with a terminal (respectively initial) structure to have finite limits (respectively finite colimits) for fuzzy presheaves.

* <ref>:
We modify the subobject classifier for presheaves by giving all its elements full membership.
This gives us the regular-subobject classifier for fuzzy presheaves.

* <ref>:
We combine how exponential objects look like for fuzzy sets and presheaves to obtain exponential objects for fuzzy presheaves, resulting in cartesian closedness.

* <ref>:
Lastly, to show that we have a locally cartesian closed category, we show that every slice of a fuzzy presheaf category gives another fuzzy presheaf category, extending on a result from the literature.

§.§ Finite limits and colimits

The goal of this subsection is to prove the following

$\FuzzyPresheafDefault$ has all finite limits and colimits.

To show existence of finite limits, it suffices to show the existence of a terminal object and of pullbacks <cit.>.
Those are the same as in $\PresheafDefault$, paired with a final structure for the membership function <cit.>.
The terminal object is $1(i) = \set{\; \cdot^\top }$ for each $i \in I$, with the single element having full membership $\top \in \labels(i)$.
The pullback of two functions $f$ and $g$ is depicted on the right.
Its membership function must be maximal satisfying $\delta \leq \alpha g'$ and $\delta \leq \beta f'$, and is therefore simply the meet of both conditions.
The proof that $\FuzzyPresheafDefault$ has all finite colimits is dual.

[scale cd =.8, column sep=1mm,row sep=2mm]
A ×_C B

A                         B

["α"', color=gray, from=2-1, to=6-5]
["γ"', color=gray, from=3-6, to=6-5]
["β", color=gray, from=2-8, to=6-5]
["δ"'pos=0.7, color=gray, dotted, from=1-3, to=6-5]
["g'"', dotted, from=1-3, to=2-1]
["f'", dotted, from=1-3, to=2-8]
["f"pos=0.7, from=2-1, to=3-6]
["g"', from=2-8, to=3-6]

$\delta_i (d) \defeq \alpha_i g'_i (d) \meet \beta_i f'_i (d)$

§.§ Regular-subobject classifier

The goal of this subsection is to prove the following.

$\FuzzyPresheafDefault$ has a regular-subobject classifier.

We first look at some examples of regular monomorphisms

* In $\Set$, a monomorphism is a subset inclusion (up to isomorphism), and all monomorphisms are regular <cit.>.

* In $\PresheafDefault$, a morphism $m : A \to B$ is (regular) monic if and only if every $m_i : A(i) \to B(i)$, where $i \in I$, is (regular) monic.
All monomorphisms are therefore regular for the same reason as in $\Set$.

* In $\FuzzySetDefault$, a regular monomorphism $m : (A,\alpha) \regmono (B,\beta)$ is an equaliser of some functions $f_1,f_2 : B \rightrightarrows C$.
Because $m: (A,\beta m) \rightarrow (B,\beta)$ also equalises $f_1$ and $f_2$, the universal property of the equaliser implies $\beta m \leq \alpha \leq \beta m$ and thus equality $a = \beta m$.
So when $A \subseteq B$, $\alpha$ is the restriction $\beta\restrict{A}$ <cit.>.

\[\begin{tikzcd}[column sep = 2em, row sep = .4em] %scale cd=.5
A && B && C \\
A \\
&& {\color{gray}\labels}
\arrow["{f_1}", shift left=1, from=1-3, to=1-5]
\arrow["{f_2}"', shift right=1, from=1-3, to=1-5]
\arrow["m", hook, from=1-1, to=1-3]
\arrow[equal, from=2-1, to=1-1]
\arrow["\beta", color=gray, from=1-3, to=3-3]
\arrow["\gamma", color=gray, from=1-5, to=3-3]
\arrow["\beta m"', color=gray, from=2-1, to=3-3]
\arrow["\alpha", color=gray, pos=.6, from=1-1, to=3-3]
\arrow["m", hook, crossing over, from=2-1, to=1-3]
\end{tikzcd}\]

Fuzzy presheaves being pointwise fuzzy sets, we have the following.

A regular monomorphism ${m : (A,\alpha) \regmono (B,\beta)}$ between fuzzy presheaves is a natural transformation ${m : A \to B}$ such that each $m_i : (A(i),\alpha_i) \regmono (B(i),\beta_i)$ is regular, i.e., $\alpha_i = \beta_i m_i$.

[column sep=0mm, row sep=3mm, ampersand replacement=&]
A(i) &  & B(i)

& (i)
["α_i"', color=gray, from=1-1, to=2-2]
["β_i", color=gray, from=1-3, to=2-2]
["m_i", from=1-1, to=1-3]
["=" description, draw=none, color=gray, from=1-2, to=2-2]

We denote the pullback of a morphism $m : A \to C$ along another morphism $f : B \to C$ by $\pullbackby{f}m$.

We continue <ref> and look at the (regular-)subobject classifiers of the aforementioned categories.

* In $\Set$, we have $\true : \set{\cdot} \to \Omega \defeq \set{0,1} : \cdot \mapsto 1$.
For $m : A \mono B$, the characteristic function $\chi_A : B \to \set{0,1}$ is $1$ on $m(A) \subseteq B$ and $0$ on the rest.

[row sep=2mm, column sep=5mm,ampersand replacement=&]
A && ·

B && 0,1
["m"', tail, from=1-1, to=3-1]
["", from=1-3, to=3-3]
["!", from=1-1, to=1-3]
["χ_A"', from=3-1, to=3-3]
["α=βm"description,outer sep=0,inner sep=0,pos=0.4, color=gray, from=1-1, to=2-2]
["⊤"description, color=gray, from=1-3, to=2-2]
["⊤"description, color=gray, from=3-3, to=2-2]
["β"description, color=gray, from=3-1, to=2-2]

* In $\FuzzySetDefault$ <cit.>, we have $\Omega \defeq \set{\; 0^\top,1^\top}$ with both elements having full membership.
The square being a pullback forces $\alpha = \beta m$.
Hence $\Omega$ classifies only regular subobjects.

[ampersand replacement=&]
[loop, distance=1em, in=205, out=155, "0"']
[r, "t"', bend right=15]
& 1
[loop, distance=1em, in=295, out=245, "(s, t)"']
[loop, distance=1em, in=115, out=65, "s →t"']
[l, "s"', bend right=15]

* In $\Graph$
[42], the terminal object is
\(
\set{
\begin{tikzcd}
\cdot \arrow[loop, distance=.8em, in=200, out=160]
\end{tikzcd}
\),
the classifying object $\Omega$ is shown on the right, and
\(
\true :
\begin{tikzcd}
\cdot
\arrow[loop, distance=.8em, in=200, out=160]
\end{tikzcd}
\mapsto
\begin{tikzcd}
\arrow[loop, distance=.8em, in=20, out=-20, "s \to t"']
\end{tikzcd}
\).
Given a graph $H$ and a subgraph $G \subseteq H$,  the characteristic function $\chi_G$ sends vertices in $G$ to $1$ and edges in $G$ to $s \to t$.

Vertices not in $G$ are sent to $0$; and edges not in $G$ are sent to $(s,t)$ if both endpoints are in $G$, to $0$ if neither endpoint is in $G$, and to $s$ or $t$ if only the source or target is in $G$, respectively.

When $I$ is small, $\PresheafDefault$ has a subobject classifier [24].
By smallness of $I$, the class of the subobjects of a presheaf $B \in \PresheafHatDefault$ (also called subpresheaves) is necessarily a set.

This allows us to define a functor $\Sub_{\PresheafHatDefault} : \opcat{\PresheafHatDefault} \to \Set$:

* $\Sub_{\PresheafHatDefault}(B) \defeq \set{\text{subobjects } m : A \mono B}$,

* $\Sub_{\PresheafHatDefault}(f:B \to C)$ sends a subobject $(A\stackrel{n}{\mono} C)$ of $C$ to $\pullbackby{f}n$, the pullback of $n$ along $f$, which is a subobject of $B$.

The classifying object is the presheaf $\Omega \defeq \Sub_{\PresheafHatDefault} (y(-)) : \opcat{I} \to \Set$.
For $i \in I$, $\Omega(i)$ is thus the set of all subpresheaves of $y(i)$, which are sometimes called sieves.
Let $\true_i : \set{\cdot} \to \Omega(i) : \cdot \mapsto y(i)$, because $y(i)$ is indeed a subpresheaf of itself.
We prove that $\true$ classifies subobjects.
Pick a subpresheaf $m : A \mono B$, and suppose w.l.o.g. $A(i) \subseteq B(i)$ for each $i \in I$.
We want to define the natural transformation $\chi_A : B \to \Omega$.
For $i \in I$ and $b \in B(i)$, then $(\chi_A)_i(b) \in \Omega(i)$ must be a subpresheaf of $y(i) = I(-,i)$.
On $j \in I$, let

\begin{equation}
\label{eq:def_chi_A}
\defeq \setvbar{\iota : j \to i}{B(\iota)(b) \in A_j}.
\end{equation}

We have the following properties:

* $\chi_A$ is natural,

$\chi_A$ characterises the subpresheaf $A \subseteq B$, i.e., gives a pullback square, and

* $\chi_A$ is unique in satisfying <ref>.
[The symbol $\blacksquare$ denotes that the proof is in the appendix.
A sketch of the proof is in <cit.>.

In $\FuzzyPresheafDefault$, we consider the same construction and give full membership value to $\Omega$, analogously to the fuzzy set regular-subobject classifier.
Explicitly, for $i \in I$, let $\omega_i : \Omega(i) \to \labels(i) : \big(A \mono y(i)\big) \mapsto \top$.
By <ref>, $(\Omega,\omega)$ is the regular-subobject classifier that we seek and <ref> is hence proved.

§.§ Cartesian closed

The goal of this section is to prove the following.

$\FuzzyPresheafDefault$ is cartesian closed.

Let $(A,\alpha)$ be a fuzzy presheaf.
We construct a product functor, an exponentiation functor, and an adjunction between them:
$- \times (A,\alpha) \dashv -^{(A,\alpha)}$.

The product of two fuzzy presheaves $(C,\gamma)$ and $(A,\alpha)$ is $(C \times A, \gamma\pi_1 \meet \alpha\pi_2)$.
The membership function is written $\gamma \meet \alpha$ for short.
Given ${f:(C',\gamma') \to (C,\gamma)}$, then $f \times (A,\alpha) \defeq f \times \id{A}$.

[sep=tiny, ampersand replacement=&]
C' ×A
[rr, "f ×𝕀A"]
[dr, color=gray, "γ' α"']
[d, "≤" description, draw=none, color=gray]
& C ×A
[dl, color=gray, "γα"]

The $- \times (A,\alpha)$ functor is well-defined on morphisms.

Because $\gamma' \leq \gamma f$, it follows that $\gamma' \meet \alpha \leq (\gamma \meet \alpha) \circ (f \times \id{A})$.

To construct exponential objects    of fuzzy presheaves, we first look at simpler examples.

* In $\Set$, given two sets $A,B$, then $B^A \defeq \Set(A,B)$.

* In $\FuzzySet{\labels}$ <cit.>, given fuzzy sets $(A,\alpha: A \to \labels), (B, \beta: B \to \labels)$, then $(B,\beta)^{(A,\alpha)}$ has carrier $B^A$ as in $\Set$ and membership function

\[
\theta(f: A \to B) \defeq \bigmeet_{a \in A} \left( \alpha(a) \Rightarrow \beta f (a) \right).
\]

Logically speaking, the truth value of $f$ is the minimum truth-value of truth preservation by $f$, i.e., if $a$ then $f(a)$.

* In $\Graph$ [42] (i.e., directed multigraphs), given two graphs $A,B$ then $B^A$ is the graph

* with vertex set $B^A(V) \defeq \Graph \big(\set{\cdot} \times A, B\big)$,

* with edge set $B^A(E) \defeq \Graph \big(\set{s \to t} \times A,B \big)$,

* the source of $m: \set{s \to t} \times A \to B$ is $m(s,-) : \set{\cdot} \times A \to B$, and

* the target function is analogous.

* In $\PresheafHatDefault$ <cit.>, given $A,B : \opcat{I} \to \Set$, then $B^A=\hat{I}(y(-)\times A, B)$ is:

* on $i \in I$, the set of all natural transformations $y(i) \times A \Rightarrow B$.

* on $\iota : j \to i$, the precomposition by $y(\iota) \times \id{A}$.

\begin{equation}
\label{eq:exponent_def_objects_iota}
y(i) \times A \xrightarrow{m} B
\quad \longmapsto \quad
y(j) \times A \xrightarrow{y(\iota) \times \id{A}} y(i) \times A \xrightarrow{m} B
\end{equation}

Notice how this generalises the $\Graph$ case: for
\(
\opcat{I} =
\smash{\begin{tikzcd}[ampersand replacement=\&]
\ar[r, "s"{description}, shift left=3pt]
\ar[r, "t"{description}, shift right=3pt]
\& V
\end{tikzcd}}
\),
we indeed have $y(V) \isom \set{\cdot}$ and $y(E) \isom \set{s \to t}$.

Given fuzzy presheaves $(A,\alpha)$ and $(B,\beta)$, let
\(
\defeq
\big( \PresheafHatDefault(y(-) \times A,B), \theta \big).
\)
The carrier is the same as in $\PresheafHatDefault$ above.
On $i \in I$, it is the set of natural transformations $y(i) \times A \Rightarrow B$ and on $\iota:j \to i$ it is the precomposition by $y(\iota) \times \id{A}$.
The membership function is, for each $i \in I$:

\begin{equation}
\label{eq:exponent_def_objects_i}
\theta_i
\Big(
y(i) \times A \xrightarrow{m} B
\Big)
\defeq
\bigmeet_{a \in A(i)}
\big(
\alpha_i a \Rightarrow \beta_i m_i(\id{i},a)
\big).
\end{equation}

Given $(B,\beta) \stackrel{g}{\to} (B', \beta')$, the morphism $g^{(A,\alpha)}$ is postcomposition by $g$:

\begin{equation} \label{eq:exponent_def_morphisms}
\begin{tikzcd}[row sep=tiny, column sep = small]
\PresheafHatDefault(y(i) \times A,B)
\ar[rr, "g^{(A,\alpha)}_i \defeq g \circ -"]
\ar[dr, color=gray, "\theta_i"']
&& \PresheafHatDefault(y(i) \times A,B')
\ar[dl, color=gray, "\theta'_i"] \\
& {\color{gray}\labels(i)} &
\end{tikzcd}
\end{equation}

The exponentiation functor is well-defined on morphisms.

The mapping $\smash{g^{(A,\alpha)}}$ is clearly natural in $i \in I$.
Indeed, $\smash{g_i^{(A,\alpha)}}$ is postcomposition by $g$ (<ref>), $\smash{\PresheafHatDefault(y(\iota)\times A, B)}$ is precomposition by $y(\iota)\times\id{A}$ (<ref>), and pre- and postcomposition always commute.

Fix an arbitrary $i \in I$.
The other criteria to verify is that (<ref>) $\leq$-commutes, i.e., $\smash{\theta_i \leq \theta'_i g_i^{(A,\alpha)}}$.
Take some $m : y(i) \times A \to B$.
We prove $\smash{\theta_i(m) \leq \theta'_i  g_i^{(A,\alpha)} (m)}$.
By hypothesis $g:(B,\beta) \rightarrow (B', \beta')$, so $\beta_i \leq \beta'_i g_i$.
For any $a' \in A(i)$, we have $m_i(\id{i},a') \in B(i)$.

\begin{align*}
\forall a' \in A(i): \beta_i m_i (\id{i},a') \leq \beta_i' g_i m_i (\id{i},a')
\\
\forall a' \in A(i): \alpha_i(a') \meet \beta_i m_i (\id{i},a') \leq \beta_i' g_i m_i (\id{i},a')
\\
\forall a' \in A(i): \alpha_i(a') \meet (\alpha_i(a') \Rightarrow \beta_i m_i (\id{i},a')) \leq \beta'_i g_i m_i (\id{i},a')
\\
\forall a' \in A(i): (\alpha_i (a') \Rightarrow \beta_i m_i (\id{i},a')) \leq (\alpha_i (a') \Rightarrow \beta'_i g_i m_i (\id{i},a'))
\\
\forall a' \in A(i): \textstyle{\bigmeet}_{a \in A(i)} (\alpha_i (a) \Rightarrow \beta_i m_i (\id{i},a)) \leq (\alpha_i (a') \Rightarrow \beta'_i g_i m_i (\id{i},a'))
\\
\textstyle{\bigmeet}_{a \in A(i)} (\alpha_i (a) \Rightarrow \beta_i m_i (\id{i},a)) \leq \textstyle{\bigmeet}_{a' \in A(i)} (\alpha_i (a') \Rightarrow \beta'_i g_i m_i (\id{i},a'))
\\
&\stackrel{\smash{\mathclap{ \eqref{eq:exponent_def_objects_i}, \eqref{eq:exponent_def_morphisms} }}}{\Rightarrow}
\hspace*{1em}
\theta_i (m) \leq \theta'_i g^{(A,\alpha)}_i (m).
\qedhere
\end{align*}

Given a fuzzy presheaf $(A,\alpha)$, then $- \times (A,\alpha) \dashv -^{(A,\alpha)}$.

As a consequence, <ref> is now proved.

§.§ Locally cartesian closed

The goal of this section is to prove the following.

$\FuzzyPresheafDefault$ is locally cartesian closed.

Because we consider slice categories, let us fix an arbitrary fuzzy presheaf $(D,\delta)$ for the rest of this section.
We aim to prove that $\nicefrac{\FuzzyPresheafDefault}{(D,\delta)}$ is cartesian closed.
Here are the details of this category.

* Its objects are of the form $((A,\alpha),p)$ where $(A,\alpha)$ is a fuzzy presheaf and $p : (A,\alpha) \to (D,\delta)$ is a fuzzy presheaf morphism to the fixed object $(D,\delta)$, hence satisfying $\alpha \leq \delta p$.
We denote this object by $(A,\alpha,p)$ for simplicity.

* A morphism $f:(A,\alpha,p) \to (B,\beta,q)$ is a natural transformations $f: A \to B$ satisfying $p = qf$.
For $p,q$ and $f$ to be also well-defined in the base category $\FuzzyPresheafDefault$, we must also have $\alpha \leq \delta p$, $\beta \leq \delta q$ and $\alpha \leq \beta f$.

\[
\begin{tikzcd}[sep=small]
\ar[rr, "p"]
\ar[dr, color=gray, "\alpha"']
& {}
\ar[d, "\leq" description, draw=none, color=gray]
& D
\ar[dl, color=gray, "\delta"] \\
& {\color{gray}\labels} &
\end{tikzcd}
\qquad \qquad
\begin{tikzcd}[sep=tiny]
&&& D \\
A &&&& B \\
\\
&& {\color{gray}\labels}
\arrow["\delta"'{pos=0.9}, color=gray, from=1-4, to=4-3]
\arrow["f", crossing over, from=2-1, to=2-5]
\arrow["p", from=2-1, to=1-4]
\arrow["q"', from=2-5, to=1-4]
\arrow["\alpha"', color=gray, from=2-1, to=4-3]
\arrow["\beta", color=gray, from=2-5, to=4-3]
\end{tikzcd}
\]

To prove locally cartesian closedness, we extend on the technique
used in <cit.>.
We demonstrate that the slice category $\nicefrac{\FuzzyPresheafDefault}{(D,\delta)}$ is equivalent to another category of fuzzy presheaves $\FuzzyPresheaf{J}{\tilde{\labels}}$ for some other $J$ and $\tilde{\mathcal{L}}$.
Because cartesian closedness is preserved by categorical equivalence <cit.>, and because $\FuzzyPresheaf{J}{\tilde{\labels}}$ is cartesian closed by <ref>, then <ref> follows immediately.
The category $J$ is the category of elements of $D$, so let us recall its definition.

Given a presheaf $D \in \PresheafDefault$, its category of elements is denoted $\elements{D}$ or $\int_I D$ and contains the following:

* objects are pairs $(i,d)$ where $i \in I$ and $d \in D(i)$, and

* morphisms $\iota: (j,e) \to (i,d)$ are $I$-morphisms $\iota:j \to i$ such that $D(\iota)(d) = e$.

Recall that $\Graph$ it is the presheaf category on
$\opcat{I} = \smash{
\begin{tikzcd}[ampersand replacement=\&]
\ar[r, "s"{description}, shift left=3pt]
\ar[r, "t"{description}, shift right=3pt]
\& V
\end{tikzcd}
Given a graph $D$, the objects of its category of elements are ${\setvbar{(V,v)}{v \in D(V)}} \cup {\setvbar{(E,e)}{e \in D(E)}}$.
Each edge $e \in D(E)$ induces two $\elements{D}$-morphisms, one going onto the source of $e$, $(E,e) \to (V,s(e))$, and one onto its target $(E,e) \to (V,t(e))$.
All morphisms of $\elements{D}$ are obtained this way.

Let $I$ be a small category and $(\labels(i))_{i \in I}$ a family of complete Heyting algebras.
For any object $(D,\delta) \in \FuzzyPresheafDefault$, we have an equivalence of categories

\[
\quot{\FuzzyPresheafDefault}{(D,\delta)}
\equivcat
\FuzzyPresheaf{\elements{D}}{\tilde{\labels}}
\]

where for $(i,d) \in \opcat{\elements{D}}$, $\tilde{\labels}(i,d) \defeq \labels(i)_{\leq \delta_i(d)}$.

By <ref>, then <ref> is proved.
By <ref>, the proof of <ref> is complete.

If $I$ is a finite category, then every finite presheaf category $\FinSet^{\opcat{I}}$ is a topos <cit.>.
Analogously, if $I$ is finite we also have that every finite fuzzy presheaf category is a quasitopos.

§ FUZZY PRESHEAVES ARE RM-ADHESIVE

In this section we show that fuzzy presheaves are rm-adhesive. To state and motivate the result we need some definitions.

[row sep=20,between origins,column sep=20,between origins, ampersand replacement=&]
& F  [rr] [dd] [dl] & &  G [dd] [dl]

E [rr, crossing over] [dd] & & H

& B [rr] [dl] & &  C [dl]

A [rr] && D [from=uu,crossing over]

A pushout square is Van Kampen (VK) if, whenever it lies at the bottom of a commutative cube, like $ABCD$ on the diagram, where the back faces $FBAE$, $FBCG$ are pullbacks, then

the front faces are pullbacks $\iff$ the top face is pushout.

A pushout square is stable (under pullback) if, whenever it lies at the bottom of such a cube, then

the front faces are pullbacks $\implies$ the top face is pushout.

A category $\cat{C}$ is

* adhesive if pushouts along monomorphisms exist and are VK;

* rm-adhesive[Also known as quasiadhesive.] if pushouts along regular monomorphisms exist and are VK;

* rm-quasiadhesive if pushouts along regular monomorphisms exist, are stable, and are pullbacks.

Toposes are adhesive <cit.> (and thus rm-adhesive), and quasitoposes are rm-quasiadhesive [15]. Not all quasitoposes are rm-adhesive. The category of simple graphs is a counterexample <cit.>.

[column sep=12, row sep=12,ampersand replacement=&,nodes=rectangle,inner sep=0.5mm,outer sep=0]
& K
[ld, "u" description]
[rrd, "r" description, pos=0.3]
[dd, equals]
& &

[dd, "u'" description]
& & & R
[ld, "w" description] [dd, equals]

& K
[ld, "t_K" description]
[rrd, "r" description, pos=0.3]
& G_R
[from=llu, "g_R" description, crossing over, pos=0.25]

[rrd, "r'" description]
& & & R
[ld, "t_R" description]

& & R'
[from=uu, "w'" description, crossing over]

Knowing whether a quasitopos $\cat{C}$ is rm-adhesive is considerably relevant for . Every  rewrite step defines a commutative cube (shown on the right)
where the bottom and top faces are pushouts, and the back faces are pullbacks. So if $t_K$ is a regular mono (as often is the case), it follows that the front faces are pullbacks. The termination method for  rewriting [29], recently developed by the second and third author, depends on the front faces being pullbacks, as well as other quasitopos properties. We expect that the dependency will hold for future theory as well.

Coproducts are a generalisation of the notion of disjoint unions in $\Set$.
However, a notion of union can still be defined.
In a quasitopos, there is an elegant description of binary union of regular subobjects <cit.>.

The binary union of two regular subobjects $f: A \regmono C$ and $g : B \regmono C$ in a quasitopos is obtained as the pushout of the pullback of $f$ and $g$.

\begin{equation}
\label{eq:binary:union:diagram}
\begin{tikzcd}[column sep=normal, row sep=tiny]
& A
\arrow[rd, "f''" description]
\arrow[rrrd, "f" description, hook, bend left=10]
& & \\
D \defeq A \sqcap_C B
\arrow[ru, "g'" description]
\arrow[rd, "f'" description]
& & A \sqcup_{D} B
\arrow[rr, "h" description, dotted]
&& C \\
& B
\arrow[rrru, "g" description, hook, bend right=10]
\arrow[ru, "g''" description]
& &
\end{tikzcd}
\end{equation}

In a quasitopos, if $f$ or $g$ of (<ref>) is regular monic, then $h$ is monic.

To prove  $\FuzzyPresheafDefault$ rm-adhesive, we use the following theorem.

If $\cat{C}$ is a quasitopos, then $\cat{C}$ is rm-adhesive iff the class of regular subobjects is closed under binary union.

If $I$ is a small category and $(\labels(i))_{i \in I}$ is a family of complete Heyting algebras, then $\FuzzyPresheafDefault$ is rm-adhesive.

By <ref>, $\FuzzyPresheafDefault$ is a quasitopos, and so by <ref>, it suffices to show that the class of regular subobjects is closed under binary union. By the reasoning given in Example <ref>, it suffices to show this property pointwise, i.e., on the level of $\FuzzySetDefault$.

So let two regular subobjects $f : A \regmono C$ and $g : B \regmono C$ of $\FuzzySetDefault$ be given.
In (<ref>), $f'$ and $g'$ are regular monic by (general) pullback stability, and then $f''$ and $g''$ are regular monic by pushout stability in quasitoposes <cit.>.
Moreover, by <ref>, $h$ is monic.

Now consider an arbitrary element $y \in A \sqcup_D B$.
By general pushout reasoning for $\Set$, $y$ is in the image of $f''$ or $g''$, say w.l.o.g. $y = f''(a)$ for some $a \in A$.
Because $f = hf''$ and $f$ is regular (i.e., membership-preserving), $a$ and $h(y)$ have the same membership value.
The membership value of $y$ is sandwiched between the ones of $a$ and of $h(y)$ and all three are thus equal.
This means that $h$ preserves the membership, i.e., is regular.

§ EXAMPLES AND APPLICATIONS

In this section, we showcase the wide variety of structures that presheaf categories cover.
We can therefore add labels from a complete Heyting algebra to all of those categories, and have an rm-adhesive quasitopos.

We describe multiple categories of graph as presheaf categories $\PresheafDefault$ and specify $\opcat{I}$ for each.

* Multigraphs: We allow parallel edges, i.e., with same source and target.

* Directed: denoted $\Graph$ in this paper;
\(
\opcat{I} =
\smash{
\begin{tikzcd}[ampersand replacement=\&]
\ar[r, "s"{description}, shift left=3pt]
\ar[r, "t"{description}, shift right=3pt]
\& V.
\end{tikzcd}
\)

* Undirected <cit.>:
each edge $e$ requires another one $\sym(e)$ in the other direction, which is equivalent to having an undirected edge.

\[
\opcat{I} =
\smash{
\begin{tikzcd}[ampersand replacement=\&]
\ar[loop, "\sym"', distance=1em, in=205, out=155]
\ar[r, "s"{description}, bend left = 0, shift left=3pt]
\ar[r, "t"{description}, bend right = 0, shift right=3pt]
\& V
\end{tikzcd}
\quad
\text{where}
\qquad
\begin{aligned}
\sym \cdot \sym &= \id{E}, \\
s \cdot \sym &= t, \\
t \cdot \sym &= s.
\end{aligned}
\]

* Directed reflexive <cit.>:
Each vertex $v$ has a specific loop
\(
\begin{tikzcd}
\arrow[loop, "\refl_v"', distance=.8em, in=200, out=160]
\end{tikzcd}
\)
preserved by graph homomorphisms.
It is equivalent to omitting those reflexive loops and considering that an edge mapped onto a reflexive loop is now sent to the vertex instead, giving degenerate graphs.

\[
\opcat{I} =
\smash{
\begin{tikzcd}[ampersand replacement=\&]
\ar[r, "s"{description}, bend left = 0, shift left=6pt]
\ar[r, "t"{description}, bend right = 0, shift right=6pt]
\& V
\ar[l, "\refl"{description}]
\end{tikzcd}
\quad
\text{where}
\qquad
s \cdot \refl = t \cdot \refl = \id{V}.
\]

* Undirected reflexive <cit.>: with both $\sym$ and $\refl$ in $\opcat{I}$, we must add the equation $\sym \cdot \refl = \refl$.

* (Multi) Hypergraphs:
An hyperedge can contain any number of vertices.

* For hyperedges to be ordered lists $\langle v_1, \ldots, v_{m} \rangle$ of vertices, let $\opcat{I}$ have objects $V$ and $E_m$ for each $m \in \N_{\geq 1}$.
Homomorphisms preserve arities.

\[
\opcat{I}
\text{ contains for each $m \in \N_{\geq 1}$:}
\quad
\smash{
\begin{tikzcd}[ampersand replacement=\&, column sep=large]
\ar[r, "s_1"{description}, bend left = 0, shift left=6pt]
\ar[r, "\cdots"{description}, draw=none]
\ar[r, "s_{m}"{description}, bend right = 0, shift right=6pt]
\& V
\end{tikzcd}
\]

* For hyperedges to be unordered sets $\set{v_1, \ldots, v_{m}}$, take the convention that all possible ordered list containing the same vertices must exist.
For that, add $m$ symmetry arrows, i.e., $\opcat{I}$ contains for each $m \in \N_{\geq 1}$:

\[
\smash{
\begin{tikzcd}[ampersand replacement=\&, column sep=large]
\ar[loop, "\sym_1"', distance=1em, in=115, out=65]
\ar[loop, "\cdots"{description}, distance=1em, in=205, out=155]
\ar[loop, "\sym_{m}"', distance=1em, in=295, out=245]
\ar[r, "s_1"{description}, bend left = 0, shift left=6pt]
\ar[r, "\cdots"{description}, draw=none]
\ar[r, "s_{m}"{description}, bend right = 0, shift right=6pt]
\& V
\end{tikzcd}
\quad
\text{where}
\qquad
\begin{aligned}
\sym_j\cdot \sym_j &= \id{E}, \\
s_1 \cdot \sym_1 &= s_2, \\
s_2 \cdot \sym_1 &= s_1, \\
s_i \cdot \sym_1 &= s_i \text{ for } i \neq 1,2, \\
\ldots
\end{aligned}
\]

* To consider $m$-uniform hyperedges, i.e., having exactly $m$ vertices in all of them, for $m$ fixed, let $\opcat{I}$ have as objects only $E_m$ and $V$ in the previous examples.

* We can extend the previous hyperedge examples to admit targets <cit.> by having for each $m,n$ an object $E_{m,n}$ with

\[
\opcat{I}(E_{m,n},V)
\set{s_0,\ldots,s_{m-1}}
\cup
\set{t_0, \ldots, t_{n-1}}.
\]

* Here is an alternative definition of a hypergraph:
Let $G$ be a hypergraph if it has three sets $G(R), G(E), G(V)$ and two functions $f : G(R) \to G(E)$ and $g : G(R) \to G(V)$.
We read $r \in G(R)$ as meaning that $g(r)$ is a vertex incident to the hyperedge $f(r)$.
Note that a vertex can be incident to same hyperedge multiple times and that morphisms do not preserve arities here.

\[
\opcat{I} =
\smash{
\begin{tikzcd}[ampersand replacement=\&, sep=small]
\& R
\ar[l, "f"']
\ar[r, "g"]
\& V
\end{tikzcd}
\]

As pointed out in [3], the category of Petri nets is not a topos because it is not cartesian closed.
However, the authors show that the category of pre-nets, which are Petri nets where the input and the output of a transition are ordered, is equivalent to a presheaf category.

Here is an example of how the fuzzy structure can be used in hypergraph rewriting.
Assume we are in a distributed system setting, with $\resources \supseteq \{ \mathletter, \mykey \}$ a globally fixed set of resources. A system state $S = \langle \processes, \holds, \connections, \myconnect \rangle$ consists of: a set of processes $\processes$, a resource assignment $\holds : \processes \to \powerset(\resources)$, a set of ternary connections $\connections$, and a connection assignment $\myconnect : \connections \to \processes \times \processes \times \processes$.

Suppose that in this system, a process $p$ can transmit $\mathletter$ to a process $q$ if, for some $C \in \connections$ and $r \in \processes$: (i) $p$, $q$ and $r$ are distinct; (ii) $\mathletter \in \holds(p)$; (iii) $\mathletter \notin \holds(q)$; (iv) $\mathletter \notin \holds(q)$; (v) $\myconnect(C) = (p,q,r)$.

Executing the transmission changes the state by removing $\mathletter$ from $\holds(p)$, adding $\mathletter$ to $\holds(q)$, removing $\mykey$ from $\holds(r)$ and removing $C$ from $\connections$.
We can thus think of $r$ as a mediator for the transmission, which provides $\mykey$ as a required resource that is consumed.

We can model states as objects of the fuzzy presheaf $\FuzzyPresheafDefault$ where:
\(
\opcat{I} =
\smash{
\begin{tikzcd}[cramped, column sep=20, ampersand replacement=\&]
\connections
\arrow[r, "s" description, shift left=5.5pt]
\arrow[r, "m" description]
\arrow[r, "t" description, shift right=5.5pt]
\& \processes
\end{tikzcd}
\)
and $\processes$ is labeled from the subset lattice $(\powerset(\resources), \subseteq)$, which is a complete Heyting algebra. Then the transmission described above can be informally defined as a hypergraph transformation rule:

[baseline=-3mm,->,node distance=12mm,nodes=rectangle]
(p) $p^{P \uplus \{\,\text{\raisebox{-.2ex}{\Letter }}\,\}}$;
(q) [right=of p] $q^{Q\, \setminus \{\,\text{\raisebox{-.2ex}{\Letter}}\,\}}$;
(r) at ($(p)!.5!(q) + (0mm,-6mm)$) $r^{R \uplus \{\mykey\}}$;
[->] (p) to (q);
[-,densely dotted] ($(p)!.5!(q)$) to (r);

at (40mm,-3mm) $\Longrightarrow$;
(p) $p^{P}$;
(q) [right=of p] $q^{Q \cup \{\,\text{\raisebox{-.2ex}{\Letter}}\,\}}$;
(r) at ($(p.east)!.5!(q.west) + (0mm,-6mm)$) $r^{R}$;

which is formally definable with a single  rule, so that it is applicable in any context. For extensive details on how this works for directed multigraphs, see <cit.>, which extends naturally to hypergraphs.

Other concrete examples of modellings using fuzzy multigraphs and fuzzy multigraph rewriting using  include:

* Binary decision diagrams reduction <cit.>.[To appear at the end of March 2023.]

* Processes that consume data from FIFO channels

* Terms and linear term rewriting <cit.>.

§ FUZZY SIMPLE GRAPHS FORM A QUASITOPOS

In <ref>, we described different multigraph categories as presheaf categories.
Hence, adding a fuzzy structure to these categories results in quasitoposes by <ref>.
This raises the question whether simple fuzzy graph categories are quasitoposes, and if so, whether it can be shown using <ref>.

First, simple graphs do not arise as presheaf categories, meaning <ref> cannot be applied.
Here is one way to observe this: presheaves are toposes and in toposes, all monomorphisms are regular.
However, monomorphisms in directed simple graphs <cit.> and in undirected simple graphs <cit.> are regular only if they reflect edges,[
A graph homomorphism $f : G \to H$ reflects edges if, for every $v,w \in G(V)$, every edge between $f_V(v)$ and $f_V(w)$ has an $f$-preimage.]
which is not always the case.

Nevertheless, we show in this section that directed and undirected simple fuzzy graph categories are quasitoposes, by using a different technique. In more detail,  given a (Lawvere-Tierney) topology $\topology$ on a topos, the $\topology$-separated elements form a subcategory which is a quasitopos <cit.>.
Vigna [42] has used this fact to prove that the (directed/undirected) simple graphs are exactly the $\lnot \lnot$-separated elements of the respective (directed/undirected) multigraph category, where $\lnot \lnot$ is a topology. We extend the approach by Vigna, showing that directed and undirected simple fuzzy graphs are quasitoposes.

Because we start from fuzzy multigraphs, which form a quasitopos, we need to work with the more general definition of a topology on a quasitopos (<ref>).
The result that the separated elements form a quasitopos still holds true with this more general definition of a topology <cit.>.
Recall <ref> if needed for the notations used.

Alternatively, Johnstone et al. show that Artin Glueing [9] can be used to prove that directed simple graphs form a quasitopos.
Given a functor $T : \cat{C} \to \cat{D}$, denote by $\cat{C} \sslash T$ the full subcategory of the slice category $\cat{C} / T$ consisting of the monomorphisms $X \mono TY$.
Then directed simple graphs can be seen as $\Set \sslash T$ for $TX = X \times X$.
Because $\Set$ is a quasitopos and $T$ preserves pullbacks, we have by <cit.> that $\Set \sslash T$, i.e., directed simple graphs, is a quasitopos.

A topology $\topology$ on a quasitopos $\cat{E}$ is a family of mappings $\MonoClass(A) \to \MonoClass(A)$ for each $A \in \cat{E}$.
It sends every monomorphism $m : A_0 \mono A$ to another monomorphism $\topology m : A_1 \mono A$ with same codomain $A \in \cat{E}$, such that

* If $m \leq m'$, then $\topology m \leq \topology m'$.

* $m \leq \topology m$.

* $\topology \topology m \simeq \topology m$.

* For all $f:B \to A$, we have $\topology(\pullbackby{f}m) \simeq \pullbackby{f}(\topology m)$.

* If $m$ is regular, then so is $\topology m$.

Notice that axioms $(i)-(iii)$ says that $\topology$ is a closure operation.
For instance in $\Set$, given a subset $A_0 \subseteq A$, $(ii)$ requires that $A_0 \subseteq \topology(A_0) \subseteq A$.
By $(iv)$ and $(v)$ the closure operation must commute with pullbacks and preserve regularity.

We give two basic examples of topologies.
The third example is more advanced; examples of it in a few categories are given in the next lemma.

* The trivial topology
$\topology(A_0 \stackrel{m}\mono A) \defeq (A \stackrel{\id{A}}{\longequal} A)$.

* The discrete topology
$\topology(A_0 \stackrel{m}\mono A) \defeq (A_0 \stackrel{m}\mono A)$.

* Let $m : A_0 \mono A$.
Consider the (necessarily monic) morphism from the initial object $0 \mono A$ and factorise it as (epi mono, regular mono) $\overline{o_A} \circ e : A_0 \epimono A_1 \regmono A$.
Let $\lnot m$ be the exponential object $(\overline{o_A} : A_1 \regmono A)^{(m:A_0 \mono A)}$ in the slice category $\cat{E}/A$.
Then $\lnot \lnot$ is a topology called the double negation.

We detail the $\lnot \lnot$ topology in a few categories.
In each situation, we consider subobjects of an object $A$ or $(A,\alpha)$.

* In $\Set$,
\(
\lnot A_0 = A \setminus A_0.
\)
Therefore, $\lnot \lnot = \id{}$.

* In $\FuzzySetDefault$,
\(
\lnot(A_0,\alpha_0) = (A \setminus A_0, \alpha).
\)
Therefore, $\lnot \lnot$ is the identity on the subset but replaces its membership function $\alpha_0$ with $\alpha$, the one of $A$.

* In $\Graph$,

$\lnot A_0$ is the largest subgraph of $A$ totally disconnected from $A_0$.
Hence, $\lnot \lnot A_0$ is the largest subgraph of $A$ induced by $A_0(V)$, i.e., every edge from $A$ with source and target in $A_0$ is added in $\lnot \lnot A_0$.

* In $\FuzzyGraph$, $\lnot \lnot$ acts like in $\Graph$ on the underlying graph, i.e., it adds all edges that had source and target in the subgraph, and it replaces the membership function of the subobject with the one of the main object.

The notions of density and separatedness from standard topology, can also be defined for (quasi)topos topologies.
To illustrate what density is, recall that $\Q$ is called dense in $\R$ because closing it under the standard metric topology, i.e., adding an arbitrary small open interval around each rational number, gives the whole space $\R$.
In standard topology, recall also that every separated space $B$ (a.k.a. Hausdorff space), has the property that functions $f : A \to B$ are fully determined by the images on any dense subsets of $A$.

Given a topology $\topology$ in a quasitopos $\cat{E}$:

* a monomorphism $A_0 \stackrel{m}{\mono} A$ is $\topology$-dense if $\topology(A_0 \stackrel{m}{\mono} A) = (A \stackrel{\id{A}}{\longequal} A)$,

[ampersand replacement=&, sep=small]
A_0 &

A & B
[from=1-1, to=2-2, "f"]
[from=1-1, to=2-1, tail, "m"']
[from=2-1, to=2-2, dotted, "g"']

* an object $B$ is called $\topology$-separated if for every $\topology$-dense subobject $m : A_0 \mono A$ and every morphism $f : A_0 \to B$ there exists at most one factorisation $g : A \to B$ of $f$ through $m$.

The $\lnot \lnot$-separated graphs are precisely the simple graphs.

In $\Graph$, a subgraph $A_0 \subseteq A$ is $\lnot \lnot$-dense if it contains all the vertices $A_0(V) = A(V)$.
As a consequence, a graph $B$ is $\lnot \lnot$-separated if it has no parallel edges.

Similarly, the $\lnot \lnot$-separated fuzzy graphs are the simple fuzzy graphs.

In the category of (directed and undirected) fuzzy graphs, a subgraph $(A_0,\alpha_0) \subseteq (A,\alpha)$ is $\lnot \lnot$-dense if it contains all the vertices $A_0(V) = A(V)$.
Hence, a fuzzy graph $(B,\beta)$ is $\lnot \lnot$-separated if it has no parallel edges.

Directed and undirected simple fuzzy graphs form quasitoposes.

Immediate by <ref> and <cit.>.

§ CONCLUSION

In this paper, we introduced the concept of fuzzy presheaves and proved that they form rm-adhesive quasitoposes.
Furthermore, we showed that simple fuzzy graphs, both directed and undirected, also form quasitoposes.

There are several directions for future work.
The alternative definition of fuzzy presheaves from <ref>, with poset morphisms, can be explored further.
For graphs, it means that the membership of an edge gives a lower-bound for or determines the membership of its source and target.

To obtain fuzzy presheaves, we have added a pointwise fuzzy structure to presheaves.
More generally, different notions of fuzzy categories have been defined [40, 41].
It is natural to wonder if a fuzzy (quasi)topos is also a quasitopos.

Finally, a more abstract question is whether having a fuzzy structure is a particular instance of a more abstract categorical construction.
For instance, one could express an inequality in a poset $\mathcal{L}$ via a natural transformations and then say that a diagram is $\leq$-commuting when it commutes up to this natural transformation.
Another possibility would be to consider poset-enriched categories for comparing morphisms via inequality.
Fuzzy structures do look like slice or comma categories but do not precisely fall under their scope.
For comma categories, Artin Glueing gives a nice criteria for obtaining new quasitoposes [19].
We wonder if more abstract uniform theorems for obtaining quasitoposes can be expressed and proved.

§.§.§ Acknowledgments

We thank Helle Hvid Hansen for discussions and valuable suggestions.
The authors received funding from the Netherlands Organization for Scientific Research (NWO) under the Innovational Research Incentives Scheme Vidi (project. No. VI.Vidi.192.004).

[1]
Adámek, J., Herrlich, H., Strecker, G.E.: Abstract and Concrete Categories
: The Joy of Cats. Wiley, New York (1990)

[2]
Awodey, S.: Category Theory. Oxford Logic Guides, Ebsco Publishing (2006)

[3]
Baez, J.C., Genovese, F., Master, J., Shulman, M.: Categories of nets. In: 36th
Annual Symposium on Logic in Computer Science. pp. 1–13. IEEE (2021).

[4]
Bauderon, M.: A uniform approach to graph rewriting: The pullback approach. In:
Graph-Theoretic Concepts in Computer Science, 21st International Workshop,
WG. LNCS, vol. 1017, pp. 101–115. Springer (1995).

[5]
Behr, N., Harmer, R., Krivine, J.: Concurrency theorems for non-linear
rewriting theories. In: Graph Transformation - 14th International Conference,
ICGT 2021. LNCS, vol. 12741, pp. 3–21. Springer (2021).

[6]
Behr, N., Harmer, R., Krivine, J.: Concurrency theorems for non-linear
rewriting theories. CoRR  abs/2105.02842 (2021),

[7]
Borceux, F.: Handbook of categorical algebra. 1, Encyclopedia of Mathematics
and its Applications, vol. 50. Cambridge University Press, Cambridge (1994),
basic category theory

[8]
Borceux, F.: Handbook of categorical algebra. 3, Encyclopedia of Mathematics
and its Applications, vol. 52. Cambridge University Press, Cambridge (1994),
categories of sheaves

[9]
Carboni, A., Johnstone, P.T.: Connected limits, familial representability and
artin glueing. Math. Struct. Comput. Sci.  5(4),  441–459 (1995).

[10]
Cardoso, J., Valette, R., Dubois, D.: Fuzzy petri nets: An overview. IFAC
Proceedings Volumes  29(1),  4866–4871 (1996).
10.1016/S1474-6670(17)58451-7, 13th World Congress of IFAC, 1996

[11]
Corradini, A., Duval, D., Echahed, R., Prost, F., Ribeiro, L.: AGREE -
algebraic graph rewriting with controlled embedding. In: Graph Transformation
- 8th International Conference, ICGT 2015. LNCS, vol. 9151, pp. 35–51.
Springer (2015). 10.1007/978-3-319-21145-9_3

[12]
Corradini, A., Duval, D., Echahed, R., Prost, F., Ribeiro, L.: The PBPO graph
transformation approach. J. Log. Algebraic Methods Program.  103,
213–231 (2019). 10.1016/j.jlamp.2018.12.003

[13]
Corradini, A., Heindel, T., Hermann, F., König, B.: Sesqui-pushout
rewriting. In: Graph Transformations, Third International Conference, ICGT
2006. LNCS, vol. 4178, pp. 30–45. Springer (2006). 10.1007/11841883_4

[14]
Ehrig, H., Pfender, M., Schneider, H.J.: Graph-grammars: An algebraic approach.
In: 14th Annual Symposium on Switching and Automata Theory. pp. 167–180.
IEEE Computer Society (1973). 10.1109/SWAT.1973.11

[15]
Garner, R., Lack, S.: On the axioms for adhesive and quasiadhesive categories.
Theory and Applications of Categories  27,  27–46 (May 2012)

[16]
Goguen, J.: $L$-fuzzy sets. Journal of Mathematical Analysis and Applications
18(1),  145–174 (1967). 10.1016/0022-247X(67)90189-8

[17]
Johnstone, P.T.: On a topological topos. Proceedings of the London Mathematical
Society  s3-38(2),  237–271 (1979). 10.1112/plms/s3-38.2.237

[18]
Johnstone, P.T.: Sketches of an elephant: a Topos theory compendium. Oxford
logic guides, Oxford Univ. Press, New York, NY (2002)

[19]
Johnstone, P.T., Lack, S., Sobocinski, P.: Quasitoposes, quasiadhesive
categories and artin glueing. In: Algebra and Coalgebra in Computer Science,
Second International Conference, CALCO 2007. Lecture Notes in Computer
Science, vol. 4624, pp. 312–326. Springer (2007).

[20]
Lack, S., Sobocinski, P.: Adhesive categories. In: Foundations of Software
Science and Computation Structures, 7th International Conference, FOSSACS
2004. LNCS, vol. 2987, pp. 273–288. Springer (2004).

[21]
Lack, S., Sobociński, P.: Adhesive and quasiadhesive categories. RAIRO -
Theoretical Informatics and Applications  39 (07 2005).

[22]
Löwe, M.: Algebraic approach to single-pushout graph transformation.
Theor. Comput. Sci.  109(1&2),  181–224 (1993).

[23]
Mac Lane, S.: Categories for the working mathematician, vol. 5. Springer
Science & Business Media (1971)

[24]
Mac Lane, S., Moerdijk, I.: Sheaves in geometry and logic. Springer-Verlag, New
York (1994), a first introduction to topos theory, Corrected reprint of the
1992 edition

[25]
Mathew, S., Mordeson, J.N., Malik, D.S.: Fuzzy graph theory, vol. 363. Springer
(2018). 10.1007/978-3-319-71407-3

[26]
Mori, M., Kawahara, Y.: Fuzzy graph rewritings.
UTF8min数理解析研究所講究録  918,
65–71 (1995)

[27]
Overbeek, R., Endrullis, J.: From linear term rewriting to graph rewriting with
preservation of termination. In: Proc. Workshop on Graph Computational Models
(GCM). EPTCS, vol. 350, pp. 19–34 (2021). 10.4204/EPTCS.350.2

[28]
Overbeek, R., Endrullis, J.: A PBPO$^+$ graph rewriting tutorial. CoRR
abs/2301.12912 (2023). 10.48550/arXiv.2301.12912

[29]
Overbeek, R., Endrullis, J.: Termination of graph transformation systems using
weighted subgraph counting. CoRR  abs/2303.07812 (2023).

[30]
Overbeek, R., Endrullis, J., Rosset, A.: Graph rewriting and relabeling with
PBPO$^+$. In: ICGT (2020). 978-3-030-78946-6_4

[31]
Overbeek, R., Endrullis, J., Rosset, A.: Graph rewriting and relabeling with
PBPO$^+$: A unifying theory for quasitoposes (2022).

[32]
Pal, M., Samanta, S., Ghorai, G.: Modern trends in fuzzy graph theory. Springer
(2020). 10.1007/978-981-15-8803-7

[33]
Parasyuk, I.N., Ershov, S.V.: Transformations of fuzzy graphs specified by
FD-grammars. Cybernetics and Systems Analysis  43,  266–280
(2007). 10.1007/s10559-007-0046-6

[34]
Parasyuk, I.N., Yershov, S.V.: Categorical approach to the construction of
fuzzy graph grammars. Cybernetics and Systems Analysis  42,
570–581 (2006). 10.1007/s10559-006-0094-3

[35]
Parasyuk, I.N., Yershov, S.V.: Transformational approach to the development of
software architectures on the basis of fuzzy graph models. Cybernetics and
Systems Analysis  44,  749–759 (2008).

[36]
Plessas, D.J.: The Categories of Graphs. Ph.D. thesis, The University of
Montana (2011), <www.scholarworks.umt.edu/etd/967/>, Dissertations &
Professional Papers. 967.

[37]
Rosenfeld, A.: Fuzzy graphs. In: Fuzzy sets and their applications to cognitive
and decision processes, pp. 77–95. Elsevier (1975)

[38]
Srivastava, A.K., Tiwari, S.P.: On categories of fuzzy petri nets. Adv. Fuzzy
Sys.  2011 (jan 2011). 10.1155/2011/812040

[39]
Stout, L.N.: The logic of unbalanced subobjects in a category with two closed
structures, pp. 73–105. Springer, Dordrecht (1992).

[40]
Sugeno, M., Sasaki, M.: L-fuzzy category. Fuzzy Sets and Systems
11(1),  43–64 (1983). 10.1016/S0165-0114(83)80068-2

[41]
Syropoulos, A., Grammenos, T.: A Modern Introduction to Fuzzy Mathematics. John
Wiley & Sons (2020)

[42]
Vigna, S.: A guided tour in the topos of graphs (2003).

[43]
Wyler, O.: Lecture notes on Topoi and Quasitopoi. World Scientific (1991)

[44]
Zadeh, L.A.: Fuzzy sets. Inf. Control.  8(3),  338–353 (1965).

[1]
Adámek, J., Herrlich, H., Strecker, G.E.: Abstract and Concrete Categories
: The Joy of Cats. Wiley, New York (1990)

[2]
Awodey, S.: Category Theory. Oxford Logic Guides, Ebsco Publishing (2006)

[3]
Baez, J.C., Genovese, F., Master, J., Shulman, M.: Categories of nets. In: 36th
Annual Symposium on Logic in Computer Science. pp. 1–13. IEEE (2021).

[4]
Bauderon, M.: A uniform approach to graph rewriting: The pullback approach. In:
Graph-Theoretic Concepts in Computer Science, 21st International Workshop,
WG. LNCS, vol. 1017, pp. 101–115. Springer (1995).

[5]
Behr, N., Harmer, R., Krivine, J.: Concurrency theorems for non-linear
rewriting theories. In: Graph Transformation - 14th International Conference,
ICGT 2021. LNCS, vol. 12741, pp. 3–21. Springer (2021).

[6]
Behr, N., Harmer, R., Krivine, J.: Concurrency theorems for non-linear
rewriting theories. CoRR  abs/2105.02842 (2021),

[7]
Borceux, F.: Handbook of categorical algebra. 1, Encyclopedia of Mathematics
and its Applications, vol. 50. Cambridge University Press, Cambridge (1994),
basic category theory

[8]
Borceux, F.: Handbook of categorical algebra. 3, Encyclopedia of Mathematics
and its Applications, vol. 52. Cambridge University Press, Cambridge (1994),
categories of sheaves

[9]
Carboni, A., Johnstone, P.T.: Connected limits, familial representability and
artin glueing. Math. Struct. Comput. Sci.  5(4),  441–459 (1995).

[10]
Cardoso, J., Valette, R., Dubois, D.: Fuzzy petri nets: An overview. IFAC
Proceedings Volumes  29(1),  4866–4871 (1996).
10.1016/S1474-6670(17)58451-7, 13th World Congress of IFAC, 1996

[11]
Corradini, A., Duval, D., Echahed, R., Prost, F., Ribeiro, L.: AGREE -
algebraic graph rewriting with controlled embedding. In: Graph Transformation
- 8th International Conference, ICGT 2015. LNCS, vol. 9151, pp. 35–51.
Springer (2015). 10.1007/978-3-319-21145-9_3

[12]
Corradini, A., Duval, D., Echahed, R., Prost, F., Ribeiro, L.: The PBPO graph
transformation approach. J. Log. Algebraic Methods Program.  103,
213–231 (2019). 10.1016/j.jlamp.2018.12.003

[13]
Corradini, A., Heindel, T., Hermann, F., König, B.: Sesqui-pushout
rewriting. In: Graph Transformations, Third International Conference, ICGT
2006. LNCS, vol. 4178, pp. 30–45. Springer (2006). 10.1007/11841883_4

[14]
Ehrig, H., Pfender, M., Schneider, H.J.: Graph-grammars: An algebraic approach.
In: 14th Annual Symposium on Switching and Automata Theory. pp. 167–180.
IEEE Computer Society (1973). 10.1109/SWAT.1973.11

[15]
Garner, R., Lack, S.: On the axioms for adhesive and quasiadhesive categories.
Theory and Applications of Categories  27,  27–46 (May 2012)

[16]
Goguen, J.: $L$-fuzzy sets. Journal of Mathematical Analysis and Applications
18(1),  145–174 (1967). 10.1016/0022-247X(67)90189-8

[17]
Johnstone, P.T.: On a topological topos. Proceedings of the London Mathematical
Society  s3-38(2),  237–271 (1979). 10.1112/plms/s3-38.2.237

[18]
Johnstone, P.T.: Sketches of an elephant: a Topos theory compendium. Oxford
logic guides, Oxford Univ. Press, New York, NY (2002)

[19]
Johnstone, P.T., Lack, S., Sobocinski, P.: Quasitoposes, quasiadhesive
categories and artin glueing. In: Algebra and Coalgebra in Computer Science,
Second International Conference, CALCO 2007. Lecture Notes in Computer
Science, vol. 4624, pp. 312–326. Springer (2007).

[20]
Lack, S., Sobocinski, P.: Adhesive categories. In: Foundations of Software
Science and Computation Structures, 7th International Conference, FOSSACS
2004. LNCS, vol. 2987, pp. 273–288. Springer (2004).

[21]
Lack, S., Sobociński, P.: Adhesive and quasiadhesive categories. RAIRO -
Theoretical Informatics and Applications  39 (07 2005).

[22]
Löwe, M.: Algebraic approach to single-pushout graph transformation.
Theor. Comput. Sci.  109(1&2),  181–224 (1993).

[23]
Mac Lane, S.: Categories for the working mathematician, vol. 5. Springer
Science & Business Media (1971)

[24]
Mac Lane, S., Moerdijk, I.: Sheaves in geometry and logic. Springer-Verlag, New
York (1994), a first introduction to topos theory, Corrected reprint of the
1992 edition

[25]
Mathew, S., Mordeson, J.N., Malik, D.S.: Fuzzy graph theory, vol. 363. Springer
(2018). 10.1007/978-3-319-71407-3

[26]
Mori, M., Kawahara, Y.: Fuzzy graph rewritings.
UTF8min数理解析研究所講究録  918,
65–71 (1995)

[27]
Overbeek, R., Endrullis, J.: From linear term rewriting to graph rewriting with
preservation of termination. In: Proc. Workshop on Graph Computational Models
(GCM). EPTCS, vol. 350, pp. 19–34 (2021). 10.4204/EPTCS.350.2

[28]
Overbeek, R., Endrullis, J.: A PBPO$^+$ graph rewriting tutorial. CoRR
abs/2301.12912 (2023). 10.48550/arXiv.2301.12912

[29]
Overbeek, R., Endrullis, J.: Termination of graph transformation systems using
weighted subgraph counting. CoRR  abs/2303.07812 (2023).

[30]
Overbeek, R., Endrullis, J., Rosset, A.: Graph rewriting and relabeling with
PBPO$^+$. In: ICGT (2020). 978-3-030-78946-6_4

[31]
Overbeek, R., Endrullis, J., Rosset, A.: Graph rewriting and relabeling with
PBPO$^+$: A unifying theory for quasitoposes (2022).

[32]
Pal, M., Samanta, S., Ghorai, G.: Modern trends in fuzzy graph theory. Springer
(2020). 10.1007/978-981-15-8803-7

[33]
Parasyuk, I.N., Ershov, S.V.: Transformations of fuzzy graphs specified by
FD-grammars. Cybernetics and Systems Analysis  43,  266–280
(2007). 10.1007/s10559-007-0046-6

[34]
Parasyuk, I.N., Yershov, S.V.: Categorical approach to the construction of
fuzzy graph grammars. Cybernetics and Systems Analysis  42,
570–581 (2006). 10.1007/s10559-006-0094-3

[35]
Parasyuk, I.N., Yershov, S.V.: Transformational approach to the development of
software architectures on the basis of fuzzy graph models. Cybernetics and
Systems Analysis  44,  749–759 (2008).

[36]
Plessas, D.J.: The Categories of Graphs. Ph.D. thesis, The University of
Montana (2011), <www.scholarworks.umt.edu/etd/967/>, Dissertations &
Professional Papers. 967.

[37]
Rosenfeld, A.: Fuzzy graphs. In: Fuzzy sets and their applications to cognitive
and decision processes, pp. 77–95. Elsevier (1975)

[38]
Srivastava, A.K., Tiwari, S.P.: On categories of fuzzy petri nets. Adv. Fuzzy
Sys.  2011 (jan 2011). 10.1155/2011/812040

[39]
Stout, L.N.: The logic of unbalanced subobjects in a category with two closed
structures, pp. 73–105. Springer, Dordrecht (1992).

[40]
Sugeno, M., Sasaki, M.: L-fuzzy category. Fuzzy Sets and Systems
11(1),  43–64 (1983). 10.1016/S0165-0114(83)80068-2

[41]
Syropoulos, A., Grammenos, T.: A Modern Introduction to Fuzzy Mathematics. John
Wiley & Sons (2020)

[42]
Vigna, S.: A guided tour in the topos of graphs (2003).

[43]
Wyler, O.: Lecture notes on Topoi and Quasitopoi. World Scientific (1991)

[44]
Zadeh, L.A.: Fuzzy sets. Inf. Control.  8(3),  338–353 (1965).

§ APPENDIX

§.§ Proof of <ref>

Given $j \xrightarrow{\iota} i$ and a sieve $A \stackrel{n}{\rightarrowtail} y(i)$,

\begin{equation}
\label{eq:formula_Omega(iota)(n)=y(j)_iff   _iota_in_A(j)}
\Omega(\iota)(n) = y(j) \iff j \xrightarrow{\iota} i \in A(j).
\end{equation}

Observe first the following:

\begin{equation}
\label{eq:formula_iota_in_A(j)_iff_forall_k_iotakappa_in_A(k)}
j \xrightarrow{\iota} i \in A(j) \iff \forall k \in I, \forall k \xrightarrow{\kappa} j : \ \  k \xrightarrow{\kappa} j \xrightarrow{\iota} i \in A(k).
\end{equation}

The direction $(\Rightarrow)$ follows from the definition of $A$: as a subfunctor of $y(i)$ its effect on morphisms is precomposition.
Hence, $A(\kappa)(\iota) = \iota \circ \kappa$ needs to be in $A(k)$ for well-definedness.
Conversely, $(\Leftarrow)$ follows from taking $k=j$ and $\kappa=\id{j}$.

Name $A_0$ the pullback of $n$ along $y(\iota)=\iota \circ -$ and take $k \in I$.
Observe that the pullback is

\begin{align*}
&= \setvbar{\big(k \xrightarrow{\kappa} j, a \in A(k)\big)} {k \xrightarrow{\kappa} j \xrightarrow{\iota} i = n_k(a)} \\
&\isom \setvbar{k \xrightarrow{\kappa} j} {k \xrightarrow{\kappa} j \xrightarrow{\iota} i \in \ima(n_k) \isom A(k)}
\end{align*}

\begin{align*}
\Omega(\iota)(n) = A_0 = y(j)
&\iff \forall k \in I : \ \ A_0(k) = I(k,j) \\
&\iff \forall k \in I, \forall k \xrightarrow{\kappa} j : \ \ k \xrightarrow{\kappa} j \xrightarrow{\iota} i \in A(k) \\
j \xrightarrow{\iota} i \in A(j).
\end{align*}

* Take $\iota : j \to i$ in $I$.
We show the following commute

\[\begin{tikzcd}[ampersand replacement=\&]
{B(i)} \& {\Sub_{\PresheafHatDefault}(I(-,i))} \\
{B(j)} \& {\Sub_{\PresheafHatDefault}(I(-,j))}
\arrow["{B(\iota)}"', from=1-1, to=2-1]
\arrow["{\Sub_{\PresheafHatDefault}(y(\iota))}", from=1-2, to=2-2]
\arrow["{(\chi_A)_i}", from=1-1, to=1-2]
\arrow["{(\chi_A)_j}"', from=2-1, to=2-2]
\end{tikzcd}\]

Take $b \in B(i)$.
We are comparing presheaves $\opcat{I} \to \Set$, hence take also $k \in I$.

\begin{align*}
\Big( \Sub_{\PresheafHatDefault}(y(\iota)) \circ (\chi_A)_i \Big) (b)(k)
\Sub_{\PresheafHatDefault}(y(\iota)) \big(\setvbar{\kappa:k \to i}{B(\kappa)(b) \in m_k(A_k)}\big) \\
\{(k \xrightarrow{\rho} j, k \xrightarrow{\kappa} i) ~\vert~ B(\kappa)(b) \in m_k(A_k) \text{ and } \\
& \hspace*{11.6em}  k \xrightarrow{\rho}j \xrightarrow{\iota} i = k \xrightarrow{\kappa}i \} \\
\setvbar{\rho : k \to j}{B(\rho)\big(B(\iota)(b)\big) \in m_k(A_k)} \\
\Big( (\chi_A)_j \circ B(\iota) \Big) (b)(k)
\end{align*}

* The pullback of $\chi_A$ and $\true$ is, for $i \in I$:

\begin{align*}
&\setvbar{\big(b \in B(i), \cdot \in 1 \big)}
{(\chi_A)_i(b) = \true_i(\cdot)} \\
\setvbar{b \in B(i)}
{\forall j \in I: \ (\chi_A)_i(b)(j) = \true_i(\cdot)(j) = y(i)(j) = I(j,i)} \\
\setvbar{b \in B(i)}
{\forall j \in I: \ \setvbar{j \xrightarrow{\iota} i}{B(\iota)(b) \in A(j)} = I(j,i)} \\
\setvbar{b \in B(i)}
{\forall j \in I, \forall j \xrightarrow{\iota} i: \ B(\iota)(b) \in A(j)} \\
&= A(j).
\end{align*}

The last equality hold since: $(\supseteq)$ follows from $B(\iota)(b) = A(\iota)(b)$ when $b \in A(i)$ since $A$ is a subobject of $B$, and $(\subseteq)$ by taking $\iota = \id{i}$.

* Suppose another natural transformation $\nu : B \to \Omega$ such that the pullback of $\nu$ and $\true$ gives $A \subseteq B$ and $! : A \to 1$.
Consider the element $B(\iota)(b)$ in $B(j)$ and the condition for it to be in the subobject $A(j)$:

\begin{align*}
B(\iota)(b) \in A(j)
\nu_j\big(B(\iota)(b)\big) = \true_j(\cdot)
\tag{pullback} \\
\Omega(\iota)(\nu_i(b)) = y(j)
\tag{$\nu$ nat.~and $\true$ def.} \\
&\iff \iota \in \nu_i(b)(j).
\tag{by (\ref{eq:formula_Omega(iota)(n)=y(j)_iff   _iota_in_A(j)})}
\end{align*}

If we take back the definition of $\chi_A$, we have thus

\begin{align*}
&= \setvbar{j \xrightarrow{\iota} i}{B(\iota)(b) \in A_j}
\tag{def.~\ref{eq:def_chi_A}} \\
&\isom \setvbar{j \xrightarrow{\iota} i}{\iota \in \nu_i(b)(j)}
\tag{equivalence above} \\
&\isom \nu_i(b)(j).
\end{align*}

Hence, $\chi_A$ and $\nu$ are equal, proving the uniqueness.

§.§ Proof of <ref>

We exhibit a natural isomorphism to show the exponentiation adjunction.

((C,γ) ×(A,α), (B,β))
[r, shift left=.4em, "ϕ", ""']
((C,γ), (B,β)^(A,α) )
[l, shift left=.4em, "ψ"]

Let $\phi$ be defined as follows.

\[
\biggl(
\begin{tikzcd}[ampersand replacement=\&, row sep = 0.15em, column sep = tiny]
{C \times A} \&\& B \\
\& {\color{gray}\labels}
\arrow["h", from=1-1, to=1-3]
\arrow["{\gamma \meet \alpha}"', color=gray, from=1-1, to=2-2]
\arrow["\beta", color=gray, from=1-3, to=2-2]
\end{tikzcd}
\biggr)
\quad
\xmapsto{\phi}
\quad
\biggl(
\begin{tikzcd}[ampersand replacement=\&, row sep = 0.15em, column sep = tiny]
C \&\& \PresheafHatDefault(y(-) \times A, B) \\
\& {\color{gray}\labels}
\arrow["\phi(h)", from=1-1, to=1-3]
\arrow["\gamma"', color=gray, from=1-1, to=2-2]
\arrow["\theta", color=gray, from=1-3, to=2-2]
\end{tikzcd}
\biggr)
\]

For $i,j \in I$ and $c \in C(i)$, let $\phi(h)_i(c)_j: y(i)(j) \times A(j) \rightarrow B(j)$ be

\begin{equation}
(j \xrightarrow{\iota} i, a) \mapsto h_j( C(\iota)(c), a). \label{eq:def_phi}
\end{equation}

The natural transformation $\phi$ from <ref> is well-defined:

* $\phi$ is natural in $C$ and $B$,

* $\phi(h)_i(c)$ is natural in $j \in I$, for any $i \in I$ and $c \in C(i)$, and

* $\gamma \leq \theta \cdot \phi(h)$.

* We verify that $\phi$ is natural in $C$ and $B$.
Take $f: (C',\gamma') \to (C,\gamma)$ and $g: (B,\beta) \to (B', \beta')$.

\begin{equation}
\label{eq:f}
\begin{tikzcd}[scale cd =.8, ampersand replacement=\&]
{C'} \& {} \& C \\
\& {\color{gray}\labels}
\arrow["{\gamma'}"', color=gray, from=1-1, to=2-2]
\arrow["f", from=1-1, to=1-3]
\arrow["\gamma", color=gray, from=1-3, to=2-2]
\arrow["\leq" description, draw=none, color=gray, from=1-2, to=2-2]
\end{tikzcd}
\end{equation}

\begin{equation}
\label{eq:g}
\begin{tikzcd}[scale cd =.8, ampersand replacement=\&]
B \& {} \& {B'} \\
\& {\color{gray}\labels}
\arrow["\beta"', color=gray, from=1-1, to=2-2]
\arrow["g", from=1-1, to=1-3]
\arrow["{\beta'}", color=gray, from=1-3, to=2-2]
\arrow["\leq" description, draw=none, color=gray, from=1-2, to=2-2]
\end{tikzcd}
\end{equation}

We want to prove that the following commute:

\[\begin{tikzcd}[column sep = huge]
{\Hom \big( (C,\gamma) \times (A,\alpha),(B,\beta) \big)} & {\Hom \big( (C,\gamma), (B,\beta)^{(A,\alpha)} \big)} \\
{\Hom \big( (C',\gamma') \times (A,\alpha),(B',\beta') \big)} & {\Hom \big( (C',\gamma'), (B',\beta')^{(A,\alpha)} \big)}
\arrow["{g \circ - \circ (f \times \id{A})}"', from=1-1, to=2-1]
\arrow["{g^{(A,\alpha)} \circ - \circ f}", from=1-2, to=2-2]
\arrow["{\phi_{(C,\gamma), (B,\beta)}}", from=1-1, to=1-2]
\arrow["{\phi_{(C',\gamma'), (B',\beta')}}"', from=2-1, to=2-2]
\end{tikzcd}\]

We check it.
Take $i \in I, c' \in C'(i), j \in I, j \xrightarrow{\iota} i$ and $a \in A(j)$:

\begin{align*}
\phi \big( gh(f\times\id{A})_i (c') \big)_j (\iota, a)
&= \big( gh(f\times\id{A}) \big)_j (C'(\iota)(c'), a)
\tag{by \eqref{eq:def_phi}} \\
&= g_j h_j \big( f_j \cdot C'(\iota) (c'), a \big)
\\
&= g_j h_j \big( C(\iota)(f_i(c')), a \big)
\tag{$f$ nat.} \\
&= g_j \Big( \phi(h)_i \big(f_i(c') \big) \Big)_j (\iota, a)
\tag{by \eqref{eq:def_phi}} \\
&= \Big(  g \cdot \phi(h)_i \big( f_i(c') \big) \Big)_j (\iota, a)
\\
&= g^{(A,\alpha)}_i \Big( \phi(h)_i \big( f_i(c') \big) \Big)_j (\iota, a)
\tag{by \eqref{eq:exponent_def_morphisms}} \\
&= \big( (g^{(A,\alpha)} \cdot \phi(h) \cdot f)_i (c') \big)_j (\iota, a)
\end{align*}

* We verify that $\phi(h)_i(c)$ is natural in $j$: given $k \xrightarrow{\kappa} j$

\[\begin{tikzcd}[scale cd=.75, row sep = .5em]
{y(i)(j) \times A(j)} &&&& {B(j)} \\
& {(j \xrightarrow{\iota}i,a)} && {h_j\big(C(\iota)(c),a\big)} \\
\\
\\
&&& {B(\kappa)\Big( h_j \big(C(\iota)(c),a\big)  \Big)} \\
& {\left(k \xrightarrow{\kappa} j \xrightarrow{\iota}i, A(\kappa)(a)\right)} && {h_k \big( C(\iota\kappa)(c), A(\kappa)(a) \big)} \\
{y(i)(k) \times A(k)} &&&& {B(k)}
\arrow["{y(i)(\kappa) \times A(\kappa)}"', from=1-1, to=7-1]
\arrow["{B(\kappa)}", from=1-5, to=7-5]
\arrow["{\big(\phi(h)_i(c)\big)_k}"', from=7-1, to=7-5]
\arrow["{\big(\phi(h)_i(c)\big)_j}", from=1-1, to=1-5]
\arrow[maps to, from=2-2, to=6-2]
\arrow[maps to, from=2-2, to=2-4]
\arrow[maps to, from=2-4, to=5-4]
\arrow[maps to, from=6-2, to=6-4]
\arrow["\text{nat.~} h",equal, from=5-4, to=6-4]
\end{tikzcd}\]

* Since $h:(C\times A, \gamma \meet \alpha) \to (B,\beta)$, we have $\gamma \meet \alpha \leq \beta h$.

\begin{align*}
\forall i \in I, \forall c \in C(i), \forall a \in A(i): \gamma_i(c) \meet \alpha_i(a) \leq \beta_i h_i (c,a)
\\
\forall i \in I, \forall c \in C(i), \forall a \in A(i): \gamma_i(c) \leq \big( \alpha_i(a) \Rightarrow \beta_i h_i (c,a) \big)
\\
\forall i \in I, \forall c \in C(i), \forall a \in A(i): \gamma_i(c) \leq \big( \alpha_i(a) \Rightarrow \beta_i (\phi(h)_i(c))_i (\id{i},a) \big)
\\
\forall i \in I, \forall c \in C(i): \gamma_i(c) \leq \textstyle{\bigmeet}_{a \in A(i)} \big( \alpha_i(a) \Rightarrow \beta_i (\phi(h)_i(c))_i (\id{i},a) \big)
\\
\forall i \in I, \forall c \in C(i): \gamma_i(c) \leq \theta_i \big( \phi(h)_i(c) \big)
\\
\gamma \leq \theta \cdot \phi(h)
\qedhere
\end{align*}

Let $\psi$ be defined on $i \in I$ as follows.

\[
\biggl(
\begin{tikzcd}[ampersand replacement=\&, row sep = 0.15em, column sep = tiny]
C \&\& \PresheafHatDefault(y(-) \times A, B) \\
\& {\color{gray}\labels}
\arrow["k", from=1-1, to=1-3]
\arrow["\gamma"', color=gray, from=1-1, to=2-2]
\arrow["\theta", color=gray, from=1-3, to=2-2]
\end{tikzcd}
\biggr)
\quad
\xmapsto{\psi}
\quad
\biggl(
\begin{tikzcd}[ampersand replacement=\&, row sep = 0.15em, column sep = tiny]
{C \times A} \&\& B \\
\& {\color{gray}\labels}
\arrow["\psi(k)", from=1-1, to=1-3]
\arrow["{\gamma \meet \alpha}"', color=gray, from=1-1, to=2-2]
\arrow["\beta", color=gray, from=1-3, to=2-2]
\end{tikzcd}
\biggr)
\]

For $i \in I, c \in C(i)$ and $a \in A(i)$, let

\begin{equation}
\psi(k)_i(c, a) \defeq k_i(c)_i (\id{i},a).
\label{eq:def_psi}
\end{equation}

The natural transformation $\psi$ from <ref> is well-defined:

* $\psi$ is natural in $C$ and $B$

$\psi(k)$ is natural in $i \in I$, and

$\gamma \meet \alpha \leq \beta \cdot \psi(k)$.

* This follows from $\phi$ being natural in $C$ and $A$ and $\psi$ being the inverse of $\phi$ as proved below in <ref>.

* We verify that $\psi(k)$ is natural in $i$: given $j \xrightarrow{\iota} j$

\[\begin{tikzcd}[scale cd=.75, row sep = .5em]
{C(i) \times A(i)} &&&& {B(i)} \\
& {(c,a)} && {k_i(c)_i(\id{i},a)} \\
\\
\\
&&& {B(\iota) \big( k_i(c)_i (\id{i},a) \big)} \\
& {\big( C(\iota)(c) , A(\iota)(a) \big)} && {k_j\big( C(\iota)(c) \big)_j \big(\id{j}, A(\iota)(a) \big)} \\
{C(j) \times A(j)} &&&& {B(j)}
\arrow["{C(\iota) \times A(\iota)}"', from=1-1, to=7-1]
\arrow["{B(\iota)}", from=1-5, to=7-5]
\arrow["{\psi(k)_i}"', from=7-1, to=7-5]
\arrow["{\psi(k)_j}", from=1-1, to=1-5]
\arrow[maps to, from=2-2, to=6-2]
\arrow[maps to, from=2-2, to=2-4]
\arrow[maps to, from=2-4, to=5-4]
\arrow[maps to, from=6-2, to=6-4]
\arrow["(\ast)",equal, from=5-4, to=6-4]
\end{tikzcd}\]

where $(\ast)$ is the following reasoning:

\begin{align*}
B(\iota)\big( k_i(c)_i (\id{i},a) \big)
&= k_i(c)_j \cdot \big( y(i)(\iota) \times A(\iota) \big) (\id{i},a)
\tag{$k_i(c)$ nat.} \\
&= k_i(c)_j \big( \iota, A(\iota)(a) \big)
\tag{Def.~\ref{def:contravariant_hom_functor}} \\
&= \big( k_i(c) \cdot (y(\iota) \times \id{A}) \big)_j (\id{j}, A(\iota)(a))
\tag{Def.~\ref{def:yoneda_embedding}} \\
&= \big( \PresheafHatDefault(y(\iota) \times A,B) \cdot k_i(c) \big)_j (\id{j}, A(\iota)(a))
\tag{by \eqref{eq:exponent_def_objects_iota}} \\
&= k_j \big( C(\iota)(c) \big)_j \big(\id{j}, A(\iota)(a) \big)
\tag{$k$ nat.}
\end{align*}

* Since $k:(C,\gamma) \to ( \PresheafHatDefault(y(-) \times A,B) , \theta )$, we have $\gamma \leq \theta k$.

\begin{align*}
\forall i \in I, \forall c \in C(i): \gamma_i(c) \leq \theta_i (k_i(c))
\\
\forall i \in I, \forall c \in C(i): \gamma_i(c) \leq \textstyle{\bigmeet}_{a \in A(i)} \left( \alpha_i(a) \Rightarrow \beta_i \cdot k_i(c)_i (\id{i},a) \right)
\\
\forall i \in I, \forall c \in C(i), \forall a \in A(i): \gamma_i (c) \leq \big( \alpha_i (a) \Rightarrow \beta_i \cdot k_i(c)_i (\id{i},a) \big)
\\
\forall i \in I, \forall c \in C(i), \forall a \in A(i): \gamma_i (c) \meet \alpha_i(a) \leq \beta_i \cdot k_i(c)_i (\id{i},a)
\\
\forall i \in I, \forall c \in C(i), \forall a \in A(i): \gamma_i (c) \meet \alpha_i(a) \leq \beta_i \cdot \psi(k)_i (c,a)
\\
\gamma \meet \alpha \leq \beta \cdot \psi(k)
\qedhere
\end{align*}

Both $\phi$ and $\psi$ are inverses of each other.

We first verify that $\psi \phi = \id{}$.
Take $(C \times A, \gamma \meet \alpha) \xrightarrow{h} (B,\beta)$.
For $i \in I, c \in C(i)$ and $a \in A(i)$, we have

\begin{align*}
\psi(\phi(h))_i (c,a)
&= \big( \phi(h)_i(c) \big)_i (\id{i},a)
\tag{by \eqref{eq:def_psi}} \\
&= h_i \big( C(\id{i})(c) , a \big)
\tag{by \eqref{eq:def_phi}} \\
&= h_i (c,a)
\end{align*}

We now verify that $\phi \psi = \id{}$.
Take $(C,\gamma) \xrightarrow{k} (\PresheafHatDefault(y(-) \times A, B) , \theta)$.
For $i \in I, c \in C(i), j \in I, j \xrightarrow{\iota} i$ and $a \in A(j)$, we have

\begin{align*}
\big( \phi(\psi(k))_i (c) \big)_j (\iota,a)
&= \psi(k)_j \big( C(\iota)(c) , a \big)
\tag{by \eqref{eq:def_phi}} \\
&= k_j \big( C(\iota)(c) \big)_j (\id{j}, a)
\tag{by \eqref{eq:def_psi}} \\
&= \big( k_j \cdot C(\iota) (c) \big)_j (\id{j}, a)
\\
&= \big( \PresheafHatDefault( y(\iota) \times A , B ) \cdot k_i (c) \big)_j (\id{j}, a)
\tag{$k$ nat.} \\
&= \big( k_i(c) \cdot (y(\iota) \times \id{A}) \big)_j (\id{j}, a)
\tag{by \eqref{eq:exponent_def_objects_iota}} \\
&= k_i (c)_j \cdot (y(\iota) \times \id{A})_j (\id{j},a)
\\
&= k_i (c)_j (\iota, a)
\tag{Def.~\ref{def:contravariant_hom_functor}}
\end{align*}

§.§ Proof of <ref>

To prove <ref>, we construct a functor in each direction and then prove that they are quasi-inverses.

We define the mapping

\[
\to
\FuzzyPresheaf{\elements{D}}{\tilde{\labels}}
\]

by $F(A,\alpha,p) \defeq (\tilde{A},\tilde{\alpha})$, where $\tilde{A}(i,d) \defeq p_i\inv(d)$,

\begin{align}
\tilde{A} \big(\iota: (j,e) \to (i,d) \big)
\defeq
A(\iota)\restrict{p_i\inv(d)} : p_i\inv(d) &\to p_j\inv(e),
\nonumber \\
\tilde{\alpha}_{(i,d)}
\defeq
\alpha_i\restrict{p_i\inv(d)} : p_i \inv(d) &\to \labels(i)_{\leq \delta_i(d)},
\label{eq:def_tilde_alpha}
\intertext{and $F(f:(A,\alpha,p) \to (B,\beta,q)) \defeq \tilde{f} : (\tilde{A},\tilde{\alpha}) \to (\tilde{B},\tilde{\beta})$, where}
\tilde{f}_{(i,d)} \defeq f_i\restrict{p_i\inv(d)} : p_i \inv(d) &\to q_i \inv(d).
\label{eq:def_tilde_f}
\end{align}

$F$ is a well-defined functor.

Take $i \in I, d \in D(i)$ and $a \in p_i \inv (d)$.
For $\tilde{f}_{(i,d)}$ to be well-defined, we first verify that

\begin{equation} \label{eq:f_i_sends_preimage_on_preimage}
f_i(p_i \inv(d)) \subseteq q_i \inv (d).
\end{equation}

This holds since

\begin{align*}
a \in p_i \inv (d)
p_i (a) = d \\
q_i f_i (a) = d
\tag{$p=qf$}\\
f_i(a) \in q_i \inv (d).
\end{align*}

Second, the naturality of $\tilde{f}$ result from the naturality of $f$, since the restrictions do not change anything.
We also check that $\tilde{\alpha} \leq \tilde{\beta} \tilde{f}$:

\begin{align*}
\tilde{\alpha}_{(i,d)} (a)
&= \alpha_i \restrict{\scaleto{p_i^{-1}  (d)}{8pt}} (a)
\tag{def.~$\tilde{\alpha}$ \eqref{eq:def_tilde_alpha}} \\
&\leq (\beta f)_i \restrict{\scaleto{p_i \inv (d)}{8pt}} (a)
\tag{def.~$f$} \\
&= \beta_i \restrict{\scaleto{q_i \inv (d)}{8pt}} f_i \restrict{\scaleto{p_i \inv (d)}{8pt}} (a)
\tag{by \eqref{eq:f_i_sends_preimage_on_preimage}} \\
&= \tilde{\beta}_{(i,d)} \tilde{f}_{(i,d)} (a).
\tag{defs.~$\tilde{\beta}$ \eqref{eq:def_tilde_alpha} and $\tilde{f}$ \eqref{eq:def_tilde_f}}
\end{align*}

Lastly, the functoriality of $F$ is clear from its definition, and the proof is complete.

We define the mapping

\[
\FuzzyPresheaf{\elements{D}}{\tilde{\labels}}
\to
\quot{\FuzzyPresheafDefault}{(D,\delta)}
\]

by $G(\tilde{A}, \tilde{\alpha}) \defeq (A,\alpha, p)$, where $A(i) \defeq \smash{\bigsqcup_{d \in D(i)}} \tilde{A}(i,d)$,

\[
A(\iota : j \to i) \defeq D(\iota) \times \tilde{A}(\iota) : \bigsqcup_{d \in D(i)} \tilde{A}(i,d) \to \bigsqcup_{e \in D(j)} \tilde{A}(j,e)
\]

\begin{equation}
\begin{tikzcd}[row sep = tiny, ampersand replacement=\&]
{A(i) = \bigsqcup_{d \in D(i)} \tilde{A}(i,d)}
\ar[rd, color=gray, "{ \alpha_i \defeq (d,\tilde{a}) \mapsto \tilde{\alpha}_{(i,d)} (\tilde{a})}"']
\ar[rr, "p_i \defeq \pi_1"]
\& \& D(i)
\ar[dl, color=gray, "\delta_i"]
\\
\& {\color{gray}\labels(i)} \&
\end{tikzcd}
\label{eq:def_alpha_p} %\\
\end{equation}

and $G(\tilde{f}) \defeq f$, where

\begin{equation}
f_i :
{\displaystyle \bigsqcup_{d \in D(i)} \tilde{A}(i,d)}
\to
{\displaystyle \bigsqcup_{d \in D(i)} \tilde{B}(i,d)}
(d , \tilde{a})
\mapsto
(d, \tilde{f}_{(i,d)}(\tilde{a})).
\label{eq:def_f}
\end{equation}

$G$ is a well-defined functor.

We first check that $p$ is natural in $i \in I$:

[column sep=large]
[r, mapsto, "D(ι) ×Ã(ι)"]
[d, mapsto, "p_i = π_1"']
( D(ι)(d), Ã(ι)(ã) )
[d, mapsto, "p_j = π_1"]

[r, mapsto, "D(ι)"']

We then check that $\alpha \leq \delta p$.
Take $i \in I$ and $(d,\tilde{a}) \in A(i)$.

\[
\alpha_i(d,\tilde{a}) \stackrel{\text{Def.~}\ref{def:G}}{=} \tilde{\alpha}_{(i,d)} (\tilde{a}) \in \tilde{\labels}(i,d) = \labels(i)_{\leq \delta_i(d)},
\]

it follows that, $\alpha_i(d,\tilde{a}) \leq \delta_i(d) = \delta_i p_i (d, \tilde{a})$, as desired.
Moreover, $p = qf$ holds immediately from the definition.
We also check that $\alpha \leq \beta f$: for $i \in I$ and $(d, \tilde{a}) \in A(i)$ we have

\begin{align*}
\alpha_i (d, \tilde{a})
&= \tilde{\alpha}_{(i,d)} (\tilde{a})
\tag{def.~$\alpha$ \eqref{eq:def_alpha_p}} \\
&\leq \tilde{\beta}_{(i,d)} \big( \tilde{f}_{(i,d)} (\tilde{a}) \big)
\tag{def.~$\tilde{f}$} \\
&= \beta_i \big(d, \tilde{f}_{(i,d)} (\tilde{a}) \big)
\tag{def.~$\beta$ \eqref{eq:def_alpha_p}} \\
&= \beta_i f_i (d, \tilde{a}).
\tag{def.~$f$ \eqref{eq:def_f}}
\end{align*}

Lastly, the functoriality of $G$ is clear from its definition, and the proof is complete.

$F$ and $G$ from <ref> are quasi-inverses.

We want to construct two natural isomorphisms.

* The first one is $\sigma : GF \xlongrightarrow{\isom} \id{ \nicefrac{\scriptstyle \FuzzyPresheafDefault}{\scriptstyle (D,\delta)}}$.
Given $(A,\alpha,p)$, let $(\tilde{A},\tilde{\alpha}) \defeq F(A,\alpha)$ and $(A', \alpha', p') \defeq G(\tilde{A}, \tilde{\alpha})$.
For $i \in I$, let $\sigma_{(A,\alpha,p),i}$ and $\sigma_{(A,\alpha,p),i}\inv$ be the partitioning and de-partitioning of $A(i)$:

\begin{align*}
A'(i) = \bigsqcup_{d \in D(i)} p_i \inv (d)
\qquad &\stackrel[\mathclap{\sigma_{(A,\alpha,p),i} \inv}]{\mathclap{\sigma_{(A,\alpha,p),i}}}{\rightleftarrows} \qquad
A(i), \\
(d,a) \qquad &\mapsto \qquad a, \\
(p_i(a), a) \qquad &\mapsfrom \qquad a.
\end{align*}

Observe that indeed $p' = p  \sigma_{(A,\alpha,p)}$: for $i \in I$ and $(d \in D(i), a \in p_i \inv (d))$, we have

\[
p_i ( \sigma_{(A,\alpha,p),i} (d,a)) = p_i (a) = d = \pi (d,a) = p_i' (d,a).
\]

We also have $\alpha' \leq \alpha \sigma_{(A,\alpha,p)}$, as we even have equality: for $i \in I$ and $(d \in D(i), a \in p_i \inv (d))$, we have:

\[
\alpha'_i (d,a) = \alpha_i (a) = \alpha_i \sigma_{(A,\alpha,p),i}(d,a).
\]

We have $\sigma$ natural in $(A,\alpha,p)$: given $f:(A,\alpha,p) \to (B,\beta,q)$

\[
\begin{tikzcd}
{GF(A,\alpha,p)} & {(A,\alpha,p)} \\
{GF(B,\beta,q)} & {(B,\beta,q)}
\arrow["{GF(f)}"', from=1-1, to=2-1]
\arrow["f", from=1-2, to=2-2]
\arrow["{\sigma_{(A,\alpha,p)}}", from=1-1, to=1-2]
\arrow["{\sigma_{(B,\beta,q)}}"', from=2-1, to=2-2]
\end{tikzcd}
\quad
\stackrel[\text{with $i$}]{\text{instantiated}}{\Rightarrow}
\quad
\begin{tikzcd}
{\bigsqcup_{d \in D(i)} p_i\inv(d)} & {A(i)} \\
{\bigsqcup_{d \in D(i)} q_i\inv(d)} & {B(i)}
\arrow["{\bigsqcup_{d \in D(i)} \inl_d f_i}"', from=1-1, to=2-1]
\arrow["{f_i}", from=1-2, to=2-2]
\arrow["{\pi_2}", from=1-1, to=1-2]
\arrow["{\pi_2}"', from=2-1, to=2-2]
\arrow["\circlearrowleft", phantom, from=1-1, to=2-2]
\end{tikzcd}
\]

and $\sigma_{(A,\alpha,p)}$ natural in $i$: given $j \iota i$

\[\begin{tikzcd}
{\bigsqcup_{d \in D(i)} p_i\inv(d)} & {A(i)} \\
{\bigsqcup_{e \in D(j)} p_j\inv(e)} & {A(j)}
\arrow["{D(\iota) \times A(\iota)}"', from=1-1, to=2-1]
\arrow["{A(\iota)}", from=1-2, to=2-2]
\arrow["{\pi_2}", from=1-1, to=1-2]
\arrow["{\pi_2}"', from=2-1, to=2-2]
\arrow["\circlearrowleft", phantom, from=1-1, to=2-2]
\end{tikzcd}\]

* The second one is $\tau : FG \xlongrightarrow{\isom} \id{(\Presheaf{\elements{D}}, \tilde{\labels})}$.
Given $(\tilde{A},\tilde{\alpha})$, let $(A,\alpha,p) \defeq G(\tilde{A},\tilde{\alpha})$ and $(\tilde{A}', \tilde{\alpha}')$.
For $(i,d) \in \opcat{\elements{D}}$:

\begin{align*}
(\tilde{A}', \tilde{\alpha}') (i,d)
&=  \Big( p_i\inv(d) \xrightarrow{\alpha_i} \labels(i)_{\leq \delta_i(d)} \Big)
\tag{def.~$F$} \\
%&= \setvbar{(e,\tilde{a}) \in \bigsqcup_{e \in D(i)} \tilde{A}(i,e)}{p_i(e,\tilde{a}) = \pi_1 (e,\tilde{a}) = d} \xrightarrow{(e,\tilde{a}) \mapsto \tilde{\alpha}_{(i,e)} (\tilde{a})} \tilde{\labels}(i,d)
% \tag{def.~$G$}\\
&= \Big( \set{d} \times \tilde{A}(i,d) \xrightarrow{\tilde{\alpha}_{(i,d)} \cdot \pi_2} \tilde{\labels(i,d)} \Big)
\tag{def.~$G$}
\end{align*}

So let

\[
\begin{tikzcd}[column sep = large]
\set{d} \times \tilde{A}(i,d)
&& \tilde{A}(i,d) \\
& {\color{gray}\tilde{\labels}(i,d)}
\arrow["\tau_{ (\tilde{A}, \tilde{\alpha}), (i,d) } \defeq \pi_2", shift left, from=1-1, to=1-3]
\arrow["\tau_{ (\tilde{A}, \tilde{\alpha}), (i,d) }\inv \defeq \set{d} \times \id{ \tilde{A}(i,d) }", shift left, from=1-3, to=1-1]
\arrow["\tilde{\alpha}_{(i,d)} \cdot \pi_2"', color=gray, from=1-1, to=2-2]
\arrow["\tilde{\alpha}_{(i,d)}", color=gray, from=1-3, to=2-2]
\end{tikzcd}
\]

We have $\tau$ natural in $(\tilde{A}, \tilde{\alpha}):$ given $\tilde{f} : (\tilde{A}, \tilde{\alpha}) \to (\tilde{B}, \tilde{\beta})$

\[
\begin{tikzcd}
{FG(\tilde{A},\tilde{\alpha})} & {(\tilde{A},\tilde{\alpha})} \\
{FG(\tilde{B},\tilde{\beta})} & {(\tilde{B},\tilde{\beta})}
\arrow["{FG(\tilde{f})}"', from=1-1, to=2-1]
\arrow["\tilde{f}", from=1-2, to=2-2]
\arrow["{\tau_{(\tilde{A},\tilde{\alpha})}}", from=1-1, to=1-2]
\arrow["{\tau_{(\tilde{B},\tilde{\beta})}}"', from=2-1, to=2-2]
\end{tikzcd}
\quad
\stackrel[\text{with $(i,d)$}]{\text{instantiated}}{\Rightarrow}
\quad
\begin{tikzcd}
{\set{d} \times \tilde{A}(i,d)} & {\tilde{A}(i,d)} \\
{\set{d} \times \tilde{B}(i,d)} & {\tilde{B}(i,d)}
\arrow["{\id{\set{d}} \times \tilde{f}_{(i,d)}}"', from=1-1, to=2-1]
\arrow["{\tilde{f}_{(i,d)}}", from=1-2, to=2-2]
\arrow["{\pi_2}", from=1-1, to=1-2]
\arrow["{\pi_2}"', from=2-1, to=2-2]
\arrow["\circlearrowleft", phantom, from=1-1, to=2-2]
\end{tikzcd}
\]

and $\tau_{(\tilde{A},\tilde{\alpha})}$ natural in $(i,d)$: given $(j,e) \xrightarrow{\iota} (i,d)$

\[\begin{tikzcd}
{\set{d} \times \tilde{A}(i,d)} & {\tilde{A}(i,d)} \\
{\set{e} \times \tilde{A}(j,e)} & {\tilde{A}(j,e)}
\arrow["{D(\iota) \times \tilde{A}(\iota)}"', from=1-1, to=2-1]
\arrow["{\tilde{A}(\iota)}", from=1-2, to=2-2]
\arrow["{\pi_2}", from=1-1, to=1-2]
\arrow["{\pi_2}"', from=2-1, to=2-2]
\arrow["\circlearrowleft", phantom, from=1-1, to=2-2]
\end{tikzcd}\]

§.§ Proof of <ref>

We do the reasoning for each category.

* In $\Set$, given a set $A$ the morphism from the initial object $0_A : \emptyset \mono A$ is the empty function.
It factors as $\overline{0_A} \cdot e: \emptyset \epimono \emptyset \regmono A$, hence $\overline{0_A}$ is still the empty function $\emptyset$.
Using the formula for exponential objects in the slice category $\Set/A$ <cit.>, we have for $m : A_0 \mono A$:

\begin{align*}
\lnot m
&= (\emptyset: \emptyset \mono A)^{(m : A_0 \mono A)}
\tag{def.~$\lnot$} \\
&= \pi_1 : \setvbar{(a,h)}{a \in A, h : m\inv(a) \to \emptyset\inv(a)} \mono A
\tag{formula} \\
&= \inclusion : \setvbar{a \in A}{m \inv (a) = \emptyset} \mono A.
\tag{$h$ must be $\emptyset$}
\end{align*}

When $A_0 \subseteq A$, then $\lnot A_0 = \set{a \notin A} = A \setminus A_0$, as desired.

* In $\FuzzySetDefault$, the initial object is $(\emptyset, \emptyset \xrightarrow{\emptyset} \mathcal{L})$.
Given a fuzzy set $(A,\alpha)$, the factorisation of the morphism $0_A$ from the initial object does not change anything, as in $\Set$, and thus $0_A = \overline{0_A} = (\emptyset, \emptyset) \mono (A, \alpha)$.
By definition,

\[
\lnot \big((A_0,\alpha_0) \stackrel{m}{\mono} (A,\alpha) \big) = \big( (\emptyset,\emptyset) \stackrel{\emptyset}{\mono} (A,\alpha) \big)^{\big((A_0,\alpha_0) \stackrel{m}{\mono} (A,\alpha)\big)}.
\]

Using the formula for exponential objects in the slice category $\FuzzySetDefault/(A,\alpha)$ <cit.>, we obtain the same carrier set as in $\Set$, and the membership function is

\begin{align*}
\xi(a,h) &= \alpha(a) \meet \textstyle{\bigmeet_{a' \in m\inv(a)} \big(\alpha(a') \Rightarrow \emptyset h (a') \big)}
\tag{formula} \\
&= \alpha(a) \meet \top
\tag{big meet is empty, so by convention is $\top$} \\
&= \alpha(a).
\end{align*}

\[
\begin{tikzcd}
\setvbar{(a,h)}{h : m\inv(a) \to \emptyset\inv(a)} & & A \\
& \labels
\ar[from=1-1, to=1-3, "\pi_1"]
\ar[from=1-1, to=2-2, "\xi"']
\ar[from=1-3, to=2-2, "\alpha"]
\end{tikzcd}
\]

We can simplify the carrier set, as in $\Set$.
When $A_0 \subseteq A$, we obtain thus $\lnot (A_0,\alpha_0) = (A \setminus A_0, \alpha)$, as desired.

* In $\Graph$, given a graph $A$, we similarly have $0_A = \overline{0_A} = \emptyset \mono A$.
Take $m : A_0 \mono A$.
We have

\begin{align*}
\lnot m
&= (\emptyset \stackrel{\emptyset}{\mono} A)^{(A_0 \stackrel{m}{\mono} A)}
\tag{def.~$\lnot$} \\
\begin{cases}
\text{vertex set:} \setvbar{(v,h)}{v \in A(V), h:\set{\cdot} \times m\inv(v) \to \emptyset\inv(v)}  \\
\text{edge set:} \setvbar{(e,k)}{e \in A(E), k:\set{\cdot \to \cdot} \times m\inv(e) \to \emptyset\inv(e)}
\end{cases}
\stackrel{\inclusion}{\mono} A
\tag{formula} \\
\begin{cases}
\text{vertex set:} \setvbar{v \in A(V)}{m\inv(v) = \emptyset} \\
\text{edge set:} \setvbar{e \in A(E)}{m\inv(e) = \emptyset}
\end{cases}
\stackrel{\inclusion}{\mono} A
\tag{simplifying}
\end{align*}

Notice that this gives the largest subgraph of $A$ totally disconnected from $A_0$.
Indeed, consider $A_0 \subseteq A$ for simplification.
Then $m \inv(v) = \emptyset \iff \set{v} \cap A_0 = \emptyset$, i.e., $v \notin A_0(V)$.
However, $m \inv(e) \neq \emptyset \iff \set{e} \cap A_0 = \emptyset$, does not mean that $e \notin A_0$.
Its source or target can be in $A_0$ and thus in the intersection.

\[
\lnot \lnot m =
\begin{cases}
\text{vertex set:} \setvbar{v \in A(V)}{m\inv(v) \neq \emptyset} \\
\text{edge set:} \setvbar{e \in A(E)}{m\inv(e) \neq \emptyset} \ \
\end{cases}
\stackrel{\inclusion}{\mono} A,
\]

is the subgraph $A_0$ where all edges with source and target in $A_0$ are added.

* In $\FuzzyGraph$, given $(A_0,\alpha_0) \subseteq (A,\alpha)$, the $\lnot \lnot$ operation is a combination of both previous cases.
On the underlying subgraph $A_0$, it gives the largest subgraph of $A$ totally disconnected from $A_0$.
On the membership function, it replaces it with the one $\alpha$ of the main object.

The reasoning is the same as in <ref>.
One might think that that the membership functions is problematic, for instance because of situations like that:

\[
\begin{tikzcd}[ampersand replacement=\&, sep=small]
\set{\cdot^{0.2}} \& \\
\set{\cdot^{0.6}} \& \set{\cdot^{0.4}}
\ar[from=1-1, to=2-1, tail]
\ar[from=1-1, to=2-2]
\ar[from=2-1, to=2-2, dotted, "\nexists"']
\end{tikzcd}
\]

However, the definition of separated elements in <ref> says that for all dense subobjects $B_0 \mono B$, there must exist at most one factorisation.
Hence, it is always possible to consider the case where the membership values in $B_0$ and $B$ are the same, making it the same situation as <ref>, and hence the same reasoning.