Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Is it 16 (2^4)?

I completely forgot how to calculate the number of relations on a given set.

share|cite|improve this question
How do $a$ and $b$ relate to $16$, $2$, and $4$? This question needs a lot of editing before anyone can understand what you are talking about. – Gerry Myerson Nov 23 '12 at 2:42
@GerryMyerson I just read the words "set", "$16$" and "$2^4$" and concluded that the OP had some issue with counting the number of functions from a $4$ element set to a $2$ element set. Anyway I have now deleted my answer since I didn't read the question properly. – user17762 Nov 23 '12 at 2:49
up vote 5 down vote accepted

If you mean $S = \{a, b\}$, a set with $2$ elements, then a relation is simply an element of the powerset of $S^2$. So your answer is correct.

share|cite|improve this answer
Good job of mind-reading. – Gerry Myerson Nov 23 '12 at 2:45
Haha thank you. – beauby Nov 23 '12 at 2:45

Suppose $X$ is a set of $n$ elements. Then for any ordered pair $(x,y)$ of elements of $X$, we can say Yes or No to the question of whether $(x,y)$ is in the (binary) relation on $X$. There are $2^{n^2}$ ways to make the choices, and therefore $2^{n^2}$ binary relations on $X$.

If $X$ is the $2$-element set $\{a,b\}$, the number of relations on $X$ is therefore $2^{(2^2)}$.

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.