binary operation on a set

Printable View

May 27th 2010, 04:48 PM
oldguynewstudent

binary operation on a set

Given a set S, a function f: S X S $\longrightarrow$ S is called a binary operation on S. If S is a finite set, then how many different binary operations on S are possible?

I have no clue on this one? Could someone point me in the right direction?

I realize that if S has n elements then SxS would have $n^2$ possible ordered pairs. However, I'm not sure what is meant by how many different binary operations. Would we have addition, subtraction, multiplication, division, exponentiation, etc. times $n^2$ binary operations?
May 27th 2010, 07:28 PM
Drexel28

Quote:

Originally Posted by oldguynewstudent

Given a set S, a function f: S X S $\longrightarrow$ S is called a binary operation on S. If S is a finite set, then how many different binary operations on S are possible?

I have no clue on this one? Could someone point me in the right direction?

I realize that if S has n elements then SxS would have $n^2$ possible ordered pairs. However, I'm not sure what is meant by how many different binary operations. Would we have addition, subtraction, multiplication, division, exponentiation, etc. times $n^2$ binary operations?

It's asking how many functions are there from a set with $n^2$ elements to a set with $n$ elements.
May 28th 2010, 05:18 AM
oldguynewstudent

Quote:

Originally Posted by oldguynewstudent

Given a set S, a function f: S X S $\longrightarrow$ S is called a binary operation on S. If S is a finite set, then how many different binary operations on S are possible?

With the help of Drexel28, we have a set S with n elements which gives $n^2$ mapped to n. This should give us $n^3$ binary operations, correct?
May 28th 2010, 05:28 AM
aman_cc

Quote:

Originally Posted by oldguynewstudent

With the help of Drexel28, we have a set S with n elements which gives $n^2$ mapped to n. This should give us $n^3$ binary operations, correct?

Shouldn't it be (n)^(n^2)
June 16th 2012, 04:50 PM
rcopher6

Re: binary operation on a set

Yes I believe that (n)^(n^2) is correct
June 16th 2012, 09:12 PM
Deveno

Re: binary operation on a set

in general, the number of functions f:A→B is:

|B|^|A|.

it is easiest to see this when |B| = 2, such as when B = {0,1}, so that the functions f:A→{0,1} can be put in a 1-1 correspondence with the subset of A:

given a subset S of A, we define:

f(a) = 1, if a is in S
f(a) = 0, if a is not in S.

thus the number of functions f:A→{0,1} is the same number as 2^|A|, the cardinality of the power set of A.

so, yes, the correct answer is n^(n²).