Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: To “induce”

Julius Hamilton (Nov 12 2024 at 21:17):

Let there be functions $f : X \to Y, g : Y \to Z$.

$$\begin{CD} @. Z \\ @. @A{g}AA \\ X @>{f}>> Y \end{CD}$$

Can we say then that a function $h : X \to I$ ‘induces’ a function $i : I \to Z$?

$$\begin{CD} I @>{i}>> Z \\ @AhAA @AgAA \\ X @>f>> Y \end{CD}$$

A commutative square can be thought of as a “change in context”. Let $f$ be a function of interest. Function $h$ makes one consider what the “analogous” function to $f$ is which acts on $I$ instead of $X$.

Here is something confusing my intuition.

Consider pre-composing $f$ with a function $k : J \to X$.

$$\begin{CD} J @>k>> X @>f>> Y \end{CD}$$

This is not a transformation of the function $f$. It’s like we started “further back”. It is easy to think of this as a substitution operation. Substitute $x \in X$ with $k(j), \; j \in J$. It’s easy to compute what function $f$ becomes when pre-composed.

If we transform the domain of $f$, there should be an equivalent way to compute how it transforms $f$. But there is not an immediate computation. $f$ does not compose with $h$, nor vice versa.

There are two contexts in which I have thought about this.

1. Let $\mathcal{P} : \text{Set} \to \text{Set}$ be the power-set functor. It seems like the natural choice for $\mathcal{P}(f)$ is the induced function which sends $s \in P(X)$ to $t \in P(Y)$ such that $t$ is the result of swapping each $x \in s$ for $f(x)$.

2. Given a preorder relation $\leq$ on $X$, the equivalence relation $x \sim y \leftrightarrow x \leq y \wedge y \leq x$ ‘induces’ a partial order $\leq'$. For each ordered pair $(x, y)$ in the relation $\leq$, we substitute $x$ and $y$ with their equivalence classes $[x]$ and $[y]$ resp.

It doesn’t feel intuitive to me. In the example of precomposition above, there is an obvious way to compute how $k$ ‘transforms’ $f$. But in the case where we apply a function $h$ to each $x \in X$, what’s a good way to express “that which $f$ becomes when we replace $x \in X$ with $h(x) \in I$”?

Riley Shahar (Nov 12 2024 at 21:33):

Julius Hamilton said:

But in the case where we apply a function $h$ to each $x \in X$, what’s a good way to express “that which $f$ becomes when we replace $x \in X$ with $h(x) \in I$”?

Is there a reason you expect to be able to compute this in general? In good cases you can compute it exactly when:

1. $h$ is an epi, and
2. $f$ is constant on fibers of $h$.

(This is essentially the content of the first isomorphism theorem, for instance.) I guess morally, (1) is telling you that knowing how the extension operates on the image of $f$ is enough to determine a unique map on $I$, while (2) is telling you that it's actually possible to extend $f$ to $I$ in a sensible way. I think you shouldn't expect to be able to solve this problem if you don't have both of these conditions or some analogues.

The situation is different with precomposition, because there we already have a map ($k$ in your example) which is defined on the entire domain of the thing we want to work on, so we don't need to worry about (1), and because all our maps are going in the same direction, so we don't need to be worried about losing information too soon (which is kind of what happens if $f$ is not constant on a fiber of $h$---it means $h$ loses some information that we needed to compute $f$).

John Baez (Nov 12 2024 at 23:07):

@Julius Hamilton - I think Riley was being slightly too polite to be maximally clear. Valuing politeness over maximal clarity is probably a very good strategy in life, but I'm old enough to get away with being a bit more rude. When you said

Julius Hamilton said:

Let there be functions $f : X \to Y, g : Y \to Z$.

$$\begin{CD} @. Z \\ @. @A{g}AA \\ X @>{f}>> Y \end{CD}$$

Can we say then that a function $h : X \to I$ ‘induces’ a function $i : I \to Z$?

$$\begin{CD} I @>{i}>> Z \\ @AhAA @AgAA \\ X @>f>> Y \end{CD}$$

the natural reaction of a mathematician is "huh?" - because in general there is no function $i$ making that second square commute, much less a unique one.

So your question was like asking "can we say that if we open the 10th floor window and walk out, we safely 'float' through the air?" - as if it were a mere question about terminology, when in fact the whole possibility of doing this is deeply in doubt.

Thus, Riley was left wondering if you were talking about some special circumstances in which $h$ does give rise to a unique function $i$ making that second square commute. And Riley described a circumstance in which it does.

John Baez (Nov 12 2024 at 23:14):

In short, there's a difference between a terminology question and a factual question, and your question blurred the line in an uncomfortable way. This is the sort of thing mathematicians slowly learn to avoid... though I sometimes do it myself when I'm confused about what's going on.

David Corfield (Nov 13 2024 at 08:43):

You may enjoy this discussion by @Matteo Capucci (he/him) which develops an idea I had which sees induction (and abduction) as the finding of arrows in situations where there is no required single solution, so unlike composition of arrows (deduction).

