# Are there an infinite number of binary operations for any set?

I have just begun to take a look at A First Course in Abstract Algebra by Fraleigh.

The following definition is provided (ed. 6, pp. 32).

Definition: A binary operation, $*$ on a set $S$ is a function mapping $S \times S$ into $S$. For each $(a,b) \in S \times S$, we will denote the element $*((a,b))$ of $S$ by $a*b$.

After experimenting with the definition, I began to wonder whether regardless of what $S$ is, will there always be a possible binary operation. I thought, yes.

Conjecture: Let $S$ be a set. Regardless of what $S$ contains, there always exists at least one binary operation on $S$.

Proof:

Let $S = \emptyset$. Then the statement there exists a function mapping $S \times S$ into $S$ is vacuously true since there are no elements to map. Thus the proposition is true for the empty set case.

Suppose $S$ is not empty. Let $a$ and $b$ be two arbitrary elements of $S$, and in the case where $S$ has just one element $a= b$. Definite $*$ to always return the first item in the ordered pair, such that $a*b=a$. This would map $S \times S$ into $S$ regardless of what the set $S$ may be.

Therefore, every possible set has a possible binary operations.

This seems to demonstrate there is always a binary operation for a set, but then it lead me to wonder whether there is also an infinite number of binary operations for any given set $S$.

Conjecture: Let $S$ be a set. Regardless of what $S$ contains, there is an infinite number of possible binary operations on $S$.

After thinking of possible binary relations, I think I have come up with a proof that shows the above statement is true.

Proof: If $S$ is empty, then any declared binary operation would be vacuously true.

If $S$ is not empty, and $S$ is an infinite set. Define a binary operation on $S$ as: let $a$ and $b$ be two arbitrary elements of $S$. Then $a *_n b$ always returns the $n^{th}$ element in the set $S$. Any infinite number of $n$ can be chosen, thus there are an infinite number of binary relations on $S$ when $S$ is infinite.

If $S$ is not empty and finite, define a new set $S'$. $S'$ contains the same elements as $S$ in the same order, and where $S$ terminates, $S'$ continues with the last element of $S$ repeated over again. Thus defining the binary operation as in the infinite case, but on $S'$, we get the same result since every element in $S'$ is in $S$.

Example: Let $S = \{ a , b , c \}$. Then $S' = \{ a , b , c , c , c , ... \}$

What I am wondering is:

Are my proofs of my conjectures correct?

Is there a more elegant way to address the question?

-
If $S$ is empty then all binary operations are the same. If $S$ is finite then the number of distinct binary operations is finite. Your $S'$ is not a binary operation $S \times S \to S$ – Henry Jan 1 '14 at 23:50
You have not yet fuly grasped what a set is. For starters, there is no ordering in a set, so it doesn't make sense to say "in the same order", or to speak of the $n$th element of a set. Also, a set does not have repeated elements, so your sets $S$ and $S'$ are the same set. – fkraiem Jan 1 '14 at 23:54
@mathematics2x2life Your comment is incorrect. The empty function is a binary operation on the empty set. – Andreas Blass Jan 2 '14 at 0:10
@mathematics2x2life: a binary operation on $S$ is a function $f : S\times S\to S$. The product $\emptyset\times\emptyset\cong\emptyset$, so giving a function $f : \emptyset\times\emptyset\to\emptyset$ is the same as giving a function $f : \emptyset\to\emptyset$, and we can: the empty function. – Stahl Jan 2 '14 at 0:10

A binary operation is a function $f : S\times S\to S$. However, if $0 < \left|S\right| = n < \infty$, we can count the number of such functions: $$\#\{f: S\times S\to S\} = \left|S\right|^{\left|S\times S\right|} = n^{n^2}< \infty.$$ If $S$ is infinite, then there are clearly an infinite number of such functions. So your second conjecture holds if $S$ is infinite, but not if $S$ is finite (if $S = \emptyset$, there is a unique function $f : \emptyset\times\emptyset\to\emptyset$). Your first conjecture is true: if $S\neq\emptyset$, then say $a\in S$. Define $f : S\times S\to S$ to be the constant function sending any element of $S\times S$ to $a$. This is a binary operation for any nonempty set, and we have already seen a binary operation for $\emptyset$ (your argument for nonempty $S$ also works).
To address the proposal directly, consider $S' = \{a, b, c, c, c, \ldots\}$. The notation is a little ambiguous, but it suggests that the operations $*_3$ and $*_4$ on $S'$ are defined by $x*_3 y = c$ and $x*_4 y=c$ for all $x,y$. So we have the identity $x*_3 y = x*_4 y$. For any reasonable definition of equality of operations, this means that $*_3=*_4$, or in English: they are the same operation. In set theory, operations are defined in such a way that this is indeed the case.
As fkraiem notes, sets do not have repeated elements, so $S' = \{a, b, c, c, c, \ldots\} = \{a,b,c\}$. Likewise, the set of operations you've defined is $$\{*_1,*_2,*_3,*_4,*_5,\ldots\}=\{*_1,*_2,*_3,*_3,*_3,\ldots\}=\{*_1,*_2,*_3\},$$ which is a finite set.