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: theory: type theory & logic

Topic: Functions, Relations

Julius Hamilton (Nov 25 2024 at 19:43):

I’m acknowledging in advance that this is not a focused question or post. The CPU of my mind feels a bit overclocked, and I’m choosing to externalize some thoughts to try to flush them out.

1. It is very common to define logic as the study of “reason”, but lately I feel like it is just as much the study of “meaning”. The question of whether or not something is true or false feels much conceptually simpler than the question of how we can analyze and represent the structure and the dynamics of phenomena in the world. A very hard part about logic is the lack of a “starting place” or “origin”, because we use pre-existing systems of meaning to describe other ones. To an extent, with logic, we are always (insidiously?) invited to “move backwards”, which means that as we observe the systems of meaning we use to describe things, someone who wants “everything to be explained”may want to “reify” their meta-language into their object-language. A big problem with systems of meaning is that whatever conceptual ontology they are comprised of, there always seems to be further expressible notions implied by them, and we keep having to add more and more notions to our language.

2. There are many different kinds of logic. I started by learning some first-order logic. Then I also explored axiomatizing structures as purely “equational theories”; and also got exposed to regular logic, which is somewhere in-between. It did not occur to me before that “systems of equations” are just logical theories, but in a reduced type of logic that doesn’t have any logical connectives ($\neg, \wedge, \ldots$). Technically, a theory like $\{f(x) = x, f(c_0) = c_1, g(x, y) = f(y)\}$ is universally quantified over its variables, and I think we can argue that many of the constant terms can be replaced with existentially quantified variables too (e.g., $\exists x [f(x) = c_1]$, so let’s refer to one such element as $c_0$). On the other hand, I think we can get rid of the notion of quantification, for these theories in a logically equivalent way.

3. This has led me to explore different ways of stripping away the parts of first-order logic. I’ve tried to “catalogue” many different first-order signatures and theories and study them a bit. If your signature is $\{c_0\}$, the only atomic formula (excluding variables) you can make is $c_0 \equiv c_0$, which is already assumed. It is interesting how first-order logic gives a distinguished place to equality, as a relation; can we eliminate it, and only use relations that are in the signature?

4. I tried to write out a bunch of different first-order formulae, in order from simpler to longer or more complex. For example: $\{\forall x [x \equiv c_0], \forall x [f(f(x)) = x], \forall x [R_0(x, c_0)], \forall x \exists y [R_0(x, y)], \ldots\}$. I don’t know if this is true, but I ended up feeling like, “all of the really interesting formulae / theories involve quantification and relations”. It seems like there are many formulae involving constants and functions that don’t have a big impact on the rest of the theory, i.e., you’re just specifying certain values for functions, like “$f(f(f(x))) = c_0$”. The axioms of ZFC are more complex, by comparison. The axiom of pairing involves 4 quantified variables and logical connectives: $\forall x \forall y \exists z \forall w [R_0(w, z) \leftrightarrow (w \equiv x \vee w \equiv y)]$.

5. I’m not sure which common algebraic structures can be axiomatized in a purely equational theory. If we focus mainly on binary operations, it seems like a lot of the common formulae for magmas, monoids, groups, etc., are in reach: $f(x, y) = f(y, x), f(f(x,y), z) = f(x, f(y,z)), f(c_0, x) = x$. It remains to be seen what is gained by adding in logical connectives. I’m not sure, but it seems logical connectives and relations go more hand in hand; i.e. together they can express a lot more. What is strange is that relations can be expressed as functions into a type $\text{Bool}$. Maybe there’s something to be said about how from different points of view, we can see functions or relations as being “more fundamental”.

I will pause here for a moment to reflect.

John Baez (Nov 26 2024 at 01:57):

I’m not sure which common algebraic structures can be axiomatized in a purely equational theory.

You may be amused by how Terence Tao led an effort to study all 4694 algebraic structures involving a single binary operation $\circ$ and a single equation that uses the operation $\circ$ a total of at most 4 times. Some of these equations imply others, so the people in this project figured out which of all the

$4694 \times 4693 = 22028942$

possible implications are valid. This seems like a colossal waste of time to me, but then so does US-style football, and colleges in the US spend $2.7 billion a year on that. So clearly my opinion is unimportant in matters like these. At least classifying algebraic structures is less likely to cause brain injuries.

Madeleine Birchfield (Nov 26 2024 at 03:35):

Julius Hamilton said:

What is strange is that relations can be expressed as functions into a type Bool.

This is only true if your logic is classical (i.e. your logic assumes excluded middle).

Madeleine Birchfield (Nov 26 2024 at 03:36):

There are many other kinds of logic where excluded middle does not hold and so relations aren't functions into the booleans (i.e. set with two elements), such as intuitionistic logic, geometric logic, and affine logic.

Mike Shulman (Nov 26 2024 at 03:53):

