## Category Theory

# The Fibonacci Sequence as a Functor

Over the years, the articles on this blog have spanned a wide range of audiences, from fun facts (Multiplying Non-Numbers), to undergraduate level (The First Isomorphism Theorem, Intuitively), to graduate level (What is an Operad?), to research level. Today's article is more on the fun-fact side of things, along with—like most articles here—an eye towards category theory.

So here's a fun fact about greatest common divisors (GCDs) and the **Fibonacci sequence **$F_1,F_2,F_3,\ldots$, where $F_1=F_2=1$ and $F_n:=F_{n-1} + F_{n-2}$ for $n>1$. For all $n,m\geq 1$,

In words, the greatest common divisor of the $n$th and $m$th Fibonacci numbers is the Fibonacci number whose index is the greatest common divisor of $n$ and $m$. (Here's a proof.) Upon seeing this, your "spidey senses" might be tingling. *Surely* there's some structure-preserving map $F$ lurking in the background, and this identity means it has a certain nice property. But what *is* that map? And what structure does it preserve? And what's the formal way to describe the nice property it has?

The short answer is that the natural numbers $\mathbb{N}=\{1,2,3,\ldots\}$ form a partially ordered set (poset) under division, and the function $F\colon \mathbb{N}\to\mathbb{N}$ defined by $n\mapsto F_n:=F(n)$ preserves *meets*: $F_n\wedge F_m = F(n\wedge m)$.

# Language Modeling with Reduced Densities

Today I'd like to share with you a new paper on the arXiv—my latest project in collaboration with mathematician Yiannis Vlassopoulos (Tunnel, IHES). To whet your appetite, let me first set the stage. A few months ago I made a 10-minute introductory video to my PhD thesis, which was an investigation into mathematical structure that is both algebraic and statistical. In the video, I noted that **natural language **is an example of where such mathematical structure can be found.

Language isalgebraic, since words can be concatenated to form longer expressions. Language is alsostatistical, since some expressions occur more frequently than others.

As a simple example, take the words "orange" and "fruit*." W*e can stick them together to get a new phrase, "orange fruit." Or we could put "orange"* *together with "idea"* *to get "orange idea*." *That might sound silly to us, since the phrase "orange idea"* *occurs less frequently in English than "orange fruit*." *But that's the point. These frequencies contribute something to the meanings of these expressions. So* *what is* this* kind of mathematical structure? As I mention in the video, it's helpful to have a set of tools to start exploring it, and basic ideas from quantum physics are one source of inspiration. I won't get into this now—you can watch the video or read the thesis! But I do want to emphasize the following: In certain contexts, these tools provide a way to see that statistics can serve as a proxy for meaning. I didn't explain *how* in the video. I left it as a cliffhanger.

But I'll tell you the rest of the story now.

# What is an Adjunction? Part 3 (Examples)

Welcome to the last installment in our mini-series on adjunctions in category theory. We motivated the discussion in Part 1 and walked through formal definitions in Part 2. Today I'll share some examples. In Mac Lane's well-known words, "adjoint functors arise everywhere," so this post contains only a tiny subset of examples. Even so, I hope they'll help give you an eye for adjunctions and enhance your vision to spot them elsewhere.

An adjunction, you'll recall, consists of a pair of functors $F\dashv G$ between categories $\mathsf{C}$ and $\mathsf{D}$ together with a bijection of sets, as below, for all objects $X$ in $\mathsf{C}$ and $Y$ in $\mathsf{D}$.

In Part 2, we illustrated this bijection using a free-forgetful adjunction in linear algebra as our guide. So let's put "free-forgetful adjuctions" first on today's list of examples.

# What is an Adjunction? Part 2 (Definition)

Last time I shared a light introduction to adjunctions in category theory. As we saw then, an adjunction consists of a pair of opposing functors $F$ and $G$ together with natural transformations $\text{id}\to\ GF$ and $FG\to\text{id}$. We compared this to two stricter scenarios: one where the composite functors *equal* the identities, and one where they are *naturally* *isomorphic *to the identities. The first scenario defines an isomorphism of categories. The second defines an equivalence of categories. An adjunction is third on the list.

In the case of an adjunction, we also ask that the natural transformations—called the *unit* and *counit*—somewhat behave as inverses of each other. This explains why the ${\color{red}\text{arrows}}$ point in opposite directions. (It also explains the "co.") Except, they can't *literally* be inverses since they're not composable: one involves morphisms in $\mathsf{C}$ and the other involves morphisms in $\mathsf{D}$. That is, their (co)domains don't match. But we can fix this by applying $F$ and $G$ so that (a modified version of) the unit and counit can indeed be composed. This brings us to the formal definition of an adjunction.

# What is an Adjunction? Part 1 (Motivation)

Some time ago, I started a "What is...?" series introducing the basics of category theory:

- "What is a category?"
- "What is a functor?" Part 1 and Part 2
- "What is a natural transformation?" Part 1 and Part 2

Today, we'll add adjunctions to the list. An *adjunction* is a pair of functors* *that interact in a particularly nice way. There's more to it, of course, so I'd like to share some motivation first. And rather than squeezing the motivation, the formal definition, and some examples into a single post, it will be good to take our time: Today, the motivation. Next time, the formal definition. Afterwards, I'll share examples.

Indeed, I will make the admittedly provocative claim that adjointness is a concept of fundamental logical and mathematical importance that is not captured elsewhere in mathematics.

- Steve Awodey (inCategory Theory, Oxford Logic Guides)

# Limits and Colimits Part 3 (Examples)

Once upon a time, we embarked on a mini-series about limits and colimits in category theory. Part 1 was a non-technical introduction that highlighted two ways mathematicians often make new mathematical objects from existing ones: by taking a subcollection of things, or by gluing things together. The first route leads to a construction called a *limit, *the second to a construction called a *colimit*.

The formal definitions of limits and colimits were given in Part 2. There we noted that one speaks of "the (co)limit of [something]." As we've seen previously, that "something" is a *diagram—*a functor from an indexing category to your category of interest. Moreover, the shape of that indexing category determines the name of the (co)limit: product, coproduct, pullback, pushout, etc.

In today's post, I'd like to solidify these ideas by sharing some examples of limits. Next time we'll look at examples of colimits. What's nice is that *all* of these examples are likely familiar to you—you've seen (co)limits many times before, perhaps without knowing it! The newness is in viewing them through a categorical lens.

# Announcing Applied Category Theory 2019

Hi everyone. Here's a quick announcement: the Applied Category Theory 2019 school is **now accepting applications**! As you may know, I participated in ACT2018, had a great time, and later wrote a mini-book based on it. This year, it's happening again with new math and new people! As before, it consists of a five-month long, online school that culminates in a week long conference (July 15-19) and a week long research workshop (July 22-26, described below). Last year we met at the Lorentz Center in the Netherlands; this year it'll be at Oxford.

Daniel Cicala and Jules Hedges are organizing the ACT2019 school, and they've spelled out all the details in the official announcement, which I've copied-and-pasted it below. Read on for more! And please feel free to spread the word. Do it quickly, though. *The deadline is soon!*

**APPLICATION DEADLINE: JANUARY 30, 2019**

# Notes on Applied Category Theory

Have you heard the buzz? *Applied category theory* is gaining ground! But, you ask, what *is* applied category theory? Upon first seeing those words, I suspect many folks might think either one of two thoughts:

*Applied category theory? Isn't that an oxymoron?**Applied category theory? What's the hoopla? Hasn't category theory always been applied?*

For those thinking thought #1, I'd like to convince you the answer is *No way!* It's true that category theory sometimes goes by the name of *general abstract nonsense*, which might incline you to think that category theory is too pie-in-the-sky to have any impact on the "real world." My hope is to convince you that that's *far* from the truth.

For those thinking thought #2, *yes*, it's true that ideas and results from category theory have found applications in computer science and quantum physics (not to mention pure mathematics itself), but these are not the only applications to which the word *applied *in *applied category theory* is being applied.

So what *is* applied category theory?

# Limits and Colimits, Part 2 (Definitions)

Welcome back to our mini-series on categorical limits and colimits! In Part 1 we gave an intuitive answer to the question, "What *are* limits and colimits?" As we saw then, there are *two* main ways that mathematicians construct *new* objects from a collection of given objects: 1) take a "sub-collection," contingent on some condition or 2) "glue" things together. The first construction is usually a limit, the second is usually a colimit. Of course, this might've left the reader wondering, "Okay... but what are we taking the (co)limit *of* ?" The answer? A *diagram*. And as we saw a couple of weeks ago, a diagram is really a functor.

