1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $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)\}$. $\endgroup$ – Nap D. Lover Apr 18 '16 at 17:07
  • $\begingroup$ 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''. $\endgroup$ – chizhek Apr 18 '16 at 17:09
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.