analogue of a set with n binary operations - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T06:48:07Z http://mathoverflow.net/feeds/question/110378 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110378/analogue-of-a-set-with-n-binary-operations analogue of a set with n binary operations joe 2012-10-23T00:52:17Z 2012-10-23T17:32:42Z <p>So a group is a type of structure with one binary operations that satisfies some list of axioms. A ring is a structure that has two binary operations that satisfy some list of axioms. Do there exist structures with n, independent (meaning it isn't possible to decompose the structure into collections of structures with two or less binary operations), binary operations that satisfy some list of axioms? Is it possible to define a consistent structure of this sort? If someone could point me in the direction of an article or something, or offer your own point of view, I would appreciate it.</p> http://mathoverflow.net/questions/110378/analogue-of-a-set-with-n-binary-operations/110379#110379 Answer by Roy Maclean for analogue of a set with n binary operations Roy Maclean 2012-10-23T01:03:40Z 2012-10-23T02:03:19Z <p>The study of sets with an arbitrary number of operations is called <a href="http://en.wikipedia.org/wiki/Universal_algebra" rel="nofollow">universal algebra</a>.</p> <p>Also universal algebra isn't limited to binary operations but studies operations of any arity: nullary, unary, binary, ternary, ... , n-ary.</p> <p>(Universal algebra does however typically restrict itself to axioms that are defined by equations which means fields are excluded from this way of studying algebra.)</p> <p>Beware however that operations that are ostensibly independent might not be. See for example the earlier mathoverflow question: <a href="http://mathoverflow.net/questions/57465/can-we-unify-addition-and-multiplication-into-one-binary-operation-to-what-exten" rel="nofollow">Can we unify addition and multiplication into one binary operation? To what extent can we find universal binary operations?</a></p> <p>In a ring the distributive law connects the addition and multiplication operations, so that they cannot in a sense be independent, but there is nothing to stop a structure of n operations from being consistent if none of the axioms connect any of the operations to each other. Like Gerhard Paseman comments about, it depends what you mean by independent. </p> <p>Questions along similar lines to the linked question about universal operations could be asked about any given universal-algebraic variety - given a variety in which every operation is connected to the other operations by axioms, then to what extent can the number of operations be reduced and still define the same class of structures. For questions about reducing the number of operations or axioms see <a href="https://www.cs.unm.edu/~mccune/projects/gtsax/" rel="nofollow">https://www.cs.unm.edu/~mccune/projects/gtsax/</a></p> <p>P.S. I'll mention here as a curiosity the topic of n,m-operations. That is operations that not only have a domain-arity but also a co-domain arity. e.g. $*:G \times G \times G \rightarrow G \times G$. Concepts such as associativity can be generalized to n,m-operations but n,m-operations haven't been studied much in universal algebra.</p> http://mathoverflow.net/questions/110378/analogue-of-a-set-with-n-binary-operations/110386#110386 Answer by Aaron Meyerowitz for analogue of a set with n binary operations Aaron Meyerowitz 2012-10-23T05:57:55Z 2012-10-23T16:46:30Z <p>I don't know that there is anything as nice as the way that the two main operations in a ring fit together. However there are ways to introduce many linked operations which, while mainly done for the purpose of doing so, are perhaps not <em>too</em> overly frivolous. Here is one:</p> <p>Given a finite set $S$ with $k$ elements, there are $k^{k^2}$ binary operations and each operation $\diamond$ can be represented by its Cayley Table the $k \times k$ square with $i,j$ entry $i \diamond j$ (assuming a known order). This single operation defines a quasi-group if the table is a Latin Square, each symbol appears once in each row and column. Equivalently (and without an agreed order), for every $a,b$ there are unique $x,y$ with $x \diamond a=b$ and $a \diamond y=b.$ This defines two operations $y=a \backslash b$ and $x=b / a$ with $$b=a \diamond (a \backslash b)=a \backslash (a \diamond b)=(b /a) \diamond a=(b \diamond a) / a.$$ This equational definition of a quasi-group via 3 operations is available for infinite quasi-groups as well. If we introduce the projections $a\pi_1b=a$ and $a\pi_2b=b$ then we can write the previous equations as $$a\pi_2b=(a\pi_1b)\diamond(a\backslash b)=\cdots$$</p> <p>Two Latin Squares (given by quasigroups $(S,\cdot)$ and $(S,\diamond)$) are <em>orthogonal</em> if the map $(x,y) \to (x\cdot y,x\diamond y)$ is a bijection from $S \times S$ to itself. It is not known how many pairwise orthogonal quasi-groups (aka Mutually Orthogonal Latin Squares <strong>MOLS</strong>) are possible on a set of size $k.$ Certainly no more than $k-1$ and this is possible when (and perhaps only when) $k$ is a prime power. </p> <p>So I suppose that a set of $t$ <strong>MOLS</strong> on the same set could be described as $t$ operations $\diamond_i$ whose individual quasi-group nature is asserted (as before) using another $2t$ operations $a \backslash_i b$ and $a/_i b$ (along with $\pi_1$ and $\pi_2$) and whose pairwise orthogonality is specifieded using a further $t(t-1)$ operations $\leftarrow_{ij}$ and $\rightarrow_{ij}$ so that $x=a \leftarrow_{ij}b$ and $y=a \rightarrow_{ij} b$ satisfy $(x\diamond_iy,x\diamond_jy)=(a,b).$ Or, if we have no shame, $$((a \leftarrow_{ij}b)\diamond_i(a \rightarrow_{ij} b),(a \leftarrow_{ij}b)\diamond_j(a \rightarrow_{ij} b))=(a\pi_1b,a\pi_2b).$$</p> <p>On one hand $\leftarrow_{ij}=\rightarrow_{ji}$ so maybe a total count of $t^2+2t+2$ is too greedy. On the other hand, maybe more operations such as $a\diamond^i b=b\diamond_ia$ could be shoehorned in. But I will stop there.</p> http://mathoverflow.net/questions/110378/analogue-of-a-set-with-n-binary-operations/110391#110391 Answer by Martin Brandenburg for analogue of a set with n binary operations Martin Brandenburg 2012-10-23T06:45:15Z 2012-10-23T14:37:26Z <p>For every symmetric monoidal category $C$ the category of commutative monoids $\mathrm{CMon}(C)$ is again symmetric monoidal, the forgetful functor to $C$ being a monoidal functor. Thus we may iterate this construction and define $\mathrm{CMon}^{(n)}(C)$ for all $n \in \mathbb{N}$. Intuitively, objects of this category have $n$ commutative operations which are compatible with each other. However, this sequences already terminates at $n \geq 1$. Every commutative monoid in $C$ has a unique structure as an object in $\mathrm{CMon}(C)$.</p> <p>For example, for $C=\mathrm{Ab}$, starting with abelian groups ($n=0$), next we get commutative rings ($n=1$). But for a commutative ring $R$ there is exactly one unit $u : \mathbb{Z} \to R$ and exactly one ring homomrphism $\mu : R \otimes R \to R$ making it into a commutative monoid of commutative rings, namely $u(z)=z \cdot 1_R$ and $\mu(a \otimes b)=a \cdot b$.</p> <p>This explains a little bit why there are so few structures with three or more binary operations.</p> http://mathoverflow.net/questions/110378/analogue-of-a-set-with-n-binary-operations/110450#110450 Answer by Gerhard Paseman for analogue of a set with n binary operations Gerhard Paseman 2012-10-23T17:32:42Z 2012-10-23T17:32:42Z <p>I've decided to expand my comment since I like my interpretation of your idea of independence.</p> <p>Let's use the language of universal algebra, where we take a well understood case of an underlying set A and some system F of total functions f of finite arity n (so $f:A^n\longrightarrow A)$. For increased graspibility, I will assume A is a finite set and F is a finite nonempty tuple, where in the question all the functions in F have $n=2$, but I will allow $n$ the freedom to vary.</p> <p>One reading of the poster's notion of independence is related to indecomposability of F: given A,F (I am omitting the brackets of the traditional notation), it should not be able to represent it in a nontrivial fashion as some amalgam of A,G and A,H, where G and H are smaller tuples. (I will pretend that the mechanism of tuple concatenation is not allowed, e.g. F = G concat H is illegal.) In particular, each f in F is not derivable from the other operations in F. Using 1 in A as a symbol for a constant function, which I will also call a function of arity 0, the algebras A,+,%,1 and A,+,%,1,g are different, but if g is essentially the function derived from the term (x%(x+1)), then the second algebra does not meet the notion of independence.</p> <p>A fuller exposition of this notion can be seen in looking at certain closed collections of functions on A, called clones. At <a href="http://en.wikipedia.org/wiki/Post" rel="nofollow">http://en.wikipedia.org/wiki/Post</a>'s_lattice one can see containment relations as well as lists of generators for each clone. Most of the generators are binary functions, but some functions of higher arity are needed since there are infinitely many classes of such functions. By itself, each generating tuple F is a tuple for such an independent algebra {0,1},F .</p> <p>Now for larger sets, there are larger examples, including the n-quasigroup examples suggested by Aaron Meyerowitz. It is not clear to me that such examples are independent in the above sense, however. There are also n-semilattices as well as lattices enriched with n extra binary operations; I will let you search the general algebra literature for those.</p> <p>There are also primal algebras, which have F as a one-tuple on a finite set A, such that the single (usually binary) function f in F can generate all other functions on A. Also there are quasiprimal algebras which are like primal algebras, except their clones are maximal but incomplete: adding any other function outside their clone to the signature F would generate the clone of all functions.</p> <p>This may read more like an advertisement for clone theory than an answer, but the post did ask for other points of view.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2012.10.23</p>