Equivalence Relation on Power Set induced by Intersection with Subset/Cardinality of Set of Equivalence Classes

Theorem

Let $A, T$ be sets such that $A \subseteq T$.

Let $S = \powerset T$ denote the power set of $T$.

Let $\alpha$ denote the relation defined on $S$ by:

$\forall X, Y \in S: X \mathrel \alpha Y \iff X \cap A = Y \cap A$

We have that $\alpha$ is an equivalence relation.

Let $A$ be finite with $\card A = n$, where $\card {\, \cdot \,}$ denotes cardinality.

The cardinality of the set of $\alpha$-equivalence classes is given by:

$\card {\set {\eqclass X \alpha: X \in S} } = 2^n$

Proof

That $\alpha$ is an equivalence relation is proved in Equivalence Relation on Power Set induced by Intersection with Subset.

Let $U \subseteq A$.

Then $U$ is in its own $\alpha$-equivalence class.

Now suppose $U' \subseteq A$ such that $U \ne U'$.

From Intersection with Subset is Subset:

$U \cap A = U$

and:

$U' \cap A = U'$

So:

$U \ne U' \implies \eqclass U \alpha \ne \eqclass {U'} \alpha$

and so there are as many $\alpha$-equivalence classes as there are subsets of $A$.

That is:

$\card {\set {\eqclass X \alpha: X \in S} } = \powerset A$

The result follows from Cardinality of Power Set of Finite Set.

$\blacksquare$

Sources

• 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $2 \ \text {(iii)}$