0

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?

COMP232
  • 11

1 Answers1

1

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.

Brian M. Scott
  • 616,228
  • Thank you very much for clearing that up. – COMP232 Nov 29 '13 at 02:50
  • @COMP232: You’re very welcome. – Brian M. Scott Nov 29 '13 at 02:53
  • 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. – COMP232 Nov 29 '13 at 03:17
  • @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$. – Brian M. Scott Nov 29 '13 at 03:21
  • 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! – COMP232 Nov 29 '13 at 03:56
  • @COMP232: Ah, I understand now; yes, that’s exactly right. In general a partition ${P_1,\ldots,P_n}$ of a set $S$ corresponds to the equivalence relation $$(P_1\times P_1)\cup(P_2\times P_2)\cup\ldots\cup(P_n\times P_n);.$$ – Brian M. Scott Nov 29 '13 at 03:59