0
$\begingroup$

In this question I don't understand why the number of subsets is equal to the number of relations.

Any help is welcome.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ It’s the definition of relation on $A$: by definition a relation on $A$ is a subset of $A\times A$ and vice versa. $\endgroup$ – Brian M. Scott May 5 '15 at 23:13
1
$\begingroup$

Firstly, to avoid misunderstandings: the number of relations on A is asserted to be the number of subsets of A x A (and not of A !).

Secondly: this is indicated by the first sentence of the solution: "A relation on A is a subset of A x A" - I hope it is clear that if a relation is a subset (and different subsets are thus different relations), then the number of relations is the number of subsets.

$\endgroup$
1
$\begingroup$

A relation $R$ on a set $A$ is by definition a subset of the set $A \times A$. So to find the numbers of relations on a set $A$, we can simply find the number of subsets $A \times A$.

We know that if $A$ has $n$ elements, then $A \times A$ has $n^2$ elements, and the set of subsets of $A$, also known as the power set $\mathcal{P}(A)$, has $2^n$ elements. Hence, there $2^{n^2}$ subsets of $A \times A$, and this is the same as the number of relations on $A$.

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