What are "multi-images" really called, and where can I learn more about them?

96 Views Asked by At

Given a function $f : A \rightarrow B$, between finite sets, there is a multiset induced on $B$ by declaring the multiplicity of $b \in B$ to be the cardinality of $f^{-1}(b).$ For argument's sake, lets call this the multi-image of $f$.

Multi-images can also be defined in a more algebraic way. Given a function $f : A \rightarrow B$, we get an induced function $\mathbb{N}\langle f \rangle : \mathbb{N}\langle A \rangle \rightarrow \mathbb{N}\langle B\rangle$ by assuming $\mathbb{N}$-linearity and agreement with $f$ when restricted to $A$. Then the multi-image of $f$ is $$\mathbb{N}\langle f\rangle \left(\sum_{a \in A} \langle a \rangle\right).$$ This sum makes sense because $A$ is finite. Abusing notation a bit, we can write $f$ instead of $\mathbb{N}\langle f \rangle$, and we can write $A$ in place of that sum, in which case the multi-image can be denoted $f(A)$, so long as we tell the reader what we're doing.

Furthermore, if we allow multisets to be infinite, we don't have to assume that $A$ and $B$ are finite. At this level of generality, the above paragraph continues to make sense, so long as we replace commutative monoids with complete monoids, replacing ordinary linearity with infinitary linearity, and replacing the initial semiring $\mathbb{N}$ with the initial monoid object in the category of complete monoids.

The multi-image construction can be seen as a de-categorification of the operation that replaces each function $f : A \rightarrow B$ with the corresponding slice of $B$.

Now in my opinion, multi-images are a very natural construction. For example, injectivity and surjectivity can be decided from the multi-image alone (compare with ordinary images, which can only detect surjectivity.) However, I can't find any information about them online, and the term "multi-image" seems not to get any hits.

Question. Do multi-images have an accepted name, and if so, where can I learn more about them?

For example, I'd be interested in seeing uses of multi-images in combinatorics, where remembering the number of ways something can happen is a desirable feature.

1

There are 1 best solutions below

0
On BEST ANSWER

This is the pushforward of counting measure on $A$ to $B$ along $f$. You'll probably have more success using the term "pushforward" as a search term in general, as overloaded as it is, because almost nobody thinks in terms of multisets.

Here is a neat categorical version of this construction. Let me write a function between finite sets as $f : X \to Y$, and consider any category $C$. Pullback along $f$ defines a functor

$$f^{\ast} : C^Y \to C^X$$

between the category of maps $Y \to C$ and the category of maps $X \to C$, and an interesting question to ask is when this map has a left or a right adjoint. Note that if $Y$ is a point this question is exactly asking when $C$ has $X$-ary colimits or limits respectively. In general, the left adjoint is given by taking colimits along the fibers of $f$, whenever these exist, and the right adjoint is given by taking limits along the fibers of $f$, again whenever these exist.

This construction is a simple example of a Kan extension. In more general Kan extensions $X$ and $Y$ are now themselves categories. It's again true that left and right Kan extension are given by fiberwise colimits and limits when this makes sense, except that the notion of "fiber" is more complicated.