2
$\begingroup$

Is it 16 (2^4)?

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

  • 0
    @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.2012-11-23

2 Answers 2

6

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.

  • 4
    Good job of mind-reading.2012-11-23
1

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