Confusion on sets and relations

Question

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

Answer 1

$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)$,

\begin{align}\mathcal{P}(A\times A)&=\{\emptyset, \{(1,1)\},\{(1,2)\},\{(2,1)\},\{(2,2)\},\\ &\quad\quad\{(1,1),(1,2)\},\{(1,1),(2,1)\},\{(1,1),(2,2)\},\\ &\quad\quad\{(1,2),(2,1)\},\{(1,2),(2,2)\},\{(2,1),(2,2)\},\\ &\quad\quad\{(1,1),(1,2),(2,1)\},\{(1,1),(1,2),(2,2)\},\\ &\quad\quad\{(1,1),(2,1),(2,2)\},\{(1,2),(2,1),(2,2)\},\\ &\quad\quad\{(1,1),(1,2),(2,1),(2,2)\}\}.\end{align}

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

Answer 2

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.