Let A 1,2
Find the number of binary operations that can be defined on A
Answers
Step-by-step explanation:
What is the number of binary operations on the set {1, 2, 3}?
Become a certified electric vehicle engineer.
A binary operation on a set S is a function from S^2 to S.
Now let’s find the cardinality of T^S, the set of functions from S to T.
But let’s start from the beginning. Let S a finite set and T a non empty set and y an element of T.
f:S→S×{y}
x→f(x)=(x,y)
Let x,x’ in S such that f(x)=f(x’)
(x,y)=(x’,y)<=> x=x’ thus f is injective.
Now, for all z in S×{y}, there exists an x in S such that z=(x,y)=f(x). Thus f is surjective.
f being injective and surjective is bijective, and |S×{y}|=|S|
Now, let S and T two finite sets such that |T|=n
T={y1,…yn} with yi != yj for i != j
Thus T=U(i=1,n)({yi})
Thus, |S×T|=|S×U(i=1,n){yi}|=|U(i=1,n)(S×{yi})|=Σ(i=1,n)(|S×{yi}|)=Σ(i=1,n)(|S|)=n|S|=|S|×|T|
Now, for n>=2, let S1,…., Sn finite sets.
For n=2, |S1×S2|=|S1|×|S2|.
Suppose that |Π(i=1,n)(Si)|=Π(i=1,n)(|Si|)
Let’s prove that |Π(i=1,n+1)(Si)|=Π(i=1,n+1)(|Si|)
|Π(i=1,n+1)(Si)|=|(Π(i=1,n)(Si))×S(n+1)|=|Π(i=1,n)(Si)|×|Si|=(Π(i=1,n)(|Si|))×|S(n+1)|=Π(i=1,n+1)(|Si|)
Thus, |Π(i=1,n)(Si)|=Π(i=1,n)(|Si|)
Now, back to where we started: Let S and T two finite sets such that |S|=n.
S={x1,…xn} with xi != xj for i != j.
φ:T^S→T^n
f→φ(f)=(f(x1),….,f(xn))
Let f and g in T^S such that φ(f)=φ(g)
(f(x1),….,f(xn))=(g(x1),….,g(xn))
<=> f(xi)=g(xi) for all int i between 1 and n <=> f=g
Thus φ is injective.
Let Y=(y1,…,yn) in T^n
And f:S→T
xi→ f(xi)=yi for all int i between 1 and n
Y=(f(x1),….,f(xn))=φ(f)
Thus φ is surjective.
Being injective and surjective, φ is bijective.
Thus, |T^S|=|T^n|=|Π(i=1,n)T|=Π(i=1,n)|T|=|T|^n=|T|^|S|
Thus there are |S|^(|S^2|)=|S|^(|S×S|)=|S|^(|S|×|S|)=|S|^(|S|^2) binary operations on a finite set S.
In the case of {1,2,3}, there are 3^(3^2)=3^9=19683 binary operations in {1,2,3}.
hope it helps you