Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: The free category with finite limits on a set

fosco (Jan 11 2023 at 12:58):

Let $S$ be a set, regarded as discrete category.

Is there any hope to describe explicitly the free category with finite limits on $S$? Other than when $S$ is a singleton (it's the opposite of finite sets and functions), I can't see how.

Spencer Breiner (Jan 11 2023 at 13:07):

Shouldn't this just be a sum of copies of $\bf Set^{op}$? Building the free finite-limit category ought to be a left adjoint, hence preserve the coproduct.

Spencer Breiner (Jan 11 2023 at 13:09):

Sum in finite-limit categories (e.g., shared terminal object).

Reid Barton (Jan 11 2023 at 13:10):

It should be the opposite of (finite sets equipped with a map to S).

Reid Barton (Jan 11 2023 at 13:11):

If S is finite then it's also the opposite of (S-indexed families of finite sets).

Nathanael Arkor (Jan 11 2023 at 13:14):

To put it another way, the free finite limit completion of a discrete category is the free finite product completion of a discrete category, because there are no nontrivial nondiscrete limits in a discrete category.

fosco (Jan 11 2023 at 13:25):

Mmh, I find both arguments convincing, but somehow I'm having trouble proving the universal property..

fosco (Jan 11 2023 at 14:20):

I really want to believe your conjecture but I can't figure out how to make it precise: let $F : S \to {\cal A}$ be a functor, i.e. a $S$-family of objects of a category with finite limits.

Now, there is an obvious unit map $S\to (Fin/S)^{op}$ sending $s$ to $s:\{*\}\to S$.

fosco (Jan 11 2023 at 14:23):

Trying to extend $F$ to a $\bar F$ along the above candidate unit,

1. On one side, in order for $\bar F$ to act like $F$ on objects of the form $s : \{*\}\to S$, one would like to define $\bar F (A\to S)=\prod_{\{s\mid A_s\ne\emptyset\}}Fs$
2. On the other hand, this functor is clearly not product preserving (it doesn't preserve the terminal object, i.e. the identity of $S$ --I am thinking $S$ finite)

Reid Barton (Jan 11 2023 at 14:25):

The terminal object is the empty set mapping to S.

fosco (Jan 11 2023 at 14:26):

ah but the domain is the opposite of $(Fin/S)$. Then the terminal object is not 1_S

fosco (Jan 11 2023 at 14:26):

indeed, indeed

Reid Barton (Jan 11 2023 at 14:26):

Probably easier to just replace limits by colimits throughout

fosco (Jan 11 2023 at 14:44):

Ok now I am convinced!

John Baez (Jan 11 2023 at 15:11):

Spencer Breiner said:

Shouldn't this just be a sum of copies of $\mathsf {Set^{op}}$? Building the free finite-limit category ought to be a left adjoint, hence preserve the coproduct.

By the way, this is the free category with all small limits on a set. The free category with finite limits on a set $S$ should be a sum of $S$ copies of $\mathsf {FinSet^{op}}$, I believe.

John Baez (Jan 11 2023 at 15:18):

But this should be $(\mathsf{FinSet}/S)^{\mathsf{op}}$, as Reid said - that's a bit more concrete.

John Baez (Jan 11 2023 at 15:20):

And as Nathaniel pointed out, this is also the free category with finite products on $S$.

John Baez (Jan 11 2023 at 15:21):

(I'm just trying to put all this nice stuff in one place.)

fosco (Jan 11 2023 at 21:21):

Now that I think about it, why the extension of $F$ preserves products? Given a coproduct in $Fin/S$, i.e. the map $A\sqcup B\to S$, why is $\bar F\left[\begin{smallmatrix}A\sqcup B \\\downarrow\\ S\end{smallmatrix}\right]\cong F\left[\begin{smallmatrix}A \\\downarrow\\ S\end{smallmatrix}\right]\times\bar F\left[\begin{smallmatrix} B \\\downarrow\\ S\end{smallmatrix}\right]$, if $\bar F$ sends $a : A\to S$ to the product $\prod_{s\in im(a)} Fs$?

John Baez (Jan 11 2023 at 22:34):

There's a funny mix of products and coproducts in your question. I find it easier to work only with coproducts until the very last minute.

I claim the free category with finite colimits on a set $S$ is $\mathsf{FinSet}/S$. Given a functor $F: S \to \mathsf{A}$ where $A$ has finite colimits we want to extend $F$ to a finite-colimit-preserving functor $\overline{F} : \mathsf{FinSet}/S \to \mathsf{A}$.

Here's how $\overline{F}$ works: it sends $f: A \to S$ to

$\sum_{x \in A} F(f(x))$

The coproduct in $\mathsf{FinSet}/S$ of $f: A \to S$ and $g: B \to S$ is $\langle f, g \rangle: A \sqcup B \to S$. Here $\langle f, g \rangle$ is my notation for the map that equals $f$ on $A$ and $g$ on $B$.

So, $\overline{F}$ sends the coproduct of $f: A \to S$ and $g: B \to S$ to

$\sum_{x \in A \sqcup B} F(\langle f, g \rangle (x)) = \sum_{x \in A } F(f(x)) + \sum_{x \in B} F(g(x))$

So $\overline{F}$ preserves binary coproducts.

John Baez (Jan 11 2023 at 22:36):

Once we finish showing that $\mathsf{FinSet}/S$ is the free category with finite colimits on $S$, we can instantly conclude that $(\mathsf{FinSet}/S)^{\text{op}}$ is the free category with finite limits on $S$.

Tom Hirschowitz (Jan 12 2023 at 10:33):

Spencer Breiner said:

Shouldn't this just be a sum of copies of $\bf Set^{op}$? Building the free finite-limit category ought to be a left adjoint, hence preserve the coproduct.

Right, but the left adjoint goes to categories with finite limits, hence the free finite-limit category on $S$ should be a coproduct of $S$ copies of $\mathbf{Set}^{\mathit{op}}$ in the (large) category of finite-limit categories. And this coproduct is not preserved by the forgetful functor to $\mathbf{CAT}$, is it?

fosco (Jan 12 2023 at 11:19):

John Baez said:

There's a funny mix of products and coproducts in your question. I find it easier to work only with coproducts until the very last minute.

I claim the free category with finite colimits on a set $S$ is $\mathsf{FinSet}/S$. Given a functor $F: S \to \mathsf{A}$ where $A$ has finite colimits we want to extend $F$ to a finite-colimit-preserving functor $\overline{F} : \mathsf{FinSet}/S \to \mathsf{A}$.

Here's how $\overline{F}$ works: it sends $f: A \to S$ to

$\sum_{x \in A} F(f(x))$

The coproduct in $\mathsf{FinSet}/S$ of $f: A \to S$ and $g: B \to S$ is $\langle f, g \rangle: A \sqcup B \to S$. Here $\langle f, g \rangle$ is my notation for the map that equals $f$ on $A$ and $g$ on $B$.

So, $\overline{F}$ sends the coproduct of $f: A \to S$ and $g: B \to S$ to

$\sum_{x \in A \sqcup B} F(\langle f, g \rangle (x)) = \sum_{x \in A } F(f(x)) + \sum_{x \in B} F(g(x))$

So $\overline{F}$ preserves binary coproducts.

Yes, I just got the wrong definition of $\bar F$, silly mistake.