# A Diagram is a Functor

Last week was the start of a mini-series on limits and colimits in category theory. We began by answering a few basic questions, including, "What *ARE* (co)limits?" In short, they are a way to construct new mathematical objects from old ones. For more on this non-technical answer, be sure to check out Limits and Colimits, Part 1. Towards the end of that post, I mentioned that (co)limits aren't really related to limits of sequences in topology and analysis (but see here). There is however one similarity. In analysis, we ask for the limit *of* a sequence. In category theory, we also ask for the (co)limit *OF* something. But if that "something" is not a sequence, then what is it?

Answer: a diagram.

# Limits and Colimits, Part 1 (Introduction)

I'd like to embark on yet another mini-series here on the blog. The topic this time? Limits and colimits in category theory! But even if you're not familiar with category theory, I do hope you'll keep reading. Today's post is just an informal, non-technical introduction. And regardless of your categorical background, you've *certainly* come across many examples of limits and colimits, perhaps without knowing it! They appear everywhere--in topology, set theory, group theory, ring theory, linear algebra, differential geometry, number theory, algebraic geometry. The list goes on. But before diving in, I'd like to start off by answering a few basic questions.

# The Yoneda Lemma

Welcome to our third and final installment on the Yoneda lemma! In the past couple of weeks, we've slowly unraveled the mathematics behind the Yoneda perspective, i.e. the categorical maxim that an object is completely determined by its relationships to other objects. Last week we divided this maxim into two points...

