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: partial groups and groupoids

Joe Moeller (Sep 01 2021 at 01:38):

If you had a group object internal to sets and partial functions, could you infer a set of objects making it into a groupoid?

John Baez (Sep 01 2021 at 02:44):

Nice question!

Chad Nester (Sep 01 2021 at 06:01):

This is also an interesting question for partial monoids / categories. It should be the same construction.

Chad Nester (Sep 01 2021 at 06:05):

We can construct the suspension of a total group/monoid by taking both the source and target map to be the unique total map into 1, but this should only define a category in the total case.

Martti Karvonen (Sep 01 2021 at 07:25):

I think you just get groups this way: there is a unique unit $e\in G$, and $g e=g=e g$ for all $g$ and in particular $ge$, $eg$ are always defined. The condition for inverses implies that the inverse operation is total. Now for any $g,h$ we have $g=ge=g(hh^{-1})=(gh)h^{-1}$, so in particular $gh$ is defined and multiplication is total.

Oscar Cunningham (Sep 01 2021 at 07:42):

Another way to see it is to use the fact that the category of sets and partial functions is equivalent to the category of pointed sets. For Lawvere theories, we have that an X internal to the category of Ys is the same as a Y internal to the category of Xs. So groups in pointed sets are the same as pointed groups. But since there's a unique map $1\to G$, these are just groups. Likewise for monoids.

Chad Nester (Sep 01 2021 at 13:07):

The Cartesian product of sets is not a categorical product in the category of pointed sets (partial functions).

John Baez (Sep 01 2021 at 13:12):

Interesting! And yet there's some sense in which a groupoid is like a group with a partially defined multiplication. Given a groupoid let $G$ be the set of all its morphisms. Let the product of $g,h \in G$ be the composite $g \circ h$ if the target of $h$ equals the source of $g$ and leave it undefined otherwise. Define the inverse in the obvious way; this is totally defined.

What sort of "group with partially defined multiplication" do we get this way? The big difference from a group object in the category of sets and partial maps is that $G$ does not have an identity element.

Joe Moeller (Sep 01 2021 at 13:13):

Right, this is basically the intuition my question was based on. In what technical sense could you say that a groupoid really is a group with partially defined multiplication?

John Baez (Sep 01 2021 at 13:15):

It's sort of interesting that in the construction I sketched - which Joe must have been thinking about already - "inverse" is totally defined and yet there's no specific identity element.

John Baez (Sep 01 2021 at 13:15):

So it really seems that a groupoid is like a group with partially defined multiplication and many identity elements.

Fawzi Hreiki (Sep 01 2021 at 13:16):

Maybe it's better to abstract a bit and consider the case of categories vs. monoids. The single sorted definition of a category still requires some way of keeping track of domains and codomains.

Fawzi Hreiki (Sep 01 2021 at 13:17):

Perhaps there is some natural notion of a monoid with partially defined multiplication. But a category will then likely be such a think plus some extra structure

Martti Karvonen (Sep 01 2021 at 13:20):

Chad Nester said:

The Cartesian product of sets is not a categorical product in the category of pointed sets (partial functions).

Yeah so my argument suffers from this issue and only discusses the situation where $\times$ means the cartesian product of sets, but I don't see an issue with the argument given by @Oscar Cunningham . Surely there is a sense in which groupoids are partial groups and categories are partial monoids, but I'm not sure what's the way to formalize that. For one, I really don't think that the units should be single-valued.

Fawzi Hreiki (Sep 01 2021 at 13:21):

The answer you're looking for may lie in directed graphs - the category of groupoids is monadic over the category of involutive directed graphs.

Chad Nester (Sep 01 2021 at 13:22):

@Oscar Cunningham is talking about interpreting lawvere theories in the category of sets and partial functions. That the Cartesian product of sets is not a categorical product in sets and partial functions is a problem for his argument

Martti Karvonen (Sep 01 2021 at 13:22):

Chad Nester said:

The Cartesian product of sets is not a categorical product in the category of pointed sets (partial functions).

