Category theory

https://arbital.com/p/category_theory

by Mark Chimes Jun 15 2016 updated Oct 21 2016

How mathematical objects are related to others in the same category.

[summary: Category theory studies the abstraction of mathematical objects (such as sets, groups, and [topology topological spaces]) in terms of the morphisms between them. ]

[summary(technical): A category consists of a collection of [-object_category_theory objects] and a collection of morphisms (also called arrows). To each morphism $f$ is associated a pair of objects: $\text{dom}(f)$ which is the source or [domain_of_function domain] and $\text{cod}(f)$ which is the target or [codomain_of_function codomain] of $f$. If $\text{dom}(f) = X$ and $\text{cod}(f) = Y$, this is written $f: X \rightarrow Y$.

These morphisms must satisfy three conditions:

1. [Composition_of_functions Composition]: For any two morphisms $f: X \rightarrow Y$ and $g: Y \rightarrow Z$, there exists a morphism $X \rightarrow Z$, written as $g \circ f$ or simply $gf$.
2. Associativity: For any morphisms $f: X \rightarrow Y$, $g: Y \rightarrow Z$ and $h:Z \rightarrow W$ composition is associative, i.e., $h(gf) = (hg)f$.
3. [identity_map Identity]: For any object $X$, there is a (unique) morphism, $1_X : X \rightarrow X$ which, when composed with another morphism, leaves it unchanged. I.e., given $f:W \rightarrow X$ and $g:X \rightarrow Y$ it holds that: $1_X f = f$ and $g 1_X = g$. ]

[summary(motivation): Many mathematical constructions (such as [-product_mathematics products]) appear across different fields of mathematics, consisting of different ingredients but nevertheless capturing a similar idea (and often even under the same name). Category theory allows one to precisely describe the property that these different constructions all at once. This allows one to prove [-theorem theorems] about all these structures at once. Hence, once you prove that a specific mathematical structure is, say, a product, then all the category-theoretic theorems about products are true for that structure. In fact, sometimes there are structures which non-obviously satisfy a category-theoretic property. Especially when [duality_category_theory category-theoretic duality] is involved.

In addition, category theory allows the simple description of [-functor functors], [-natural_transformation natural transformations] and [-adjunction adjunctions]. These are mathematically powerful concepts which are very difficult to describe without the language of category theory. In fact, one of the founders of category theory, Saunders Mac Lane, has remarked that category theory was initially developed in order to provide a language in which to speak about natural transformations.

Powerfully, functors and adjunctions between categories allow one to translate concepts from one mathematical theory to another. They provide a "translation" (either full or partial) that allows one type of object to be viewed as another, and theorems to be translated across domains. In fact, using [-duality_cateory_theory duality], very non-obvious translations can be found because a theorem in one category can be translated to its "opposite theory" in the other category. Connections which are not obvious in the language of the mathematical theories themselves, become clear in the language of category theory. ]

Category theory studies the abstraction of mathematical objects (such as sets, groups, and [topology topological spaces]) in terms of the morphisms between them. Such a collection of objects and morphisms is a category. Morphisms often represent functions. For example, in the category of sets, morphisms represent all functions, in the category of groups they represent group homomorphism and in the category of topological spaces, they represent [continuous continuous] maps.

Categories are usually drawn as diagrams with the objects represented by variables or points with (labeled) arrows between them representing morphisms. For this reason, morphisms are also referred to as arrows.

Morphisms do not have to represent functions. For example, any partially ordered set $(P, \leq)$ may be seen as a category where the objects are the elements of the poset and there is a (unique) morphism $x \rightarrow y$ between two elements $x$ and $y$ if and only if $x \leq y$.

Definition

A category consists of a collection of [-object_category_theory objects] and a collection of morphisms. A morphism $f$ goes from one object, say $X$, to another, say $Y$, and is drawn as an arrow from $X$ to $Y$. Note that $X$ may equal $Y$ (in which case $f$ is referred to as an [endomorphism endomorphism]). The object $X$ is called the source or [domain_of_function domain] of $f$ and $Y$ is called the target or [codomain_of_function codomain] of $f$. This is written as $f: X \rightarrow Y$.

These morphisms must satisfy three conditions:

1. [Composition_of_functions Composition]: For any two morphisms $f: X \rightarrow Y$ and $g: Y \rightarrow Z$, there exists a morphism $X \rightarrow Z$, written as $g \circ f$ or simply $gf$.
2. Associativity: For any morphisms $f: X \rightarrow Y$, $g: Y \rightarrow Z$ and $h:Z \rightarrow W$ composition is associative, i.e., $h(gf) = (hg)f$.
3. [identity_map Identity]: For any object $X$, there is a (unique) morphism, $1_X : X \rightarrow X$ which, when composed with another morphism, leaves it unchanged. I.e., given $f:W \rightarrow X$ and $g:X \rightarrow Y$ it holds that: $1_X f = f$ and $g 1_X = g$.

