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: measuring similarity of objects with functors

David Egolf (Oct 28 2023 at 16:38):

We can think of a functor $F: C \to D$ as a measuring system, where the measurement of an object $c$ is an object $F(d)$. Extremely similar input objects yield extremely similar output objects, in the sense that if $c \cong c'$ in $C$, then $F(c) \cong F(c')$ in $D$.

Let us imagine there is an unknown object $x$ in $C$. We do not know $x$, but we know what $F(x)$ is. We would like to determine what $x$ could be, consistent with the measurement $F(x)$. One approach would be to consider one object of $C$ at a time, calculate $F(c)$ and then determine whether $F(c) \cong F(x)$. If we did this for every object $c$ of $C$, then we would be able to determine the objects in $C$ that $x$ could possibly be, given the measurement $F(x)$. (Note that this doesn't necessarily determine $x$ up to isomorphism though, as $F(c) \cong F(c')$ might be true even for non-isomorphic $c$ and $c'$).

However, this procedure is potentially very slow: $C$ could have a lot of objects. In addition, we don't necessarily gain a lot of insight as to the nature of $x$ once we have performed a calculation that tells that $F(x)$ is not isomorphic to $F(c)$. This feels a lot like a search that wanders around aimlessly until it happens upon the exact right answer.

I wonder if there is some way to modify this procedure to be faster. Instead of just assessing whether $F(c) \cong F(x)$, maybe we could try and define some notion of similarity in $C$ and $D$ that is (at least somewhat) preserved by $F$. The idea is to assess how "close" $F(c)$ is to $F(x)$, and then use that to guide our search for our next candidate object $c'$.

What are some examples of ways to measure the similarity of objects in some categories? And are there any functors that preserve these measures of similarity, in the sense that if $c$ is "close" to $c'$, then $F(c)$ is "close" to $F(c')$? (It might be even more helpful to know that if $F(c)$ is close to $F(c')$, then $c$ is close to $c'$, but this might be a lot to ask for!)

John Baez (Oct 28 2023 at 16:47):

David Egolf said:

We can think of a functor $F: C \to D$ as a measuring system, where the measurement of an object $c$ is an object $F(d)$. Extremely similar input objects yield extremely similar output objects, in the sense that if $c \cong c'$ in $C$, then $F(c) \cong F(c')$ in $D$.

Nitpicky comment: I wouldn't translate $\cong$ as 'extremely similar', I'd translate it as 'the same in some way' or (even better) 'isomorphic'. 'Extremely similar' sounds like some distance is small. Thus, 'extremely similar' is not a transitive relation.

John Baez (Oct 28 2023 at 16:50):

David Egolf said:

What are some examples of ways to measure the similarity of objects in some categories? And are there any functors that preserve these measures of similarity, in the sense that if $c$ is "close" to $c'$, then $F(c)$ is "close" to $F(c')$?

There are many answers to this, but if your notion of 'close' is captured by a distance function, then one of the simplest is o use categories internal to the category $\mathsf{Met}$ of metric spaces. For a category internal to $\mathsf{Met}$, the set of objects is a metric space! Thus, you can talk about the distance between two objects.

If you do this, it's natural to let $F$ be a functor internal to $\mathsf{Met}$. Then $F$ is continuous on objects, so if $c$ is "close" to $c'$, then $F(c)$ is "close" to $F(c')$.

This is a nice example of how internal categories work.

David Egolf (Oct 28 2023 at 17:01):

Awesome, thanks! Now I have (another) good reason to learn more about internalization.

Mike Shulman (Oct 28 2023 at 17:14):

As you noted, even your impractical procedure won't tell you for sure what $c$ is, since functors don't preserve non-isomorphicness. A much more common use of functors is to determine that two objects are not isomorphic, since functors do reflect non-isomorphicness: if $F(c)\not\cong F(c')$, then $c\not\cong c'$. This is a version of what's called "computing an invariant". For instance, if two topological spaces have non-isomorphic fundamental groups, then they cannot be homeomorphic.

John Baez (Oct 28 2023 at 18:51):

Mike's comment also explains why functors that do reflect isomorphicness - or equivalently, preserve non-isomorphicness - are prized. Rare, but prized! These functors are sometimes called essentially injective. The link gives a few sufficient conditions for a functor to be essentially injective.

Kevin Arlin (Oct 28 2023 at 19:20):

Whereas, just for one more follow-on, functors that reflect whether a particular morphism is an isomorphism, called conservative, are quite common.

David Egolf (Oct 28 2023 at 19:26):

Thanks everyone for your interesting comments!

For context, I was reading about the concept of an invariant (in the sense that Mike Shulman describes above). As I often enjoy doing, I was wondering if this idea could be (in a very broad sense) helpful for thinking about medical imaging systems. That's why I asked the question above: in a medical imaging context, I am more interested in characterizing the thing being observed, as opposed to showing that two things that we are observing must be different based on a difference in our measurements.

Since there are so many possible things that we could be imaging, it's not that helpful to rule out any particular thing that we could be imaging. It's more helpful to measure how close the measurements induced by our current guess for the unknown object would be to the measurements we actually observe.

David Egolf (Oct 28 2023 at 19:32):

Very broadly, I wonder if one could "categorify" the concept of "not-being-isomorphic". One would replace the binary condition of being non-isomorphic (or not) with potentially a specific way in which two objects are not isomorphic. I have no idea if that line of thought goes anywhere though!

For example, in the category of finite sets and functions between them, a demonstration of non-isomorphicness of $A$ and $B$ could look like an injective function that is not surjective from $A$ to $B$.

John Baez (Oct 28 2023 at 20:05):

Before trying to categorify "not-being-isomorphic" it's worth slowing down and thinking a bit about "not-being-equal".

The most famous to categorify the concept of "not-being-equal" is a metric space, where for any two elements of a set we get an element of $[0,\infty)$ (or for a Lawvere metric space, $[0,\infty])$ saying how unequal they are.

John Baez (Oct 28 2023 at 20:08):

We could replace $[0,\infty)$ by some other monoidal preorder to get variants of this idea, and then we can go even further and use a monoidal category. We wind up getting the concept of "category enriched over a monoidal category".

Todd Trimble (Oct 28 2023 at 20:31):

(Warning, however, for Lawvere metric spaces: the axioms are the triangle inequality and $0 \geq d(x, x)$ [same as $0 = d(x, x)$], but one drops the symmetry condition $d(x, y) = d(y, x)$ and the separation condition that $d(x, y) = 0$ implies $x = y$. In fact the principled definition of the Lawvere metric = internal hom on $[0, \infty]$ itself is given by truncated substraction, $d(x, y) = \max\{y - x, 0\}$, where both symmetry and separation are violated. [This is the principled definition because it gives the usual adjunction relation between tensor and internal hom.] Here, $d(x, y) = 0$ iff $x \geq y$, so one could say that $d(x, y)$ is here a measure of how far away $x$ is from being greater than or equal to $y$. But one can symmetrize this to get $d(x, y) + d(y, x) = |x-y|$, the standard metric.)