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: deprecated: mathematics

Topic: there are no functions of 3 variables

John Baez (Dec 29 2020 at 19:09):

Why are binary operations so much more popular than ternary operations?

In 1900 Hilbert conjectured that there exist continuous functions of 3 real variables that can't be expressed in terms of continuous functions of 2 real variables.

More precisely, in his 13th problem he conjectured that there exists a continuous function $f:[0,1]^3 \to \mathbb{R}$ that cannot be expressed in terms of composition and addition of continuous functions from $\mathbb{R}^2$ to $\mathbb{R}$.

In 1957, V. I. Arnol'd proved that this is false.

Even more shocking results are known:

• Sidney A. Morris, Hilbert 13: Are there any genuine continuous multivariate real-valued functions?

Are there other results, e.g. of a more algebraic nature, that explain why operations of arity 3 and higher are less important than binary operations?

Eric Forgy (Dec 29 2020 at 19:20):

I was thinking about logic gates. The Nand operator is pretty powerful. All computers and everything computers can do is based on it.

Dan Doel (Dec 29 2020 at 19:21):

I would guess the answer is at least partly going to be the same as, "why are single sorted theories so popular?" I.E. because mathematicians will jump through as many hoops as necessary to use a single sorted theory instead of many-sorted. :smile:

Dan Doel (Dec 29 2020 at 19:22):

See, it's not a ternary operation, it's an indexed family of binary operations.

John Baez (Dec 29 2020 at 20:06):

I'd often guessed the dominance of binary operations was a purely psychological thing, but Arnold's result (and related ones) show that in analysis there's a certain sense in which it's an objective phenomenon.

(In fact Kolmogorov showed the only continous real-valued functions you need are functions of one variable: the rest you can get by composition and addition. And to some extent this matches the continuous functions of one variable that we use: $\sin, \cos$ etc.)

Todd Trimble (Dec 29 2020 at 20:53):

Related.

Todd Trimble (Dec 29 2020 at 21:03):

You may have heard that compact Hausdorff spaces are algebras for a monad on $\mathsf{Set}$, making them infinitary algebras of a sort. In fact, all the interesting operations are infinitary. Given an ultrafilter $U$ on an infinite set $J$, and a compact Hausdorff space $X$, there is a corresponding operation $X^J \to X$ which takes a $J$-tuple conceived as a function $f: J \to X$, pushes forward the ultrafilter $U$ along $f$ to get an ultrafilter on $X$, and then sends $f$ to the unique point in $X$ to which the push-forward ultrafilter converges.

Todd Trimble (Dec 29 2020 at 21:05):

This is only interesting when $U$ is non-principal. If $\text{prin(j)}$ is the principal ultrafilter generated by an element $j \in J$, then the corresponding operation is the $j$-th projection $\pi_j: X^J \to X$.

Jorge Soto-Andrade (Dec 29 2020 at 21:45):

I would say: because we have two hands.... Ask the octopuses about their
math!

Chad Nester (Dec 30 2020 at 10:02):

Maybe it’s because binary operations are ternary relations. I’m thinking about Pierce’s lines of identity here, in which it would be impossible to identify three or more things without ternary identity relations (branching lines).

Chad Nester (Dec 30 2020 at 10:03):

... but once you have ternary identity relations you can build n-ary ones for any n, in the same way that you can build regular polygons out of triangles.

Chad Nester (Dec 30 2020 at 10:04):

Which suggests to me that while ternary relations (e.g. binary operations) are absolutely necessary, we might expect to decompose relations of higher arity.

Todd Trimble (Dec 30 2020 at 13:11):

John, although I think you were just kidding with the ZZZ (riffing on my "yawn"), people might think the emoji applies to the entirety of my comment, which would be a shame because this is actually a really cool fact.

Oscar Cunningham (Dec 30 2020 at 13:47):

@Todd Trimble Does this make $-^J$ into a comonad?

Todd Trimble (Dec 30 2020 at 13:52):

Not that I know of. Of course $-^J$ is a monad, with monad structure induced from the comonoid structure $1 \leftarrow J \stackrel{\Delta}{\to} J \times J$.

John Baez (Dec 30 2020 at 16:06):

Todd Trimble said:

John, although I think you were just kidding with the ZZZ (riffing on my "yawn"), people might think the emoji applies to the entirety of my comment, which would be a shame because this is actually a really cool fact.

I'll delete it. I was joking about your "yawn". I was looking for a yawn emoji and that's the closest I could find. I don't think I've ever said or suggested anyone's comments on any forum are boring. I'm not sure why, but the idea of doing so has never even crossed my mind.

Jens Hemelaer (Dec 30 2020 at 16:44):

I don't know if this is related to the result by Arnol'd, but something similar happens in universal algebra. You can always equip a set with a binary operation such that the monoid of endomorphisms is whatever monoid you want. Or you can equip each set in a collection with a binary operation, and then the category of these (with as maps the functions respecting the binary operation) is any small category you want.

John Baez (Dec 30 2020 at 17:19):

That's very nice, Jens. I hadn't known that. You're not saying all operations in any variety are generated by binary operations (since that's false), but what you say seems to imply that given any variety, we can find a variety with operations generated by binary operations that's equivalent as a category...

... well, at least if we restrict to algebras of cardinality $\le \kappa$, to fulfill your smallness hypothesis. (Algebras of cardinality $\le \kappa$ give an essentially small category). I feel there should be more elegant way to deal with this.

Jens Hemelaer (Dec 30 2020 at 19:37):

Yes, if $\mathcal{C}$ is a variety of algebras of cardinality $<\kappa$, then there exists a functor $F$ sending each algebra $A$ to a pair $(S_A,\mu_A)$, where $S_A$ is a set and $\mu_A$ is a binary operation on $S_A$, and such that $F$ is a fully faithful as functor from your original category to the category $\mathcal{D}$ of sets with binary operation. I don't know if the essential image of $F$ is necessarily a subvariety of $\mathcal{D}$.

Jens Hemelaer (Dec 30 2020 at 19:37):

John Baez said:

I feel there should be more elegant way to deal with this.

Yes, I agree!

Nathanael Arkor (Dec 30 2020 at 19:56):

Is $\mathcal C$ here a multisorted variety? In which case, this result says that for any locally strongly $\kappa$-presentable category $\mathcal C$, there exists a fully faithful functor $F : \mathcal C \to \mathrm{Magma}$?

Nathanael Arkor (Dec 30 2020 at 19:56):

What's the intuition behind the binary operation $\mu_A$?

Jens Hemelaer (Dec 30 2020 at 20:29):

@Nathanael Arkor Yes, sets with a binary operation are also called magma's, I forgot this terminology.

I had a single-sorted variety in mind, but the result is much stronger: any small category is a full subcategory of the category of magma's. Moreover, under some set-theoretic and class-theoretic assumptions, any concrete category is a full subcategory of the category of magma's. In this sense, the category of magma's is "universal".

I don't know the intuition behind the binary operation $\mu_A$. The proof of the result goes as follows. First it is shown that any small category (or even concrete category) can be embedded in the category of directed graphs. This is done in sevaral papers with authors including Hedrlín, Pultr, Vopěnka and Kučera. Then it was shown by Hedrlín and Pultr that the category of directed graphs is fully embedded in the category of magma's. (For references, see the introduction of this paper with @[Mod] Morgan Rogers.)

Nathanael Arkor (Dec 30 2020 at 20:51):

Ah, I was aware of the result about directed graphs, but not magmas. Do you know whether a variant holds in more general settings, such as for small enriched categories, or internal categories?

Jens Hemelaer (Dec 30 2020 at 21:23):

The first part of the proof works internal to the category of finite sets (Hedrlín and Kučera mention this in their paper). So any finite category is a full subcategory of the category of finite directed graphs and graph morphisms between them, I don't know if you can fully embed it in the category of finite magmas. I haven't looked at further generalizations in the enriched setting.

Morgan Rogers (he/him) (Dec 31 2020 at 18:12):

Jens Hemelaer said:

Nathanael Arkor Yes, sets with a binary operation are also called magma's, I forgot this terminology.

I think "magma" restricts us to associative binary operations, but I can't remember if that matters.

Dan Doel (Dec 31 2020 at 18:16):

Associative is semigroup.

