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: Testing vs Generating, Characteristic functions vs ??

Peva Blanchard (Apr 11 2024 at 06:53):

Another side quest that originates from @David Egolf 's thread.

Consider a function $f : X \rightarrow Y$ between sets. We were exercising around the ways $f$ acts on the subsets of $X$ (taking direct images) and on the subsets of $Y$ (taking inverse images).

Testing and characteristic function

The usual way to characterise a subset $V \subset Y$ is via a characteristic function $\chi_V : V \rightarrow 2$. The inverse image is intensionally defined as:

$$f^{-1}(V) = \{ x \in X | f(x) \in V \}$$

Equivalently,

$$\chi_{f^{-1}(V)} = \chi_V \circ f$$

So taking inverse images of subsets of $Y$ via $f$ is the same pre-composing characteristic functions with $f$.

"Generating function"

Now, I wanted to look at these things from another point of view. I don't know exactly how to formalize this, but I would say that a subset $U$ of $X$ is "generatively defined or presented" when we have a "generating function" $\gamma_U : I \rightarrow U$ from some indexing set (e.g. natural numbers if $U$ is countable).

I am not sure about the exact definition of a "generating function"; intuitively I would require it to be surjective at least, and I would allow it to be non-injective. All in all, I picture this function as a machine that produces elements of $U$ in an exhaustive manner.

Now, from this point of view, the direct image has an obvious "generating function":

$$\gamma_{f(U)} = f \circ \gamma_U$$

This, I think, captures the notation

$$f(U) = \{ f(x) | x \in U \}$$

My question

I find the symmetry between "characteristic functions/consumer" and "generating functions/producer" quite amusing. I know that, one side, the characteristic functions, plays a big role in other topics, notably via the concept of sub-object classifier.

I was wondering if the other side has been studied too.

edit: the above is corrected as I used the terms "intensional/extensional" in a non-standard way.

Matteo Capucci (he/him) (Apr 11 2024 at 07:22):

First, let me point out your usage of intensional and extensional is quite non-standard: both things you present are quite extensional in nature. At least as far as those words mean anything in this setting (I think of intensional as syntactic and extensional as semantical).
Anyway, I'd say what you describe is exactly the universal property of subobject classifiers: it relates 'generating functions' $I \to U$ to characteristic functions $U \to \Omega$. Two caveats. The 'generating function' has to be injective (mono), or: you must factor it through the inclusion of its image first. Second, the intuition of 'generating elements' is quite brittle in my opinion, since to claim $\gamma_U$ is effectively enumerating elements of $U$ requires to take seriously what 'effective' means, and a general set-theoretic function isn't effective at all. If you really want that you might want to work in the [[effective topos]].

Peva Blanchard (Apr 11 2024 at 07:25):

I see, thank you, let me rename the topic so as to avoid confusion for other members then.

Peva Blanchard (Apr 11 2024 at 12:17):

Mmh, I'm not sure to follow your answer, but that's because my question was ill-formed. I'll edit it again.

Oscar Cunningham (Apr 14 2024 at 09:32):

Suppose a set $A$ has $n$ elements. Then $A$ has $2^n$ subsets. There are also $2^n$ functions $A\to 2$, so it's no surprise that the subsets can be put in bijection with the characteristic functions.

But on the 'generating' side of things, the number of quotients of $A$ would be the $n\text{th}$ Bell number, which doesn't have a nice formula. So it's unlikely that there's a similar correspondence.

By the way, a related concept is exact sequences, which occur when a set can be described both by generating and by testing. The elements y of the form f(x) for some x are also the ones with g(y) = 0.

Amar Hadzihasanovic (Apr 14 2024 at 10:09):

In a parallel world, instead of functions of finite sets (the subprop of commutative Frobenius algebras generated by the $0 \to 1$ and $2 \to 1$ operations) mathematicians have formed their intuitions on "fusions" of finite sets (the subprop generated by the $2 \to 1$ and $1 \to 0$ operations) and everybody knows the Bell numbers as $0^n$, the number of total fusions of $n$ elements.

John Baez (Apr 14 2024 at 10:11):

Oscar Cunningham said:

Suppose a set $A$ has $n$ elements. Then $A$ has $2^n$ subsets. There are also $2^n$ functions $A\to 2$, so it's no surprise that the subsets can be put in bijection with the characteristic functions.

But on the 'generating' side of things, the number of quotients of $A$ would be the $n\text{th}$ Bell number, which doesn't have a nice formula. So it's unlikely that there's a similar correspondence.

There are various cool formulas for the Bell numbers $B_n$, but I think your point is that we don't have

$B_n = n^k$

for some $k \in \mathbb{N}$, so the set of quotients of finite sets $A$ can't possibly be isomorphic to $\mathrm{hom}(K, A)$ for any fixed finite set $K$. So there's no "quotient object coclassifier" in $\mathsf{Set}$.

Peva Blanchard (Apr 14 2024 at 14:22):

Wow thanks, I didn't know about Bell numbers. I very recently learned about "de/categorication" (thanks @John Baez ), and if I understood correctly, the Bell numbers are somehow a decategorification of the co-presheaf $B$ that associates with every finite set $X$ the (finite) set of its quotient objects.

I did delve about the reason why there is no "quotient object coclassifier" in the other thread. In fact, there cannot be such an object in a category with a strict initial object.

