There are 16 possible binary operations on a set of 2 elements. How many of these give a structure of a group?

According the following problem:

Let S be a set having exactly one element. How many different binary operations can be defined on S? Answer the question if S has exactly 2 elements exactly 3 elements exactly n elements.

there are 16 possible binary operations on a set of 2 elements. How many of these give a structure of a group? How many of the 19,683 possible binary operations on a set of 3 elements give a group structure.

2 Answers

Relevance
  • 1 decade ago
    Favorite Answer

    Well, a binary operation is a function b:S×S → S.

    How do you figure out how many of these there are?

    The total number of functions F:A → B is going to be counted quite simply. For each a in A, you need to pick a value b from B. So you have |B| choices for each |A|. So:

    Pick a1 in A, and choose b1 in B so that f(a1) = b1 (there are |B| choices).

    Pick a2 in A, and choose b1 in B so that f(a2) = b2 (there are |B| choices).

    etc. You will have |B| choices, and you will choose |A| times.

    So there are |B|^|A| choices.

    In this case, for A = S×S and B=S, you get:

    The number of B:S×S→S is |S|^|S×S| = S^(S^2)

    For S = 1, you get 1^(1^2) = 1.

    For S = 2, you get 2^(2^2) = 2^4 = 16.

    For S = 3, you get 3^(3^2) = 3^9 = 19683

    Now, how many groups of order 2 and 3 are there? Only one of each type.

    So among the 16 choices, you have to have the same "pattern" of multiplication as only a single specific group. For example, if S={a,b} then the only possibilities are these two tables:

    × | a b

    -----------

    a | a b

    b | b a

    or the same with a/b switched:

    × | b a

    -----------

    b | b a

    a | a b

    So there are 2 out of 16 that are a group.

    For the case of 3, S={a,b,c} there are three possibilities:

    × | a b c

    ----------

    a | a b c

    b | b c a

    c | c a b

    × | b a c

    ----------

    b | b a c

    a | a c b

    c | c b a

    × | c a b

    ----------

    c | c a b

    a | a b c

    b | b c a

    Basically, you MUST get the same group structure -- you just might have "a" and "b" and "c" playing different roles in the group. The only role that matters in these groups is which element is the identity -- and you only have three choices here.

    So only 3 out of the 19,683 possibilities work.

    In general, I think this question is difficult. However it is technically possible. We can arrange the elements of S in any way, so we're acting on S by permutation, however, sometimes we get repeats (in the case that n=3, it only matters who the identity is -- the other two don't matter, due to an automorphism of the group).

    So I believe (could be wrong..) that you can simply say:

    # binary relations on S = |S|^( |S|^2 )

    # that give group structure = ∑ n! / |Aut(G)|

    where G ranges over isomorphism classes of groups of order n -- not easy to classify -- and Aut(G) is the isomorphism group of the group G -- not always easy to compute.

    • Commenter avatarLogin to reply the answers
  • 6 years ago

    Can some one please list the 16 cases. I can list the following 8

    a*a -> a

    a*b -> a

    b*a -> a

    b*b -> a

    a*a -> b

    a*b -> b

    b*a -> b

    b*b -> b

    • rajesh6 years agoReport

      replace a by b and vice versa on the right side of the cases you have made.....means...
      a*a- b
      a*b- b
      b*a- b
      b*b- b
      a*a- a......likewise

    • Commenter avatarLogin to reply the answers
Still have questions? Get your answers by asking now.