Algebra - Number of Nonisomorphic Binary Structures

[ppd]

Homework Statement

(Fraleigh's Algebra, 2003, p. 36)
There are 16 possible binary structures on the set {a, b} of two elements. How many nonisomorphic (that is, structurally different) structures are there among these 16? Phrased more precisely in terms of the isomorphism equivalence relation ~/- (tilde over hyphen) on this set of 16 structures, how many equivalence classes are there? Write down one structure from each equivalence class. [Hint: Interchanging a and b everywhere in a table and then rewriting the table with elements listed in the original order does not always yield a table different from the one we started with.]

Homework Equations

A binary operation * on a set S is a function mapping S X S into S. For each (a, b) in S X S, we will denote the element *((a, b)) of S by a * b.

A binary operation on a finite set can be defined by means of a table in which the elements of the set are listed across the top as heads of columns and at the left side as heads of rows. We always require that the elements of the set be listed as heads across the top in the same order as heads down the left side. A table defines a binary operation * on a finite set S by the following rule:
(ith entry on the left) * (jth entry on the top) = (entry in the ith row and jth column of the table body)

Let us consider a binary algebraic structure <S, *> to be a set S together with a binary operation * on S.



(Please now refer to spreadsheet attachment for tables.)

The textbook states that Tables 1 and 2 are isomorphic (i.e. structurally alike) because we simply changed the names of all the entries. The textbook gives Table 3 and changes the order of column heads to make Table 4, and we see that Tables 1 and 4 are isomorphic because we simply have new names for the elements. The textbook states that Table 5 is nonisomorphic (i.e. structurally different) from Table 1 because the whole table contains a single repeated element. The textbook states that Table 6 is nonisomorphic to Table 1 because the same element appears on the upper left to lower right diagonal but Table 1 has the elements on this diagonal vary.

The Attempt at a Solution

Using tables I wrote out the possible binary structures for {a, b}. There are two tables with all a's or all b's. There are eight tables with three of a kind. There are six tables with two of each kind.

The simple answer is that because each table is distinct from the others they are all nonisomorphic to each other. For example the table of all a's is nonisomorphic to the table of all b's because in the first table everything maps to the first element of the set, in the second table everything maps to the second element. If we had a set {#, ?} and had a table with all #'s then this table would be isomorphic to the table of all a's.
But this answer seems too simple so I don't think it's correct.

Another answer is that tables with the a's and b's switched from each other are isomorphic to each other because we have renamed all the a's with b's and all the b's with a's. In this line of thought, the table with all a's is isomorphic to the table of all b's, but not to a table with three a's and one b. In this situation, there would be 8 pairs of tables that are isomorphic to each other with the a's and b's simply switching places to get the other table in each pair. But the hint the textbook gives for this problem says that interchanging a and b may give the same table!

So I feel that I am stuck because both of these lines of thought seem reasonable but I have the feeling that they are both incorrect. I want to know what is the correct method for solving the problem . Thank you.

 

[ystael]

The simple answer is that because each table is distinct from the others they are all nonisomorphic to each other. For example the table of all a's is nonisomorphic to the table of all b's because in the first table everything maps to the first element of the set, in the second table everything maps to the second element. If we had a set {#, ?} and had a table with all #'s then this table would be isomorphic to the table of all a's.
But this answer seems too simple so I don't think it's correct.

This is wrong because it doesn't use the correct meaning of "isomorphic" (see below). In particular a set is not an ordered thing -- it doesn't have a "first element" or "second element" -- precisely because there is a bijection which exchanges the two elements.

Another answer is that tables with the a's and b's switched from each other are isomorphic to each other because we have renamed all the a's with b's and all the b's with a's. In this line of thought, the table with all a's is isomorphic to the table of all b's, but not to a table with three a's and one b. In this situation, there would be 8 pairs of tables that are isomorphic to each other with the a's and b's simply switching places to get the other table in each pair. But the hint the textbook gives for this problem says that interchanging a and b may give the same table!

You are right that you should take "tables with the a's and b's switched from each other" to be isomorphic, but wrong (thus the hint) that this leads you to get eight pairs of tables. Try this process with the "take the first one" binary operation, $$x * y = x$$. If you write out the table and then exchange $$a$$ and $$b$$, you will find the table is the same.

First of all, what is an isomorphism? An isomorphism is a structure-preserving bijection. What are the bijections from $$S = \{a, b\}$$ to itself? There are two: the identity map $$\iota: S \to S$$ given by $$\iota(x) = x$$, and the exchange map $$\tau: S \to S$$ given by $$\tau(a) = b, \tau(b) = a$$. This means that each of the sixteen binary operation structures on $$S$$ is isomorphic to at most one other one; that is, you are trying to partition the set of structures into equivalence classes of size one or two, so the number $$n$$ of equivalence classes should satisfy $$8 \leq n \leq 16$$.

So you have basically the right approach. Write out the sixteen tables and try applying $$\tau$$ to each one to exchange the elements. Some of the operation tables will turn into different tables, and some will stay the same. In the former case you have an isomorphism class of size two; in the latter, a class of size one.

 

[ppd]

Thank you for your response. I appreciate your help in thinking about this problem.