Isn't the categorical product for pointed sets exactly the cartesian product (like always for models of algebraic theories)? When you transport it along the equivalence to sets and partial functions, the categorical product of $X$ and $Y$ seems to become $X\times Y+X+Y$.

John Baez (Sep 01 2021 at 13:22):

There's a definition of group where you just say an identity element exists but don't specify it: you leave its existence as a property, rather than specifying a structure. Then you can prove that given two identity elements, they must be equal.

However, this proof requires that multiplication is total. If it's just partially defined, it seems we can have many identity elements. We have to say $e$ is an identity element if $eg = g$ when this is defined and $ge = g$ when this is defined, and assert the existence of identity elements.

All this is sort of annoying, but there should be a definition of groupoid that proceeds along these lines: it's a set with a partially defined multiplication, for which identity elements and inverses exist.

Fawzi Hreiki (Sep 01 2021 at 13:24):

John Baez said:

There's a definition of group where you just say an identity element exists but don't specify it: you leave its existence as a property, rather than making the identity into a structure. Then you can prove that given two identity elements, they must be equal.

However, this proof requires that multiplication is total. If it's just partially defined, it seems we can have many identity elements. We have to say $e$ is an identity element if $eg = g$ when this is defined and $ge = g$ *when this is defined, and assert the existence of identity elements.

All this is sort of annoying, but there should be a definition of groupoid that proceeds along this line.

This is precisely what happens with the single sorted definition of a category.

Chad Nester (Sep 01 2021 at 13:27):

I'm having some trouble with Zulip on my phone, so can't respond at length right now, but I want to point out that most categories are examples of partial monoids with nontrivial partiality. @Oscar Cunningham 's argument would imply that composition is defined for any two morphisms in any category, regardless of their domain and codomain.

Zhen Lin Low (Sep 01 2021 at 13:39):

Chad Nester said:

The Cartesian product of sets is not a categorical product in the category of pointed sets (partial functions).

It is. Maybe you're confusing this with the fact that the category of pointed sets is symmetric monoidal closed but not cartesian closed.

Fawzi Hreiki (Sep 01 2021 at 13:40):

The specified point is just the pairing of the two specified points right?

Oscar Cunningham (Sep 01 2021 at 13:42):

@Chad Nester I think my answer is valid. But one confusing thing about it is that the identity is 'nothing'. This is because in categorical terms the identity is defined as a map $1\to G$, where $1$ is the terminal object. But in the category of sets and partial functions the terminal object is $\emptyset$. So the identity of a group $G$ is the unique empty function $\emptyset\to G$.

This matches with the pointed set point of view, because the equivalence from partial functions to pointed sets adds a new point to each set as the destination for the elements which go nowhere. This point is the identity for groups internal to pointed sets. So for example if we take the group $S_3$ considered as a pointed group, it has six elements with the identity as the point. But when we transfer it across the equivalence with partial functions, it becomes a five element set in which multiplication is only partially defined. An element cannot be multiplied by its inverse.

Fawzi Hreiki (Sep 01 2021 at 13:42):

In general, the forgetful functor $\text{Set}_* \rightarrow \text{Set}$ has a left adjoint given by $X \mapsto X + 1$

Fawzi Hreiki (Sep 01 2021 at 13:42):

So the forgetful functor preserves limits and hence in particular group/monoid objects.

Cole Comfort (Sep 01 2021 at 13:44):

Oscar Cunningham said:

Chad Nester I think my answer is valid. But one confusing thing about it is that the identity is 'nothing'. This is because in categorical terms the identity is defined as a map $1\to G$, where $1$ is the terminal object. But in the category of sets and partial functions the terminal object is $\emptyset$. So the identity of a group $G$ is the unique empty function $\emptyset\to G$.

This matches with the pointed set point of view, because the equivalence from partial functions to pointed sets adds a new point to each set as the destination for the elements which go nowhere. This point is the identity for groups internal to pointed sets. So for example if we take the group $S_3$ considered as a pointed group, it has six elements with the identity as the point. But when we transfer it across the equivalence with partial functions, it becomes a five element set in which multiplication is only partially defined. An element cannot be multiplied by its inverse.