Note that composition is written 'backwards' since given an element $x \in X$ and two functions $f: X \rightarrow Y$ and $g: Y \rightarrow Z$, the result of applying $f$ then $g$ is $g(f(x))$ which equals $(g \circ f)(x)$.

Motivation

Many mathematical constructions (such as [-product_mathematics products]) appear across different fields of mathematics, consisting of different ingredients but nevertheless capturing a similar idea (and often even under the same name). Category theory allows one to precisely describe the property that these different constructions all at once. This allows one to prove [-theorem theorems] about all these structures at once. Hence, once you prove that a specific mathematical structure is, say, a product, then all the category-theoretic theorems about products are true for that structure. In fact, sometimes there are structures which non-obviously satisfy a category-theoretic property. Especially when [duality_category_theory category-theoretic duality] is involved.

In addition, category theory allows the simple description of [-functor functors], [-natural_transformation natural transformations] and [-adjunction adjunctions]. These are mathematically powerful concepts which are very difficult to describe without the language of category theory. In fact, one of the founders of category theory, Saunders Mac Lane, has remarked that category theory was initially developed in order to provide a language in which to speak about natural transformations.

Powerfully, functors and adjunctions between categories allow one to translate concepts from one mathematical theory to another. They provide a "translation" (either full or partial) that allows one type of object to be viewed as another, and theorems to be translated across domains. In fact, using [-duality_cateory_theory duality], very non-obvious translations can be found because a theorem in one category can be translated to its "opposite theory" in the other category. Connections which are not obvious in the language of the mathematical theories themselves, become clear in the language of category theory.

Categories Give an External View

Although the objects and morphisms of a category are intended to represent e.g. sets and functions, from the [-personification_of_mathematics point of view of the category] the objects and morphisms have no internal structure. It is not possible to talk directly about the elements of an object or how a given morphism maps elements. Instead (from the viewpoint of the category) the information about the objects and morphisms are given completely by which objects are sources and targets for the morphisms and how the morphisms are composed.

In fact, this is the strength of category theory: abstracting away the internal details allows one to focus only on relevant information and also capture information about multiple similar types of structures that act in a certain way across different mathematical theories.

This is similar to the way that a group abstracts away what elements are whilst only capturing the information of how they are 'added' or 'multiplied'.

It is also somewhat similar to the concept of a program's API (or an interface in Java); we can't see inside the program or know how it implements something, but we know what kind of inputs and outputs programs have, and what kinds of inputs and outputs a composition of such programs have.

Note that since it abstracts something away, a category does not always capture enough information for one's purposes. For example, there is addition of group homomorphisms defined pointwise. For this purpose, other structures such as [enriched_category enriched categories] and [n_category n-categories] may be used. However, for many purposes, categories are at a very good between isomorphic objects. This is considered a feature of category theory.

Common Symbols: Convention

Different texts make use of different conventions. This site makes use of the following common convention:

• Categories are written in blackboard bold upper-case letters and are usually near the beginning of the alphabet. E.g. $\mathbb{A}, \mathbb{B}, \mathbb{C}$.
• Objects are written as upper-case letters usually near the beginning or end of the alphabet. E.g. $A, B, C, W, X, Y, Z$.
• Morphisms are labelled with lower-case letters, usually near f or near u. E.g. $e, f, g, h, u, v, w$.
• Elements of an object, where necessary, are written as lower-case letters, usually near the beginning or end of the alphabet. E.g. $a, b, c, x, y, z$
• Functors are written as upper-case letters usually near F. E.g. $E, F, G, H$.
• Natural transformations are written as Greek letters, usually near the beginning of the alphabet. E.g. $\alpha, \beta, \gamma, \delta$.
• The morphisms forming part of a cone or cocone for a limit or colimit are often written as Greek letters with subscripts, usually $\kappa$ or $\lambda$.

These conventions are merely guidelines and far from universally followed. Check the definition for the symbol in question to see what it represents

[-isomorphism_category_theory Isomorphisms in Category Theory]

In category theory, isomorphic objects are not distinguished. Many [-universal_constructions] do not pin down a [-specific_construction_category_theory specific construction] but instead only specify it [-isomorphism_category_theory up to isomorphism].

Doing something in category theory which relies on a specific construction, that is, requiring objects to be equal instead of merely isomorphic, is colloquially referred to as [-evil_category_theory evil].

Universal Properties

One of the most important concepts in category theory is that of a universal property. An object in a category which satisfies a universal property is in a sense the 'best' (often meaning smallest or largest) object satisfying a certain property. This can often be used to describe in a universal way constructions like products which are defined for multiple distinct structures. In category theory, it is defined once without referring to a specific construction. This definition can then be applied to multiple categories.

