# Relations which are both equivalence and partial-order.

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?

• Is the empty relation reflexive? Nov 8, 2016 at 15:37
• Remember reflexivity.
– mrp
Nov 8, 2016 at 15:38
• @TobiasKildetoft got it . Nov 8, 2016 at 15:39
• @mrp always from now on Nov 8, 2016 at 15:40

## 1 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\}$.

• Can we say that $R$ is actually the relation of equality $=$? May 31, 2020 at 9:49
• @manooooh yes, that's correct.
– mrp
May 31, 2020 at 12:57