Cardinality of Set of Characteristic Functions on Finite Set

Theorem

Let $I$ be a finite set.

The number of characteristic functions on $I$ is:

$2^{\card I}$

where $\card I$ denotes the cardinality of $I$.

Proof

Let $A = \set {0, 1}$.

A characteristic function of $I$ is a mapping from $I$ to $A$.

Hence the set of characteristic functions on $I$ is the indexed Cartesian space $A_I$:

$A^I = \ds \prod_{i \mathop \in I} A := \set {f: \paren {f: I \to A} \land \paren {\forall i \in I: \paren {\map f i \in A} } }$

Hence from Cardinality of Set of All Mappings:

$\card {A^I} = 2^{\card I}$

$\blacksquare$

Sources

• 1975: Bert Mendelson: Introduction to Topology (3rd ed.) ... (previous) ... (next): Chapter $1$: Theory of Sets: $\S 10$: Arbitrary Products: Exercise $1$