@Madeleine Birchfield But that's a bit of a red herring because usually relations are still functions into a type of "truth values" or "propositions", it just doesn't happen to be provable that that type has only two elements.

Matteo Capucci (he/him) (Nov 26 2024 at 13:55):

John Baez said:

This seems like a colossal waste of time to me

AFAIU, it's mainly to get training data for AI proof assistants

Julius Hamilton (Nov 26 2024 at 14:51):

John Baez said:

You may be amused by how Terence Tao led an effort to study all 4694 algebraic structures involving a single binary operation $\circ$ and a single equation that uses the operation $\circ$ a total of at most 4 times... This seems like a colossal waste of time to me.

Why do you feel that way?

John Baez (Nov 26 2024 at 15:17):

At least 99% of these algebraic structures are completely useless (or to be kind, never yet used by mathematicians), and I haven't seen anyone give an explanation for why it would be helpful to determine their logical relations. There could be a very interesting theory of 'randomly chosen algebraic structures' and their average properties, but I didn't see anyone saying they would use the data generated by this project to generate conjectures about that theory.

Maybe I was missing the point; @Matteo Capucci (he/him) wrote:

AFAIU, it's mainly to get training data for AI proof assistants

Has someone (e.g. Tao) come out and explained that? I must have missed it. That could make sense.

I was speaking solely as a mathematician who likes interesting mathematical results. From that viewpoint, this project is a bit like a chef trying to cook 4693 dishes by combining the ingredients in their refrigerator in all possible ways, and then taste-testing them to answer all 22028942 possible questions about which dish tastes better than which.

Matteo Capucci (he/him) (Nov 26 2024 at 15:40):

Uhm from the link you sent. But reading again, I seem to have slightly misunderstood: the effort is more to benchmark the usage of AI/proof assistants for polymath projects rather than testing the tools themselves...

John Baez (Nov 26 2024 at 15:50):

Okay, I hadn't really read that article - I just heard about this project from a bunch of posts by Tao on the Mastodon.

I guess I knew it was some kind of test project to see if AI could be used to help with Tao's Polymath projects, where swarms of humans are supposed to collaborate and prove things. ("Benchmark" sounds too formal, I thought that was when you had some way of numerically scoring how well a system worked.) But being an old fuddy-duddy, I would like to see if AI could be used to find results mathematicians would be interested in. I'm not very surprised that it can be used to generate 22028942 uninteresting results.

Zoltan A. Kocsis (Z.A.K.) (Nov 29 2024 at 09:10):

A priori, the Equational Theories Project (ETP) might feel like a questionable use of time, but the project's actual outcomes seem highly valuable to me.

Some specific results:

1. Effective methods for building infinite countermodels in first-order logic theorem proving. Once integrated into practical tools, I am fairly sure these will have impact on open questions of the form "construct an f.p. group such that..." and similarly for open questions about other structures such as lattices (let’s revisit in five years to evaluate this prediction).

2. Tools to replay the results of powerful automated provers (e.g. Vampire) directly in Lean, so that they can be verified and used in formal developments. This is obviously quite useful, not just for mathematics, but for software verification as well!

Softer results:

1. A reality check on the current capabilities of automated tools. Interestingly, ATP tools successfully proved all true implications in the dataset, contrary to expectations (but failed to disprove many false ones with infinite or very large finite countermodels, which was very much in line with expectations). Beyond a sanity check on our automated (and manual!) techniques, it is, to a much lesser extent, a sanity check on our foundations as well. We know that PA, or even ZFC, is not sufficient to settle all magma law implications, now we have definite lower bounds on how much they do settle. It would have been surprising if one of these implications was impossible to settle using ZFC, of course (although I know a logician who thought that at least one implication will remain unsettled for years; we now know that he was mistaken).

