Simple Binary Operations Question

Problem:

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

----------

I think I'm getting a little confused with the term "element", because it seems to me, there can be an infinite amount of binary operations performed on a set that's simply non-empty.

Can't I just say $\displaystyle a * a$ and then start listing off different things the binary operation $\displaystyle *$ could be? (cos, sin, +, -, +7, literally an infinite amount of things)

Or does this problem mean element as in the arbitrary a, not being operated on with itself, and it just wants me to count the different combinations I can use the elements with? So if n=1, there are zero binary operations (or 1 if I can do a*a?). With n=2, I could do a*b, b*a, (a*a), (b*b)?

Any clarification appreciated.

Re: Simple Binary Operations Question

Quote:

Originally Posted by

**tangibleLime** Problem:

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

----------

I think I'm getting a little confused with the term "element", because it seems to me, there can be an infinite amount of binary operations performed on a set that's simply non-empty.

Can't I just say $\displaystyle a * a$ and then start listing off different things the binary operation $\displaystyle *$ could be? (cos, sin, +, -, +7, literally an infinite amount of things)

Or does this problem mean element as in the arbitrary a, not being operated on with itself, and it just wants me to count the different combinations I can use the elements with? So if n=1, there are zero binary operations (or 1 if I can do a*a?). With n=2, I could do a*b, b*a, (a*a), (b*b)?

Any clarification appreciated.

I think you're misinterpreting $\displaystyle S$ to be $\displaystyle \mathbb{R}$. For example, if $\displaystyle S=\{\text{cow,chicken,dog}\}$ what does $\displaystyle +$ even mean? So think about it, forget the rule that actually defines the operation, a binary operation on a set $\displaystyle S$ is merely (assuming you just mean ANY operation, not associative) a mapping $\displaystyle S\times S\to S$. So, the question could really be stated as "If $\displaystyle \text{card}(S)=n$ how many mappings $\displaystyle S\times S\to S$ are there?" Does that help?

Re: Simple Binary Operations Question

Thanks, that does help.

So I'll take the cardinality of S and set that to $\displaystyle n$. I think that the problem wants me to find all of the permutations of the elements, which would be $\displaystyle n!$... but since a binary operation (I assume by the word "binary") only has two elements at a time, I need to use the formula,

$\displaystyle \frac{n!}{(n-k)!}$

Correct?

Re: Simple Binary Operations Question

Quote:

Originally Posted by

**tangibleLime** Thanks, that does help.

So I'll take the cardinality of S and set that to $\displaystyle n$. I think that the problem wants me to find all of the permutations of the elements, which would be $\displaystyle n!$... but since a binary operation (I assume by the word "binary") only has two elements at a time, I need to use the formula,

$\displaystyle \frac{n!}{(n-k)!}$

Correct?

Not quite. I'm actually not sure how you actually arrived at that. So, let's talk more generally. If $\displaystyle X$ has $\displaystyle n$ elements and $\displaystyle Y$ has $\displaystyle m$ elements then how many functions $\displaystyle f:X\to Y$ are there? Well, it's pretty easy to see that what $\displaystyle x\in X$ and $\displaystyle x'\in X$ get mapped to are entirely indpendent events. So, if $\displaystyle X=\{x_1,\cdots,x_n\}$ then it should be pretty clear that the number of mappings $\displaystyle X\to Y$ is equal to $\displaystyle v_1\cdots v_n$ where $\displaystyle v_k$ is the number of different elements $\displaystyle x_k$ can get mapped to in $\displaystyle Y$. Well, it's pretty clear that for a general function any element of $\displaystyle X$ can get mapped to any element of $\displaystyle Y$ and so in particular $\displaystyle v_k=m$ for each $\displaystyle k\in\{1,\cdots,n\}$. So, the total number of mappings $\displaystyle X\to Y$ should be equal to $\displaystyle v_1\cdots v_n=m\cdots m=m^n$. Make sense?

Can you conclude now?

Re: Simple Binary Operations Question

Okay, I think I got it.

I was using [tex]\frac{n!}{(n-k)!} because I thought it wanted all of the different combinations of mixing the elements in S with each other.

For example, if S={a, b, c}, then the following binary operations are possible:

a*b

a*c

a*a

b*a

b*c

b*b

c*a

c*b

c*c

Which... now that I look at it, is $\displaystyle n^{n}$, which is what you came up with. Maybe I was just incorrect in the permutation aspect... am I thinking about this the right way as I just explained?

Thanks!

Re: Simple Binary Operations Question

Quote:

Originally Posted by

**tangibleLime** Okay, I think I got it.

I was using [tex]\frac{n!}{(n-k)!} because I thought it wanted all of the different combinations of mixing the elements in S with each other.

For example, if S={a, b, c}, then the following binary operations are possible:

a*b

a*c

a*a

b*a

b*c

b*b

c*a

c*b

c*c

Which... now that I look at it, is $\displaystyle n^{n}$, which is what you came up with. Maybe I was just incorrect in the permutation aspect... am I thinking about this the right way as I just explained?

Thanks!

Not really. You are focusing too much on a particular operation. Consider this let $\displaystyle S=\{a,b\}$ consider the following operations

$\displaystyle \begin{array}{c|cc} \star & a & b\\ \hline a & a & a\\ b & a & a\end{array}\quad \begin{array}{c|cc} \ast& a & b\\ \hline a & b & a\\ b & a & b\end{array}\quad\begin{array}{c|cc} \oplus& a & b\\ \hline a & b & b\\ b & a & a\end{array}$

Then, the FUNCTIONS $\displaystyle \ast:S\times S\to S$, $\displaystyle \star:S\times S\to S$, and $\displaystyle \oplus:S\times S\to S$ are examples of binary operations which to reiterate are FUNCTIONS. So, we know that the number of binary operations (...functions...) is at least $\displaystyle 3$ since we have just found three different ones. If counting the functions is hard to you, you can really just count the number of ways to fill those $\displaystyle 2\times 2$ tables I made in. Does that help?

Re: Simple Binary Operations Question

OH, okay, it makes PERFECT sense now. I was thinking about it in the wrong manner. Thanks for the clarification!

Re: Simple Binary Operations Question

Quote:

Originally Posted by

**tangibleLime** OH, okay, it makes PERFECT sense now. I was thinking about it in the wrong manner. Thanks for the clarification!

Anytime ;)