There is no terminal object in sets and partial functions, rather a restriction terminal object. There is a unique total function to this object from every object.

Oscar Cunningham (Sep 01 2021 at 13:46):

I think $\emptyset$ is a terminal object. If you disagree, which set doesn't have exactly one partial function to the empty set?

Nick Hu (Sep 01 2021 at 13:47):

There are no functions (partial or total) from non-empty sets to $\emptyset$, surely?

John Baez (Sep 01 2021 at 13:48):

????????

Joe Moeller (Sep 01 2021 at 13:48):

There's always a partial function $X \to \emptyset$ which does not assign any element anywhere.

Joe Moeller (Sep 01 2021 at 13:49):

in the equivalent category of pointed sets, it's the unique map $X \cup \{*\} \to \{*\}$.

Nick Hu (Sep 01 2021 at 13:50):

Right, I guess it's clear if you define a partial function $X \xrightarrow{f} Y$ as the data of a function $X \to Y + 1$

Jules Hedges (Sep 01 2021 at 13:53):

Another equivalent view is that a partial function $f : X \to Y$ is the same as a choice of corange $\mathrm{corng} (f) \subseteq X$ and a function $\mathrm{corng} (f) \to Y$. So the unique partial function $X \to \empty$ always comes from choosing $\mathrm{corng} (!) = \empty \subseteq X$ and the unique function $\empty \to \empty$

Cole Comfort (Sep 01 2021 at 13:54):

I was confused, Par has both a terminal object and a restriction terminal object which are different

John Baez (Sep 01 2021 at 13:57):

If you're a mathematician and you haven't done your homework at all, and the teacher asks you if you've done your homework, you can say "I've partially done it" - and you aren't lying.

Nick Hu (Sep 01 2021 at 13:58):

Just like when people write "I have a number of years of experience in this area" on a job application, because 0 is a number

Jules Hedges (Sep 01 2021 at 13:59):

This is the first time I've heard a good argument why 0 should not be considered a number

Oscar Cunningham (Sep 01 2021 at 13:59):

If you're French you can say you've done a positif amount of homework, because 0 is positif.

Martti Karvonen (Sep 01 2021 at 14:10):

Cole Comfort said:

I was confused, Par has both a terminal object and a restriction terminal object which are different

Similarly, both products and restriction products exist but don't coincide.

Jules Hedges (Sep 01 2021 at 14:11):

Do I remember right that partial functions has biproducts? I think it behaves mostly like Rel

Cole Comfort (Sep 01 2021 at 14:11):

Ah yes, the product is +, is it?

Jules Hedges (Sep 01 2021 at 14:14):

If it's true there might be a slick way to see it by constructing an adjunction with Rel or something like that

Oscar Cunningham (Sep 01 2021 at 14:15):

Partial functions doesn't have biproducts. The coproduct is the same as it is in $\mathbf{Set}$ whereas the product of $X$ and $Y$ is $X+X\times Y+Y$.

Chad Nester (Sep 01 2021 at 14:16):

Does anyone think of this product when they say "partial group"? Surely we want the Cartesian product of sets...

John Baez (Sep 01 2021 at 14:17):

No, nobody thinks of this product when they say "partial group".

Martti Karvonen (Sep 01 2021 at 14:17):

Guess not, but if you say "group object in Pfn" that's an obvious reading

Oscar Cunningham (Sep 01 2021 at 14:19):

Right. The usual definition of 'group internal to a category' uses products by default, because people assume you're talking about the Lawvere theory. But if you want a group internal to an arbitrary monoidal category you can use Hopf algebras.

Oscar Cunningham (Sep 01 2021 at 14:22):

The difference is that the Lawvere theory of groups assumes you have the diagonal map $G\to G\times G$ so that it can phrase the equation $xx^{-1}=1$, in which $x$ appears twice. Whereas Hopf algebras are equipped with a duplicating map.