Julius Hamilton (Nov 13 2024 at 19:01):

Cool, thanks. Let me see if I can revise my own question.

I’ve heard the term “induced” used here and there. I haven’t been able to find a precise definition for it by Googling. It seems to be that one usually says “$X$ induces $Y$”. I think $X$ is commonly a function or a relation, and $Y$ can be any type of structure.

Does this mean “to induce”, in this context, means “apply function $X$ to some relevant part of something, and the result is $Y$”? This would imply that $Z$, the “original” structure, features the domain of $X$, $D$, somewhere in its definition.

For example, consider a relation $(D, \leq)$. It looks like this: $\{(d_1, d_2), (d_1, d_3), (d_3, d_7), \ldots \}$. Let’s say $X$ is a function $\{(d_1, e_3), (d_2, e_1), (d_3, e_1), (d_7, e_2), \ldots \})$. Is this enough to be able to say, “$X$ induces the relation $\{(e_3, e_1), (e_1, e_2), \ldots \}$”?

This also relates somewhat to a previous question of mine about set comprehension. I am really interested in how the same mathematical thing can have many different conceptual metaphors by which we interpret it. This relates to an article Peva Blanchard linked to about how “$X$ is like a burrito.” In yet another thread (or maybe Stack Exchange), some people including Mike Shulman were talking about how at some point in math, teachers actually have to get their students to “unlearn” the idea that a function is “like a machine which takes in inputs and gives out outputs” (or something like this). I specifically remember being taught exactly that metaphor, in elementary school.

Abstractly, if a function is a collection of ordered pairs, we might observe very carefully what one’s mind is “adding in” that is not intrinsically there, in the definition. For example, a function does not have to be a “process” which “acts on” or “transforms” inputs. In a way, the relationship between inputs and outputs does not have “temporality”. It’s just “an association”.

I am still affected by the idea of a function as a “transformation”. In the above definition of “inducing”, it feels as if we transform a structure into another one, through the act of replacing certain terms. But to define that as a function, I think we would be talking about a general-purpose “replacement function”, which replaces the relevant elements, in any number of structures. I don’t know if that’s definable or not.

When I say, “$X$ induces the relation $Y$”, it feels like there should be a notation like $\underset{\scriptscriptstyle X}{\underset{\rightarrow}{Z\!\!}} = Y$.

(I’ll leave the question of when an induced thing is possible aside for a moment, that question is of equal importance to me though.)

Julius Hamilton (Nov 13 2024 at 19:17):

To be able to formally say “the relation that is obtained by replacing $D$ with $X(D)$”, I am considering expressing it by set comprehension: something like $Y = \{(X(d_0), X(d_1)) | (d_0, d_1) \in Z \}$. I think this is the most correct version, but I wonder if there are other ways.

Maybe this was all an exercise in reinforcing some things I already knew, though. Maybe the above is the standard way.

Riley Shahar (Nov 13 2024 at 19:33):

You shouldn't always expect that every use of a term in informal mathematical speech necessarily has the same underlying formal meaning (or even that it has a precise intended formal meaning). As you say, "$X$ induces $Y$" usually means that somehow the data of $X$ (maybe plus some ambient data) is enough to give us the data of $Y$. That can have a lot of different precise meanings in different contexts.

E.g. all of the following seem to me like totally standard uses of the term induce:

• A relation $R$ on $X$ and a relation $S$ between $X$ and $Y$ together induce a conjugate relation on $Y$ (in the manner you describe).
• An element of a set $A$ and an endomorphism of $A$ together induce a map $\mathbb{N}\to A$.
• A continuous map $f: X\to Y$ of spaces induces a map $\mathcal{O}(Y)\to \mathcal{O}(X)$ between their frames of opens.
• An inner product structure on a vector space $V$ induces a norm, which induces a metric, which induces a topology.
• A representation of a subgroup $H$ of a group $G$ induces a representation of $G$.
• The presence of a terminal object and binary pullbacks in a category induces all finite limits.
• The existence of a bimodule with certain properties induces an additive equivalence of module categories.

and so on.

(I guess a lot of these are some kind of functoriality, but that might just be my mathematical biases... the point is I think you shouldn't really expect a general definition of the term.)

Julius Hamilton said:

For example, consider a relation $(D, \leq)$. It looks like this: $\{(d_1, d_2), (d_1, d_3), (d_3, d_7), \ldots \}$. Let’s say $X$ is a function $\{(d_1, e_3), (d_2, e_1), (d_3, e_1), (d_7, e_2), \ldots \})$. Is this enough to be able to say, “$X$ induces the relation $\{(e_3, e_1), (e_1, e_2), \ldots \}$”?

You could definitely say that. But it's not a formal claim, it's just a verb that communicates the right vibes in this instance.

Mike Shulman (Nov 13 2024 at 21:26):

As you say, "X induces Y" usually means that somehow the data of X (maybe plus some ambient data) is enough to give us the data of Y.

Yeah, and that's basically equivalent to saying there exists a function $F$ such that $F(X)=Y$.