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: Natural Numbers Object

Julius Hamilton (Apr 05 2024 at 02:10):

In a category $C$ with a terminal object, a natural numbers object $X$ is an arrow $f$ from the terminal object to $X$, and an arrow $X \rightarrow X$, such that for any object $A$ of $C$, and similar arrows from the terminal object $1 \rightarrow A$, and from $A \rightarrow A$, there is a unique arrow $u$ such that this diagram commutes:

E8C72EC7-EE95-4228-9FAB-CB3601DD4550.jpg

The top bar of this diagram, $1 \rightarrow N \rightarrow N$, we can think of as a successor function. An initial object is an object for which there is exactly one morphism from it to every object in the category. In the case of sets, there is only one possible function on an empty set, the “empty function”. Therefore, in the category of sets, the initial object is the empty set. A terminal object, conversely, is the object for which for every object in the category, there is precisely one possible morphism into it. The terminal object in $\mathbf Set$ is any singleton set. Now, why would a natural numbers object require there to be a terminal object? My guess is, since a terminal object “collapses” all the information of any object with a morphism into it, there is also something special about a morphism out of a terminal object. It is easy to visualize a morphism out of a terminal object as a “selector” (or “global element”) when you think in the category of sets. Clearly, a singleton set can only map to one element, “selecting” it. But i am trying to understand what its significance is in an abstract category.

I also want to understand the bottom part of the diagram. It’s as if $N$ is “prior” to any object $A$. I suppose I would like better intuition for why that property should be what characterizes them.

Julius Hamilton (Apr 05 2024 at 02:16):

I want to use the above to work up to responding to this question on Philosophy SE.

In that question, there is an arbitrary function which can be applied successively, $D()$. However, it also needs, like, an “external semantics”. I want to figure out how to express that categorically.

Ryan Wisnesky (Apr 05 2024 at 03:23):

the bottom part of the diagram says, that given any other Nat algebra (A,q,f), there is a unique map u from N to A. This map u is often called "fold q f" in functional programming languages and expresses induction/recursion

Joshua Meyers (Apr 05 2024 at 04:12):

My guess is, since a terminal object “collapses” all the information of any object with a morphism into it, there is also something special about a morphism out of a terminal object. It is easy to visualize a morphism out of a terminal object as a “selector” (or “global element”) when you think in the category of sets. Clearly, a singleton set can only map to one element, “selecting” it. But i am trying to understand what its significance is in an abstract category.

In an abstract category $C$, we define a generalized element of $X$ of shape $T$ to be a morphism $T\to X$, where $T$ may not be the terminal object. The special thing that happens when $T$ is the terminal object is that a morphism $x:T\to X$ induces a generalized element $x_A:A\to T\xrightarrow{x} X$ of shape $A$ for any object $A$; and what's more, given any morphism $f:A\to B$ we have $f\circ x_A=x_B$ --- so we get exactly one generalized element of every possible shape and they are all compatible with respect to every possible way of going between shapes! That's why this is called a global element: it is a way of being shape-independent. We can also talk about global elements in categories that may not have a terminal object: we just directly define a global element of $X$ as a family of generalized elements $x:_A:A\to X$, exactly one for each shape, such that for every morphism $f:A\to B$ we have $f\circ x_A=x_B$. If our category does turn out to have a terminal object after all, this definition is equivalent to the previous definition (this would be a good thing to prove for practice).

Chad Nester (Apr 05 2024 at 07:15):

I'll mention that you can do this in a mere monoidal category (here strict for the sake of concision), where instead of a diagram $1 \stackrel{z}{\to} N \stackrel{s}{\leftarrow} N$ with $1$ a terminal object you instead have a diagram $I \stackrel{z}{\to} N \stackrel{s}{\leftarrow} N$ with $I$ the monoidal unit. Such a diagram is a left natural numbers object in case for any diagram $B \stackrel{b}{\to} A \stackrel{a}{\leftarrow} A$ there exists a unique arrow $h : N \otimes B \to A$ such that $(z \otimes 1_B)h = b$ and $(s \otimes 1_B)h = ha$, forming a diagram a lot like the one in the image you posted. This also supports the representation of any primitive recursive function, just like the usual sort of natural numbers object. In fact, you don't even have to ask for uniqueness of $h$, it's enough for it to exist!

The reference for this is "Monoidal Categories With Natural Numbers Object" by Paré and Román. Another good reference is "Partial Recursive Functions and Finality" by Plotkin.

Chad Nester (Apr 05 2024 at 07:22):

I don't think you really need this machinery to express $D^n(S)$ for some $D : P \to P$ and $S : 1 \to P$.

Chad Nester (Apr 05 2024 at 07:25):

When I write $D^n(S) = SD\cdots \text{(n times)} \cdots D : I \to N$ I'm using the usual natural numbers (the set $\mathbb{N}$), and constructing an arrow of my category for each $n \in \mathbb{N}$ by using the fact that I can do this sort of iteration at the metatheoretic level.

Chad Nester (Apr 05 2024 at 07:26):

What a natural numbers object does is move this iteration out of the metatheory, making it something I can do explicitly in the category I'm working with.

Chad Nester (Apr 05 2024 at 07:26):

... Does this make sense?

Matteo Capucci (he/him) (Apr 05 2024 at 07:37):

There is such a thing as a 'parametrized NNO' in which 1 is replaced by a general object $A$, see Definition 2.2 here

