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: when are "derived" operations preserved by a functor?

David Egolf (Jun 01 2023 at 16:59):

A functor $F: C \to D$ preserves the operation $\circ$ of composition in the sense that $F(f \circ g) = F(f) \circ F(g)$ . It is possible to define a new two-argument operation in terms of $\circ$ , and I'm curious when such an operation will also be preserved by the functor.

For example, let $f*g = f \circ g \circ f$ . When $f$ and $g$ are such that $f*g$ is defined, then $F(f * g) = F(f \circ g \circ f) = F(f) \circ F(g) \circ F(f) = F(f)*F(g)$ . In this case, the operation $*$ is preserved by $F$ . As a second example, let $f \square g = f \circ f \circ g \circ g$ . When $f \square g$ is defined, then $F(f \square g) = F(f \circ f \circ g \circ g) = F(f) \circ F(f) \circ F(g) \circ F(g) = F(f) \square F(g)$ . So the operation $\square$ is also preserved by $F$ .

I'm curious if this always works. However, I'm not sure how to tackle this question. As a first step, I could try and precisely describe what I mean by a a "two argument-operation defined in terms of $\circ$ ". Perhaps I could try and define this set of operations inductively, and then try to prove that $F$ preserves all these operations using (structural?) induction on the resulting set.

Once I understand the case above, I'm also interested in the case where $F$ is a map that preserves multiple operations. For example, if $F$ is a homorphism between Boolean algebras then $F(a \land b) = F(a) \land F(b)$ and $F(a \lor b) = F(a) \lor F(b)$ . Then will $F$ preserve new two-argument operations defined in terms of $\land$ and $\lor$ ?

Mike Shulman (Jun 01 2023 at 17:11):

In general the answer is yes, and one way to make it precise is with universal-algebraic tools such as "operads" and "Lawvere theories". For instance, the Lawvere theory of Boolean algebras is a category $\mathbf{B}$ with finite products generated "freely" by one object $X$ that has the structure of an internal Boolean algebra. Then the morphisms $X^n \to X$ in this category are precisely the " $n$ -ary operations that can be defined in terms of the defining Boolean algebra operations". Moreover, freeness of $\mathbf{B}$ means that to give an actual Boolean algebra is equivalent to giving a finite-product-preserving functor $\mathbf{B} \to \rm Set$ , and similarly to give a Boolean algebra homomorphism is equivalent to giving a natural transformation between such functors. Naturality of such a transformation then tells you that any such homomorphism automatically commutes with any of the "definable operations". The case of categories is similar, except that you need something fancier instead of a finite-product category.

David Egolf (Jun 01 2023 at 18:21):

Thanks @Mike Shulman! I will plan to read your response more carefully and type something up in response when I have the energy.

John Baez (Jun 01 2023 at 18:27):

David Egolf said:

A functor $F: C \to D$ preserves the operation $\circ$ of composition in the sense that $F(f \circ g) = F(f) \circ F(g)$ . It is possible to define a new two-argument operation in terms of $\circ$ , and I'm curious when such an operation will also be preserved by the functor.

[...]

I'm curious if this always works.

Yes it does!

However, I'm not sure how to tackle this question. As a first step, I could try and precisely describe what I mean by a "two-argument operation defined in terms of $\circ$ ". Perhaps I could try and define this set of operations inductively, and then try to prove that $F$ preserves all these operations using (structural?) induction on the resulting set.

That basically works, but one thing @Mike Shulman was trying to tell you is that the induction will work a lot easier if you use arbitrary finitary operatons: $n$ -argument operations for arbitrary $n = 0,1,2,\dots$ Plus you'll get a stronger result: if $F$ preserves some binary operation $\circ$ it'll preserve all finitary operations defined in terms of that binary operation.

And it's not really harder to prove an even stronger result: : if $F$ preserves some collection of finitary operations, it'll preserve all the finitary operations defined in terms of those operations!

John Baez (Jun 01 2023 at 18:34):

The formalisms Mike was alluding to - "operads" and "Lawvere theories" - give two distinct ways to make precise the concept of "defined in terms of".

