1
$\begingroup$

Let $S=\{1,2,\ldots,11\}$. Find number of binary operations $\circ:S\times S\rightarrow S$ such that $\circ$ is commutative, associative, and $$a\circ b=a\circ c\Rightarrow b=c,$$ $$ab\leq11\Rightarrow a\circ b=ab.$$

I can only approach this problem by listing all $ab>11$, which becomes undoably tedious, so I'm stuck. I'm wondering if there is any theorem or technique that I can apply to this problem.

$\endgroup$
  • $\begingroup$ It's associative, has an identity element ($1\circ a=a$ for all $a$), and has cancellation. Can it be anything other than the group operation on a group of 11 elements? $\endgroup$ – Gerry Myerson Sep 7 '16 at 13:27
  • $\begingroup$ There is a result that the number of different binary operations defined on a finite set $S$ such that $|S|=n$ is $n^{n^2}$ and the number of commutative binary operations on $S$ is $n^{\frac{n(n+1)}{2}}$. $\endgroup$ – StubbornAtom Sep 7 '16 at 13:31
  • $\begingroup$ @StubbornAtom But there are two other restrictions. How do I do this then? $\endgroup$ – Colescu Sep 7 '16 at 13:38
  • $\begingroup$ That is what we have to think about. $\endgroup$ – StubbornAtom Sep 7 '16 at 13:40
  • 1
    $\begingroup$ @YuxiaoXie: Look at Gerry Myerson’s hint: he practically told you the answer. $\endgroup$ – Brian M. Scott Sep 7 '16 at 17:36
1
$\begingroup$

Maybe there's an elegant solution, but this is messier than I expected it to be. If I haven't missed any cases, I get 14 different binary operations satisfying the required property. (Of course, there's only one solution up to isomorphism, but that's not what the problem asked for.)

First observe that $\langle S, \circ\rangle$ is an Abelian group. We already know that it's associative and commutative. The rule that $ab\leq11\Rightarrow a\circ b=ab$ implies that $1$ is an identity. So all that's left to show that $S$ is an Abelian group is that every element has an inverse.

But if $a$ is any element of $S,$ then the cancellation law tells us that the function $x \to a \circ x$ is one-to-one. Any one-to-one function from a finite set to itself must be onto. So there exists some $x\in S$ such that $a\circ x = 1.$ By commutativity, $x$ is an inverse of $a.$

So $S$ is an Abelian group. Since it's of prime order, it must be cyclic.

If $G$ and $H$ are any two cyclic groups of prime order, and if $a\in G$ and $b \in H$ are not the identity (in their respective groups), then there is a unique isomorphism $f \colon G \to H$ such that $f(a)=b,$ given by $f(a^n)=b^n$ for all integers $n.$

So there is a unique isomorphism $f \colon \langle S,\circ \rangle \to \langle \mathbb{Z}_{11},+ \rangle$ such that $f(2)=1.$

We have:

$$f(1)=0$$

$$f(2)=1$$

$$f(4)= 2$$

$$f(8) = 3$$

The remaining values $f(x)$ for $x=3, 5, 6, 7, 9, 10, 11$ must be $4, 5, 6, 7, 8, 9, 10,$ in some order (and so must be distinct).

We have

$$f(6)=f(3 \circ 2) = f(3)+f(2) = f(3)+1 \,(\operatorname{mod} 11)$$

$$f(9)= f(3\circ 3) = 2 f(3)\,(\operatorname{mod} 11)$$

Now, $f(3)$ can't be $6$ or $7,$ since then $f(9)$ would be $1$ or $3.$ Also, $f(3)$ can't be $10,$ since then $f(6)$ would be $0.$ So here is a table of possible values for $f(3), f(6),$ and $f(9)\!:$

\begin{array} &f(3) & f(6) &f(9) \\ \hline 4&5&8 \\5&6&10 \\8&9&5 \\9&10&7 \end{array}

We also know that $f(10)=f(5)+1.$ For each possible value of $f(3),$ we can enumerate the values for $f(5)$ and $f(10)$ that work:

\begin{array} &f(3) & f(6) & f(9) & f(5) & f(10) \\ \hline 4&5&8 &6&7 \\ 4&5&8 &9&10 \\5&6&10 &7&8 \\5&6&10 &8&9 \\8&9&5 &6&7 \\9&10&7 &4&5 \\9&10&7 &5&6 \end{array}

The remaining two possibilities in each row must be $f(7)$ and $f(11)\!:$

\begin{array} &f(3) & f(6) & f(9) & f(5) & f(10) &f(7)\text{ and }f(11)\text{ in either order} \\ \hline 4&5&8 &6&7 &9\text{ and }10 \\ 4&5&8 &9&10 &6\text{ and }7 \\5&6&10 &7&8 &4\text{ and }9 \\5&6&10 &8&9 &4\text{ and }7 \\8&9&5 &6&7 &4\text{ and }10 \\9&10&7 &4&5 &6\text{ and }8 \\9&10&7 &5&6 &4\text{ and }8 \end{array}

So this gives 14 possible isomorphisms $f,$ two for each row, depending on whether $f(7)$ and $f(11)$ are as written in the table above or reversed.

In fact, each such function $f$ is a bijection that induces a binary operation $\circ_f$ on $S$ which satisfies the criterion -- specifically, $x \circ_f y = f^{-1}((f(x) + f(y)) \,(\operatorname{mod} 11)).$ The function $f \colon \langle S,\circ_f \rangle \to \langle \mathbb{Z}_{11}, + \rangle$ is an isomorphism.

Finally, if $f$ and $g$ are distinct functions as above, then $\circ_f \ne \circ_g,$ since otherwise $f \circ g^{-1}$ would be an isomorphism of $\mathbb{Z}_{11}$ with itself which maps the (non-zero) element $1$ to the element $1,$ but which is not the identity.

It follows that there are 14 binary operations with the required properties.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.