Morgan Rogers (he/him) (Dec 31 2020 at 18:17):

Oops. That's the kind of assertion one should look up before sending. My bad.

Morgan Rogers (he/him) (Dec 31 2020 at 18:28):

John Baez said:

Are there other results, e.g. of a more algebraic nature, that explain why operations of arity 3 and higher are less important than binary operations?

I wonder if this can be formulated in a way which gives a definite target for a counterexample, like the formal generalised statement of Hilbert's 13th problem. That statement apparently relies on the topological and linear structures on $\mathbb{R}$, but if we work in the category of topological spaces we can make it purely categorical.

Let $\mathcal{C}$ be a category with finite products. What conditions must we impose on $\mathcal{C}$ and an object $X$ of $\mathcal{C}$ such that every morphism $X \times X \times X \to X$ can be decomposed into composites of products of morphisms which are either endomorphisms $X \to X$, binary operations $X \times X \to X$, or the diagonal map $\Delta_X : X \to X \times X$?

Morgan Rogers (he/him) (Dec 31 2020 at 18:31):

The fact that the result fails when we restrict to continuously differentiable functions suggests (this is mentioned in the post-script of the paper John shared) suggests that this is a non-trivial problem, but perhaps there are some nice general conditions one could identify.

Dan Doel (Dec 31 2020 at 19:18):

So, for instance, instead of the constructor of a ternary tree from three subtrees, one could instead have two binary operations, one which takes two trees and builds a ternary tree with any nonsense for one of the subtrees, and another which replaces whatever spot has the nonsense from the first operation with the third desired subtree.

However, my question is: how does the fact that this is possible mean that it's deserves to be a popular way of presenting ternary trees, other than a psychological bias toward binary operations? It seems needlessly convoluted, and the fact that it can be done isn't the same question as whether or not you would do it, and why.

Jason Erbele (Jan 01 2021 at 01:13):

Dan Doel said:

However, my question is: how does the fact that this is possible mean that it's deserves to be a popular way of presenting ternary trees, other than a psychological bias toward binary operations? It seems needlessly convoluted, and the fact that it can be done isn't the same question as whether or not you would do it, and why.

This isn't exactly an answer, but it might give a point of departure to look for an answer:
Why do we do any kind of decomposition into atomic pieces? I don't know about the case you are asking about, but often there are theorems that tell us we can recover interesting data from the atoms of a thing. E.g. zeros of a polynomial can be recovered by decomposing into its atoms — factoring the polynomial into its linear factors.

Morgan Rogers (he/him) (Jan 01 2021 at 12:43):

In any non-trivial situation there will be a lot more ternary operations than binary operations on an object. Knowing that ternary operations can be decomposed in this way gives a way to prove things about them using an induction argument involving essentially only binary operations. The nature of things that can be proved in this way surely depends on the nature of the answer to the question above.
It's not that it would necessarily be a useful thing to do for any specific concrete ternary operation, but rather a tool for proving things about collections of such operations.

TJ Davis (Apr 18 2021 at 22:28):

Can’t this be considered part of the adjunction $Hom(A,Hom(B,C)) \equiv Hom(A,B\times C)$ in Set? I guess for arity 3: $Hom(A,B\times C \times D) \equiv Hom(A,B \times (C \times D)) \equiv Hom(A,Hom(B,C\times D))\equiv Hom(A,Hom(B,Hom(C,D)))$?

Fabrizio Genovese (Apr 19 2021 at 09:14):

Do you mean the adjunction $Hom(A \times B, C) \simeq Hom(A, Hom(B,C))$?

TJ Davis (Apr 19 2021 at 17:19):

^Yes. I mistyped it.

Carlos Zapata-Carratala (Apr 22 2021 at 15:27):

@John Baez I have been thinking about this precise question recently. I gave a seminar in the Edinburgh category theory group where I presented some arguments that point at the very likely existence of ternary operations that cannot be reduced to binary ones: cubic matrices, ternary groups (which I would define as whatever object that integrates a 3-Lie algebra) and ternary relations.

https://www.youtube.com/watch?v=IOd-sDQ0roA&t=1064s&ab_channel=CarlosZapata-Carratala

John Baez (Apr 22 2021 at 17:23):

Nice!