John Baez (Jun 01 2023 at 18:36):

But while they're incredibly fascinating formalisms which I (among many) have spent years studying, you don't strictly need them to carry out the inductive argument you're hinting at.

John Baez (Jun 01 2023 at 18:36):

They become essential when you want to go further with the study of finitary operations.

David Egolf (Jun 02 2023 at 18:30):

Mike Shulman said:

In general the answer is yes, and one way to make it precise is with universal-algebraic tools such as "operads" and "Lawvere theories". For instance, the Lawvere theory of Boolean algebras is a category $\mathbf{B}$ with finite products generated "freely" by one object $X$ that has the structure of an internal Boolean algebra. Then the morphisms $X^n \to X$ in this category are precisely the " $n$ -ary operations that can be defined in terms of the defining Boolean algebra operations". Moreover, freeness of $\mathbf{B}$ means that to give an actual Boolean algebra is equivalent to giving a finite-product-preserving functor $\mathbf{B} \to \rm Set$ , and similarly to give a Boolean algebra homomorphism is equivalent to giving a natural transformation between such functors. Naturality of such a transformation then tells you that any such homomorphism automatically commutes with any of the "definable operations". The case of categories is similar, except that you need something fancier instead of a finite-product category.

This was great motivation for me to learn a bit about Lawvere theories, which have always scared me away before. I don't understand all the details, but I think I follow the big picture reasonably well now!

A couple things that would require more work from me to understand are:

How do we figure out the structure of a Lawvere theory $T$ so that product preserving functors from $T$ to $\mathsf{Set}$ will yield examples of the kind of algebraic object of interest? For example, to get a group, it looks like we set $T$ to be the opposite of the category of free groups with group homomorphisms between them. To get Boolean algebras in this way, I don't know how to set up $T$ . However, you did mention it should have "the structure of an internal Boolean algebra". Maybe this can motivate me to learn about "internal" things at some point!
Following up from the first point, it would be nice to concretely describe the "definable" operations that commute with homomorphisms. For example, in the case of binary operations, it's not yet clear to me how the additional morphisms from $X^2$ to $X$ in $\mathbf{B}$ arise from the presence of the "basic" 2-ary operations (say $\land$ and $\lor$ for Boolean algebras).

Anyways, this was interesting to learn a bit about!

Mike Shulman (Jun 02 2023 at 18:56):

In general, the Lawvere theory of $T$ is always the opposite of the category of finitely generated free $T$ -algebras. So for Boolean algebras, it would be the opposite of the category of finitely generated free Boolean algebras.

John Baez (Jun 02 2023 at 19:40):

Following up from the first point, it would be nice to concretely describe the "definable" operations that commute with homomorphisms.

The "definable" operations are precisely the morphisms in your Lawvere theory; any homomorphism between models of the Lawvere theory will automatically preserve (commute with) all these operations.

John Baez (Jun 02 2023 at 19:43):

That's because a model of a Lawvere theory $T$ is a (nice) functor from that theory to Set, say $F: T \to \mathsf{Set}$ , and a homomorphism between Lawvere theories is (any) natural transformation between such functors. As you know, a natural transformation between two functors out of $T$ gives a commutative square for each morphism in $T$ . These commutative squares say that homomorphisms between models of $T$ commute with all the operations in $T$ !

John Baez (Jun 02 2023 at 19:52):

How do we figure out the structure of a Lawvere theory $T$ so that product preserving functors from $T$ to $\mathsf{Set}$ will yield examples of the kind of algebraic object of interest?

Mike told you one method: if you hand me the category of finitely generated groups, I can just take its opposite and that's the Lawvere theory for groups, and similarly for any other gadget described by a Lawvere theory. This is an amazing, wonderful theorem that becomes quite obvious when you look at a few examples. But this trick only works if your gadget is described by a Lawvere theory, and it can sometimes be rather awkward to "hand someone" the category of all finitely generated gadgets of some sort.

David Egolf (Jun 02 2023 at 19:54):

