Let $|A| = n \geq 2$ a set. How many equivalence relations are there on $A$ that have two equivalence classes?

Question

Let $|A| = n \geq 2$ a set. How many equivalence relations are there on $A$ that have two equivalence classes?

Note the answer is in this post. My problem is I don't fully understand it. Can someone give a concrete example with say a set $3 = n = |A| = |\{a_1, a_2, a_3\}|$ to show how they find the formula $\frac {2^n-2}2$?

I understand the first part of the sentence of "user873979" due to the simple fact that $$A = \bigcup_{\alpha \in A}[\alpha] \quad\text{and} \quad [\alpha]\cap[\beta] = \emptyset \quad \text{for }\alpha,\beta \in A.$$ But then then I get lost after that I don't understand.

Also note that I know that given a relation $\sim$ on an arbitrary set $|A|=n$, we know $|\sim| = \sum\limits_{i=1}^n |A_i|^2$.

Again, if one could explain the linked post in terms of the example set I gave, i.e., $3 = n = |A| = |\{a_1, a_2, a_3\}|$, that would be very helpful I am sure! Thank you!

Answer 1

You basically want to count the number of partitions of $A$ into two disjoint nonempty sets whose union is $A$.

You can count this by choosing a nonempty proper subset of $A$ to be one equivalence class, and letting the complement be the other equivalence class. (The original subset must be proper in order for the complement to be nonempty as well.)

There are $2^n$ subsets of $A$, and we don't want the empty set $\varnothing$ or the whole set $A$, so that leaves $2^n-2$. Finally, we don't care about which of the two equivalence classes is "first," so we divide by two.

---

Explicit explanation for $n=3$ with $A=\{1,2,3\}$:

There are $2^3=8$ subsets $\varnothing, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2,3\}, \{1,2,3\}$. We ignore $\varnothing$ and $\{1,2,3\}$, leaving $2^3-2=6$.

Given one subset, say, $\{1,3\}$, we can let the complement, $\{2\}$ in this case, be the other equivalence class. So the equivalence classes $\{1,3\}, \{2\}$ corresponds to one relation on $\{1,2,3\}$. You can do this for any of the $6$ sets mentioned above. Finally, since $\{1,3\},\{2\}$ and $\{2\}, \{1,3\}$ correspond to the same relation (the order does not matter), we divide by $2$.

Answer 2

I can't access to the link provided, but to calculate how many equivalence classes are there with two equivalence classes, note that that's the same as asking in how many ways you can split $A$ into two disjoint non-empty subsets, and that is the same as asking how many non-empty proper subsets $A$ has, divided by two because we're then counting each set twice.
For example, for $A=\{a,b,c\}$, there are the following non-empty proper subsets: $$\{a\},\, \{b\},\, \{c\},\, \{a,b\},\, \{a,c\},\, \{b,c\}.$$ Notice that there is duplication since each one is already the complement of another.
So, if $|A|=n$, we have that $A$ has $2^n$ subsets; one of them is empty and the other is $A$ itself, so there are $2^n-2$ non-empty proper subsets.
Since we are already counting doubles (because the complement of a non-empty proper subset is also a non-empty proper subset), we reach the $\frac{2^n-2}{2}$ pairs of disjoint non-empty subsets.