2
$\begingroup$

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?

$\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$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.