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?
$\begingroup$
$\endgroup$
4
asked Nov 8, 2016 at 15:33
-
$\begingroup$ Is the empty relation reflexive? $\endgroup$– Tobias KildetoftNov 8, 2016 at 15:37
-
1$\begingroup$ Remember reflexivity. $\endgroup$– mrpNov 8, 2016 at 15:38
-
$\begingroup$ @TobiasKildetoft got it . $\endgroup$– Shubham Singh rawatNov 8, 2016 at 15:39
-
$\begingroup$ @mrp always from now on $\endgroup$– Shubham Singh rawatNov 8, 2016 at 15:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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\}$.
-
$\begingroup$ Can we say that $R$ is actually the relation of equality $=$? $\endgroup$– manoooohMay 31, 2020 at 9:49
-
1