Total number of equivalence class for a set

Question

Question: Let S be a set of all equivalence relations on the set $$A = \{1,2,3,4,5,6,7,8,9\}$$

in which one equivalence class is: $\{1,3,5,7,9\}$. What is ${|S|}$?

Initially I thought the equivalence classes are: (i) odd numbers, (ii) even numbers. Thus, making $|S| = 2$. However the textbook's answer is: $$1 + {{4}\choose{3}} + {{4}\choose{2}} + {{\frac{1}{2}}{{4}\choose{2}}} + 1 = 15$$

I can't seem to get the point just by looking at the answer and trying to reverse it. I'm looking for an explanation on what that answer really stands for. Any help is greatly appreciated.

Answer 1

From what's given to you, you cannot figure out what the equivalence relation is. All you know is that $\{ 1,3,5,7,9 \}$ is one equivalence class of the equivalence relation, but there are many options for what other equivalence classes there are as part of the equivalence relation. You yourself indicated one possibility, which is that there is one other equivalence class, namely $\{ 2,4,6,8\}$. But another possibility is that there are two more equivalence classes, such as $\{2,4 \}$ and $\{ 6,8\}$ ... or you could have $\{ 2,6\}$ and $\{ 4,8 \}$, ... or $\{ 2,4,6 \}$ and $\{8\}$. Or maybe there are three further equivalence classes, such as $\{2,4\}$, $\{6\}$, and $\{8\}$. ... and of course you could have four more equivalence classes.

Now, if you work out the number of possible equiavelnce relations you can get this way, you'll get to $15$, exactly as indicated by the formula: there is $1$ way to put the $4$ remaining elements into $1$ set, and also also $1$ way to put them all in their own separate set. There are ${4 \choose 3}=4$ ways to put $3$ of them in one set (leaving the remaining one by itself), ${4 \choose 2}=6$ ways to pick two of them to go into one set and putting the remaining two by themselves in separate sets, and $3$ ways to split the four elements into two sets of two.

Answer 2

The question can be rephrased as: how many partitions exist on the set $\{2,4,6,8\}$?

This because these partitions correspond one-to-one with partitions of $\{1,2,3,4,5,6,7,8,9\}$ that have $\{1,3,5,7,9\}$ as element.

Secondly equivalence relations on set $\{1,2,3,4,5,6,7,8,9\}$ that have $\{1,3,5,7,9\}$ as element correspond one-to-one with equivalence relations on set $\{1,2,3,4,5,6,7,8,9\}$ that have set $\{1,3,5,7,9\}$ as equivalence class.

There are $B_4=15$ possibilities where $B_n$ denotes the Bell number.

Also a look at Stirling numbers of the second kind might be helpful.