Three ways for functions to act on power sets

30 Oct 2023

If \(f\) is a function from a set \(A\) to a set \(B\), there are two well-known ways to lift \(f\) to a function of subsets:

  • The preimage of a subset \(Y \subseteq B\) is the subset \(\{ x \in A \mid f(x) \in Y \}\). I will denote this as \(f^*(Y)\).
  • The image of a subset \(X \subseteq A\) is the subset \(\{ f(x) \mid x \in X \}\), which can be written more explicitly as \(\{y \in B \mid \exists x \in X . f(x) = y\}\). I will denote this as \(f_\exists(X)\).

The preimage function \(f^* : P(B) \to P(A)\) has many nice properties:

  1. \(f^*(\varnothing) = \varnothing\).
  2. \(f^*(B) = A\).
  3. If \(X \subseteq Y\), then \(f^*(X) \subseteq f^*(Y)\).
  4. \(f^*(X \cup Y) = f^*(X) \cup f^*(Y)\).
  5. \(f^*(X \cap Y) = f^*(X) \cap f^*(Y)\).
  6. \(f^*({\sim}X) = {\sim}f^*(X)\)     (where \({\sim}\) denotes the complement of a subset).

The image, however, has fewer nice properties. In particular, if \(f^*\) is replaced by \(f_\exists\), then properties 1, 3, and 4 hold, but properties 2, 5, and 6 do not.

The fact that the preimage is generally “nicer” than the image shows up in many fields of mathematics. In topology, for instance, a continuous function is defined by the property that the preimage of any open subset is an open subset. And in algebra, one encounters theorems such as “the preimage of a normal subgroup is a normal subgroup” and “the preimage of a prime ideal is a prime ideal,” which do not hold if “preimage” is replaced with “image.”

It turns out there is a third, lesser-known, way for \(f\) to act on power sets, which has properties dual to those of the image. For the purposes of this article, I will call this the coimage and denote it by \(f_\forall\). The coimage of a subset \(X \subseteq A\) is defined as \(f_\forall(X) = \{ y \in B \mid \forall x \in A. f(x) = y \implies x \in X \}\). In other words, \(f_\forall(X)\) is the subset of \(B\) consisting of elements whose fibers are contained in \(X\).

The image and the coimage satisfy the following properties:

  1. \(f_\exists(\varnothing) = \varnothing\).
  2. \(f_\forall(A) = B\).
  3. If \(X \subseteq Y\), then \(f_\exists(X) \subseteq f_\exists(Y)\) and \(f_\forall(X) \subseteq f_\forall(Y)\).
  4. \(f_\exists(X \cup Y) = f_\exists(X) \cup f_\exists(Y)\).
  5. \(f_\forall(X \cap Y) = f_\forall(X) \cap f_\forall(Y)\).
  6. \(f_\exists({\sim}X) = {\sim}f_\forall(X)\) and \(f_\forall({\sim}X) = {\sim}f_\exists(X)\).

Perhaps the nicest characterization of the image and the coimage is as follows:

  • \(f_\exists(X)\) is the smallest subset \(Y \subseteq B\) for which \(x \in X\) implies \(f(x) \in Y\).
  • \(f_\forall(X)\) is the largest subset \(Y \subseteq B\) for which \(f(x) \in Y\) implies \(x \in X\).

In category theory, the image and coimage are encountered as the left and right adjoints of the preimage respectively. This means that

  • \(f_\exists(X) \subseteq Y\) if and only if \(X \subseteq f^*(Y)\)     (\(f_\exists\) is left adjoint to \(f^*\)).
  • \(Y \subseteq f_\forall(X)\) if and only if \(f^*(Y) \subseteq X\)     (\(f_\forall\) is right adjoint to \(f^*\)).

Or equivalently,

  • \(X \subseteq f^*(f_\exists(X))\).
  • \(f_\exists(f^*(Y)) \subseteq Y\).
  • \(f^*(f_\forall(X)) \subseteq X\).
  • \(Y \subseteq f_\forall(f^*(Y))\).

The main reason why \(f^*\) has so many nice properties, whereas \(f_\exists\) and \(f_\forall\) each satisfy only around half of those properties, is that \(f^*\) has both a left and a right adjoint, while \(f_\exists\) has only a right adjoint, and \(f_\forall\) has only a left adjoint.

Lastly, the notation I have been using for the image and coimage (\(f_\exists\) and \(f_\forall\)) was not chosen at random. You are probably aware that there is a correspondence between subset operations and logical operations, with \(\cap\) corresponding to \(\land\), \(\cup\) corresponding to \(\lor\), and complement (which I have been denoting \({\sim}\)) corresponding to \(\neg\). It turns out that this correspondence can be extended to include quantifiers, and that \(f_\exists\) and \(f_\forall\) correspond to \(\exists\) and \(\forall\) respectively.

For example, property 5 above, which says that \(f_\forall(X \cap Y) = f_\forall(X) \cap f_\forall(Y)\), corresponds to the logical rule \((\forall x. P(x) \land Q(x)) \iff (\forall x. P(x)) \land (\forall x. Q(x))\). And just as it is not the case that \(f_\forall(X \cup Y) = f_\forall(X) \cup f_\forall(Y)\), it is also not the case that \((\forall x. P(x) \lor Q(x)) \iff (\forall x. P(x)) \lor (\forall x. Q(x))\).