John Baez said:

Following up from the first point, it would be nice to concretely describe the "definable" operations that commute with homomorphisms.

The "definable" operations are precisely the morphisms in your Lawvere theory; any homomorphism between models of the Lawvere theory will automatically preserve (commute with) all these operations.

I think I understand that. I'm curious how we figure out what those morphisms in the Lawvere theory are, I suppose. So, if I start with a kind of algebraic object of interest (for example - Boolean algebras), there are some operations that we know are preserved by homomorphisms to begin with (for example, $\land$ and $\lor$ ). These operations correspond to morphisms in the Lawvere theory corresponding to that kind of algebraic object. However, there will also be additional morphisms in the Lawvere theory describing the "definable" operations. The process by which these additional morphisms are formed in the Lawvere theory is not yet clear to me.

However, now that I know how we can form the Lawvere theory for an algebraic structure of interest, (as you have both described above), maybe I could figure out the answer to this question.

John Baez (Jun 02 2023 at 19:58):

How do we figure out the structure of a Lawvere theory $T$ so that product preserving functors from $T$ to $\mathsf{Set}$ will yield examples of the kind of algebraic object of interest?

Luckily there's another method. If you hand me a bunch of finitary operations obeying a bunch of equations, I can inductively build all the operations obtainable from these operations, and all the equations they obey - and if I do it right this is a Lawvere theory! E.g. starting with the famous operations of a group and the famous equations they must obey, I will get the Lawvere theory for groups.

But you'll notice this "inductively building up" business is exactly what you were asking about at first. So there's not really any way around it - which is why I didn't advertise Lawvere theories at first: you were well on the way to reinventing them. The only hint I had to give you is not to focus solely on binary operations!

John Baez (Jun 02 2023 at 20:00):

The process by which these additional morphisms are formed in the Lawvere theory is not yet clear to me.

A Lawvere theory is a category with finite products, and this tells you how to get new morphisms from old: first by composing them (which you can do in any category), and then by a coupld other tricks, which are built into the definition of "finite products".

John Baez (Jun 02 2023 at 20:03):

For example in any category with finite products we have a "diagonal morphism" $\Delta_X : X \to X \times X$ for any object $X$ , so one operation we always get to use is something like

$\Delta_X(x) = (x,x)$

This "duplicates a variable".

In the Lawvere theory for groups we also have an operation called "multiplication" $m: X \times X \to X$ , which lets us multiply. For short we could write it like this:

$x \cdot y := m(x,y)$

Composing this with $\Delta_X$ we get a squaring operation $m \circ \Delta: X \to X$ which does this:

$m (\Delta(x)) = x \cdot x$ .

John Baez (Jun 02 2023 at 20:04):

And so on. When you understand finite products, you know all the tricks here.

David Egolf (Jun 02 2023 at 20:09):

Ah, I see! A morphism to $X^n$ from some object $Y$ is determined uniquely by $n$ morphisms from $Y$ to $X$ . So, if we know some morphisms to $X$ we can induce new morphisms to $X^n$ . I think the duplication example you gave is the induced morphism from $X$ to $X \times X$ induced by two copies of the identity morphism from $X$ to $X$ .

Then, as you pointed out, we can get even more morphisms by composing the morphisms we get this way with other rmorphisms we already have!

So this seems like a way to get at new operations that will be preserved by homomorphisms, starting with old ones that we already know will be preserved.

John Baez (Jun 02 2023 at 21:06):

Yes, exactly! Here are three other things we can do in any category with finite products. Given a morphism $f: X \to Y$ and a morphism $f' : X' \to Y'$ we can "set them side by side", forming the morphism

$f \times f' : X \times X' \to Y \times Y'$

John Baez (Jun 02 2023 at 21:08):

Also, every category with finite products lets us "delete data", since there's a unique morphism from any $X$ to the terminal object $1$ . This lets us take a morphism $f: X^n \to X^m$ and "throw out" any one of the $m$ outputs and get a morphism from $X^n$ to $X^{m-1}$ .

John Baez (Jun 02 2023 at 21:09):

Thirdly, there's a god-given isomorphism $S_{X,Y} : X \times Y \to Y \times X$ that lets us "switch things around".

John Baez (Jun 02 2023 at 21:11):

These three, together with composing morphisms and "duplicating data" using the diagonal are all the basic ways, to build new morphisms from old in a category with finite products.

David Egolf (Jun 04 2023 at 16:00):

Thanks for pointing out those other things we can do! They were interesting to think about.

I think the list of things you've provided closely relates to the idea that we can view a category with finite products as a cartesian monoidal category.

John Baez (Jun 04 2023 at 16:50):

Yes, very good point! I was breaking the concept of "category with finite products" into pieces using the fact that it can be seen as a cartesian monoidal category.

John Baez (Jun 04 2023 at 16:51):

And it turns out to be very interesting to drop the cartesianness and see what you can do using just a symmetric monoidal category. Then you can still build new operations (morphisms) from old by composing them or "setting them side by side" (tensoring them), but you cannot duplicate or delete arguments.

Josselin Poiret (Jun 05 2023 at 09:01):

Mike Shulman said:

In general, the Lawvere theory of $T$ is always the opposite of the category of finitely generated free $T$ -algebras. So for Boolean algebras, it would be the opposite of the category of finitely generated free Boolean algebras.

for a nice reference of this fact (and Lawvere theories in general), Algebraic Theories by Adámek, Rosický and Vitale is a must

Josselin Poiret (Jun 05 2023 at 09:01):

specifically, that's corollary 11.22

Josselin Poiret (Jun 05 2023 at 09:11):

(I have to say I was wondering if that was true because I was thinking of animated ∞-categories, where the algebraic theory you get out of the category you want to animate might not be the algebraic theory you started out with, ie. for abelian groups you get the theory of $\mathbb{Z}$ -modules, but it is obtained by the finitely presentable objects instead. Haven't thought about this in some time)

Jencel Panic (Jun 10 2023 at 06:52):

I thought I'd prove this as an exercise:

Take a chain of function applications:

$f \circ g \circ d \circ ...$

Because of associativity, this chain is equivalent to applying the first function and then applying the rest:

$f \circ (g \circ d \circ ...)$

Let there exist a functor $F$ with our category as a source. According to the functor laws, the above chain is equivalent to.

$F(f) \circ F(g \circ d \circ ...)$

But $g \circ d \circ ...$ is a chain of functional applications, so it is equivalent to $F(g) \circ F(d \circ ...)$ . Applying this gives us:

$F(f) \circ F(g) \circ F(d) \circ ...)$

From then on we proceed inductively, until we reach the end.

Feedback is welcome, I am new in writing proofs.

David Egolf (Jun 10 2023 at 16:48):

Hi Jencel!
If I understand properly, I think you were working on proving that $F(f \circ g \circ d \circ ...) = F(f) \circ F(g) \circ F(d) \circ....$ for some sequence of composable morphisms $f,g,d,\dots$ in the category that $F$ is mapping from.
That's not quite what I was asking about in this thread, but it does seem related!

Jencel Panic (Jun 10 2023 at 18:11):

Hm, I guess it is indeed not all there is to it.

Jencel Panic (Jun 10 2023 at 18:45):

Let $A$ be a hom set for an object in the source category

(I assume it is the same object, as otherwise you won't be able to generate the operator in a total way).

$f$ , $g$ , $d$ ...

And let $B$ be the hom set for a corresponding object of the target.

$F(f)$ , $F(g)$ , $F(d)$ ...

What we want to prove (if I am not mistaken) is that any morphism that is a result of a composition of morphisms in $A$ is mapped to the result of the composition of the corresponding morphisms in $B$ .

To do so, we take a morphism in $A$ and it's counterpart in $B$

$f \circ g \circ f \to F(f \circ g \circ f )$

But we already proved that

$F(f \circ g \circ f ) = F(f) \circ F(g) \circ F(f)$

$f \circ g \circ f \to F(f) \circ F(g) \circ F(f)$