1
$\begingroup$

I am asked to show that there are exactly $(n+1)^{n^2}$ partial binary operations on a finite set of n elements.

My professor said that this can be done using a combinatoric argument, but I have failed to see how.

Things I know: There are exactly $n^{n^2}$ different binary operations on any given finite set of n elements. Also every binary operation is a partial binary operation, but not vice versa. Therefore there should be more partial binary operations than there are plain binary operations.

Any hints or clues would be much appreciated. Thank you for your time.

DEFINITION: A binary operation on a set $S$ is a function from $S \times S$ to $S$.

$\endgroup$
2
$\begingroup$

HINT: Add an $(n+1)$-st value, $\text{undefined}$, to the set of possible values of the operation.

$\endgroup$
  • $\begingroup$ Can I just say that there are at most $n+1$ partial binary operations on a finite set of n elements? Thus the cardinality of the domain would be $n+1$ and the cardinality of the codomain is $n^2$ $\endgroup$ – mathamphetamines Sep 8 '15 at 19:09
  • 1
    $\begingroup$ @mathamphetamines: No, you should think of a partial binary operation on a set $A$ as a function from $A\times A$ to $A\cup\{\text{undefined}\}$. $\endgroup$ – Brian M. Scott Sep 8 '15 at 19:29

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.