Number of (equivalence) relations fulfilling some additional conditions

Question

let say I have $A=\{1,\dots,8\}$
I want to know the following things:

1. what the number of relations on $A$?
2. what the number of reflexivity relations on $A$?
3. what the number of equivalence relations on $A$ that include $(1,2),(1,3),(2,5)$ and not include $(2,8),(4,8),(3,4)$

for the first one I can thing about that as $\mathcal {P}(A)$? and it will be $2^{|A|}$?
for the second its all $(x,x)\in \ {R}$ so I can take the number of the those relations from Hasse Diagram? or there is another way to calculate it?
what about the third? Generation functions? Combinatorics? I would like to get some advice.
thanks!

Answer 1

All three of these questions are just a matter of counting subsets.

1. The relations on $A$ are precisely the subsets of $A\times A$, i.e., the elements of $\wp(A\times A)$, not the subsets of $A$. You know that $A\times A$ has $2^{|A\times A|}$ subsets; what is $|A\times A|$?

2. There’s no need to look at Hasse diagrams; in fact I don’t think that they’re at all helpful here. Suppose that $R$ is a reflexive relation on $A$; then you know that all of the pairs $\langle a,a\rangle$ for $a\in A$ belong to $R$. Thus, $R$ is completely determined by which other pairs in $A\times A$ belong to $R$. That is, there is a bijection between reflexive relations on $A$ and subsets $S$ of $(A\times A)\setminus\Delta$, where $\Delta=\{\langle a,a\rangle:a\in A\}$: if $S\subseteq(A\times A)\setminus\Delta$, then $S\cup\Delta$ is a reflexive relation on $A$, and if $R$ is a reflexive relation on $A$, then $R\setminus\Delta\subseteq(A\times A)\setminus\Delta$. Thus, the number of reflexive relations on $A$ is equal to the number of subsets of $(A\times A)\setminus\Delta$, which you know is $2^{|(A\times A)\setminus\Delta|}$; what is $\left|(A\times A)\setminus\Delta\right|$?

3. Suppose that $E$ is an equivalence relation on $A$. Then $E$ divides the set $A$ into equivalence classes. The easiest way to count the possible equivalence relations is to count the ways to divide $A$ up into equivalence classes that meet the requirements of the problem. Since $\langle 1,2\rangle,\langle 1,3\rangle,\langle 2,5\rangle\in E$, we can infer that $1,2,3$, and $5$ must all be in the same equivalence class. The fact that $\langle 3,4\rangle,\langle 2,8\rangle$, and $\langle 4,8\rangle$ do not belong to $E$ tells you that $4$ and $8$ are not in this equivalence class, and moreover that $4$ and $8$ are not in the same class with each other. Thus, we know for sure that $E$ contains at least three equivalence classes: one containing $1,2,3$, and $5$; one containing $4$; and one containing $8$. That leaves only the elements $6$ and $7$ unaccounted for. Each of them could go into one of the three existing equivalence classes. One of them could go into one of the three existing classes, while the other could make a fourth equivalence class by itself. They could form a fourth equivalence class containing $6$ and $7$. Or they they could form a pair of equivalence classes, one containing just $6$ and the other containing just $7$. How many possibilities is that altogether? That’s how many different equivalence relations on $A$ there are that satisfy the conditions of the problem.