the power set functor

Posted Thursday March 2 2023.

If A and B are sets, then so is B^A, the set of functions A → B. In general, we have that B^A is an exponential object in the category of sets. The superscript notation is justified when A and B have finitely many elements, because then |B^A| = |B|^|A|, where vertical bars denote the cardinality of a set.

Given some fixed set S, consider the mapping F : A ↦ A^S. This defines an endofunctor on the category of sets: if f : A → B is a function between sets A and B, then F(f) is the corresponding map A^S → B^S which takes a function g ∈ A^S and returns f ∘ g ∈ B^S.

Likewise, there is a contravariant functor G : A ↦ S^A which sends every function f : A → B to the map S^B → S^A, which takes each g ∈ S^B and returns g ∘ f ∈ S^A. In the case when S = 2, the set with two elements, we can regard functions A → 2 as subsets of A. Thus, the mapping A ↦ 2^A is the contravariant power set functor. Given two sets A and B, and their power sets 2^A and 2^B, the power set functor sends any map f : A → B to the preimage map 2^B → 2^B given by U ↦ f^− 1(U) = {a ∈ A ∣ f(a) ∈ U} for each subset U ∈ 2^B.