4

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

FrostyStraw
  • 1,045

3 Answers3

4

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.

Brian M. Scott
  • 616,228
  • @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 09 '13 at 05: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 09 '13 at 05:41
  • @FrostyStraw: You’re welcome! I’m glad that you got it sorted out. – Brian M. Scott Dec 09 '13 at 05:41
  • @Brian M. Scott - Hi Brian, quick question: when we say something like $R$ is a relation between* the sets $A$ and $B$, is this short for “$R$ is a relation between the elements of $A$ and the elements of $B$“? I’m just trying to make out the usage of the word between* here. – Taylor Rendon Aug 30 '21 at 16:31
  • 1
    @TaylorRendon: Yes, though I consider that wording a bit ambiguous and would not use it: if $R\subseteq A\times B$ and $S\subseteq B\times A$, one could reasonably say that $R$ and $S$ are both relations ‘between’ the sets $A$ and $B$. I prefer to avoid the word between in this context. I would prefer to say that $R$ is a relation from $A$ to $B$, while $S$ is a relation from $B$ to $A$. – Brian M. Scott Aug 30 '21 at 17:39
2

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

Newb
  • 17,672
  • 13
  • 67
  • 114
0

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

Ross Millikan
  • 374,822