I need to calculate the number of relations over $A$, when the size of $A$ is $n$, and want to understand why my approach is not correct.
I denoted $A_i$ as subset of $A$, and I said general relation is something of the type $A_i \times A_j$ where $i$ can be equal to $j$. The number of subsets of $A$ is $2^n$. So $A_i \times A_j$ has $2^n \times 2^n$ different combinations. Therefore the number of relations should be $2^{2n}$, but it's wrong. Why?
Here's the correct answer.
On
Your question has two aspects: why is the right answer right, and why is yours wrong.
The number of possible subsets in a set $S$ with $n$ elements is $2^{n}$; this collection of subsets is often referred to as the power set of $S$. The fact that $P(S)$ has $2^n$ elements is readily seen when you list the possible subsets as binary codes. A relation in $S$ is a set of ordered pairs drawn from $S \times S$. You can think of it as a matrix of dimensions $n \times n$ with binary entries denoting which pairs of elements are in the relation. The number possible relations is the number of ways that matrix can be filled. If you consider the matrix cells as a set itself, it has $n \times n$ cells, and its power set has $2^{n \times n}=2^{n^2}$ elements.
Your approach has (greatly) undercounted possible relations. This is because you assume relations include all possible pairs in your Cartesian products of $A_i \times A_j$. Again, to use the array visualization, if you examine for example subsets with $2$ and $3$ elements, your approach is generating a series of rectangular arrays with all cells filled. But what if you left a single cell empty? That's also a relation, and not captured by your approach.
If $A=\{0\}$ then all possible relation over $A$ are $\{(0,0)\},\{\}$. And think what is $P(A)\times P(A)$, $P(A)$ denotes the set of all subsets of $A$. does all elements of $P(A)\times P(A)$ be relation on $A$ ? What if $A=\{0,1,2\}$, can you find an a relation over $A$ which is not of $P(A)\times P(A)$ ?