Martti Karvonen (Sep 01 2021 at 14:22):

If the duplicating map is taken to be the diagonal from Set, then my argument above (barring errors in it) should force multiplication to be total

Chad Nester (Sep 01 2021 at 14:24):

The point I want to make is that we can also axiomatize "group with partial multiplication operation" in a more sensible way, in which case I really don't think the multiplication is necessarily total.

James Wood (Sep 01 2021 at 14:26):

Related thread: https://categorytheory.zulipchat.com/#narrow/stream/229199-learning.3A-questions/topic/Comonoids.20in.20partial.20functions. I think the result of it was that all comonoids in partial functions (with the usual monoidal product) are trivial, so all bimonoids are just good old total monoids. I think that rules out any definition of “partial group” based on a standard notion of group object.

Oscar Cunningham (Sep 01 2021 at 14:26):

Martti Karvonen said:

If the duplicating map is taken to be the diagonal from Set, then my argument above (barring errors in it) should force multiplication to be total

Yes, and I believe that this is actually forced to happen. The groups in the category of sets and partial functions then up being normal groups, except an extra object which is the 'empty group'.

Martti Karvonen (Sep 01 2021 at 14:27):

I think my argument above works as long as all the equalities are Kleene equalities. If some of them get directed, the proof might no longer go through

Chad Nester (Sep 01 2021 at 14:32):

You're assuming that g (a variable in a partial theory) is defined, no?

Chad Nester (Sep 01 2021 at 14:32):

(that arbitrary terms denote elements)

Martti Karvonen (Sep 01 2021 at 14:47):

I'm reasoning about the carrier: if $g,h\in G$, then $g$ and $h$ are certainly defined, and $g=ge=g(hh^{-1})=(gh)h$, and for $(gh)h$ to equal $g$ surely $gh$ has to be defined as well.

Chad Nester (Sep 01 2021 at 14:53):

Ah I misunderstood: sorry.

Chad Nester (Sep 01 2021 at 14:54):

I think I buy that.aybe we need to make the unit axioms lax: of xe is defined then it must be e...

Chad Nester (Sep 01 2021 at 14:54):

I'm going to try out some examples

John Baez (Sep 01 2021 at 15:00):

I guess you meant "if xe is defined then it must be x".

Chad Nester (Sep 01 2021 at 15:08):

Yes, that.

Oscar Cunningham (Sep 01 2021 at 16:20):

A related fact is that a monoid internal to the category of pointed sets with the smash product is an ordinary monoid equipped with an 'absorbing element' $0$ such that $0m=0=m0$.

This is useful if you believe $0$ is a natural number but still want a nice way to state the unique factorisation theorem. You can say that $\mathbb N$ is the 'free commutative pointed monoid' on the set of primes, with $0$ as the point.

Robin Piedeleu (Sep 01 2021 at 20:26):

Joe Moeller said:

If you had a group object internal to sets and partial functions, could you infer a set of objects making it into a groupoid?

You might also find this paper interesting if you don't already know it. The authors answer a related question, in the setting of sets and relations (not just partial functions), with the cartesian product as monoidal product: a groupoid is a (special, dagger) Frobenius algebra in this symmetric monoidal category. The set of objects/identities is the set given by the unit of the algebra, if I remember correctly.

Sergei Burkin (Sep 02 2021 at 16:58):

There is a somewhat related point of view (shameless self plug ahead).

The classical Segal condition is essentially a way to see categories as "multi-object" monoids: for a Segal presheaf X over the simplex category $\Delta$ a morphism $[1]\to X$ can be thought of as an element of the partial monoid that corresponds to X, while a more general morphism $[n]\to X$ corresponds to n-tuple of composable elements of this partial monoid, and composability is the same as the elements of n-tuple having compatible objects. There is a general point of view on this, discussed in my work.

There should be a similar Segal condition for groupoids. In fact, there is Segal condition for groupoids, based on the category of symmetric sets. I have not checked if it fits in a general picture as above. But if everything is fine, then groupoids are "multi-object" groups in a certain precise sense.