Cardinality of Subset Relation on Power Set of Finite Set
Theorem
Let $S$ be a set such that:
- $\left|{S}\right| = n$
where $\left|{S}\right|$ denotes the cardinality of $S$.
From Subset Relation on Power Set is Partial Ordering we have that $\left({\mathcal P \left({S}\right), \subseteq}\right)$ is an ordered set.
The cardinality of $\subseteq$ as a relation is $3^n$.
Proof
Let $X \in \mathcal P \left({S}\right)$.
Since $X \subseteq S$, it follows that:
- $X' \subseteq X \implies X' \in \mathcal P \left({S}\right)$
because the Subset Relation is Transitive.
From Cardinality of Power Set of Finite Set, it follows that for any $X \in \mathcal P \left({S}\right)$:
- $\left\{{X' \in \mathcal P \left({S}\right): X' \subseteq X}\right\}$
has $2^{\left|{X}\right|}$ elements.
Therefore, the cardinality of $\subseteq$ is given by:
- $\displaystyle \sum_{X \mathop\subseteq S} 2^{\left|{X}\right|}$
Let us split the sum over $\left|{X}\right|$:
- $\displaystyle \sum_{X \mathop\subseteq S} 2^{\left|{X}\right|} = \sum_{k \mathop = 0}^n \sum_{\substack{X \mathop\subseteq S \\ \left|{X}\right| = n}} 2^{\left|{X}\right|}$
It now follows from Cardinality of Set of Subsets that:
- $\displaystyle \left|{\subseteq}\right| = \sum_{k \mathop = 0}^n \binom n k 2^k$
From the Binomial Theorem:
- $\displaystyle \sum_{k \mathop = 0}^n \binom n k 2^k = \left({1 + 2}\right)^n$
Hence:
- $\displaystyle \left|{\subseteq}\right| = 3^n$
$\blacksquare$
Sources
- 1983: George F. Simmons: Introduction to Topology and Modern Analysis ... (previous): $\S 1$: Sets and Set Inclusion