1
$\begingroup$

The number of relations between sets can be calculated using $2^{mn}$ where $m$ and $n$ represent the number of members in each set, thus total is $2^{16}$ .

Now how do I go ahead calculate only those that contains $(a, a)$ There are $4 \cdot 4=16$ pairs of one element from $A$ and one from other $A$.

Now if we always include a $(a, a)$ , so there will be $2^{16-1}$=$2^{15}$ relations.

This is what I think but I am confused. Please help me solve this sum.

$\endgroup$
  • $\begingroup$ Yes, $2^{15}$ is correct. $\endgroup$ – Adriano Apr 30 '17 at 3:30
1
$\begingroup$

You are correct. The point of $2^{mn}$ formula is that there are $mn$ ordered pairs that might or might not be part of the relation. As you have two choices repeated $mn$ times there are $2^{mn}$ choices. When we say $(a,a)$ is required to be in the relation, one of those choices is already made, so there are $mn-1$ more to make. Thus there are $2^{mn-1}=2^{15}$ relations that include $(a,a)$

$\endgroup$
1
$\begingroup$

Since there are no conditions at all that the relation is required to satisfy, the presence of any particular pair $(x,y)$ in the relation can be varied independently of any other such pair. In particular, a relation selected (uniformly) at random among all relations has a probability $\frac12$ to contain the pair $(a,a)$. This is just another way to say that the subset of relations with that property has half the size of the full set.

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