Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.


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?

share|cite|improve this 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
up vote 19 down vote accepted

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).

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.