Discrete math equivalence classes

discrete mathematicsequivalence-relations

Let $A$ be a finite set of size $k$ and $R$ a relation on the power set $P(A)$ defined by $R=\left\{(A,B) : |A|=|B|\right\}$

  1. Show that $A$ is an equivalence relation.
  2. Let $a \in A$. What is the size of the equivalence class of $\{a\}$?
  3. Let $a, b$ be two different elements of $A$. What is the size of the equivalence class of $\{a, b\}$?

I’m having a lot of trouble with this problem. It says the relation is on the power set, but then I’m finding the size of the equivalence class of elements within $A$, and then of $(a,b)$? I’m honestly completely lost and don’t have any base to build off of. I think I’m a bit confused on the concept of the size of equivalence classes in general.

Best Answer

Informally, under this equivalence relation two subsets are equivalent when they have the same size.

Thus, the equivalence class of $\{a\}$ consists of all subsets of $A$ with cardinality/size equal to one. Thus the size of this equivalence class is $k=|A|$.

The equivalence class of $\{a, b\}$ consists of all two element subsets of $A$. Thus the size of this equivalence class is $\binom{k}{2}=\frac{k(k-1)}{2}$.

Related Question