Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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"?

share|cite|improve this question
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
up vote 2 down vote accepted

The question is quite broad, therefore my answer will also be broad. I hope that it is an answer at all ...

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.