Past exam of the mathematics course of the University of Cambridge / 2022 / ia / Paper 4 / 7F / c / Solution

The definition saysEquality of sets is reflexive, symmetric, and transitive, so $\sim$ is an equivalence relation. Its classes are indexed by all subsets of $\{1,\dots ,n\}$, and every subset occurs as the support of its zero-one indicator vector. The number of classes is therefore