# Finding sets that are not groups

Find the smallest set closed under a binary operation which has an identity and inverses, but is not a group.

I'm assuming then that associativity does not hold, or else the set along with the binary operation would be a group. How do I find such sets?

-
Usually you take a (small) finite set, make a table to define the operation. –  abatkai May 4 '12 at 19:55
Quibble: it is a type error to ask whether a set is a group. The thing that has the property of groupness is a set together with a binary operation, otherwise known as a magma. –  Qiaochu Yuan May 5 '12 at 7:13

Build one by brute force. You clearly can't do it with one element, so how about two? With $e$ as the identity, the operation table would have to be:

$$\begin{array}{c|cc}&e&a\\ \hline e&e&a\\ a&a&e \end{array}$$

This, unfortunately, gives you a group, so try it with three elements. An easy way to ensure that you have inverses is to make everything its own inverse:

$$\begin{array}{c|ccc}&e&a&b\\ \hline e&e&a&b\\ a&a&e&\\ b&b&&e \end{array}$$

You won't violate associativity in a product involving the identity, so you might try to ensure that $(ab)a\ne a(ba)$. Can you do that?

-

Obviously, it can't be a one-element set, because the only operation on such a set yields a group.

Let's take a two-element set $\{a,b\}$. One of the elements has to be an identity. Let's choose $a$. So it must be that $a\cdot a=a$ and $b\cdot a=b=a\cdot b$. Now, we need an inverse of $b$, i.e. such an element $x$ that $xb=a=bx.$ If $a=x,$ we have a contradiction. If however $b=x$, we obtain a group. So a two-element set doesn't work either.

Let's take a three-element set $\{a,b,c\}$. We clearly have to put $a\cdot a=a$, $b\cdot a=b=a\cdot b$ and $c\cdot a=c=a\cdot c.$ Now, we need an inverse for $b$. Like before, it can't be $a$. Then it must be either $b$ or $c$. There is only one group with three elements up to isomorphism, that is $G=\mathbb Z/3\mathbb Z.$ So if we choose in a different way than it is in this group we should be fine. In $G$, the non-identity elements are inverse to each other. So if we choose $b$ to be the inverse of $b$, we have a chance of doing well. So $b\cdot b=b$. Now we have to choose the inverse of $c$ and fill out the rest of the multiplication table somehow. I'm sure you can do it.

-

We can find the smallest examples using Mace4. You input the axioms "exists an identity element" and "each element has an inverse", and add the "goal" of proving associativity. Mace4 will find counter-examples.

This can be achieved by the following input:

formulas(sos).

e*x=x.
x*e=x.
x*x'=e.
x'*x=e.

end_of_list.

formulas(goals).

x*(y*z)=(x*y)*z.

end_of_list.


The output is the following on my computer (I snipped some of the output; there's quite a lot):

=== Mace4 starting on domain size 3. ===

============================== MODEL =================================

interpretation( 3, [number=1, seconds=0], [

function(e, [ 0 ]),

function(c1, [ 1 ]),

function(c2, [ 1 ]),

function(c3, [ 2 ]),

function('(_), [ 0, 1, 1 ]),

function(*(_,_), [
0, 1, 2,
1, 0, 0,
2, 0, 0 ])
]).

============================== end of model ==========================


The above says:

• an identity is $e=0$,
• associativity is violated by $c_1=1$, $c_2=1$ and $c_3=2$,
• an inversion is given by $0 \mapsto 0$, $1 \mapsto 1$ and $2 \mapsto 1$.

Modifications to the above input can yield interesting results, for example, there are $46$ non-associative binary operations on the set $\{0,1,2\}$ which admit an identity element, and for which each element has at least one inverse.

-