The simplest [trivial non-trivial] universal construction is the [terminal_object terminal object]. Given a category $\mathbb{C}$, an object $T$ in $\mathbb{C}$ is called a terminal object if, for any object $X$ in $\mathbb{C}$, there is a [unique unique] morphism $f: X \rightarrow T$. In other words there is some $f: X \rightarrow T$ and if there is also $g: X \rightarrow T$ then $f=g$. In the category of sets, the terminal objects are exactly the one element sets. Given a one element set $\{a\}$, and any set $X$, there is a unique morphism $f: X \rightarrow \{a\}$, namely the function taking every $x$ in $X$ to $a$. In the category of groups, terminal objects are exactly one-element groups. Note that terminal objects need not exist. Consider a [poset_as_category poset seen as a category]. If it has a largest element $T$, then each object is less than or equal to $T$. So from each object there is a unique morphism to $T$ and hence it is terminal. If, however, there is no largest element then the category has no terminal object.

As another example, products can be defined by a universal property: Given a pair of objects $X$ and $Y$, an object $P$ along with a pair of morphisms $f: P \rightarrow X$ and $g: P \rightarrow Y$ is called the product of $X$ and $Y$ if, given any other object $W$ and morphisms $u: W \rightarrow X$ and $v:W \rightarrow Y$ there is a unique morphism $h: W \rightarrow P$ such that $fh = u$ and $gh = v$.

The above are both special cases of a very important and more general [-universal_construction universal construction]: the [-limit_category_theory limit]. This (along with the [-colimit_category_theory colimit]) is described in more detail further below.

[-duality_category_theory Duality]

