1

I have this problem and I would love some feedback on some of the answers that I have gave if they are incorrect. For some that I couldn't explain can someone explain to me how answers were achieved?.

Let:

$$A = \{a,b,c,d,x\}$$

Q: How many closed binary operations on $A$ have $x$ as the identity?

A: $5^{16}$, because $9$ operations with $x$ as the identity therefore $5^{25-9}$

Q: Of the $5^{16}$ closed binary operations on $A$ where $x$ is the identity, how many are commutative?

A: $5^4 \times 5^6$, according to answer key but I am confused and no explanation offered by textbook.

Q: How many closed binary operations on $A$ have $b$ as the identity?

A: Same as when $x$ was the identity, just change of letter

Q How many closed operations on $A$ in general have an identity?

A: $5^{17}$, I don't know this too, very confused due to lack of explanation

Edit: I understand this one now thanks to Nicolas.

I am mainly in need of help for the bolded answers that I don't know how the book obtained.

Jake
  • 13
  • For the last question, first show that there can be at most one identity. So you are adding up the cases where $x$ is, where $a$ is, where $b$ is, where $c$ is, where $d$ is. As you saw earlier, there are $5^{16}$ for each type, a total of $5\times 5^{16}$. – André Nicolas Jul 19 '14 at 02:21
  • Oh boy, I can not believe I did not see that, but what about my second Q for 5^10? – Jake Jul 19 '14 at 02:24
  • This in effect was asked and answered today (not by me, I was too slow). Will find the link. You can search also. – André Nicolas Jul 19 '14 at 02:32
  • I will try to search for it too, but not knowing the title would be like searching for a needle in a haystack if you ask me. – Jake Jul 19 '14 at 02:33
  • Here it is. – André Nicolas Jul 19 '14 at 02:35
  • Just finished reading and according to the answer and in relation to my question there should first be 5^5 in the form of (x,x). However it is 5^4, why is that O.o.? – Jake Jul 19 '14 at 02:38
  • All the results $F(x,t)$ and $F(t,x)$ are determined, we have no choice. But we have $5$ choices for all pair $(t,t)$ where $t\ne x$, and $5$ choices for $(s,t)$ where $s,t$ are different, and not equal to $x$. we must make the same choice for $(t,s)$. An answer I gave to the same person, and a long discussion we had, may help. – André Nicolas Jul 19 '14 at 02:46

1 Answers1

1

Well, a closed binary operation is nothing more than a function $f:A \times A \to A$. In this context it's obvious what the total number of operations is

$$|A|^{|A \times A|} = 5^{25}$$ Where I've use abs value bars to denote cardinality. The general strategy in this situation should be to use the information we're given to realize that actually the values of $f$ are determined by it's values on only a subset.

The condition "$x$ is the identity" is one of the easiest cases. This simply fixes the values $f$ when any argument is $x$ and does nothing otherwise. Thus operations $f$ with $x$ as the identity are in the obvious bijection with functions $g: \{a,b,c,d\} \times \{a,b,c,d\} \to A$ (if it's not obvious, just take $f(s,t) = g(s,t)$ for any $s,t \in \{a,b,c,d\}$

Now we consider commutativity. Before going to the specific condition from your problem, consider the question of how many operations in general are commutative. We have $5^{25}$ total operations, but a commutative operation has the property $f(s,t) = f(t,s)$ for $t,s$ in $A$. I assume you've seen the idea of writing down the table for a binary operation. In these terms, a commutative operation gives a table symmetric about the diagonal. So it's value is determined entirely once you've written all the values on and below the diagonal. For this case, of a 5-element set, the lower triangle has $15$ elements. So there should be $5^{15}$ commutative operations.

I won't go through the argument for how to find the number of commutative operations with $x$ as identity in total detail. But note that for example the identity law $f(x,a) =f(a,x) = a$ already specifies that $f$ is commutative for any pair of elements containing $x$. So you just have to check how many of the $g$ from before are commutative.

Finally, for the number of total operations that have identity, our first guess should be that it's just five times the number of operations with a given identity (a la the first question), as we jsut sum over all possible choices of identity. But we need to check that identities are unique, so that we don't double count, I leave that to you.

jxnh
  • 5,228
  • I still don't get it, would it be too much to ask for how they got the first number 5^4? – Jake Jul 19 '14 at 02:55
  • 5^4 represents the fact that we have five choices for each of the values $f(a,a) , f(b,b), f(c,c), f(d,d)$. $4$ is the number of places in the diagonal of the table that aren't a (this mandates that $f(x,x) = x$ so we have no choice). The $5^6$ then represents filling in the ${4 \choose 2} = 6$ values that the function takes on pairs fo arguments such that (i) the arguments are distinct (We just filled in the diagonal), (ii) neither argument is $x$ (the identity property already forced us to fill those in in one way). (iii) the place on the table is below the diagonal – jxnh Jul 19 '14 at 03:01
  • (going below the diagonal is just picking out one of the pairs (a,b) vs (b,a)) as the value on these determines it all – jxnh Jul 19 '14 at 03:02
  • I again would suggest thinking about this in terms of filling out a table of the operation values. We know that $x$ is the identity, so the column and row for $x$ are already filled out. Then we can put whatever we want in the diagonal, and below it, and then because of commutativity we have to fill the part above the diagonal as a reflection. – jxnh Jul 19 '14 at 03:04
  • So I am assuming that if we never set x as the identity, then it would be 5^5 instead of 5^4 correct? :D – Jake Jul 19 '14 at 03:22
  • Correct. But the $5^6$ would also change, because we now have choices for what happens to $(a,x), (b,x), (c,x), (d,x)$ as well. – jxnh Jul 19 '14 at 03:23
  • Right, 5^10 then I assume and thanks for clarifying things! – Jake Jul 19 '14 at 03:27