1
$\begingroup$

My question stems from the following question: How many non-isomorphic binary structures on the set of $n$ elements?

It goes on to say that for the $16$ possible binary structures on the set $\{a,b\}$ the number of non-isomorphic structures is $10$. It is also suggested here on a physics forum: https://www.physicsforums.com/threads/algebra-number-of-nonisomorphic-binary-structures.451977/

However, when I try the problem myself, I cannot see why this is the case. I have drawn out the $16$ possible tables and flip $a$ and $b$ in each to see that there are $8$ pairs. I have been trying to figure out the various hints and clues in the two links provided but the more and more I try thinking about them the more and more I want to keep saying my answer is correct and theirs are wrong, but I know that cannot be the case. The first link talks about the number of "invariant" structures but I do not know what that means.

This question also appears in Fraleigh's A First Course In Abstract Algebra.

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$?

Why is the answer to this $10$ and not $8$? I don't see how flipping $a$ and $b$ could ever result in a different structure, so how can we have more than $8$?

Any help would be greatly appreciated.

$\endgroup$
  • $\begingroup$ Did you consider the cases where you only use $a$'s or only use $b$'s? As in, everything maps to $a$ or everything maps to $b$? $\endgroup$ – Alerra Sep 18 '18 at 23:34
  • $\begingroup$ Have you actually tried to identify each of your 8 pairs in your list of 16 possible tables? In other words, don't just take for granted that the 16 tables form 8 pairs. Go through them one by one and see how they pair up. You may notice something funny... $\endgroup$ – Eric Wofsey Sep 18 '18 at 23:36
  • $\begingroup$ @Eric Wofsey I have the four pairs where there is one different element in each corner and the same in the remaining slots, the three pairs of two of each (top / bottom rows same, left / right columns same, and diagonals same) and the pair where all are the same. Am I missing something here? $\endgroup$ – WaveX Sep 18 '18 at 23:39
  • $\begingroup$ Oh, I see. You're forming the pairs wrong. I'll elaborate in an answer. $\endgroup$ – Eric Wofsey Sep 18 '18 at 23:45
1
$\begingroup$

$\newcommand{bintable}[4]{\begin{array}{c|cc} & a & b\\ \hline a & #1 & #2 \\ b & #3 & #4 \\ \end{array}}$ To determine if two multiplication tables on $\{a,b\}$ give isomorphic structures, you do not just check if one is obtained from the other by swapping $a$ and $b$ in the four entries of the table. Instead, you need to swap $a$ and $b$ in the inputs as well (that is, swap the two rows and swap the two columns). For example, the following two multiplication tables are isomorphic: $$\bintable aaab$$ $$\bintable abbb$$ The first table can be thought of as multiplication on $\{0,1\}$ with $a=0$ and $b=1$, while the second is multiplication on $\{0,1\}$ with $a=1$ and $b=0$. They are isomorphic structures by the bijection $\{a,b\}\to\{a,b\}$ that swaps $a$ and $b$, but notice that to turn one into the other, you don't just swap the four entries in the middle, but also the rows and the columns.

Why does this make a difference for counting how many isomorphism classes there are? Well, it causes there to be some multiplication tables that stay the same when you swap $a$ and $b$. For instance, $$\bintable aabb$$ does not change if you swap $a$ and $b$ in this way. More intuitively, this is the binary operation where $xy=x$ for all $x$ and $y$. That binary operation will still have the same description even if you relabel the elements of the set: it's still the binary operation that just outputs the first input, no matter what.

So, since some multiplication tables stay the same upon swapping $a$ and $b$, they don't form pairs. If you work it out, you'll find that there are $4$ tables that stay the same when you swap $a$ and $b$, and $12$ other tables which change and thus form $6$ pairs. That makes $4+6=10$ total multiplication tables up to isomorphism.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think I'm seeing what to do now. But does this mean two tables that simply swap a's and b's are not necessarily isomorphic? $\endgroup$ – WaveX Sep 19 '18 at 2:05
  • $\begingroup$ Yes, that's correct. For instance, the table $\bintable aaab$ is not isomorphic to $\bintable bbba$. We can see this because in the first table, every element is its own square, but that is not true in the second table. $\endgroup$ – Eric Wofsey Sep 19 '18 at 2:06
  • $\begingroup$ So basically to truly figure out the pairs, I need to not only switch $a$ and $b$ on the inside, but also in the table headers as well, then rearrange it so the header is in the original order? $\endgroup$ – WaveX Sep 19 '18 at 2:29
  • $\begingroup$ Exactly. ${}{}{}$ $\endgroup$ – Eric Wofsey Sep 19 '18 at 2:33
1
$\begingroup$

$\newcommand{\bintable}[4]{\begin{array}{c|cc} & a & b\\ \hline a & #1 & #2 \\ b & #3 & #4 \\ \end{array}}$

Let $S=\{a,b\}$. There are only two one-to-one functions mapping $S$ onto $S$, $\iota: S \rightarrow S$ and $\phi: S \rightarrow S$, defined as: $$ \iota(a) = a\quad \iota(b) = b, $$ $$ \phi(a) = b\quad \phi(b) = a. $$ If $\langle S, * \rangle$ is a binary structure, then $\iota: S \rightarrow S$ is an isomorphism of $\langle S, * \rangle$ with $\langle S, * \rangle$. If we take table $$\bintable abba$$ function $\iota$ maps the table exactly to itself. Isomorphism is an equivalence relation, meaning that any binary structure is isomorphic to itself. What important here is that $\langle S, * \rangle$ is the same binary structure before and after mapping with $\iota$.

If $\langle S, * \rangle$ and $\langle S, *^\prime \rangle$ are binary structures, then $\phi: S \rightarrow S$ is an isomorphism of $\langle S, * \rangle$ with $\langle S, *^\prime \rangle$. The same table, now representing $\langle S, * \rangle$, $$\bintable abba$$ becomes table, representing $\langle S, *^\prime \rangle$, $$\bintable baab$$ under $\phi$. We replaced every element in the table (including the headers) applying the rule of $\phi$. The binary structures $\langle S, * \rangle$ and $\langle S, *^\prime \rangle$ are isomorphic, but different, because $a * a = a$, but $a *^\prime a = b$.

However, if we take table $\langle S, * \rangle$ $$\bintable aabb$$ and apply $\phi$, it gives the table $\langle S, *^\prime \rangle$ $$\bintable aabb$$ The tables are identical, which means that the binary structures they describe are equal, that is, $$ a * a = a *^\prime a = a$$ $$ a * b = a *^\prime b = a$$ $$ b * a = b *^\prime a = b$$ $$ b * b = b *^\prime b = b$$ This shows that $* = *^\prime$.

Relating it all back to the question, rearranging the rows and columns after swapping the elements in the tables is done to see what binary stuctures stay unchanged (are invariant) under $\phi$. But just because they are invariant, it doesn't mean they are not isomorphic. Those four invariant tables map to itself under both $\iota$ and $\phi$, making an equivalence class with the only element - themselves.

| cite | improve this answer | |
$\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.