Given a set of values suppose $ R = \{1,2,3,4\}$ we need to find the number of relations on the set which are both partial-order and equivalence relations.
I constructed the set $R^2$ and its matrix representation. For the relation to equivalence and partial-order we need it to be reflexive , transitive , symmetric and anti-symmetric therefore we can only include the diagonal elements. So the number of elements in the power set of $\{(1,1),(2,2)(3,3)(4,4)\}$
has to be the number of relations? This also contains the empty relation.
Is the empty relation a part of the solution?
[Math] Relations which are both equivalence and partial-order.
discrete mathematicsequivalence-relationsrelations
Best Answer
Since the relation must be reflexive, it must contain the elements $(1,1)$, $(2,2)$, $(3,3)$, and $(4,4)$. It is not difficult to show (do it if it does not seem clear to you!) that the only relations that are both symmetric and anti-symmetric are identity relations of the form $\{(a,a), (b,b), \dots\}$. Hence $\{(1,1),(2,2),(3,3),(4,4)\}$ is the only relation on the set $\{1,2,3,4\}$ that is reflexive, symmetric, and anti-symmetric. Clearly it is also transitive, and hence it is the only relation that is both a partial order and an equivalence relation.
The same argument goes for any set $S$: The only relation that is both a partial order and an equivalence relation is the identity relation $R = \{(x,x) \mid x \in S\}$.