2. A useful test set for future research in machine learning, automated theorem proving, and related tools including SMT solvers for real arithmetic. With synthetic benchmarks, it is often hard to tell whether a result remains unproven due to tool limitations or simply because it is false. Now we have a reasonably large set where the conclusions are known.Similarly in machine learning: it is a sizable, complicated graph whose edge structure can definitely be predicted by knowing the strings that the vertices represent. Can our ML tools predict that structure (very preliminarily results suggested "yes", but I think that'll be revised).

As a side note, I think mathematicians are conditioned to trigger their "unproductive work" reflex prematurely upon hearing the word "magma". For instance, would a project to compile a database of varieties over finite fields or even C, organized by containment, seem like a similar waste of time? Probably not: parts of the LMFDB are like that, yet nobody raised that concern. Of course the two problems are actually related: defining x op y = ax + by translates an equation satisfied by a magma operation op directly into a polynomial equation over a field (and just like there, most specific varieties are unimportant, they won't have a group law or other really interesting structure, but studying them all is still of some use).

(Full disclosure: I did contribute to the ETP.)

John Baez (Nov 29 2024 at 17:36):

Thanks! I'm completely convinced by your reply, @Zoltan A. Kocsis (Z.A.K.). I hadn't read an account of these benefits of the magma classification project.

(And by the way, even when I thought it was a waste of time, I wasn't opposed to people doing it! I think it's really important for the advance of mathematics to let people do things just for fun. I think a more dangerous waste of time occurs when people are bossed around and forced to do unproductive things they don't enjoy, like pointless tasks devised by bureaucrats.)

John Baez (Nov 29 2024 at 19:00):

As a side note, I think mathematicians are conditioned to trigger their "unproductive work" reflex prematurely upon hearing the word "magma". For instance, would a project to compile a database of varieties over finite fields or even C, organized by containment, seem like a similar waste of time? Probably not: parts of the LMFDB are like that, yet nobody raised that concern.

The reason is that mathematicians know many connections between these varieties and interesting questions about mathematics. There are lots of important theorems like the (now-proved) Weil conjectures and modularity theorem, and open questions like the Birch--Swinnerton-Dyer conjecture and Bloch-Kato conjecture, that can be examined with the help of this database. I'm not saying that this database will directly help solve any open conjectures, but at the very least, if you're trying to learn this stuff as I am now, it's helpful to have examples to look at.

If I knew lots of interesting questions about universal algebra that could be illuminated by a database of magmas with relations involving at most 4 instances of the magma operation, I'd never have said generating such a table was a waste of time.

It's interesting that your list of justifications of this project did not include any questions of this sort. They were all more indirect.

Now that we have such a database, I hope someone is trying to come up with such questions!

Zoltan A. Kocsis (Z.A.K.) (Nov 30 2024 at 05:23):

I think we're on the very same page @John Baez.

What I mean in my side note is precisely this. It would be very surprising if tabulating all inclusion relationships between the very simplest kinds of algebraic varieties led to significant progress on big open problems like the Birch and Swinnerton-Dyer conjecture. But when we talk about varieties, there's much less of an inferential leap to big problems coming to mind, which lessens the instinct to worry about it being unproductive work.

Zoltan A. Kocsis (Z.A.K.) (Nov 30 2024 at 05:30):

(btw on questions, there were some recent comments saying that ETP may have stumbled upon a sort of "magma cohomology" that is a variant of group cohomology; while I did learn some group cohomology during my PhD, I've forgotten much, and can't comment on how promising or nonpromising this is)

John Baez (Nov 30 2024 at 05:56):

From a modern viewpoint group cohomology arises from the bar construction, which is a way to get an augmented simplicial object from an algebra of monad. To define the cohomology of a group $G$ with coefficients in some abelian group $A$ on which $G$ acts, we use the "free abelian group with action of $G$ on an abelian group" monad on $\mathsf{AbGp}$. Various other monads give various other cohomology theories. The cohomology of monoids works almost the same as for groups. Magmas would require more creativity since there's no standard notion of an "action" of a magma. (I tend to think about this when trying to understand what a module of an nonassociative algebra would be - like my favorite nonassociative algebra, the octonions.)

Nathanael Arkor (Nov 30 2024 at 09:31):

Why is it not reasonable to define an action for a magma to be a function $M \times A \to A$?

Graham Manuell (Nov 30 2024 at 10:49):

There's been a large amount of work on monoid cohomology. A number of attempts at this are mentioned here. There are not as many papers on magmas, but for example, this paper is relevant. It discusses only split extensions, but I believe it is largely understood how to go from these to more general extensions. I don't know how this relates to the kind of magma cohomology they need. A notion of action for unitary magmas is discussed here.

John Baez (Nov 30 2024 at 18:58):

Nathanael Arkor said:

Why is it not reasonable to define an action for a magma to be a function $M \times A \to A$?

Notice that this doesn't use the multiplication in the magma at all! Indeed, I have in one paper used this as the definition of a set $M$ acting on a set $A$.

So, it's a fine definition for use in cohomology iff you're happy to let the cohomology of a magma depend only on the underlying set of the magma. But then calling it "magma cohomology" seems a bit odd: you might as well call it "set cohomology".

David Egolf (Nov 30 2024 at 19:04):

I recall that one can think of a group action as a functor from the category we get by viewing that group as a one-object category. Maybe one could do a similar thing with magmas, except working with some weak notion of "category" that doesn't require associativity or unitality?

John Baez (Nov 30 2024 at 19:22):

Such a "magmagory" is an interesting intermediate between a graph and a category - I'd never thought about such things.

John Baez (Nov 30 2024 at 19:26):

There will be right adjoints from the category of categories to the category of magmagories and from the category of magmagories to the category of graphs, I think!

Mike Shulman (Dec 01 2024 at 03:14):

Another way to say that without introducing magmagories is that every set $A$ has an endomorphism monoid $\mathrm{End}(A)$, which is of course also a magma, and so we could define an action of a magma $M$ on $A$ to be a magma homomorphism $M \to \mathrm{End}(A)$. But since $\mathrm{End}(A)$ is a monoid, this is the same as a monoid homomorphism $LM \to \mathrm{End}(A)$, where $L:\mathrm{Magma} \to \mathrm{Monoid}$ is the left adjoint of the forgetful functor. In other words, an "action" of a magma in this sense is just an ordinary action of its maximal monoid quotient.

Mike Shulman (Dec 01 2024 at 03:15):

So a magma can act via its underlying set, or it can act via its monoid quotient, but it's unclear whether there's any way for it to act that uses more of the magma structure than is contained in the monoid quotient.

Mike Shulman (Dec 01 2024 at 03:16):

It seems that one would need some more general notion of "endomorphism" that isn't associative, but I don't know what that would be.

Joe Moeller (Dec 01 2024 at 04:01):

(deleted)

Zoltan A. Kocsis (Z.A.K.) (Dec 01 2024 at 04:09):

Very interesting, thanks!

Earlier I wrote:

I've forgotten much, and can't comment on how promising or nonpromising this is

Based on the discussion, I now think that it holds promise at least in the weaker sense that

1. it's not fully obvious from first principles / general theory what magma cohomology should be, since the current most general theory fails to accommodate non-associativity;
2. so the fact that they seemingly stumbled upon a variant that helps solve a practical problem we had is a useful pointer.

John Baez (Dec 01 2024 at 05:45):

Hmm, I hadn't even dug back into the thread where a potential definition of $H^2$ for magmas might be given. Now I have, and I still don't see that definition, just a remark that suggests maybe Terry Tao knows that definition.

Zoltan A. Kocsis (Z.A.K.) (Dec 01 2024 at 05:48):

I don't think a full definition has been written down at this stage (but see the blueprint), and I don't think a major followup on magma cohomology is planned until after the main article is out.

John Baez (Dec 01 2024 at 05:52):

It shouldn't take that long to write down the definition of a 2-cocycle and a 1-coboundary if anyone knows them. For group cohomology a 2-cocycle on $G$ taking values in an abelian group $A$ on which $G$ acts is a function $f: G \times G \to A$ with

$\delta f = 0$

where

$(\delta f)(g_1, g_2, g_3) := g_1 f(g_2, g_2) - f(g_1 g_2, g_3) + f(g_1, g_2 g_3) - f(g_1, g_2)$

The easiest way to get such a cocycle is to take any $h: G \to A$ and define

$f = \delta h$

where

$(\delta h)(g_1, g_2) := g_1 h(g_2) - h(g_1 g_2) + h(g_1)$

This works because one can check that

$\delta \delta h = 0$

This sort of 2-cocycle is called a 2-coboundary. The group of 2-cocycles mod 2-coboundaries is called the second cohomology $H^2(G,A)$.

John Baez (Dec 01 2024 at 05:54):

So if this works for magmas, or some other formula works for magmas, there's no need to write a whole paper about it: it should be easy to write it down like I did now.

John Baez (Dec 01 2024 at 05:56):

I guess I'll just check to see if every 2-coboundary as defined above is a 2-cocycle using the exact same formulas when $G$ is a magma: that is, see if the associative law is needed. It might well not be. Right now I believe associativity becomes necessary when we get to $H^3$, but not for $H^0, H^1$ and $H^2$.

Mike Shulman (Dec 01 2024 at 05:58):

Tao's comment suggests their goal is to construct "magma extensions" of a magma $M$ by an abelian group or ring $G$:

with a carrier of the form $G \times M$ and with law $(x, a) \diamond (y,b) = (x \diamond_G y + f(a,b), a \diamond_M b)$ for some function $f: M \times M \to G$, where $G$ is an abelian group or ring and $\diamond_G$ is some linear magma operation that obeys the required equational law. In order for this "semi-direct product" to obey the law we then have to solve a (linear!) functional equation on $f$ (these equations look a little bit like cocycle equations).

This puzzles me though; what is "the law" he refers to? A magma operation doesn't have to satisfy any law.

Mike Shulman (Dec 01 2024 at 05:59):

If we knew what law he was talking about, we could presumably figure out what equation his $f$ has to satisfy to make it work.

Zoltan A. Kocsis (Z.A.K.) (Dec 01 2024 at 06:00):

The general goal is the following: given two laws P and Q, to construct magmas which satisfy P but not Q.

Zoltan A. Kocsis (Z.A.K.) (Dec 01 2024 at 06:01):

Btw the project blueprint has a short section on magma cohomology.

Mike Shulman (Dec 01 2024 at 06:01):

In the case of group extensions, the 2-cocycle equation arises from the requirement that a group extension satisfy associativity.

Mike Shulman (Dec 01 2024 at 06:04):

Thanks for the link! That makes it fairly clear: it's not really cohomology of magmas, but of "E-magmas" for some equation E. When E is associativity, we get ordinary (semi)group cohomology; in general there is a cocycle equation that's exactly what's needed to ensure that a magma extension inherits E from its components.

Mike Shulman (Dec 01 2024 at 06:05):

(BTW I find it rather confusing that apparently they use the word "law" to refer both to a magma operation and to an equation that it might satisfy.)

John Baez (Dec 01 2024 at 06:31):

John Baez said:

I guess I'll just check to see if every 2-coboundary as defined above is a 2-cocycle using the exact same formulas when $G$ is a magma: that is, see if the associative law is needed. It might well not be. Right now I believe associativity becomes necessary when we get to $H^3$, but not for $H^0, H^1$ and $H^2$.

It turns out we need associativity-like equations already to define $H^2$ in the usual way. But we do not need $G$ to be associative.

I took a function $h \colon G \to A$ where $G$ is a magma and $A$ an abelian group equipped with a map $G \times A \to A$, and I defined $\delta h$ and $\delta \delta h$ as usual in group cohomology, namely:

$(\delta h)(g_1, g_2) := g_1 h(g_2) - h(g_1 g_2) + h(g_1)$

and

$(\delta \delta h)(g_1, g_2, g_3) := g_1 f(g_2, g_2) - f(g_1 g_2, g_3) + f(g_1, g_2 g_3) - f(g_1, g_2)$

where $f$ is an abbreviation for $\delta h$.

Then I got the all-important equation

$\delta \delta h = 0$

if two equations hold:

$g_1 (g_2 h(g_3)) = (g_1 g_2) h(g_3)$

and

$h((g_1 g_2) g_3) = h(g_1 (g_2 g_3))$

These are automatic if $G$ is a group or even a monoid acting as endomorphisms of $A$.

If $G$ is just a magma, the first equation holds if the map $G \times A \to A$ obeys this law:

$g_1 (g_2 a) = (g_1 g_2) a$

Yes, this equation still parses just fine when $G$ is merely a magma!!! So maybe this we want this equation in the definition of 'magma action' (on a set, or group).

The second equations holds if $h: G \to A$ factors through the quotient of $A$ by the equivalence relation $(g_1 g_2) g_3 \sim g_1 (g_2 g_3)$, i.e. if $h$ factors through the free monoid on our magma. So maybe we should demand that a 1-cochain be not merely an arbitrary $h : G \to A$, but one with this property.

In short, $H^2$ for monoid cohomology can be generalized to a magma $G$ if we restrict ourselves to 1-cochains that factor through the free monoid on $G$, and $G$ acts on the coefficient group $A$ in such a way that $(g_1 g_2) a = g_1 (g_2 a)$.

(The term 'free monoid on a magma' sounds funny, but I'm referring to the left adjoint to the forgetful functor from monoids to magmas, where we take our magma and force it to be a monoid.)

Mike Shulman (Dec 01 2024 at 07:30):

Note that the equation $(g_1 g_2)a = g_1 (g_2a)$ says exactly that the map $G \to \mathrm{End}(A)$ is a magma homomorphism, and therefore (since End(A) is a monoid) it also factors through the free monoid on $G$. (I was calling this the "maximal monoid quotient", although I suppose it's not exactly a quotient since it has to add an identity too.) So don't we just get the cohomology of the free monoid on $G$ this way, rather than any kind of true magma cohomology?

Mike Shulman (Dec 01 2024 at 07:41):

Actually the quotient by $(g_1 g_2)g_3 \sim g_1(g_2g_3)$ is the free semigroup on the magma, right? Which is actually a quotient. So maybe I mean semigroup cohomology.

John Baez (Dec 01 2024 at 17:38):

Mike Shulman said:

Note that the equation $(g_1 g_2)a = g_1 (g_2a)$ says exactly that the map $G \to \mathrm{End}(A)$ is a magma homomorphism, and therefore (since End(A) is a monoid) it also factors through the free monoid on $G$.

Oh, right! So magma $H^2$ is starting to seem more and more like monoid $H^2$.

So don't we just get the cohomology of the free monoid on $G$ this way, rather than any kind of true magma cohomology?

Yeah.

John Baez (Dec 01 2024 at 17:44):

Mike Shulman said:

Actually the quotient by $(g_1 g_2)g_3 \sim g_1(g_2g_3)$ is the free semigroup on the magma, right? Which is actually a quotient. So maybe I mean semigroup cohomology.

I noticed that, and decided not to confuse people by starting to talk about semigroups. To get $H^n(G,A)$ from the explicit chain complex I was talking about, it seems all we need is a semigroup $G$ acting on an abelian group $A$.

People often like to restrict attention to the smaller cochain complex consisting only of "normalized" cochains $c: G^n \to A$, which have $c(g_1, \dots, 1, \dots, c_n) = 0$. And for this to give the same cohomology groups, we probably need our semigroup to be a monoid.

A monoid has a kind of [[nerve]] that's a simplicial set, but I think a semigroup has a kind of nerve that's a [[semi-simplicial set]], and that's good enough for homology and cohomology if we don't care about 'normalization' or 'degeneracies'. You probably understand this better than I do....

John Baez (Dec 01 2024 at 17:45):

Somewhere in this study of [[centipede mathematics]] we should be talking about unital magmas. Magmas are to semigroups as unital magmas are to monoids.

Q: What sort of 'nerve' does a magma, or unital magma, have?

Amar Hadzihasanovic (Dec 01 2024 at 18:57):

A monoid has a simplicial nerve because a category has a simplicial nerve, and this is because there is a cosimplicial object in $\mathsf{Cat}$ (i.e. a functor $\Delta \to \mathsf{Cat}$) sending $[n]$ to the poset $0 < \ldots < n$, seen as a category where there is a unique morphism $i \to j$ iff $i \leq j$.

A semigroup has a semisimplicial nerve because a semicategory has a semisimplicial nerve, and this is because there is a co-semisimplicial object in $\mathsf{SemiCat}$ sending $[n]$ to the strict order $0 < \ldots < n$, seen as a semicategory where there is a unique morphism $i \to j$ iff $i < j$.

So we should find some kind of magmoidal version of these cosimplicial and co-semisimplicial objects.

Amar Hadzihasanovic (Dec 01 2024 at 19:08):

In the non-unital case, this should take values in the category $\mathsf{Magmoid}$ of “magmoids”, that is many-object magmas. By analogy with the other two, it should be indexed by a category whose objects $[n]$ are indexed by natural numbers, and send $[n]$ to a magmoid whose objects are $0, \ldots, n$.

The natural guess to me looks like the following: $[n]$ is sent to the magmoid whose objects are $0, \ldots, n$ and set of morphisms from $i$ to $j$ is the set of plane rooted binary trees with $j - i$ leaves when $j > i$, and empty otherwise.
The composite of two morphisms corresponding to trees $t_1$ and $t_2$ is the tree whose subtrees at the 2 children of the root are $t_1$ and $t_2$, respectively (I can't remember the name of this operation)

Amar Hadzihasanovic (Dec 01 2024 at 19:10):

The indexing category should be equivalent to the full subcategory of $\mathsf{Magmoid}$ on these objects. I don't know of a combinatorial description of its morphisms but I bet it's something known.

Amar Hadzihasanovic (Dec 01 2024 at 19:26):

I mean, the unifying characteristic of these objects is that they are free in the appropriate sense on the linear graph on $n+1$ vertices, so in any case a morphism is uniquely determined by what it does on the edges of this graph.

So I think that a morphism $[k] \to [n]$ in the “magmoidal simplex category” is going to be a strictly increasing map $f: [k] \to [n]$ (in particular we must have $n \geq k$) together with a sequence $t_1, \ldots, t_k$ of plane rooted binary trees such that $t_i$ has $f(i) - f(i-1)$ leaves.

Amar Hadzihasanovic (Dec 01 2024 at 19:35):

So up to $n = 2$, the $n$-simplex and magmoidal $n$-simplex have the same faces, but from $n = 3$, there are more faces in the magmoidal $n$-simplex than in the $n$-simplex, since there are two different morphisms $[1] \to [3]$ such that $0 \mapsto 0$ and $1 \mapsto 3$.
These correspond to the two binary trees with 3 leaves, or equivalently to the two possible parenthesisations of a word of length 3.

Amar Hadzihasanovic (Dec 01 2024 at 19:43):

I'll call this “magmoidal simplex” a “magmex” for brevity. In the magmicial nerve of a magma, the $n$-magmexes are, just like in the case of monoids, sequences $(x_1, \ldots, x_n)$ of elements of the magma. But now there is a 1-face of this $n$-magmex for each $1 \leq i \leq j \leq n$ and for each parenthesisation of $x_i \ldots x_j$.

Amar Hadzihasanovic (Dec 01 2024 at 19:55):

I think the unital case is pretty much exactly the same, except for the fact that

• we also allow the empty tree (with 0 leaves) acting as an identity morphism,
• consequently, morphisms of magmices are order-preserving but not strictly so, and we can have “degeneracies”...

but these are not really different from the simplicial case, essentially because units are always associative in the sense that $(a1)b = a(1b) = ab$... It's really only the “faces” which are different

John Baez (Dec 02 2024 at 00:54):

This is excellent stuff, @Amar Hadzihasanovic. This looks like it could be the right approach to understanding the cohomology of magmas and magmoids: don't try to force simplicial techniques on them, but instead develop the right sort of new shapes - magmexes! - that are suited to working with them.

Mike Shulman (Dec 02 2024 at 01:52):

So is there a chain complex associated to a magmicial set? Or does the category of magmicial sets (or magmicial spaces) admit a model structure?

John Baez (Dec 02 2024 at 02:10):

At first the Dold-Kan theorem saying the category of simplicial abelian groups is equivalent to the category of $\mathbb{N}$-graded chain complexes of abelian groups seems like a miracle. But the ideas behind it are rather robust - owing in large part to the magic of abelian groups. So it might be possible that the category of magmicial abelian groups is also equivalent to the category of $\mathbb{N}$-graded chain complexes of abelian groups... even though magmicial sets are different from simplicial sets.

At the very least, we should be able to get an $\mathbb{N}$-graded chain complex of abelian groups from a magmicial abelian group!

John Baez (Dec 02 2024 at 02:19):

I have another question: how are magmicial sets related to dendroidal sets? I can begin to answer that. It seems like magmicial sets are presheaves on some category of planar rooted binary trees, while dendroidal sets are presheaves on the larger category of nonplanar rooted trees. So it seems there are two independent switches to flip here: planar versus nonplanar trees, and binary versus arbitrary $n$-ary trees. We should thus get presheaf categories on 4 categories of trees, and these 4 categories are related by some obvious functors, so we get a bunch of essential geometric morphisms between these presheaf categories.

Amar Hadzihasanovic (Dec 02 2024 at 07:26):

An obstacle here is that, however we assign orientations to faces of a magmex, we will not get a chain complex: the reason is that the two 1-faces 1(23) and (12)3 of the 3-magmex are faces of a single 2-face each. Thus in $d^2$ of the top face they will each appear only once, and there is nothing that can "cancel them out".
We can still get an $\mathbb{N}$-graded abelian group with these "inexact" differentials, though, and that does seem to encode some interesting information; e.g. if we hit the nerve of a magma with this construction, we have $d^2(a, b, c) = a(bc) - (ab)c$, that is, $d^2(a, b, c) = 0$ if and only if $(a, b, c)$ associate.
(This is after choosing the orientation of faces induced from the $n$-oriental by the evident quotient map from the $n$-magmex to the $n$-simplex)

John Baez (Dec 02 2024 at 17:27):

Ouch! That's too bad. Could we possibly have $d^3 = 0$ or $d^n = 0$ for some fixed $n$? There's been a bit of work on such "$n$-step complexes" by Kapranov. I realize that by asking this I'm lazily hoping Amar will do even more calculations. Sorry! But I've always hoped there was some really good application of $n$-step complexes.

John Baez (Dec 02 2024 at 17:38):

I'm afraid that if $d^2 = 0$ fails so will $d^n = 0$ for every $n$.

Riley Shahar (Dec 02 2024 at 18:17):

John Baez said:

Ouch! That's too bad. Could we possibly have $d^3 = 0$ or $d^n = 0$ for some fixed $n$? There's been a bit of work on such "$n$-step complexes" by Kapranov. I realize that by asking this I'm lazily hoping Amar will do even more calculations. Sorry! But I've always hoped there was some really good application of $n$-step complexes.

For any $n$ you should have exactly the same problem: the $1$-faces $(\dots (12)3)\dots )n$ and $1(2(\dots([n-1]n)\dots)$ of the $n$-simplex both come from a unique $2$-face. (The dots are probably not clear; I mean the faces corresponding to the two "extreme" binary trees, one which is left-heavy and one which is right-heavy. So e.g. for $n = 5$ these are $(((12)3)4)5$ and $1(2(3(45)))$.)

Amar Hadzihasanovic (Dec 02 2024 at 19:20):

Another thing we could try to get a bona fide chain complex is to take the face poset of each magmex, and then take the chain complex associated to its order complex, which is an ordered simplicial complex so we can apply the usual machinery.
For simplices, the order complex of the face poset of the $n$-simplex is the barycentric subdivision of the $n$-simplex, which is homeomorphic to the $n$-simplex itself, so whether one takes the usual chain complex of a simplicial set, or first hits the simplicial set with subdivision, will have no effect on the homology. But in our case this should have the non-trivial effect of allowing us to use simplicial machinery after all.

Amar Hadzihasanovic (Dec 02 2024 at 19:26):

To be more formal: if $\mathsf{Mx}$ is the “magmex category” that I described earlier, there should be a functor $\mathsf{Mx} \to \mathsf{Pos}$ sending each magmex to its poset of faces and each inclusion of magmicial faces to a closed embedding of posets.
Then we can post-compose this functor first with the nerve $\mathsf{Pos} \to \mathsf{sSet}$ and then with the simplicial chain complex functor $\mathsf{sSet} \to \mathsf{Ch(Ab)}$.
Finally, we can extend along colimits to get a functor $[\mathsf{Mx}^\mathrm{op}, \mathsf{Set}] \to \mathsf{Ch(Ab)}$ from “magmicial sets” to chain complexes.

Amar Hadzihasanovic (Dec 02 2024 at 19:28):

If we replaced $\mathsf{Mx}$ with the simplex category $\Delta$ in this construction, we would get the functor which sends a simplicial set to the chain complex of its subdivision, which is weakly equivalent to the chain complex of the original simplicial set.

Amar Hadzihasanovic (Dec 02 2024 at 19:32):

So unless I have made a mistake somewhere, taking the “magmicial nerve” of a magma, followed by this functor, followed by homology should give some notion of homology of a magma.

Riley Shahar (Dec 03 2024 at 00:25):

John Baez said:

I have another question: how are magmicial sets related to dendroidal sets? I can begin to answer that. It seems like magmicial sets are presheaves on some category of planar rooted binary trees, while dendroidal sets are presheaves on the larger category of nonplanar rooted trees. So it seems there are two independent switches to flip here: planar versus nonplanar trees, and binary versus arbitrary $n$-ary trees. We should thus get presheaf categories on 4 categories of trees, and these 4 categories are related by some obvious functors, so we get a bunch of essential geometric morphisms between these presheaf categories.

Here's a different thought, no clue if it's worth anything, more in line with dendroidal sets. I'm going to define something I'll call an arboreal set and show how to take the arboreal nerve of a magmoid. I think a Dold-Kan-like construction is possible which will give us a chain complex-like-thing graded in a somewhat strange net, rather than in $\mathbb{N}$, but I haven't written out the details, so I'll stop at the nerve for now.

Notice that for dendroidal sets, the objects of the replacement of the simplex category are trees; whereas for magmicial sets as defined above, the morphisms are trees. We want to work with some category $\text{Tr}$ whose objects are finite rooted full binary trees with a compatible linear order on their leaves. (In other words, they are complete parenthesizations of the string "$1\dots n$" for some $n$. By compatibility, I mean that if $u < v < w$, then it should noe be the case that $u$ and $w$ are closer to each other than to $v$ in the tree.) Notice that these trees are not symmetric, so this is not just a subcategory of the dendroidal category.

We need to describe the right morphisms in this category. The idea is that a morphism embeds $T$ as a subtree of $S$, but may send edges to paths; here is one way to make that precise. The order on the leaves induces a total order on arbitrary vertices via depth-first search (take the order on the leaves, and ask that a parent precedes its children; this process determines a unique total order on the vertices). A morphism $f: T\to S$ is a strictly monotone map from the leaves of $T$ to the vertices of $S$ such that images of distinct leaves are never in an ancestor-descendant relationship.

An "arboreal set" is a presheaf on $\text{Tr}$. In particular, for each finite rooted binary tree $T$, an arboreal set has a set of "$T$-cells", and given an embedding of $T$ into $S$, there is map sending $S$-cells to $T$-cells obeying some laws.

Every magma, or more generally magmoid, $M$ has an "arboreal nerve" whose $T$-cells are the labellings of each leaf in $T$ with (composable) elements/morphisms from $M$. Given a map $f: T\to S$ and an $S$-cell, we obtain a $T$-cell whose node $t$ is labelled by the product of all the descendants of $f(t)$, associated as dictated by the tree $S$. This process satisfies all the right equations, so we get a genuine arboreal set. Moreover, this process is functorial; give a magmoid functor $F: M\to N$, we have a natural transformation which pushes the labels of $T$-cells through $F$. (I feel quite strongly that this should be induced from some functor $\text{Tr}\to\text{Magmoid}$, but as far as I can see it will take some work to write that functor down.)

Riley Shahar (Dec 03 2024 at 00:33):

I conjecture (although I haven't written it out---maybe there is an obstruction like the one Amar found for magmicial sets, and I just haven't noticed it) that an arboreal set should give you a "complex" (heavy scare quotes) graded in the poset quotient of $\text{Tr}$, i.e. for each $T$, an abelian group $A_T$, so that if there is a tree map $T\to S$ that is not an identity and factors through no other tree maps, then there is a differential $\operatorname{d}: A_S\to A_T$, so that any two distinct $$\text{d}$$s compose to the zero map. I don't know if there is a theory of such "net-graded complexes" or whether they give interesting cohomology theories in any sense, it seems like someone here would know about such a thing if it exists.

(Extremely optimistically, for any category $\mathcal{T}$ of "tree-like objects and tree embeddings," e.g. semisimplicial sets, arboreal sets, dendroidal sets, maybe there is a theory of complexes graded in the poset quotient of $\mathcal{T}$, and a "Dold-Kan for $\mathcal{T}$-sets". Any maybe we can relax the injectivity to get simplicial sets etc. That's probably way too optimistic, but it's something we could try to approach if this ends up working in some specific non-simplicial setting.)

Riley Shahar (Dec 03 2024 at 01:39):

Update: nevermind, this is too much to hope for; there is an obstruction to $\text{d}^2 = 0$ very similar to the one with magmicial sets. Sorry!!