Number of element in a relation $R$ of $\{1, \cdots, n\}$. Let $A = \{1,2,...,n\}$, and $R$ be a relation on $A$ (so $R \subset A \times A$)
i) What is the minimal possible number of elements in $R$?
I tried calculating this as just a normal cartesian product which would have $n^2$ within the set. So $R$ would also need $n^2$ number of elements to be a proper subset of $A\times  A$.
ii) What is the maximal possible number of elements in $R$?
I'm a bit more confused by this one, but I think it would have something to do with calculating it as $2^{n^2}$ i.e., if $n$ was $3$ then it would be $2^9$ or $512$ as the maximum number of elements.
 A: I think you may be missing some details concerning the definition of a binary relation from a set to another. Let us recall its definition.

Let $X$ be a set. A binary relation on $X$ is a subset $R$ of the Cartesian product $X^2$, i.e. $X \times X$.

Note that the any element from $\mathcal{P}(X \times X)$ is a binary relation on $X$. In particular, $\emptyset$ is a legit binary relation on $X$. Since $\emptyset$ has no elements, there is not a minimal number of elements that a subset of $X^2$ must have in order to be a binary relation on $X$.
For the maximal number, the story is quite different. Taking $X = \{i \in \mathbb{N} \colon i \leq n\}$, where $n \in \mathbb{N}$ (as in your example), the largest set in $\mathcal{P}(X^2)$ is $X^2$ itself. And note that $X^2$ has $n^2$ elements. No other element of $\mathcal{P}(X^2)$ has this many objects (you can easily check this by yourself). So the maximal number of elements of a subset $R$ of $X^2$ in order for $R$ to a be a binary relation on $X$ is $n^2$.
I hope this helps you with your future study.
Remark. By definition, given any two sets $A$ and $B$, we say that $A$ is a proper subset of $B$ if $A \subseteq B$ and $A \neq B$.
A: You are confusing things here. A relation is nothing but a subset of a Cartesian Product (in set theory at least).
So a relation $R$ on $A$ means that $R$ is a subset of $A\times A$.
You correctly pointed out that the size of a Cartesian product is equal to the product of the sizes (in the finite case at least). Like you wrote, $A\times A$ has $n^2$ elements.
Now,for any $2$ finite sets $X$ and $Y$ such that $X\subset Y$ it is always true that $|X|\leq|Y|$. And since $\emptyset\subset R$ and $R\subset A\times A$, what can you conclude about the size of $R$?
