Equivalence relations on an arbitrary set with constraints in the form a~b

Question

Let S = {a,b,c,d,e}.

Determine how many equivalence relations can be defined on S with constraint: a~c, d~c and c not~ e.

My approach is this: Find the equivalence classes, which are

[a] = {a,c,d} = [c] = [d].

[b] = {b}

[e] = {e}

Is it correct to say that since there are 3 equivalence classes, the equivalence relations on S with the constraints is also 3?

Or is it 7 since this implies: a~a, b~b, c~c, d~d, e~e, a~c, a~d.

I think my overall approach to this question is wrong so any help would be greatly appreciated.

Answer 1

I'd say you're putting the cart a bit before the horse. (At least in terms of how I'd approach it. We cover another idea in a bit, which is probably easier but less intuitive in my opinion.) Before looking for equivalence classes, let's first construct the minimum equivalence relation $\sim$ we can on $S$ within these constraints.

We know that if a relation consists entirely of pairs $(x,x)$ for every $x$ on the set of concern, it's an equivalence relation. Thus, $(a,a),(b,b),(c,c),(d,d),(e,e) \in \sim$.

Our constraints also specify that $(a,c),(d,c) \in \sim$ but $(c,e) \not \in \sim$.

Since $\sim$ needs to be an equivalence, we'll need symmetry. Therefore, $(c,a),(c,d)$ are in $\sim$ and $(e,c) \not \in \sim$.

With these, we can visualize our relation $\sim$ thus far as a graph, like so, where $x \to y$ if $x \sim y$.

In a graph like this, our properties desired work as so:

• Reflexivity: Every element points to itself
• Symmetry: If $x$ points to $y$, then $y$ points to $x$ (i.e. if two distinct elements are related, there's a closed loop between them)
• Transitivity: If $x$ points to $y$, and $y$ to $z$, then $x$ points to $z$. Our graph hasn't yet accounted for this. But essentially this means that, if from one element $x$ you can walk along a path to $y$ and then from $y$ to $z$, you'll need a path from $x$ to $z$.

With these in mind, we can already see we need a path to denote $a \sim d \sim a$.

This is the minimum equivalence relation on $S$ we can have with the given restraints. From here, we have freedom insofar as what points to what. Our options:

• Do nothing.
• $a \sim b$, which in turn makes $b \sim a$ by symmetry. Then $b \sim c \sim b$ by symmetry and transitivity, and then $d \sim b \sim d$ by the same. Adding any of these would result in the rest being added as well. Basically $e$ will be isolated from the rest.
• $e \sim b$ which gives $b \sim e$ in turn. Our two isolated bits have a loop in this idea.

For similar reasons to the second bullet, we cannot have $e$ be pointing to any of $a,c,d$; if we don't, we either don't have an equivalence, or we have to have $c \sim e \sim c$, which we don't desire.

Thus, there are $3$ equivalence relations.

---

An alternative approach... Every equivalence relation and its classes corresponds to a partition of the set of concern. After all, the set of equivalence classes themselves are a partition of the set. Thus, we can contain each element we know to be related in a set.

So we follow previous logic, and discover a potential "minimum" partition to be $\{\{a,c,d\},\{e\},\{b\}\}$. How might we construct further ones, and meet the constraints desired?

We need to be able to not have $c$ and $e$ in the same set, that's all. Thus, we can either:

• Do nothing
• Make a different partition by joining $\{a,c,d\}$ with $\{b\}$
• Make a different partition by joining $\{e\}$ with $\{b\}$

Again, three different partitions - and thus, three different relations.

While this method is totally valid, I personally find it less intuitive, especially if you're the type to prefer visual learning. But whatever floats your boat!

---

...granted, this question is quite old, so I imagine you don't need help now. But hopefully this helps someone in the future, and, if nothing else, gets this question out of the unanswered queue.