Powerset Functors

Definition 28   The powerset of a set $A$ is the set of all subsets of $A$. Standard notations for this include $P(A)$, ${\cal P}(A)$ and $2^A$.

Proposition 46   ${\cal P}(A)$ is partially ordered by $\subseteq$ with largest element $A$ and smallest element $\emptyset$.

(5 Points )

There are three ways to define functions on the powerset from a function

$$f:A\to B$$

Definition 29   The inverse image functor $f^*:{\cal P}(B)\to {\cal P}(A)$ takes a subset $B'$ to the set

$$f^*(B')=\{a\vert a\in A \mbox{ and } f(a)\in B'\}.$$

This is also sometimes (confusingly) written $f^{-1}(B')$.

Definition 30   The direct image functor $\exists_f:{\cal P}(A) \to {\cal P}(B)$ takes the subset $A'$ to the set

$$\exists_f(A')=\{b\vert b\in B \mbox{ and there is an }a\in A' \mbox{ with } b=f(a)\}.$$

This functor is sometimes (again, somewhat confusingly) written as $f(A')$.

Definition 31   The universal quantification functor $\forall_f:{\cal P}(A) \to {\cal P}(B)$ takes the subset $A'$ to the set

$$\forall_f(A')=\{b\vert b\in B \mbox{ and every }a\in A \mbox{ with } b=f(a) \mbox{ has }a \in A'\}.$$

This functor is much less used than the inverse image and direct image functors.

Proposition 47   The function $f^*:{\cal P}(B)\to {\cal P}(A)$ is a functor; that is, if $B''\subseteq B'$ then $f^*(B'')\subseteq f^*(B')$.

(2 Points )

Proposition 48   The function $\exists_f:{\cal P}(A) \to {\cal P}(B)$ is a functor; that is, if $A''\subseteq A'$ then $\exists_f(A'')\subseteq \exists_f(A')$.

(2 Points )

Proposition 49   The function $\forall_f:{\cal P}(A) \to {\cal P}(B)$ is a functor; that is, if $A''\subseteq A'$ then $\forall_f(A'')\subseteq \forall_f(A')$.

(2 Points )

Proposition 50   For any $f$, $f^*$ preserves intersection and union.

(4 Points )

Proposition 51   For any $f$, $\exists_f$ preserves union, but need not preserve intersection.

(4 Points )

Proposition 52   For any $f$, $\forall_f$ preserves intersection, but need not preserve union.

(4 Points )

Proposition 53   For any $A'\subseteq A$ and $B'\subseteq B$, $f^*(B')\subseteq A'$ if and only if $B' \subseteq \forall_f(A')$.

(4 Points )

Proposition 54   For any $A'\subseteq A$ and $B'\subseteq B$, $A' \subseteq f^*(B')$ if and only if $\exists_f(A') \subseteq B'$.

(4 Points )

Total for section: 141.