Try   HackMD

Presenting Functors by Operations and Equations

(draft)

The main theorem is that a functor on a variety (in the sense of universal algebra) has a presentation by operations and equations if and only if the functor preserves sifted colimits.

The theory of sifted colimits is well explained in Adamek-Rosicky-Vitale. We only cover some highlights.

In all of the following

A is a variety in the sense of univeral algebra, that is, a category of algebras specified (finitary) operations equations. (We will assume all operations to be finitary in the following, even if we drop the qualifier.)

Sifted Colimits

Filtered categories are precisely categories

D such that colimits over
D
commute with finite limits in Set. There is also a characterization of filtered categories independent of sets – a category
D
is filtered if and only if the diagonal functor
DDI
is final for each finite category
I
.

Sifted categories are the categories

D such that colimits over
D
commute with finite products. These categories are characterized by the property that the diagonal functor
DD×D
is final.

Facts:

  • Every filtered colimit is sifted.
  • Reflexive coequalisers are sifted but not filtered.
  • Sifted colimit preserving functors preserve filtered colimits.

An object

A of a category
C
is finitely presentable if its hom-functor
hom(A,):CSet
preserves filtered colimits. A category
C
is locally finitely presentable (lfp) if it is cocomplete and has a set
X
of finitely presentable objects such that each object of
C
is a filtered colimit of objects from
X
.

An object

A is strongly finitely presentable if its hom-functor
hom(A,):CSet
preserves sifted colimits. A category
C
is strongly locally finitely presentable (slfp) if it is cocomplete and has a set
X
of strongly finitely presentable objects such that each object of
C
is a sifted colimit of objects from
X
.

Let

A be a variety in the sense of universal algebra.

Facts:

  • Finitely presentable objects in
    A
    are algebras finitely presentable in a usual sense.
  • Strongly finitely presentable algebra = retract of finitely generated free algebra.
  • Finitely presentable algebra = reflexive coequalizer of strongly finitely presentable ones.
  • Sifted colimit preserving functors on
    A
    are determined by their action on finitely generated free algebras.

Let

Alg(L) be the categories of algebras for the functor
L:AA
.

Theorem: If

A is a variety and
L:AA
preserves sifted colimits then
Alg(L)
is a variety.

Proposition:

  • Let
    A
    be a variety such that every finitely presentable algebra is projective. Then any functor
    L:AA
    preserving filtered colimits preserves sifted colimits.
  • If
    T:SetSet
    preserves filtered colimits then
    T
    preserves sifted colimits.
  • For any filtered colimit preserving functor
    L:BABA
    there is a sifted colimit preserving functor
    L:BABA
    such that
    L
    and
    L
    are isomorphic when restricted to the full subcategory of BA without
    1
    . Moreover,
    Alg(L)=Alg(L)
    .

Presenting Functors on Varieties

Introduction

Given an adjunction

LR:CX such that the right-adjoint
R
is monadic (or of descent type) all objects
AC
have a presentation "by generators and relations"
LRLRALRAA.

In words,

A is the quotient of the free algebra
LRA
over generators
RA
by equations in
LRLRA
.

We apply this "monadic presentation" now to the situation where

A is an endofunctor. In fact, we apply it twice and combine two representations:

Step 1: We represent a sifted colimit preserving endofunctor on a variety

A such that the "generators" and "relations" are given by sifted colimit preserving endofunctors on Set.

Step 2: We represent a sifted colimit on Set as the quotient of polynomial functor.

Preliminaries

Let

S(C) be the category of sifted colimit preserving functors
CC
.

Fact: The category

S(C) is slfp if
C
is.

A functor

H:AB between slfp categories is called algebraically exact provided that it preserves limits and sifted colimits.

Fact: If

H is algebraically exact it has a left adjoint.

Step 1

Let

U:ASet be a variety and
FU
. Define
Ψ:S(A)S(Set)

via

ΨL=ULF and
Φ:S(Set)S(A)

via

ΦT=FTU.

Fact:

Ψ is algebraically exact and
ΦΨ
.

After the first step, we obtain a quotient

FULFUL. Here,
FULFU
results from applying the free construction
Φ=FU
to the Set-functor
ULF
. What we need next is a presentation by operations and equations of
ULF
.

Step 2

Every sifted colimit preserving on

Set (=filtered colimit preserving functor=finitary functor) can be presented as the quotient of a polynomial functor.

Indeed, if

T:SetSet is finitary then we have a natural transformation
nNTn×XnqXTX(σ,v)  T(v)(σ)

with each

qX being surjective (even for infinite sets
X
).

Note that

v can be seen both as a tuple
(x1,xn)
and as a function
nX
. Hence we can evaluate the term
σ(x1,xn)
by applying
Tv:TnTX
to
σ
.

This gives us a representation of

T as a functor by operations and equations where the set of
n
-ary operations is
Tn
and the set of equations in
n
variables is the kernel of
qn
.

The Presentation

Theorem: A functor on a variety has a presentation by operations and equations iff the functor preserves sifted colimits.

To prove "if", one shows that every sifted colimit preserving functor

L on a variety is a quotient
FGUAqALA

where

GX=nNULFn×Xn.

  • The
    n
    -ary modal operators
    σ
    are the elements of
    ULFn
    .
  • qA
    maps
    (σ,v:nUA)
    to
    L(v)(σ)
    where
    v:FnA
    is the adjoint transpose of
    v
    .[1]
  • The equations in
    n
    variables are the kernel of
    qFn
    .

In particular the

(σ,v:nUA) are modal formulas
Δ(a1,an)

where

Δ=σ and
ai=v(i)
.

The set

Σ of operations and the set
E
of equations constitute the presentation
ΣL,EL
of
L
.

Theorem: Let

AAlg(ΣA,EA) be a variety and
ΣL,EL
a presentation of
L:AA
. Then
Alg(ΣA+ΣL,EA+EL)
is isomorphic to Alg(L), where equations in
EA
and
EL
are understood as equations over
ΣA+ΣL
.

Example: The variety of modal algebras is presented by the operations and equations of Boolean algebra plus a unary operation

and two equations specifying that
preserves finite meets.

References

Kurz-Rosicky: Strongly Complete Logics for Coalgebras, 2012.


  1. Note that

    (σ,v:nUA) is a modal formula
    Δ(a1,an)
    where
    Δ=σ
    and
    ai=v(i)
    . ↩︎