Let $S$ be a set with $|S|=n$. So how many subsets $A$ of$ S\times S$ are there with the property that $(a,a)\in A$ $\forall a\in S$

Question

So this is my assignment about subsets.I am absolutely no where with this because i don't have clear idea about subsets.Any kind of help would be appreciated.

Answer 1

If I'm reading your question correctly then the answer is $2^{n(n-1)}$.

You HAVE to include all elements of the form $(a,a)$ - let $\Delta$ denote the set of all elements of this form. But you do have a choice of whether to include elements of $S\times S\setminus\Delta$. And the size of $S\times S\setminus\Delta$ is $n(n-1)$. So the number of subsets containing $\Delta$ is $2^{n(n-1)}$. As for each element of $S\times S\setminus\Delta$ you may include it or exclude it in your set $A$.