Is every associative $n$-ary operation with an identity element induced by a monoid?

115 Views Asked by At

Given any $n$-ary operation $*$ on a set $X$, an identity element for $*$ is an element $e \in X$ such that $x*e*e*...*e=e*x*e*e*...*e=...=e*e*...*e*x=x$ ($n-1$ $e$s in each product) for all $x \in X$. Also, $*$ is said to be associative if the $n$ possible ways to put parentheses around $n$ consecutive factors from any product of $2n-1$ factors under $*$ all lead to equal products.

Now, in the ternary case, one could prove that if $*$ is associative and has an identity element, then the three products $e*a*b$, $a*e*b$, and $a*b*e$ are all equal and that the ternary operation induced by the resulting binary operation is just $*$. Also, the resulting binary operation would then define a monoid.

Proof that the three induced binary operations are all the same

$e*a*b=e*a*(e*e*b)=(e*a*e)*e*b=a*e*b=a*e*(e*b*e)=(a*e*e)*b*e=a*b*e$

Proof that the resulting binary operation defines a monoid and induces $*$

All three possible ways of defining the binary product $a*b$ have already been proven to be equal, so let's just use $a*e*b$.

Associativity: $(a*b)*c=(a*e*b)*e*c=a*e*(b*e*c)=a*(b*c)$

Identity: $e*a=e*e*a=a$ and $a*e=a*e*e=a$

Induced ternary operation: $(a*b)*c=(a*e*b)*e*c=a*(e*b*e)*c=a*b*c$

$n$-ary generalization

Do the above arguments generalize to the $n$-ary case for any $n \ge 3$? In general, there would be $\binom{n}{2}$ ways to define the corresponding binary operation from the $n$-ary operation $*$, and one would then need to prove that those $\binom{n}{2}$ binary operations are all the same and that the binary operation defines a monoid whose induced $n$-ary operation is just $*$.

1

There are 1 best solutions below

0
On

Yes, this generalizes to any $n$ fairly straightforwardly. More strongly, let me prove by induction on $k$ that for each $k\leq n$ all of the $k$-ary operations given by letting $n-k$ of the inputs be $e$ are equal. Moreover, writing $p_k$ for this unique $k$-ary operation, they satisfy $$p_{k+1}(a_1,\dots,a_{k+1})=p_2(a_1,p_k(a_2,\dots,a_{k+1}))=p_2(p_k(a_1,\dots,a_k),a_{k+1}).$$ From this it follows in particular that $p_2$ is associative and each $p_k$ is just the $k$-fold multiplication induced by $p_2$.

The cases $k\leq 1$ are trivial. Now suppose we know we have a unique operation $p_k$ and consider a product $$x=a_1*\dots*a_n$$ where all but $k+1$ of the inputs are equal to $e$. The idea is then that we can repeatedly use associativity and the fact that we can rearrange a product in which all but one input is $e$ to move the last nontrivial input in $x$ to the end of the double product $x*e*\dots*e$. More precisely, if the last nontrivial input is $a_j$, we have $$\begin{align*} x&=x*e*\dots*e \\ &=a_1*\dots *a_{j-1}*(a_{j}*e\dots*e)*e\dots*e \\ &=a_1*\dots *a_{j-1}*(e*\dots*e*a_{j})*e\dots*e \\ &=a_1*\dots *a_{j-1}*e*\dots*(e*\dots *a_{j}*\dots *e) \\ &=a_1*\dots *a_{j-1}*e*\dots*(e*\dots *e*a_{j}) \\ &=(a_1*\dots *a_{j-1}*e*\dots*e)*e*\dots*e*a_{j}.\end{align*}$$ If the $k+1$ nontrivial inputs to $x$ are $b_1,\dots,b_{k+1}$, this last expression is equal to $p_k(b_1,\dots,b_k)*e*\dots*e*b_{k+1}$ and so in particular is independent of the placement of the nontrivial inputs to $x$ and thus this shows we have a unique operation $p_{k+1}$. This also shows that $p_{k+1}(b_1,\dots,b_{k+1})=p_2(p_k(b_1,\dots,b_k),b_{k+1})$, and $p_{k+1}(b_1,\dots,b_{k+1})=p_2(b_1,p_k(b_2,\dots,b_{k+1}))$ can be proved similarly.