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$
4
  • $\begingroup$ Is the empty relation reflexive? $\endgroup$ Nov 8, 2016 at 15:37
  • 1
    $\begingroup$ Remember reflexivity. $\endgroup$
    – mrp
    Nov 8, 2016 at 15:38
  • $\begingroup$ @TobiasKildetoft got it . $\endgroup$ Nov 8, 2016 at 15:39
  • $\begingroup$ @mrp always from now on $\endgroup$ Nov 8, 2016 at 15:40

1 Answer 1

4
$\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$
2
  • $\begingroup$ Can we say that $R$ is actually the relation of equality $=$? $\endgroup$
    – manooooh
    May 31, 2020 at 9:49
  • 1
    $\begingroup$ @manooooh yes, that's correct. $\endgroup$
    – mrp
    May 31, 2020 at 12:57

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.