How many different equivalent relations can you define on set of three elements?

Question

Let X be a set of three elements ${a,b,c}$.

1.How many different relations can you define?

The answer is 9, as $R\subset X \times X$

This is easy to see for me, I imagine it as a ~ a, a ~ b, ..., c ~ a, ...

2.How many different equivalent relations can you define?

The answer is five. The argument is that you can list all partitions: {{a},{b},{c}},{{a,b},{c}},{{a},{b,c}},{{a,c},{b}},{{a,b,c}}.

What I'm not following is that to have an equivalence relation I must show that it's reflexive (i.e. a ~ a), symmetric (i.e. a ~ b = b ~ a) and transitive (i.e. a ~ b, b ~ c = a ~ c). Which for me covers one equivalence relation; involving three elements. How do the rest four look like?!

Answer 1

Your answer for part (1) is incorrect. Any relation on a set $X$ is a subset of $X \times X$. Thus the number of relations is the size of the power set of $X \times X$. In this particular case, $|X \times X|=9$, thus the power set will have size $2^9=512$ relations.

For part (2): Partitions of a set are in one-one correspondence with the equivalence relations on the set, i.e. for each partition, there is an equivalence relation and vice versa.

For example, if we have the partition $\{\{a,b\}, \{c\}\}$, then the elements living in one "part" of the partition will be equivalent to each other. Thus the relation corresponding to this partition will be $$R=\{(a,a), (a,b), (b,a), (b,b), (c,c)\}.$$

Likewise, the relation for the partition $\{\{a\},\{b\}, \{c\}\}$, the corresponding relation will be $$S=\{(a,a), (b,b), (c,c)\}.$$

Answer 2

A relation on $X$ is any member of the power set of $X \times X$.

Thus an example if $X = \{a,b,c\} $ is $R_1 = \{ a\sim b, c\sim c \}$ but of course this is not an equivalence relation (for example, we would not have $R_1 (a,a)$ which is $a\sim a$).

So there are $2^9$ relations on a three-element set. The answer of $9$ is wrong.

An equivalence relation must include $\bigcup_{x\in x} x\sim x$ so in our case it must include each of $a\sim a$, $b\sim b$, $c\sim c$. And it must satisfy $$\forall{x,y \in X} : (x \sim y \in R) \implies (y \sim x \in R)$$ And it must also satisfy $$\forall{x,y,z \in X} : (x \sim y \in R) \wedge (y \sim z \in R)\implies (x \sim z \in R)$$ So our equivalence relation $E$ can be formed in exactly 5 ways:

(1) All relations in $E$ are of the form $x = x$.

(2) $E$ includes all relations of the form $x=y$ for any pair $(x,y)$. (This can be expressed by the shorthand $ a \sim b \sim c$.

(3) - (5) The union of case (1) with the two relationships $x \sim y, y \sim x $ for some particular pair of distinct elements $(x,y)$. For example, $\{ a \sim a, b\sim b, c\sim c, a\sim b, b\sim a\}$. Since there are three ways to select the "odd man out" among the three elements, 3 such relationships exist.

Answer 3

Partitions of a set are in one-one correspondence with the equivalence relations on the set, i.e. for each partition, there is an equivalence relation and vice versa.

For the set with the three elements $\{a,b,c\}$ there are five ways to partition them while the classes of each partition are disjoint and the union of the classes in each partition equals the set (by definition of a partition}.

First possible partition: $\{\{a\},\{b\},\{c\}\} : 3$ classes, each class with $1$ element.

$2$nd possible partition: $\{\{a,b\},\{c\}\} 2$ classes, one with elements $a,b$ and the other with $c$.

Similarly we see three other possible partitions: $\{\{a\},\{b,c\}\},\{\{a,c\},\{b\}\}$, and $\{\{a,b,c\}\}$.

Because these are the only five possible ways we can partition the set into disjoint classes, whose union equals exactly the original set $\{a,b,c\}$ , we conclude that there are five equivalent relations.

That is of the $512$ possible relations on the set $\{a,b,c\}$ only five are equivalent relations. Verify that each relation corresponding to each partition is an equivalent relation.