On my assignment, one of the questions ask to list all equivalence relations on S and count how many are of partial orders.

  1. Let S = {u, v, w}. List all equivalence relations on S. How many of these are also partial orders?

Am I to assume the equivalence relations are the possible combinations of each pair S x S ({}, {{u, u}}, {{u, u}, {u, v}} ...) or should their always be a given relation?


HINT: Since $S$ has $3$ elements, $S\times S$ has $3^2=9$ elements. Every subset of $S\times S$ is a relation on $S$, so there are $2^9=512$ relations on $S$. Fortunately, most of them are not equivalence relations, and you can ignore those. For instance, an equivalence relation must by definition be reflexive, so if $E$ is an equivalence relation on $S$, then you know that $E$ must contain each of the ordered pairs $\langle u,u\rangle,\langle v,v\rangle$, and $\langle w,w\rangle$. That leaves only $6$ ordered pairs that might or might not be in $E$. You could then take into account the restrictions on $E$ imposed by the requirements that $E$ be symmetric and transitive. However, this is doing it the hard way.

In fact, you know that every equivalence relation on $S$ determines and is determined by the partition of $S$ whose parts are its equivalence classes. What are the partitions of $S$? One of them is $\big\{\{u,v\},\{w\}\big\}$; what are the others? There aren’t many at all.

Once you’ve listed the partitions, determine which of them represent partial orders. Remember, a partial order is a reflexive, transitive, antisymmetric relation. Your equivalence relations are already reflexive and transitive, so you need only determine which of them are antisymmetric.

  • $\begingroup$ Thank you very much for clearing that up. $\endgroup$ – COMP232 Nov 29 '13 at 2:50
  • $\begingroup$ @COMP232: You’re very welcome. $\endgroup$ – Brian M. Scott Nov 29 '13 at 2:53
  • $\begingroup$ Our teacher had not covered partitions. Given the partitions: {{u}, {v}, {w}}, {{u, v},{w}}, {{u, w},{v}}, {{u}, {w, v}}, {{u, v, w}}, the multiplication of each collection will give all induced equivalence relation on S. $\endgroup$ – COMP232 Nov 29 '13 at 3:17
  • $\begingroup$ @COMP232: I’m not sure what you mean by multiplication here, but those are indeed the four partitions. As an example, the second one induces the equivalence relation $$\{\langle u,u\rangle,\langle u,v\rangle,\langle v,v\rangle,\langle w,w\rangle\}\;,$$ and the first one induces the relation of equality on $S$. $\endgroup$ – Brian M. Scott Nov 29 '13 at 3:21
  • $\begingroup$ Sorry if I was unclear, but the example you gave was indeed what I was referring to. Example: {{u}, {v}, {w}} = {u} x {u} + {v} x {v} + {w} x {w}. Thanks again, you are amazing! $\endgroup$ – COMP232 Nov 29 '13 at 3:56

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.