index, posts, library, music.

the power set functor

Posted Thursday March 2 2023.

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

Given some fixed set S, consider the mapping F : A ↦ AS. 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 AS → BS which takes a function g ∈ AS and returns f ∘ g ∈ BS.

Likewise, there is a contravariant functor G : A ↦ SA which sends every function f : A → B to the map SB → SA, which takes each g ∈ SB and returns g ∘ f ∈ SA. 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 ↦ 2A is the contravariant power set functor. Given two sets A and B, and their power sets 2A and 2B, the power set functor sends any map f : A → B to the preimage map 2B → 2B given by U ↦ f − 1(U) = {a ∈ A ∣ f(a) ∈ U} for each subset U ∈ 2B.