# Is there a category-theoretic perspective on induced functions?

Let $X$ and $Y$ denote sets. Given a function $f : X \rightarrow Y$ and a natural number, there is an induced function $g : X^n \rightarrow Y^n$ defined by $g(x_1,\cdots,x_n) = (f x_1,\cdots,f x_n).$

Similarly, given an arbitrary relation $f : X \rightarrow Y,$ there is an induced function $g : \mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ defined by asserting that for all $A \in \mathcal{P}(X)$ it holds that $g(A) = \{y \in Y|\exists x \in A : (x,y) \in f\}$. Edit. In other words, $g(A) = \mathrm{rng}(f|_A)$.

Intuitively, these constructions work because $X^n$ and $\mathcal{P}(X)$ are "built on top of $X$."

My question is, does category theory shed light on these kinds of constructions? And/or the idea of "built on top of"?

-
For a relation the notation is usually $f\subseteq X\times Y$. And $g$ is merely $\operatorname{rng}(f\upharpoonright A)$. – Asaf Karagila Feb 17 '13 at 2:37
EDIT: In category theory relations are viewed as possessing a "source" (or "domain") and a "target," (or "codomain") thus $f \subseteq X \times Y$ is slightly misleading as a definition, as it suggests that $f$ is merely its graph. – goblin Feb 17 '13 at 2:38
How do you do that vertical line with a "flick" at the top? – goblin Feb 17 '13 at 2:42
Right-click > Show Math As > TeX Commands: \upharpoonright. – Rahul Feb 17 '13 at 2:47
@user18921: Well, I was never a fond of the distinction between $\sin$ as a real valued function and $\sin$ as a real valued function whose values lie in the interval $[-\pi,\pi]$. But fair enough, if you want to use this approach then I am not the one who'll stop you. :-) – Asaf Karagila Feb 17 '13 at 2:50

The idea of "canonical induced maps" leads to the general notion of a functor. Your first example is the $n$th power functor in the category of sets. More generally, if $C$ is a category with products and $n \in \mathbb{N}$, then there is a functor $C^n \to C$ which maps the object $(X_1,\dotsc,X_n)$ to $X_1 \times \dotsc \times X_n$ and the morphism $(f_1,\dotsc,f_n)$ to $f_1 \times \dotsc \times f_n$, which is the morphism $f$ defined by the equation $p_i f = f_i p_i$, using the universal property of products. You can compose with the diagonal functor $C \to C^n$ to get the $n$th power functor $C \to C, X \mapsto X^n$. Your second example is the covariant power set functor $\mathcal{P} : \mathsf{Set} \to \mathsf{Set}$. It can be generalized to suitable categories with a subobject classifier. Somehow a more basic functor is the contravariant power set functor, because it is just the hom functor $\hom(-,\{0,1\})$.

The idea of objects canonically built up from other objects leads to the general notion of limits, colimits and more generally universal properties.

-

I find that the question is somewhat unfocused, or at least I can't pinpoint what it is you are trying to ask except for "on top of $X$" part which is answered simply by considering concrete categories: categories $C$ equipped with a functor $C\to Set$ which behaves like a forgetful functor. You can find a lot information in the book "Abstract and concrete categories" (free on the web) that I think might answer, or at least provide you with lots of clarifications and ideas, for what you intended to ask.

-

More than a year later, here's my answer to the question posed by my old self: the concept of a monad is what you're grasping for.

-