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

1 Answer 1

5
$\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
    Commented May 31, 2020 at 9:49
  • 1
    $\begingroup$ @manooooh yes, that's correct. $\endgroup$
    – mrp
    Commented May 31, 2020 at 12:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .