Let $A = \{1, 2, \ldots , n\}$ and R be the set of all equivalence relations on $A$. Let $∼$ be the relation of equivalence over the set R, defined by: $R ∼ S \iff |A/R| = |A/S|$. Find $|R/∼|$.
The smallest inclusion-wise equivalence relation over $A$ is $R=\{(1, 1), (2, 2), \ldots, (n, n)\}$, i.e., the identity in $A$.
What are its equivalence classes?
Well, $[1]_R = \{x\in A \mid 1 \mathrel{R} x\} = \{1\}$ and so on. So, the identity has exactly $n$ equivalence classes.
For two relations to be related by $∼$, the number of elements in their factor sets must be equal. Alright, but how do I know what that means...
In a sense, every equivalence relation over A must extend the identity because equivalence relations are reflexive (for every $a$ from $A$, it holds that $a\mathrel{R} a$). If we take a relation and union it with the identity, we get its reflexive closure. Wow, I can't believe I just said all those complex words.
Let's take another equivalence relation over $A$, for example, $S=\{(1, 1), ..., (n, n), (1, 2), (2, 1)\}$. Notice that by adding the ordered pair $(1, 2)$, to maintain symmetry, we must also add $(2, 1)$.
We haven't violated transitivity since we have $(1, 1)$ due to the reflexivity of $S$ (as an equivalence relation).
So, by adding $(a, b)$, we must also add $(b, a)$. We consider $a$ and $b$ to be distinct since we've already added all ordered pairs with equal components. We just don't need to add $(a, a)$ because it's already in the relation.
And ultimately, what happens to the equivalence classes of $S$? Well, now $1$ is not only related to itself (reflexivity) but also to $2$. The same goes for $2$: $(2, 2)$ is in $S$, but so is $(2, 1)$. How many classes did we lose? One, right? We merged $[1]$ and $[2]$.
Let $T=Id \cup \{(4, 3), (3, 4)\}.$ We have $S ~ T$.
Let's see what $[T] = \{ S | T ∼ S \}$ is. This set definitely contains $S$ since we've added two ordered pairs, and consequently, the number of elements in the factor sets of the relations $S$ and $T$ has decreased by one.
To determine the number of elements in $[R]$, i.e., $|[R]|$, we need to count how many ways we can choose two (distinct) elements from $n$.
We've seen that this leads to obtaining a new equivalence relation that extends the identity. The order doesn't matter. This can be done in $n \choose 2$ ways.
Sure, but these are equivalence relations that we've extended by $1$ (so $2$) ordered pairs...
How do I count them all?
Even after all that thought and ideas, I still don't understand how to solve the problem. Thanks!
But $|{\bf R}/$~| is simply $n$.
Indeed, let $R$ and $S$ both be in $\bf{R}$ such that the ground-set $A=\{1,2,\ldots,n\}$ is partitioned into the same number $k$ of equivalence classes by $R$, as $A=\{1,2,\ldots,n\}$ is partitioned into by $S$ i.e., $S$ partitions $A$ into $k$ equivalence classes also as $R$ does.
Then $R$ and $S$ are collapsed together into the same class in $\bf{R}/$~. Write this class as ${\bf C}_k$.
Then clearly $k$ as in 2. above can vary from $1$ to $n$ thus there are $n$ such classes in $\bf{R}/$~; indeed $\bf{R}/$~ $=$ $\{{\bf C}_k; \ k=1,2\ldots,n\}$.