For any notion in a category, its dual is obtained by `reversing all the arrows' and 'reversing the order of composition'. If a statement is true in any category, then its dual is true in any category. As a [-corollary corollary], if a statement is true in some categories, its dual is true in the duals of those categories.

As an example, consider the definition of a [-terminal_object terminal object] given above. A statement about terminal object is that any two terminal objects are isomorphic. Let's examine the exact statement. Assume $T$ is terminal. Then for any $X$ there is unique $f: X \rightarrow T$. If we reverse the arrows, we get that for every $X$ there is unique $f: X \leftarrow T$. This is the definition of an [-initial_object initial object]. Consider another terminal object $T'$. The statement that $T'$ is isomorphic to $T$ is means that there is some $f: T \rightarrow T'$ and $g: T' \rightarrow T$ such that $gf = 1_T$ and $fg = 1_{T'}$. The dual of this is just the statement that there is some $f: T \leftarrow T'$ and $g: T' \leftarrow T$ such that $fg = 1_T$ and $gf = 1_{T'}$, this is exactly the same property! (The morphisms $f$ and $g$ have just been renamed). Hence, the dual of the statement that a terminal object is unique up to isomorphism is the statement that every initial object is unique up to isomorphism.

Similarly, if something is true for every category with an initial object, its dual will be true for every category with a terminal object.

The concept of duality can be a powerful way of obtaining new results which come easily within category theory, but which are not obvious in the theory to which category theory is being applied. As an advanced example, the category of [-boolean_algebra Boolean Algebras] is dual to the category of [-stone_space Stone Spaces]. See, Stone Duality on Wikipedia for the motivation.

[todo: Add better example(s) of duality]

[-Functor Functors]

A functor is a morphism between categories.

Given two categories $\mathbb{A}$ and $\mathbb{B}$, a functor $F$ from $\mathbb{A}$ to $\mathbb{B}$, written $F: \mathbb{A} \rightarrow \mathbb{B}$ is defined as a pair of functions:

• $F_0:$ Objects($\mathbb{A}$) $\rightarrow$ Objects($\mathbb{B}$)
• $F_1:$ Morphisms($\mathbb{A}$) $\rightarrow$ Morphisms($\mathbb{B}$)

Which satisfy:

1. Preservation of domain and codomain: If $f: X \rightarrow Y$ then $F_1(f): F_0(X) \rightarrow F_1(Y)$. ( Put differently, Dom($F_1(f)$) = $F_0$(Dom($f$)) and Cod($F_1(f)$) = $F_0$(Cod($f$)) for every morphism $f$. )

1. Preservation of Identity: If the morphism $1_X: X \rightarrow X$ is the identity on $X$, then the morphism $F_1(1_X): F_0(X) \rightarrow F_0(X)$ is the identity on $F_0(X)$.

2. Preservation of composition: Given morphisms $f: X \rightarrow Y$ and $g: Y \rightarrow Z$, then the composition of their images $F_1(g) \circ F_1(f): F_0(X) \rightarrow F_0(Z)$ is the image of their composition $F_1(g \circ f): F_0(X) \rightarrow F_0(Z)$.

Instead of differentiating $F_0$ and $F_1$, they are usually both written simply as $F$. E.g. $F(f): F(X) \rightarrow F(Y)$.

[-morphism_category_theory Properties of Morphisms]

Morphisms are the central objects of study in category theory. For this reason, properties of morphisms can be very important. A morphism $f: X \rightarrow Y$ is called the following if it satisfies the given property:

• [-isomorphism_category_theory Isomorphism]: ([-self_dual_category_theory Self-dual])

There exists some $g: Y \rightarrow X$ such that $gf = 1_X$ and $fg = 1_Y$.

Intuitively, an isomorphism is a way of transforming from one object to another in a way that makes them indistinguishable using the information of the category.

• [-monomorphism Monomorphism]: ([-duality_category_theory Dual] to epimorphic)

For any object $W$ and morphisms $g,h: W \rightarrow X$, if $fg = fh$ then $g = h$.

Intuitively, $f$ being a monomorphism indicates that all of the information captured by the collection of morphisms into $X$ is preserved when composing by $f$. It generalizes the notion of an injective function, since in most [-concrete_category concrete categories] (like sets, groups, and [-topology topological spaces]) every injective map is a monomorphism. However, even in concrete categories (and certainly more generally), monomorphisms need not be injective.

• [-epimorphism Epimorphism]: (Dual to monomorphic)

For any object $Z$ and morphisms $g,h: X \rightarrow Z$, if $gf = hf$ then $g = h$.

Intuitively, $f$ being an epimorphism indicates that all the information captured by the collection of morphisms out of $Y$ is preserved when composing by $f$.. It generalizes the notion of a surjective function. However, in an even stronger sense than for monomorphisms, a function being epimorphic and a function being surjective are far from equivalent.

Properties that more closely match surjectivity include [-section_category_theory Section / Split Epimorphism], and [-regular_epimorphism regular epimorphism]. [-strict_epimorphism strict epimorphism], [-strong_epimorphism strong epimorphism], and [-extremal_epimorphism extremal epimorphism]. Note that despite the names, not all of these are necessarily epimorphisms, but are epimorphisms in "nice" categories.

• [-endomorphism Endomorphism]: (Self-dual)

$X = Y$, i.e., $f: X \rightarrow X$.

An endomorphism is a morphism from an object to itself.

• [-automorphism Automorphism]: (Self-dual)

The morphism $f$ is both an endomorphism and an isomorphism.

An automorphism is a morphism from a structure to itself that preserves all the information of the structure that is distinguishable by the category. Intuitively, it gives "another view" of a structure (say, by moving around its elements) that leaves it essentially unchanged.

• [-retraction_category_theory Retraction / Split Monomorphism]: (Dual to split epimorphic)

There exists some $g: Y \rightarrow X$ such that $gf = 1_X$

A morphism is a retraction if its effect can be "reversed" or inverted by another morphism applied after it. For example, every injective map is a retraction. The morphism which inverts the retraction is a section.

• [-section_category_theory Section / Split Epimorphism]: (Dual to split monomorphic)

There exists some $g: Y \rightarrow X$ such that $fg = 1_Y$

A morphism is a section if it "reverses" the effect of some other morphism applied before it. The morphism which is inverted is a retraction.

[-Constructions_on_categories Constructions on Categories]

Mark Chimes

This is still very much a work in progress. Anyone is welcome to submit more info or edit. I'll add more details later. The current page probably won't remain the main lens.

Jaime Sevilla Molina

Probably you will want to precisely define morphism at some point, but I recommend you do it sooner rather than later to enforce coherence.

Mark Chimes

I don't understand? A morphism is just an abstract element of a category. Its behaviour is completely characterized by the axioms of a category. It would be like formally defining an element of a set.

Jaime Sevilla Molina

2mn I am imagining myself in the shoes of somebody who doesn't know anything about cat theory getting frustrated when they find that the article keeps talking about morphisms without giving a clue of what they are.

I think that it would be valuable to spend some time working on an intuitive definition of morphism in its corresponding page to alleviate that.

Mark Chimes

Jaime Sevilla Molina I've submitted an edit to the page on morphisms and wrote an intuitive guide to isomorphisms. I hope it's suitable for now.

My plan is also eventually to write an intuitive guide to categories with lots of concrete examples which hopefully tie in to some real-world ideas and are not as reliant on abstract mathematics.

However, I'd like to get some of the basic concepts down for the sake of the main lens. Also I'm formally trained in pure math so these are the setting and examples with which I'm more familar.

Kevin Clancy

Note that since it abstracts something away, a category does not always capture enough information for one's purposes\. For example, there is addition of group homomorphisms defined pointwise\. For this purpose, other structures such as enriched categories and n\-categories may be used\. However, for many purposes, categories are at a very good between isomorphic objects\. This is considered a feature of category theory\.

It looks like there is a word missing from this sentence. I'm not sure what it is trying to say.