# Inducing a well-defined function on a set

What does it mean to say that $f$ induces a well-defined function on the set $X$?

I'm confused about what the term induce means here, and what role the set $X$ has.

-
If $f$ is a map of groups, then it is not counted as a map of sets. Of course, there is an obvious map of sets corresponding to $f$, and this is called the function on sets induced by $f$. –  only Sep 22 '12 at 21:44

Typically the expression is used in the following setting. You have a function $f:X\to Y$, and you have a partition $\mathscr{P}$ of $X$. If $f(x)=f(y)$ whenever there is a $P\in\mathscr{P}$ such that $x,y\in P$, i.e., if $f$ is constant on each member of $\mathscr{P}$, we can define a function $\bar f:\mathscr{P}\to Y$ by setting $\bar f(P)=f(x)$ for any $x\in P$; $\bar f$ is well-defined because $f(x)$ is the same no matter which $x\in P$ we happen to use to define $\bar f(P)$. In this setting we say that $f$ induces the function $\bar f:\mathscr{P}\to Y$. We may also say that $f$ respects the partition $\mathscr{P}$.

The partition $\mathscr{P}$ might arise in different ways. For example, it might be the set of equivalence classes of an equivalence relation on $X$. If we take $X=\Bbb Z$ and $\mathscr{P}$ to be the set of equivalence classes of the relation congruence modulo $5$, for instance, the function $n\mapsto n^2$ on $\Bbb Z$ respects the partition of $\Bbb Z$ into equivalence classes mod $5$: $m^2\equiv n^2\pmod5$ whenever $m\equiv n\pmod5$. Thus, it induces a corresponding squaring function on $\Bbb Z/5\Bbb Z$ taking $[n]$ to $[n^2]$.

More complicated settings are also possible. In the example above, for instance, $+:\Bbb Z\times\Bbb Z\to\Bbb Z$ respects congruence mod $5$ in the sense that if $m\equiv m'\pmod 5$ and $n\equiv n'\pmod 5$, then $m+n\equiv m'+n'\pmod5$. Congruence mod $5$ gives us the partition $\mathscr{P}=\{[0],[1],[2],[3],[4]\}$ of $\Bbb Z$, which induces a partition $\mathscr{P}\otimes\mathscr{P}=\{P\times Q:P,Q\in\mathscr{P}\}$ of $\Bbb Z\times\Bbb Z$. The operation $+$ respects $\mathscr{P}\otimes\mathscr{P}$, so it induces a corresponding operation $+_5$ of addition on $\Bbb Z/5\Bbb Z$. We would still probably speak of $+_5$ as being induced on $(\Bbb Z/5\Bbb Z)\times(\Bbb Z/5\Bbb Z)$ by $+$.

Another setting that is a step removed from the basic one is the following. We have a function $f:X\to Y$. This function induces a partition $\mathscr{P}$ of $X$ into the fibres of $f$: $\mathscr{P}=\{f^{-1}[\{y\}]:y\in Y\}$. ($\mathscr{P}$ is in fact the coarsest partition of $X$ respected by $f$.) Now suppose that we have a function $g:X\to Z$ that respects $\mathscr{P}$: $g(x)=g(y)$ whenever there is some $P\in\mathscr{P}$ such that $x,y\in P$. Then we can say that $g$ induces the following function $\bar g:Y\to Z$: for each $y\in Y$ choose an $x\in X$ such that $f(x)=y$, and let $\bar g(y)=g(x)$. If you chase back through the definition of $\mathscr{P}$, you’ll see that $\bar g$ is in fact well-defined: if $x_1,x_2\in X$ and $f(x_1)=f(x_2)=y$, then by definition there is a $P\in\mathscr{P}$ such that $x_1,x_2\in P$, so by hypothesis $g(x_1)=g(x_2)$. Thus, it doesn’t matter whether we choose $x_1$ or $x_2$ to define $\bar g(y)$.

There are other possible variations on the same theme, but this may be enough to give you a decent sense of how the word is used.

-

It means that a function is such that we can define a(nother) well defined function on some set $\,X\,$ that'll depend, in some definite way, on the original function.

For example: if $\,f:G\to H\,$ is a group homomorphism and there's some group $\,N\leq \ker f\,$ , with $\,N\triangleleft G\,$ , then $\,f\,$ induces a well-defined group homomorphism

$$\overline f:X:=G/N\to H\,\,,\,\,\text{defined by}\,\,\overline f(gN):=f(g)$$

Please do note that the original function's domain is $\,G\,$ whereas the induced function's domain is $\,G/N\,$ . These two domains are both different sets and different groups.

-
What you describe in your second paragraph is a good example of what the term means, but it’s not an example of what you describe in your first paragraph, which is simply $f\upharpoonright X$. –  Brian M. Scott Sep 22 '12 at 22:14
It may be a linguistic difference: for me, the symbol $\,f\uparrow X\,$ means the function is originally defined in some set containing $\,X\,$ and then we take $\,f\,$ only on that subset $\,X\,$. I don't think this was the intention of the OP when was asked about the function induced on some set. –  DonAntonio Sep 23 '12 at 1:52
I don’t either: that’s why I objected to your first paragraph, which to me clearly describes restricting the function to $X$, i.e., $f\upharpoonright X$. –  Brian M. Scott Sep 23 '12 at 1:54
I think I see now your point. Thanks, I shall edit shortly my answer. –  DonAntonio Sep 23 '12 at 1:56