I have a question that says

"How many relations are there on a set with n elements?"

so if I have the set A = {a, b} and I wanna find how many relations there are, I thought I would just do R = { (a,b), (a, a), (b, a), (b,b) } because it's a relation from A to itself. and my book says that "sets of ordered pairs are called binary relations. Binary relations represent relationships between elements of 2 sets." From what I see, those are all the possible ordered pairs that we can get from A x A, am I wrong?

But the answer says that "a relation on a set A is a subset of A x A. Because A x A has $n^2$ has n elements, and a set with m elements has $2^m$ subsets, there are $2^{n^2}$ subsets of A x A. Thus, there are $2^{n^2}$ relations on a set with n elements. "

And I understand how to find the amount of elements of A x A (just do |A| x |A|) and I know how to find the number of subsets, but I'm not exactly sure what the number of subsets of the set even has to do with anything. I thought a relation was dealing with the ELEMENTS, not the SUBSETS, so like..what exactly are they asking for?

Edited to add:

if my set A = {a, b}, it'll have 2^4 relations, so 16 relations. The only way I can see that there are 16 of anything is if I have the set of all the subsets of A, which would be { {0}, {a}, {b}, {a,b} }, so the ordered pairs of the set of subsets of A would be ( {0}, {a} ), ( {0}, {b}), ({0} , { a,b}), etc and I can see how the number 16 would come out of that. But then that would mean a relation isn't the ordered pairs of elements of the set, but instead of ordered pairs of subsets of the set.....which is different. I'm confusing myself

  • $\begingroup$ Binary relation on $A$ is a function $f:A\times A\to A$ $\endgroup$ – Salech Alhasov Dec 9 '13 at 4:09
  • $\begingroup$ @Salech: Absolutely not: what you’ve defined there is a binary operation on $A$. A binary relation on $A$ is any subset of $A\times A$. $\endgroup$ – Brian M. Scott Dec 9 '13 at 4:18
  • $\begingroup$ Yes! My bad! Sorry for that, and thanks! $\endgroup$ – Salech Alhasov Dec 9 '13 at 4:20

If $A=\{a,b\}$, then $A\times A$, the set of all ordered pairs of elements of $A$, is

$$A\times A=\{\langle a,a\rangle,\langle a,b\rangle,\langle b,a\rangle,\langle b,b\rangle\}\;.$$

The relations on $A$ are the subsets of $A\times A$, so they are sets of ordered pairs of elements of $A$. Since $A\times A$ has $4$ elements, it has $2^4=16$ subsets; each of these subsets is one of the $16$ relations on $A$. They are:

$$\begin{align*} &\varnothing\\ &\{\langle a,a\rangle\}\\ &\{\langle a,b\rangle\}\\ &\{\langle b,a\rangle\}\\ &\{\langle b,b\rangle\}\\ &\{\langle a,a\rangle,\langle a,b\rangle\}\\ &\{\langle a,a\rangle,\langle b,a\rangle\}\\ &\{\langle a,a\rangle,\langle b,b\rangle\}\\ &\{\langle a,b\rangle,\langle b,a\rangle\}\\ &\{\langle a,b\rangle,\langle b,b\rangle\}\\ &\{\langle b,a\rangle,\langle b,b\rangle\}\\ &\{\langle a,a\rangle,\langle a,b\rangle,\langle b,a\rangle\}\\ &\{\langle a,a\rangle,\langle a,b\rangle,\langle b,b\rangle\}\\ &\{\langle a,a\rangle,\langle b,a\rangle,\langle b,b\rangle\}\\ &\{\langle a,b\rangle,\langle b,a\rangle,\langle b,b\rangle\}\\ &\{\langle a,a\rangle,\langle a,b\rangle,\langle b,a\rangle,\langle b,b\rangle\}=A\times A \end{align*}$$

Every one of these $16$ sets of ordered pairs is a relation on $A$, and every relation on $A$ is one of these $16$ sets of ordered pairs.

  • $\begingroup$ @FrostyStraw: No: you don’t want ordered pairs of subsets of $A$. Those would be things like $\langle\{a\},\{a,b\}\rangle$. Relations on $A$ are not subsets of $\wp(A)\times\wp(A)$, which I think is what you’re suggesting here; they’re subsets of $A\times A$. Their members are just ordered pairs of elements of $A$, not ordered pairs of subsets of $A$. $\endgroup$ – Brian M. Scott Dec 9 '13 at 5:38
  • $\begingroup$ yeah I just realized that was wrong...so it just means..all the relations are the subsets of A x A. So the subsets of the set { (a,a), (a,b), (b,a), (b,b) } .....and that set will have 2^n sets, so 2^4 because there are 4 elements in that set. I'm not sure why I was so confused because it now sounds pretty simple. Thank you! @Brian M. Scott $\endgroup$ – FrostyStraw Dec 9 '13 at 5:41
  • $\begingroup$ @FrostyStraw: You’re welcome! I’m glad that you got it sorted out. $\endgroup$ – Brian M. Scott Dec 9 '13 at 5:41

A relation on a set $A$ is indeed just a subset of $A \times A$, where $\times$ is the Cartesian cross-product. If necessary, look up the Cartesian cross-product: for example, $A \times B = \{(a,b) \mid a \in A, b \in B\}$, so for example, $\{a,b,c\} \times \{1,2,3\} = \{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3),(c,1),(c,2),(c,3)\}$.

You have correctly identified that the number of subsets of a set with $n$ elements is $2^n$. In our example from above, we have subsets like $\{(a,1),(a,3)\}, \{(b,2)\},\{(c,1),(c,2),(a,2),(b,1)\}$, etc.

You have also correctly identified that $| A \times B| = |A| \times |B|$. If $A$ has $n$ elements, then $A \times A$ has $n^2$ elements. So the number of relations on $A$ is indeed $2^{n^2}$, the number of subsets of $A \times A$.


You edit shows you are getting confused because of the special property of $2$, that $2^2=2*2$. If we have $B=\{a,b,c\}$ and are looking for the number of relations on $B$, we want a subset of $B \times B$. Since $B$ has three elements, $B \times B$ has $3 \times 3=9$ elements. Then $B\times B$ has $2^9$ elements, which is $2^{3^2}$.


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.