# Equivalence relations on S given no relation?

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.
• @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 3:21