El Mehdi Cherradi (Apr 05 2024 at 09:36):

Also, the terminal object may be thought as an empty product of copies of $N$. The theory of natural numbers is basically formed from an object $N$, an 0-ary operation $0 : N^0 \to N$ and a unary operation $s : N^1 \to N$. The key idea here is that of arity of an operation (where here an arity is a natural number, but it makes sense to consider other categories of arities), this page on Lawvere theories can be relevant.

Julius Hamilton (Apr 05 2024 at 20:25):

https://en.m.wikipedia.org/wiki/Fold_(higher-order_function)

https://wiki.haskell.org/Fold

Julius Hamilton (Apr 05 2024 at 20:29):

9DD66BD3-723A-4124-9290-076167F85014.jpg

nLab

Julius Hamilton (Apr 05 2024 at 20:43):

$X$ is the functor, $J$ is the source category, $C$ is the target category.

The most important thing about functors is that they commute with the morphisms in the categories. Imagine two cities, each connected by subways, and the two cities themselves connected by two different airports (each). We could consider “air travel” functorial over these cities, because, if you were at origin airport 1 in city 1, you could get to target airport 2 in city 2, either by flying target airport 1 in city 2 and taking the subway to airport 2, or by taking the subway to origin airport 2 in city 1, then flying to target airport 2.

I would like a better understanding of what we know to be true of any two categories which have a functor between them. It indicates there is some kind of structural/geometric “congruence” between them - or at least a subpart of one of them. I will draw some diagrams of categories that have no functors between them (or, a trivial/empty functor).

Spivak mentioned somewhere that a functor can merely be seen as a way of “labeling” the objects in the target category, which reminds me of how an indexed set is just a function from an (index) set to the codomain set. Still, there must be some restriction on how we are allowed to label the objects of the target category, since not all mappings between categories are functors. Does it “group” the objects conceptually, by similar properties?

Spivak also once said that a functor can be thought of as an “observation”, a concept I will investigate.

Julius Hamilton (Apr 05 2024 at 20:50):

A “generalized element $X$ of shape $T$” is a morphism $T \rightarrow X$. Then these definitions coincide in a category where the morphisms are functors.

Julius Hamilton (Apr 05 2024 at 20:52):

The special thing that happens when $T$ is the terminal object is that a morphism $x:T\to X$ induces a generalized element $x_A:A\to T\xrightarrow{x} X$ of shape $A$ for any object $A$.

Julius Hamilton (Apr 05 2024 at 20:56):

Here, $T$ is any object where every object $X \in Ob(C)$ has exactly one morphism in the hom-set between them. This says nothing about how many morphisms there may be out of $T$, to any object $Y$. But, that morphism composed with any morphism into $T$, $f: X \rightarrow T$ has a unique property.

Julius Hamilton (Apr 05 2024 at 20:58):

Because $x: T \rightarrow X$ can only compose with a single morphism $f_A: A \rightarrow T$ (for some $A$), it follows that their composition is unique as well: there is only one morphism $f_A \circ x$ in $C$.

Julius Hamilton (Apr 05 2024 at 21:01):

And because this too is merely a morphism $A \rightarrow X$, we can also call it a “generalized element”.

Similar to epics and monics, it seems there’s something about generalized elements / terminal objects where a property is preserved in certain cases for composition of arrows with that thing.

Julius Hamilton (Apr 05 2024 at 21:02):

(to be continued.)

Julius Hamilton (Apr 05 2024 at 21:45):

given any morphism $f:A\to B$ we have $f\circ x_A=x_B$

This seems to be saying that composing a morphism with a generalized element simply returns the generalized element of the target object. I.e., the notation makes it look like the generalized element is like a variable restricted to a domain - if $f: A \to B$, then $f(x_A)=x_B$. That’s just a way of saying that the variable $x_B$ depends on $x_A$ in some way.

However, this is just a notation. $x_A$ is a morphism which “filters through” the terminal object before being mapped to any object $X$. And indeed, it is defined in terms of a “generic” (variable) object in the category - “some $X$”.

I might see it clearer now. The terminal object allows us to specify a “unique morphism” $A \to X$.

(…)

Julius Hamilton (Apr 05 2024 at 21:53):

Some stuff above I need to work out, but the point of this was:

I wanted to know what useful properties a terminal object has (emphasized for abstract categories), because a natural numbers object is defined in terms of a terminal object. Meyers’s answer is that for any morphism out of a terminal object (into $X$), it induces a generalized element for any object in the category, into $X$, and they are basically “closed” under morphisms in the category. A “generalized element” that can take any “shape” (i.e., the source object) is called a “global element”.

Julius Hamilton (Apr 05 2024 at 22:01):

Then why do we need that to define an NNO?

A “general element” is nothing but a mapping. But if the mapping is out of a terminal object, then the “general element” implies a “global element”, (because…)

The global element can be thought of as the collection of all the general elements (that have mappings between them).

Does this mean that the reason an NNO is defined in terms of a terminal object, is just to make it as “general” as possible - we do not care what the “first thing” supplied to the successor function is - we just want it to have a (categorical) property of being “any specific thing, although it doesn’t matter what”?

Julius Hamilton (Apr 05 2024 at 22:19):

Instead of seeking a direct answer to these questions, I will take a big step back and try to think about terminal objects much more broadly, before proceeding.