# What exactly do “relations on a set” mean?

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?

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

• Binary relation on $A$ is a function $f:A\times A\to A$ – Salech Alhasov Dec 9 '13 at 4:09
• @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$. – Brian M. Scott Dec 9 '13 at 4:18
• Yes! My bad! Sorry for that, and thanks! – 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.

• @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$. – Brian M. Scott Dec 9 '13 at 5:38
• 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 – FrostyStraw Dec 9 '13 at 5:41
• @FrostyStraw: You’re welcome! I’m glad that you got it sorted out. – 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}$.