# The Yoneda Embedding

Last week we began a discussion about the Yoneda lemma. Though rather than stating the lemma (sans motivation)*, *we took a leisurely stroll through an implication of its corollaries - the *Yoneda perspective, *as we called it*:*

**An object is completely determined by its relationships to other objects,**

i.e.

**by what the object "looks like" from the vantage point of each object in the category.**

But this left us wondering, *What are the mathematics** behind this idea?* *And w**hat are the actual corollaries?* In this post, we'll work to discover the answers.

# The Yoneda Perspective

In the words of Dan Piponi, it "is the hardest trivial thing in mathematics." The nLab catalogues it as "elementary but deep and central," while Emily Riehl nominates it as "arguably the most important result in category theory." Yet as Tom Leinster has pointed out, "many people find it quite bewildering."

And *what* are they referring to?

**The Yoneda lemma.**

"But," you ask, "what is the Yoneda lemma? And if it's just a *lemma* then - my gosh - what's the *theorem*?"

# Naming Functors

Mathematicians are a creative bunch, especially when it comes to naming things. And category theorists are no exception. So here's a little spin on this xkcd comic. It's inspired by a recent conversation I had on Twitter and, well, every category theory book ever.

# Group Elements, Categorically

On Monday we concluded our mini-series on basic category theory with a discussion on natural transformations and functors. This led us to make the simple observation that the elements of any set are really just functions from the single-point set {✳︎} to that set. But what if we replace "set" by "group"? Can we view group elements categorically as well? The answer to that question is the topic for today's post, written by guest-author Arthur Parzygnat.

# What is a Natural Transformation? Definition and Examples, Part 2

Continuing our list of examples of natural transformations, here is Example #2 (double dual space of a vector space) and Example #3 (representability and Yoneda's lemma).

# What is a Natural Transformation? Definition and Examples

I hope you have enjoyed our little series on basic category theory. (I know I have!) This week we'll close out by chatting about natural transformations which are, in short, a nice way of moving from one functor to another. If you're new to this mini-series, be sure to check out the very first post, *What is Category Theory Anyway?* as well as *What is a Category?* and last week's *What is a Functor?*

# What is a Functor? Definitions and Examples, Part 2

Continuing yesterday's list of examples of functors, here is Example #3 (the chain rule from multivariable calculus), Example #4 (contravariant functors), and Example #5 (representable functors).

# What is a Functor? Definition and Examples, Part 1

Next up in our mini series on basic category theory: functors! We began this series by asking *What is category theory, anyway?* and last week walked through the precise definition of a category along with some examples. As we saw in example #3 in that post, a functor can be viewed an arrow/morphism between two categories.

# What is a Category? Definition and Examples

As promised, here is the first in our triad of posts on basic category theory definitions: categories, functors, and natural transformations. If you're just now tuning in and are wondering *what is category theory, anyway? *be sure to* *follow the link to find out!

A category $\mathsf{C}$ consists of some data that satisfy certain properties...

# What is Category Theory Anyway?

A quick browse through my Twitter or Instagram accounts, and you might guess that I've had category theory on my mind. You'd be right, too! So I have a few category-theory themed posts lined up for this semester, and to start off, I'd like to (attempt to) answer the question, *What is category theory, **anyway*? for anyone who may not be familiar with the subject.

Now rather than give you a list of definitions--which are easy enough to find and may feel a bit unmotivated at first--I thought it would be nice to tell you what category theory is *in the grand scheme of (mathematical) things. *You see, it's very different than other branches of math....

# The Most Obvious Secret in Mathematics

Yes, I agree. The title for this post is a little pretentious.** **It's certainly possible that there are *other* mathematical secrets that are *more* obvious than this one, but hey, I got your attention, right? *Good*. Because I'd like to tell you about an overarching theme in mathematics - a mathematical mantra, if you will. A technique that mathematicians use *all the time* to, well, do math.