If U = {A, B, C, D, E} determine the number of relations on U that are
is my solution correct? is there any formula to better calculate total number of relations of different properties?
Thanks
On
First, re 4. For a relation to be reflexive doesn't mean that the only things it relates are identical! (There would be little use for the word "reflexive" in that case, as the only such relation on a set is the identity relation.) For example, consider $n\sim m \iff$ integers $n,m$ are either both even or both odd. This is an equivalence relation on the integers. Certainly $\sim$ is reflexive. Note that $0\sim 2\sim 4\dotsc$, but of course $0\ne 2, 2\ne 4$, etc.
Given the 5-element set $U$, the entire set of ordered pairs $U\times U$ is itself a relation on $U$ which is reflexive, symmetric and contains $(A,B)$. So the number of such relations is not $0$.
1. (solution) Suppose $R$ is a reflexive relation on $U$. "$R$ is reflexive" means $I_U \subseteq R$, where $\{(x,x)\mid x\in U\}$. Let $D_R = \{(x,y)\in R\mid x\ne y\}$ ("$D$" for different). Then $$R = I_R \cup D_R,$$ and $$I_R \cap D_R =\emptyset.$$
Clearly, if $R,S$ are reflexive relations on $U$ and $D_R = D_S$, then $R=S$. Furthermore, if $T \subseteq (U\times U \setminus I_U)$, then $I_U \cup T$ is a reflexive relation on $U$. Thus the map $$ R\mapsto D_R\colon \{R\subseteq U\times U\mid R\text{ is reflexive}\} \to \mathcal{P}(U\times U \setminus I_U) $$ is a bijection. The size of $U\times U \setminus I_U$ is: $$\begin{align} \lvert U\times U \setminus I_U\rvert &= \lvert U\rvert^2 - \lvert U\rvert \\ &= n^2 - n \quad\text{where $n = \lvert U\rvert$} \\ &= n(n-1). \end{align}$$ So the number of reflexive relations on $U$ is: $$\begin{align} \lvert \{R\subseteq U\times U\mid R\text{ is reflexive}\} \rvert &= \lvert \mathcal{P}(U\times U \setminus I_U) \rvert \\ &= 2^{\lvert U\times U \setminus I_U\rvert} \\ &= 2^{n(n-1)}\quad\text{where $n=\lvert U\rvert$}. \end{align}$$ Hence, the number of reflexive relations on the particular 5-element $U$ in question is $2^{20} = 1024^2 = 1,048,476$ — one (binary) megabyte, as it happens. As I said, it's much bigger than $32$.
2. (solution) Similar to 1. in approach, but different in detail. Assume that $U$ has a total ordering $<$ (any one will do; in the case of the 5-element $U$, let's say $A<B<C<D<E$). If $R\subseteq U\times U$ is symmetric, then $R$ decomposes into: $$ R = (R\cap I_U) \cup LT_R \cup LT_R^{-1} $$ where $LT_R = \{(x,y)\in R\mid x < y\}$ and $LT_R^{-1} = \{(x,y)\in R\mid x > y\}$ is its inverse. ($LT$ stands for less than.)
The map $$ R \mapsto \left( (R\cap I_U), LT_R \right) $$ is a bijection $$ \{R\subseteq U\times U\mid R\text{ is symmetric}\} \to \mathcal{P}(I_U) \times \mathcal{P}(\{(x,y)\mid x<y\}) $$
Let $n = \lvert U\rvert$. Then the size of $\mathcal{P}(I_U)$ is $2^n$. The size of $\{(x,y)\mid x<y\}$ is $\sum_{i=1}^{n-1} = n(n-1)/2$; so the size of $\mathcal{P}(\{(x,y)\mid x<y\})$ is $2^{n(n-1)/2}$. (Note: this can also be written, and thought of, as $2^{nC2}$ alias $2^{\binom{n}{2}}$.) Therefore the number of symmetric relations on $U$ is: $$\begin{align} \lvert \{R\subseteq U\times U\mid R\text{ is symmetric}\} \rvert &= 2^n2^{n(n-1)/2} \\ &= 2^{n + n(n-1)/2} \\ &= 2^{n(n+1)/2}. \end{align}$$ Note that this is $2^n2^{nC2} = 2^{(n+1)C2}$.
For $n=5$, the number of symmetric relations is $2^{15} = 32*1024=32,768$.
3. (solution) Similar to 2., but in this case if $R$ is symmetric and also reflexive, then $I_U\subseteq R$, so $I_U\cap R = I_U$ always, and $R\mapsto LT_R$ gives a bijection from the reflexive-and-symmetric relations on $U$ to $\mathcal{P}(\{(x,y)\mid x<y\})$, so the number of such relations is $2^{n(n-1)/2}$. Note that this is $2^{nC2}$. For $n=5$, that's $1024$.
The answers you got to 2. and 3. are the answers to 3. and 2. respectively. Obviously you were on the right and almost there, but slipped up somewhere. A simple sanity check: the number of relations that are both reflexive and symmetric can't be larger than the number of relations that are just symmetric!
I'll leave the solution to 4. as an exercise.
Let $U=\{a,b,c,d,e\}$. A reflexive relation on $U$ must contain each of the pairs $\langle a,a\rangle,\langle b,b\rangle,\langle c,c\rangle$, $\langle d,d\rangle$, and $\langle e,e\rangle$. That’s $5$ of the $25$ possible ordered pairs. Each of the other $20$ ordered pairs in $U\times U$ is optional: a reflexive relation on $U$ may contain it but need not. Thus, to make a reflexive relation on $U$ we start with the $5$ required pairs, and then for each of the other $20$ pairs we either include it or not. That’s a total of $20$ two-way decisions, so there are $2^{20}$ ways to choose which of the optional pairs will be in the reflexive relation.
You can think about symmetry in a similar fashion. Suppose that $R$ is a symmetric relation on $U$. The following diagram labels the ordered pairs in $U\times U$; the row indicates the first element of the ordered pair, and the column indicates the second. Thus, the ordered pair $\langle b,d\rangle$ corresponds to the square labelled with the black $5$, while the reversed pair $\langle b,d\rangle$ corresponds to the square labelled with the red $\color{red}5$. Squares corresponding to pairs with both elements the same are labelled with hyphens.
$$\begin{array}{|c|c|c|} \hline &a&b&c&d&e\\ \hline a&-&0&1&2&3\\ \hline b&\color{red}0&-&4&5&6\\ \hline c&\color{red}1&\color{red}4&-&7&8\\ \hline d&\color{red}2&\color{red}5&\color{red}7&-&9\\ \hline e&\color{red}3&\color{red}6&\color{red}8&\color{red}9&-\\ \hline \end{array}$$
Symmetry says that if $R$ contains one of the pairs whose corresponding square has a black number, it must also contain the pair whose corresponding square has the matching red number, and vice versa. For instance, if it contains either of the pairs $\langle b,d\rangle$ and $\langle d,b\rangle$, whose squares are numbered $5$ and $\color{red}5$, respectively, then it must contain both of those pairs. Thus, for each of the numbers $0,1,\ldots,9$ we have a two-way choice: if $k$ is one of these numbers, we can put into $R$ the two pairs corresponding to the squares labelled $k$ and $\color{red}k$, or we can leave both of those pairs out of $R$. Moreover, $R$ can contain a pair like $\langle b,b\rangle$ or not: the reversal of $\langle b,b\rangle$ is the same pair, so if $R$ contains the pair $\langle b,b\rangle$, it automatically contains its reversal as well. That’s another $5$ two-way choices, for a total of $15$ two-way choices in building a symmetric relation on $U$, or $2^{15}$ such relations.
A relation $R$ on $U$ that is both reflexive and symmetric must include all of the pairs like $\langle b,b\rangle$, and it must satisfy the symmetry condition. It should be clear that this number cannot be bigger than either of the first two answers: every relation that is both reflexive and symmetric is clearly reflexive, so there can’t be more than $2^{20}$ such relations, and it is also clearly symmetric, so in fact there can’t be more than $2^{15}$ such relations. If you carefully examine the reasoning in the previous paragraph, you should be able to figure out how many reflexive, symmetric relations there are on $U$.
The last question can be answered by similar reasoning. It is certainly not true that the answer is $0$: $\{\langle a,a\rangle,\langle a,b\rangle,\langle b,b\rangle,\langle c,c\rangle,\langle d,d\rangle,\langle e,e\rangle\}$ is a reflexive relation on $U$ that contains the pair $\langle a,b\rangle$.