On my assignment, one of the questions ask to list all equivalence relations on S and count how many are of partial orders.
- 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.