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?
2
$\begingroup$
$\endgroup$
-
$\begingroup$ Is the empty relation reflexive? $\endgroup$ – Tobias Kildetoft Nov 8 '16 at 15:37
-
$\begingroup$ Remember reflexivity. $\endgroup$ – mrp Nov 8 '16 at 15:38
-
$\begingroup$ @TobiasKildetoft got it . $\endgroup$ – Shubham Singh rawat Nov 8 '16 at 15:39
-
$\begingroup$ @mrp always from now on $\endgroup$ – Shubham Singh rawat Nov 8 '16 at 15:40
1
$\begingroup$
$\endgroup$
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\}$.