@Amar Hadzihasanovic I am intrigued by what you are saying about "fusions". Could you expand a bit more?

Amar Hadzihasanovic (Apr 14 2024 at 16:15):

I will try to be more detailed than not, sorry if you already know some of these things.
The "prop of commutative [[Frobenius algebra]] s" is a monoidal category which shows up in a lot of contexts, and is a fundamental example of a “non-cartesian” algebraic theory.

Being a prop means, roughly, that its

• objects are natural numbers,
• the monoidal product on objects is addition

so you can take two morphisms $f: n \to m$ and $g: n' \to m'$ and compose them horizontally to get a morphism $f \otimes g: n + n' \to m + m'$

Amar Hadzihasanovic (Apr 14 2024 at 16:21):

One cool fact about it is that it is equivalent to the monoidal category of 2-cobordisms: if you identify the object $n$ with $n$ copies of a circle, then morphisms $n \to m$ are “ways of connecting $n$ 'circular holes' to $m$ 'circular holes' via a 2-dimensional surface”.
There is a nice book by Joachim Kock telling this story, it's called Frobenius Algebras and 2D Topological Quantum Field Theories

Amar Hadzihasanovic (Apr 14 2024 at 16:24):

But the nLab article also summarises this correspondence with pictures. This one I took from a post by John
commutative_frobenius_algebra.jpg

Amar Hadzihasanovic (Apr 14 2024 at 16:27):

The 4 cobordisms in the top row of the picture -- of type $0 \to 1$, $2 \to 1$, $1 \to 0$, and $1 \to 2$, respectively -- actually suffice to generate all the others, that is, you can assemble any cobordism (up to the appropriate notion of equality) by just assembling together copies of those 4.

Amar Hadzihasanovic (Apr 14 2024 at 16:28):

So you can ask the question: what sub-prop (sub-monoidal category) can I obtain by just using a subset of those 4?

Amar Hadzihasanovic (Apr 14 2024 at 16:30):

If you take only the first two, that is, $0 \to 1$ and $2 \to 1$, you get a sub-prop which is equivalent to the “prop of commutative monoids”.
Which is well-known-ish to be the equivalent to the monoidal category of finite sets and functions, with disjoint union as monoidal product.

Amar Hadzihasanovic (Apr 14 2024 at 16:30):

So: the morphisms $n \to m$ that you can generate using just the $0 \to 1$ and $2 \to 1$ pieces correspond, bijectively, to functions from an $n$-element set to an $m$-element set.

Amar Hadzihasanovic (Apr 14 2024 at 16:31):

So you may as well call these morphisms “functions”.

Amar Hadzihasanovic (Apr 14 2024 at 16:33):

I do not know if there is a name for the morphisms generated using just the $2 \to 1$ and $1 \to 0$ pieces, but I was suggesting calling them “fusions” since they only allow you to “fuse” together some of the circular holes you started with into the same surface.

Amar Hadzihasanovic (Apr 14 2024 at 16:34):

Then what you have is (try it out): fusions $n \to 0$ correspond exactly to partitions of the set of $n$ elements.

Amar Hadzihasanovic (Apr 14 2024 at 16:36):

My not-very-serious suggestion was:
Imagine that our familiarity with the exponential notation $n^m$ comes from the fact that

• we are used to thinking about functions,
• $n^m$ is the cardinality of the hom-set $\mathrm{Hom}(m, n)$ in the category of finite sets and functions.

Amar Hadzihasanovic (Apr 14 2024 at 16:37):

Then in the parallel world where fusions are much better-known than functions, they defined $n^m$ to be the cardinality of the hom-set $\mathrm{Hom}(m, n)$ in the category of finite sets and fusions.

Amar Hadzihasanovic (Apr 14 2024 at 16:38):

And then $0^n$ is the $n$ th Bell number.

Peva Blanchard (Apr 14 2024 at 17:28):

This is really cool! Thank you for the detailed description. Indeed, I don't know much about props; I stumbled upon them a while back while reading graphical linear algebra.

I think I get the gist. Let me try variations to make sure I understood correctly. When we take $0 \rightarrow 1$ and $2 \rightarrow 1$ as generators, we obtain something close to $FinSet$. I would say the skeleton of $FinSet$ (?). A morphism $0 \rightarrow 1$ is like singling out an element. So $0 \rightarrow n$ is really like choosing an explicit set of $n$ elements.

Another choice than yours would be to take $1 \rightarrow 2$ and $0 \rightarrow 1$ as generators. And $0 \rightarrow n$ would also correspond exactly to partitions of the set of $n$ elements. But this is just the dual of your construction, so it makes sense.

Now, if we take $1 \rightarrow 2$ and $1 \rightarrow 0$, what do I get? I get infinitely many morphisms $n \rightarrow 0$, because the cobordisms can branch out arbitrarily often.

I'll stop here, but this is really fun :)

Amar Hadzihasanovic (Apr 14 2024 at 17:32):

The choice $1 \to 2$ and $1 \to 0$ is dual to the one that gives $\mathrm{FinSet}$, so it will actually give you something equivalent (indeed, a skeleton) to $\mathrm{FinSet}^\mathrm{op}$.

Amar Hadzihasanovic (Apr 14 2024 at 17:35):

In the subprop equivalent to $\mathrm{FinSet}$, the generator $0 \to 1$ corresponds to the unique function from the empty set to the singleton set, so it is not "singling out" any element, though.