# Confusion on sets and relations

I'm confused on how the number of subsets equals the number of relations. If set A = {1, 2} then AxA would be {}, {1}, {2}, {1,2}. I'm confused on how there are $2^{n^2}$ subsets of $A$ x $A$ because I remember hearing that sets are unique so $\{1,2\}$ is the same as $\{2,1\}$, so I don't see how it'd be $2^{2^2}=8$ subsets

• $A \times A$ is not the set of subsets of $A$ it is the cartesian product, which all relations are subsets. The power set of $A$ is the set of all subsets of $A$. So in your example $A \times A= \{(1,1),(1,2),(2,1),(2,2)\}$. – Nap D. Lover Apr 18 '16 at 17:07
• My, oh, my: the elements of the cartesian product $A\times A$, when $A=\{1,2\}$, are the four ordered pairs $(1,1)$, $(1,2)$, $(2,1)$, and $(2,2)$. Therefore the set $A\times A$ has $4$ elements, and it has $2^4$ subsets. No wonder you're stumped''. – chizhek Apr 18 '16 at 17:09

$X\times Y$ is the set of ordered pairs $(x,y)$ where $x\in X$ and $y\in Y$. So in this case, $$A\times A=\{(a,b)\;\colon\;a\in A, b\in A\}.$$

In the example you gave, $A\times A=\{(1,1),(1,2),(2,1),(2,2)\}$. Notice that ordered pairs are distinct from unordered pairs, so while (as you say) the unordered pairs are equal $\{1,2\}=\{2,1\}$, the ordered pairs are not equal $(1,2)\ne (2,1)$.

As for the subsets of $A\times A$, we know that the number of subsets of a set with $n$ elements is $2^n$. In this case there are $n^2$ members of $A\times A$, so indeed there are $2^{n^2}$ subsets. The set of subsets is the power set, $\mathcal{P}(A\times A)$,

Notice that every element of $\mathcal{P}(A\times A)$ listed is a subset of $A\times A$, and indeed there are $2^{n^2}=16$ of them.

Note: the set you listed as $A\times A$ was in fact the powerset $\mathcal{P}(A)$.

A relation $S$ on a set $A$ is a set of ordered pairs. So if $A=\{1,2\}$ then if we define $S$ as a relation on $A$ we have that $S$ is actually a set. So $S$ is any subset of $A\times A=\{(1,2),(2,1),(1,1),(2,2)\}$. As any subset of this set will define a relation then the total number of relations is just the number of elements in the power set, which in this case is $2^n=16$ (your exponentiation was wrong as $2^{2^2}=16$). So in general if $A$ has $n$ elements there are $n^2$ elements in $A\times A$. Now we have shown that the number of relations on $A$ is just the number of elements of the powerset of $A\times A$ which contains $n^2$ elements. The important part here is to note that the order in an ordered pair matters and $A\times A$ consists of ordered pairs.