Beaulampkin @beaulampkin - Tumblr Blog

Birkhoff’s HSP theorem, part 1

(As I had kind of expected, I abandoned this blog after working on it for a few days. Now, some months later, I've decided to take a different approach. Instead of writing polished wiki-style entries, I'm just going to write down my thoughts and working, stream-of-consciousness-style, while learning maths. Hopefully this will be something I can sustain for longer.)

I want to know how to prove Birkhoff's HSP theorem.

First: I want to formulate the theorem in my own words.

Theorem. For every type $T$, a variety of $T$-algebras is just a class of $T$-algebras closed under homomorphic images, subalgebras and products.

Are there any terms here whose definition I'm not totally clear on?

What about “variety”? For every type $T$, a variety of $T$-algebras is the class of the $T$-algebras satisfying all of the identities in some particular set of identities. But what is an identity exactly, and what does it mean for an algebra to satisfy it? Well, an identity is a piece of syntax of the form $t = u$, where $t$ and $u$ are $T$-terms. (This is a $T$-relative concept, so we should really talk about $T$-identities.) We could think of that as the ordered pair $(t, u)$. What is a $T$-term? It's an element of a free $T$-algebra. Are we talking about the free $T$-algebra on some specific set? Well, the generating set corresponds to the set of parameters of the term. The terms $t$ and $u$ should have the same parameters, so they should be elements of the same free $T$-algebra. But it can be any free $T$-algebra, since they can have whatever set of parameters.

So: an identity is an ordered pair $(t, u)$ where $t$ and $u$ are elements of some free $T$-algebra $T(X)$; we can say that $X$ is the set of parameters of the identity. (Technically I guess we would have to equip the identity with $X$ to make $X$ determinable from it.) As for satisfaction: a $T$-algebra $Y$ satisfies $t = u$ iff for every assignment of elements of $Y$ to each element of $X$, i.e. every function $f : X \to Y$, we have $t(f) = u(f)$. Here $t(f)$ and $u(f)$ are the images of $t$ and $u$ respectively under the unique extension $f^*$ of $f$ to $T(X$ given by the universal property of free algebras. Oh, by the way, I guess we can assume $X$ is finite.

Another way of putting this would be that $Y$ satisfies $t = u$ iff the equalizer of $t$ and $u$, when they're thought of as a functions from $Y^X$ to $Y$, is the whole of $Y^X$. (I did have to look up the Wikipedia page just to check my memory of what “equalizer” meant.)

There's also an equivalence relation here: say two $T$-terms $t$ and $u$ over $X$ are equivalent iff $t(f) = u(f)$. Here we are defining an equivalence relation for each function $f : X \to Y$. It is actually an equivalence relation, because it's just the kernel of $f^*$. So $Y$ satisfies $t = u$ iff $t$ and $u$ are equivalent in this sense for every function $f : X \to Y$. Now, I believe the intersection of equivalence relations is also an equivalence relation…let me just check that…

Theorem. Any intersection of equivalence relations is also an equivalence relation.

Proof. Suppose $X$ is a set and $S$ is a set of equivalence relations on $X$. Then:

For every $x \in X$, we have $(x, x) \in R$ for every $R \in S$, hence $(x, x) \in \bigcap S$.

For any two elements $x$ and $y$ of $X$ such that $(x, y) \in \bigcap S$, we have $(x, y) \in R$ and hence $(y, x) \in R$ for every $R \in S$, hence $(y, x) \in \bigcap S$.

For any three elements $x$, $y$ and $z$ of $X$ such that $(x, y) \in \bigcap S$ and $(y, z) \in \bigcap S$, we have $(x, y) \in R$ and $(y, z) \in R$ and hence $(x, z) \in R$ for every $R \in S$, hence $(x, z) \in \bigcap S$.

(This is one of those automatic proofs—there should be a sense in which it is obvious. I'm not going to bother worrying about that for now though.)

OK, so now we can say that $Y$ satisfies $t = u$ iff $t$ and $u$ are equivalent according to the intersection of the kernels of $f^*$ for every function $f : X \to Y$. This is a reasonable definition of equivalence of $T$-terms, if you think about. (Of course it's all relative to $Y$; it doesn't make sense in the free $T$-algebra alone.)

I guess this does require taking each identity in the set to be defined over the same free $T$-algebra. But we can do that by just unionning their variables and taking the free algebra over that union.

OK, that's enough on identities. Were there any other terms I wasn't clear on?

Oh yeah, “homomorphic images”. I guess this must mean… well, suppose I have a homomorphism $f : X \to Y$ of $T$-algebras. Then $f(X)$ is a subalgebra of $Y$. I'm sure I've proved this before, but let's just recall the proof: suppose $n \in \mathbb N$, $\omega$ is an $n$-ary function symbol in $T$ and $y_1$, $y_2$, … and $y_n$ are elements of $f(X)$. Then we have elements $x_1$, $x_2$, … and $x_n$ of $X$ such that $y_1 = f(x_1)$, $y_2 = f(x_2)$, … and $y_n = f(x_n)$. Therefore \[\omega(y_1, y_2, \dotsc, y_n) = \omega(f(x_1), f(x_2), \dotsc, f(x_n)) = f(\omega(x_1, x_2, \dotsc, x_n))\] and hence $\omega(y_1, y_2, \dotsc, y_n) \in f(X)$. There we go.

Now, if we have an arbitrary class $\mathcal A$ of $T$-algebras, then we could have $X \in \mathcal A$ but $f(X) \not \in \mathcal A$. So $\mathcal A$ would be closed under homomorphic images if this scenario is impossible.

For example, the class of the Abelian groups is closed under homomorphic images, because… well, because it's a variety, but to give a specific proof: for every group homomorphism $f : X \to Y$ such that $X$ is Abelian and any two elements $y_1$ and $y_2$ of $f(X$, we have elements $x_1$ and $x_2$ of $X$ such that $y_1 = f(x_1)$ and $y_2 = f(x_2)$, hence \[y_1 y_2 = f(x_1) f(x_2) = f(x_1 x_2) = f(x_2 x_1) = f(x_2) f(x_1) = y_2 y_1.\]

OK, now I think I understand everything about the statement. Now let's look at a proof. There's one on page 393 of An Invitation to General Algebra and Universal Constructions by George M. Bergman. It goes like:

Theorem 9.6.1 (Birkhoff's Theorem). Let $\Omega$ be a type. Then a set of $\Omega$-algebras forms a variety if and only if it is closed under forming homomorphic images, subalgebras, and products (of small families).

In fact, if $C$ is a set of $\Omega$-algebra, then any object of $\mathbf{Var}(C)$ can be written as a homomorphic image of a subalgebra of a product of a small set of members of $C$.

(I guess I didn't include the clarification about only taking products of small families in my statement of the theorem.)

What is $\mathbf{Var}(C)$? I'm guessing “the smallest variety of algebras including $C$”. For that to exist we need to be sure varieties of algebras are closed under intersections. Well, I guess they obviously are because varieties of algebras are just classes whose elements all satisfy a certain conjunction of identities, and intersecting varieties is just conjoining those conjunctions into a bigger conjunction.

OK *scrolls up* so Bergman is talking about a Galois connection between algebras and identities, and references section 6.5 of the book. I'm not sure exactly what this Galois connection would be…

Since it's now 2am, I will have to continue this tomorrow.

#mathematics #universal algebra #algebra #birkhoff's hsp theorem

Adjunctions

An adjunction $\mathcal A$ consists of:

Two categories X and Y.

Two functors $F : X \to Y$ and $G : Y \to X$ called the left and right adjoints of $\mathcal A$, respectively.

Two natural transformations $\alpha : 1_X \to GF$ and $\beta : FG \to 1_Y$ called the unit and counit of $\mathcal A$, respectively, such that the unit-counit equations hold, which are \begin{align*} \beta F \circ F \alpha &= 1_F, \\\\ G \beta \circ \alpha G &= 1_G. \end{align*} In terms of morphisms, these equations mean that for every object A in X and every object B in Y, we have \begin{align*} \beta_{F(A)} F(\alpha_A) &= 1_{F(A)}, \\\\ G(\beta_B) \alpha_{G(B)} &= 1_{G(B)}. \end{align*}

For every object A in X and every object B in Y:

We have a function $\varphi_{A, B} : \Hom_Y(F(A), B) \to \Hom_X(A, G(B))$ mapping every morphism $f : F(A) \to B$ in Y to its right adjunct under $\mathcal A$, which is $G(f) \alpha_A$.

We have a function $\psi_{A, B} : \Hom_X(A, G(B)) \to \Hom_Y(F(A), B)$ mapping every morphism $f : A \to G(B)$ in X to its left adjunct under $\mathcal A$, which is $\beta_B F(f)$.

For every morphism $f : F(A) \to B$ in Y, we have $$ \psi_{A, B}(\varphi_{A, B}(f)) = \beta_B F(G(f) \alpha_A) = \beta_B F(G(f)) F(\alpha_A) = f \beta_{F(A)} F(\alpha_A) = f 1_{F(A)} = f. $$

For every morphism $f : A \to G(B)$ in X, we have $$ \varphi_{A, B}(\psi_{A, B}(f)) = G(\beta_B F(f)) \alpha_A = G(\beta_B) G(F(f)) \alpha_A = G(\beta_B) \alpha_{G(B)} f = 1_{G(B)} f = f. $$

Therefore $\varphi_{A, B}$ and $\psi_{A, B}$ are inverses of each other, and hence are bijective.

(TODO: prove naturality)

#category theory

The category of sets

For every universe V, the category of sets $\Set_V$ is the category in which:

An object is a set in V.

A morphism $f : A \to B$ is a function, which consists of A, B and, for every $x \in A$, an $f(x) \in B$ called the image of x under f, or the element f maps x to.

For any two morphisms $f : A \to B$ and $g : B \to C$ and every $x \in A$, we have $(gf)(x) = g(f(x))$.

For any three morphisms $f : A \to B$, $g : B \to C$, $h : C \to D$ and every $x \in A$, we have $$ (h(gf))(x) = h((gf)(x)) = h(g(f(x))) = (hg)(f(x)) = ((hg)f)(x) $$ and hence $h(gf) = (hg)f$, so the associativity law is satisfied.

For every object A and every $x \in A$, we have $1_A(x) = x$.

For every morphism $f : A \to B$ and every $x \in A$, we have $$ (1_B f)(x) = 1_B(f(x)) = f(x) = f(1_A(x)) = (f 1_A)(x) $$ and hence $1_B f = f = f 1_A$, so the identity law is satisfied.

#category theory

Concrete categories preserving a transformation

For any two categories X and Y and every transformation $\alpha : F \to G$ in Op(X, Y), the set Z of the morphisms in X preserving $\alpha$ is closed under composition and contains every identity morphism in X:

Z is closed under composition

Suppose $f : A \to B$ and $g : B \to C$ are elements of Z, i.e. morphisms in X preserving $\alpha$. Then $$ G(gf) \alpha_A = G(g) G(f) \alpha_A = G(g) \alpha_B F(f) = \alpha_C F(g) F(f) = \alpha_C F(gf), $$ so $gf$ preserves $\alpha$ and hence belongs to Z.

Z contains every identity morphism in X

Suppose A is an object in X. Then $$ G(1_A) \alpha_A = 1_{G(A)} \alpha_A = \alpha_A = \alpha_A 1_{F(A)} \alpha_A F(1_A) $$ and hence $1_A$ preserves $\alpha$.

Therefore Z induces a wide subcategory $Z'$ of X, which we call the subcategory of X preserving $\alpha$. If we let $F'$ and $G'$ be the functors obtained by restricting the domains of F and G, respectively, to $Z'$, then we have a natural transformation from $F'$ to $G'$ mapping every object A in $Z'$ to $\alpha_A$.

Suppose $H : X \to \Obj(Y)$ is a function and let W be the concrete category over Y induced by H. We call the subcategory of W preserving $\alpha$ the concrete category over Y induced by H and $\alpha$.

#category theory

Product categories

For any categories $X_i : i \in I$, the product $$ \prod_{i \in I} X_i $$ of $X_i : i \in I$ is the category in which:

An object is an I-tuple $A_i : i \in I$ such that $A_i$ is an object in $X_i$ for every $i \in I$.

For any two objects $A = (A_i : i \in I)$ and $B = (B_i : i \in I)$, a morphism from A to B is an I-tuple $f_i : i \in I$ such that $f_i$ is a morphism from $A_i$ to $B_i$ in $X_i$ for every $i \in I$.

For any two morphisms $f : A \to B$ and $g : B \to C$, we have $gf = (g_i f_i : i \in I)$, where $f = (f_i : i \in I)$ and $g = (g_i : i \in I)$.

For every object $A = (A_i : i \in I)$, we have $1_A = (1_{A_i} : i \in I)$.

#category theory

The category of categories

For every universe V, the category of categories $\Cat_V$ in V is the concrete category over the quiver of quivers $\Quiv_V$ induced by:

The function U mapping every category to its underlying quiver.

The set of the quiver homomorphisms $F : U(X) \to U(Y)$, where X and Y are categories, such that:

For any two morphisms $f : A \to B$ and $g : B \to C$ in X, we have F(gf) = F(g) F(f).

For every object A in X, we have $F(1_A) = 1_{F(A)}$.

A functor is a morphism in $\Cat_V$.

#category theory

The opposite of a category

For every category X, the opposite $X^\op$ of X is the category in which:

An object is an object in X.

For any two objects A and B, a morphism from A to B is a morphism from B to A in X.

The composition of two morphisms $f : A \to B$ and $g : B \to C$ is the composition of g and f (note the reversed order) in X.

For every object A, the identity morphism on A is the identity morphism on A in X.

#mathematics #category theory

The category of quivers

For every universe V, the category of quivers $\Quiv_V$ is the concrete category over $\Set$ induced by:

The function U mapping every quiver X to $$ \Ver(X) \cup \bigcup_{(a, b) \in \Ver(X)^2} \Arr_X(a, b). $$

The set of the functions $f : U(X) \to U(Y)$, where X and Y are quivers in V, such that:

For every vertex $a$ in $X$, the image $f(a)$ is a vertex in $Y$.

For every arrow $x : a \to b$ in $X$, the image $f(x)$ is an arrow from $f(a)$ to $f(b)$ in $Y$.

A quiver homomorphism is a morphism in $\Quiv_V$.

#category theory #graph theory

Subcategories

For every category X and every set Y of objects and morphisms in X, the subcategory of X induced by Y is the category in which:

An object is an object in X belonging to Y.

For any two objects A and B, a morphism from A to B is a morphism from A to B in X which belongs to Y.

The composition of two morphisms is their composition in X.

For every object A, the identity morphism on A is the same as the one in X.

Note that this only exists if Y is closed under composition and contains every identity morphism in X.

In general, a subcategory of X is a category in which every object is also an object in X and every morphism is also a morphism in X.

The wide subcategory of X induced by Y is the subcategory of X induced by $\Obj(X) \cup Y$. In general, a wide subcategory of X is a subcategory of X with every object in X as an object of its own.

The full subcategory of X induced by Y is the subcategory of X induced by

$$ Y \cup \bigcup_{(A, B) \in (\Obj(X) \cap Y)^2} \Hom_X(A, B). $$

In general, a full subcategory of X is a subcategory Y of X with every morphism in X whose source and target are in Y as a morphism of its own.

#category theory

Concrete categories

For every category Y and every function $F : X \to \Obj(Y)$, the concrete category over Y induced by F is the category $X'$ in which:

An object is an element of X.

For every object A, we call F(A) the underlying object of A in Y (wrt F).

A morphism $f : A \to B$ is an ordered triple $(f', A, B)$ such that $f : F(A) \to F(B)$ is a morphism in Y.

We call $f'$ the underlying morphism of f in Y (wrt F). We may write it as F(f) (so that $f = (F(f), A, B)$).

The composition of two morphisms $f : A \to B$ and $g : B \to C$ is $(F(g) F(f), A, C)$ (so that $F(gf) = F(g) F(f)$).

This satisfies the associativity law because for any three morphisms $f : A \to B$, $g : B \to C$, $h : C \to D$, we have $$ h(gf) = (F(h) F(gf), A, D) = (F(h) F(g) F(f), A, D) = (F(hg) F(f), A, D) = (hg)f. $$

For every object A, we have $1_A = (1_{F(A)}, A, A)$ (so that $F(1_A) = 1_{F(A)}$).

This satisfies the identity law because for every morphism $f : A \to B$, we have \begin{align*} 1_B f &= (F(1_B) F(f), A, B) = (F(1_B f), A, B) = (F(f), A, B) = f, \\\\ f 1_A &= (F(f) F(1_A), A, B) = (F(f 1_A), A, B) = (F(f), A, B) = f. \end{align*}

We can make F into a functor from $X'$ to Y in the way suggested by the notation. This functor is always fully faithful. It is called the forgetful functor from $X'$ to Y.

For every set Z of morphisms in Y which is closed under composition and contains every identity morphism in Y, the set $Z'$ of the morphisms f in $X'$ with $F(f) \in Z$ is also closed under composition and contains every identity morphism in $X'$:

$Z'$ is closed under composition

Suppose $f : A \to B$ and $g : B \to C$ are elements of $Z'$. Then F(f) and F(g) both belong to Z, and since Z is closed under composition it follows that $F(gf) = F(g) F(f) \in Z$ and hence $gf \in Z'$.

$Z'$ contains every identity morphism in $X'$

Suppose $A$ is an object in $X'$. Then $F(1_A) = 1_{F(A)} \in Z$ and hence $1_A \in Z'$.

We call the wide subcategory $Z''$ of $X'$ induced by $Z'$ the concrete category over Y induced by F and Z. By restricting the forgetful functor from $X'$ to Y so that its domain is $Z''$ we obtain a functor which is faithful, but not generally full. This functor is called the forgetful functor from $Z''$ to Y.

Most of the specific categories that turn up in general mathematics can be constructed as concrete categories over $\Set$ (or over a category which was constructed similarly).

#category theory

Categories

A category is a quiver equipped with some additional stuff. We use different terminology when talking about categories: we say object instead of “vertex”, morphism instead of “arrow”, domain instead of “source”, codomain instead of “target”, hom-set instead of “arrow set”, and we write Obj(X) instead of Ver(X) and Hom(A, B) instead of Arr(A, B). Also, note that we call a morphism whose domain and codomain are equal an endomorphism on the common value of its domain and codomain.

To make it into a category, a quiver X must be equipped with:

For any two morphisms $f : A \to B$ and $g : B \to C$ in X, a morphism $gf : A \to C$ (which may also be written as $g \circ f$, when that looks better) called the composition of f and g (in X).

For every object A in X, an endomorphism $1_A$ on A called the identity morphism on A (in X).

Furthermore, the following laws must be satisfied:

Associativity

For any three morphisms $f : A \to B$, $g : B \to C$, $h : C \to D$ in X, we have $h(gf) = (hg)f$.

Identity

For every morphism $f : A \to B$ in X, we have $1_B f = f = f 1_A$.

#category theory

Quivers

A quiver X consists of:

A set Ver(X), whose elements are called the vertices in X.

Pairwise disjoint sets $\Arr_X(a, b) : (a, b) \in \Ver(X)^2$.

For any two vertices a and b in X, we may write $\Arr_X(a, b)$ as Arr(a, b) for short. We call it the arrow set from a to b (in X). We call an $x \in \Arr(a, b)$ an arrow from a to b (in X), and write it as $x : a \to b$ to indicate what arrow set it belongs to.

Every arrow x in X belongs to a unique arrow set Arr(a, b) in X. We call a the source of x (in X), or the vertex x is on (in X), and we call b the target of x (in X), or the vertex x is into (in X).

A quiver X can be thought of a diagram, with points on the page corresponding to vertices in X and arrows drawn between those points corresponding to arrows in X between the corresponding vertices.

Quivers may also be called graphs, although that term is somewhat vague and has several possible meanings. In graph theory, the word “graph” normally refers to a special kind of quiver, and quivers in general will normally be referred to as “directed multigraphs” or something like that. In general mathematics, “graph” is also used to refer to the graph of a function or relation, which is a more or less totally different concept.

#mathematics #category theory #graph theory

Natural transformations between monoid homomorphisms

For any two monoids X and Y and any two homomorphisms f and g from X to Y, a transformation from f to g is simply an element $\alpha$ of Y. The transformation is natural iff for every $x \in X$, we have $g(x) \alpha = \alpha f(x)$.

I have never seen this notion referred to anywhere, so I don’t know if it’s actually useful for anything---not that I know much about the theory of monoids.

Unlike with preorders, the functor category Nat(X, Y) is not itself a monoid. Composition of natural transformations in Nat(X, Y) is just multiplication in Y.

For any three monoids X, Y, Z and any two natural transformations $\alpha : f_1 \to g_1$ and $\beta : f_2 \to g_2$ in Nat(X, Y) and Nat(Y, Z) respectively, we have $$ \beta \star \alpha = g_2(\alpha) \beta = \beta f_1(\alpha). $$

#category theory #monoid theory

Preordering preorder homomorphisms

For any two prosets X and Y and any two homomorphisms f and g from X to Y, there is a transformation from f to g iff for every $x \in X$, we have f(x) ≤ g(x). Moreover any such transformation is trivially natural. Therefore the functor category Nat(X, Y) is a proset, whose underlying set is the set of the homomorphisms from X to Y. Of course, the rule that f ≤ g iff f(x) ≤ g(x) for every $x \in X$ does not require the homomorphism-ness of $f$ and $g$ at all to be well-posed and therefore this preordering might as well be extended to the set of all the functions from X to Y.

For any three prosets X, Y, Z, any two homomorphisms $f_1$ and $g_1$ from X to Y and any two homomorphisms $f_2$ and $g_2$ from Y to Z such that $f_1 \le g_1$ and $f_2 \le g_2$, we have $f_2 f_1 \le g_2 g_1$ by the existence of horizontal compositions.

This can of course be proven more directly. For every $x \in X$, we have $f_1(x) \le g_1(x)$ because $f_1 \le g_1$. Now there are two paths we can go down:

We could observe that $f_2(f_1(x)) \le f_2(g_1(x))$ because $f_2$ is a homomorphism and $f_2(g_1(x)) \le g_2(g_1(x))$ because $f_2 \le g_2$.

We could observe that $f_2(f_1(x)) \le g_2(f_1(x))$ because $f_2 \le g_2$ and $g_2(f_1(x)) \le g_2(g_1(x))$ because $g_2$ is a homomorphism.

We can see from this that in fact the conclusion will hold even if only one of $f_2$ and $g_2$ is a homomorphism, and it is not required that $f_1$ and $g_1$ be a homomorphism at all.

This is an interesting case where although category theory gives us a quick theorem, we can get a somewhat more general theorem by dropping down to ordinary order theory.

#category theory #order theory

Whiskerings

Suppose X, Y, Z are categories.

For every morphism $\alpha : F \to G$ in Nat(X, Y) and every functor $H : Y \to Z$, the left whiskering $H \alpha$ of $\alpha$ by $H$ is $1_H \star \alpha$, i.e. the natural transformation from HF to HG mapping every object A in X to $H(\alpha_A)$.

For every functor $F : X \to Y$ and every natural transformation $\alpha : G \to H$ in Nat(Y, Z), the right whiskering $\alpha F$ of $\alpha$ by $F$ is $\alpha \star 1_F$, i.e. the natural transformation from GF to HF mapping every object A in X to $\alpha_{F(A)}$.

Here Nat(X, Y) and Nat(Y, Z) are functor categories.

#category theory #mathematics

Horizontal composition

For any three categories X, Y, Z and any two morphisms $\alpha : F_1 \to G_1$ and $\beta : F_2 \to G_2$ in the functor categories Nat(X, Y) and Nat(Y, Z) respectively, the horizontal composition $\beta \star \alpha$ of $\beta$ and $\alpha$ is the transformation from $F_2 F_1$ to $G_2 G_1$ such that for every object A in X, we have $$ (\beta \star \alpha)_A = G_2(\alpha_A) \beta_{F_1(A)} = \beta_{G_1(A)} F_2(\alpha_A). $$ The two right-hand sides here are equal because $\beta$ is natural and hence the morphism $\alpha_A$ in $Y$ preserves $\beta$.

This transformation is natural, because for every morphism $f : A \to B$ in X, we have

\begin{align*} (G_2 G_1)(f) (\beta \star \alpha)_A &= G_2(G_1(f)) G_2(\alpha_A) \beta_{F_1(A)} &\quad \text{definition of $(\beta \star \alpha)_A$} \\\\ &= G_2(G_1(f) \alpha_A) \beta_{F_1(A)} &\quad \text{$G_2 is a functor$} \\\\ &= G_2(\alpha_B F_1(f)) \beta_{F_1(A)} &\quad \text{$f$ preserves $\alpha$} \\\\ &= G_2(\alpha_B) G_2(F_1(f)) \beta_{F_1(A)} &\quad \text{$G_2$ is a functor} \\\\ &= G_2(\alpha_B) \beta_{F_1(B)} F_2(F_1(f)) &\quad \text{$F_1(f)$ preserves $\beta$} \\\\ &= (\beta \star \alpha)_B (F_2 F_1)(f). &\quad \text{definition of $(\beta \star \alpha)_B$} \end{align*}

For any two morphisms $\alpha_1 : F_1 \to G_1$ and $\beta_1 : G_1 \to H_1$ in Nat(X, Y) and any two morphisms $\alpha_2 : F_2 \to G_2$ and $\beta_2 : G_2 \to H_2$ in Nat(Y, Z), we have the interchange law $$ (\beta_2 \star \beta_1)(\alpha_2 \star \alpha_1) = \beta_2 \alpha_2 \star \beta_1 \alpha_1, $$ because for every object A in X, we have \begin{align*} (\beta_2 \alpha_2 \star \beta_1 \alpha_1)_A &= H_2((\beta_1 \alpha_1)_A) (\beta_2 \alpha_2)_{F_1(A)} &\quad \text{definition of $(\beta_2 \alpha_2 \star \beta_1 \alpha_1)_A$} \\\\ &= H_2((\beta_1)_A (\alpha_1)_A) (\beta_2)_{F_1(A)} (\alpha_2)_{F_1(A)} &\quad \text{definitions of $(\beta_1 \alpha_1)_A$ and $(\beta_2 \alpha_2)_{F_1(A)}$} \\\\ &= H_2((\beta_1)_A) H_2((\alpha_1)_A) (\beta_2)_{F_1(A)} (\alpha_2)_{F_1(A)} &\quad \text{$H_2$ is a functor} \\\\ &= H_2((\beta_1)_A) (\beta_2 \star \alpha_1)_A (\alpha_2)_{F_1(A)} &\quad \text{definition of $(\beta_2 \star \alpha_1)_A$} \\\\ &= H_2((\beta_1)_A) (\beta_2)_{G_1(A)} G_2(\alpha_1) (\alpha_2)_{F_1(A)} &\quad \text{definition of $(\beta_2 \star \alpha_1)_A$} \\\\ &= (\beta_2 \star \beta_1)_A (\alpha_2 \star \alpha_1)_A &\quad \text{definitions of $(\beta_2 \star \beta_1)_A$ and $(\alpha_2 \star \alpha_1)_A$} \\\\ &= ((\beta_2 \star \beta_1)(\alpha_2 \star \alpha_1))_A. &\quad \text{definition of $((\beta_2 \star \beta_1)(\alpha_2 \star \alpha_1))_A$} \end{align*}

Furthermore, for any two functors $F : X \to Y$ and $G : Y \to Z$, we have $1_G \star 1_F = 1_{GF}$. To prove this, observe that for every object A in X, we have

$$ (1_G \star 1_F)_A = G((1_F)_A) (1_G)_{F(A)} = G(1_{F(A)}) 1_{G(F(A))} = 1_{G(F(A))} 1_{G(F(A))} = 1_{G(F(A))} = 1_{(GF)(A)} = (1_{GF})_A. $$

We therefore have a bifunctor from $\Nat(X, Y) \times \Nat(Y, Z)$ to $\Nat(X, Z)$ mapping any two functors $F : X \to Y$ and $G : Y \to Z$ to $GF : X \to Z$ and any two natural transformations $\alpha : F_1 \to G_1$ and $\beta : F_2 \to G_2$ in Nat(X, Y) and Nat(Y, Z) respectively to $\beta \star \alpha : F_2 F_1 \to G_2 G_1$.

This is like how in a category, for any three objects A, B, C, we have a binary function from $\Hom(A, B) \times \Hom(B, C)$ to $\Hom(A, C)$ mapping any two morphisms $f : A \to B$ and $g : B \to C$ to $gf : A \to C$.

#mathematics #category theory

Functor categories

Suppose X and Y are categories.

For any two natural transformations $\alpha : F \to G$ and $\beta : G \to H$ in Op(X, Y), the composition $\beta \alpha$ is natural, because for every morphism $f : A \to B$ in X, we have

$$ H(f) (\beta \alpha)_A = H(f) \beta_A \alpha_A = \beta_B G(f) \alpha_A = \beta_B \alpha_B F(f) = (\beta \alpha)_B F(f). $$

And for every functor $F : X \to Y$, the identity transformation $1_F$ is natural, because for every morphism $f : A \to B$ in X, we have

$$ F(f) (1_F)_A = F(f) 1_{F(A)} = F(f) = 1_{F(B)} F(f) = (1_F)_B F(f). $$

Therefore the set of the natural transformations in Op(X, Y) is the set of the morphisms in a wide subcategory Nat(X, Y) of Op(X, Y), which is called the functor category from X to Y.

#mathematics #category theory

Trending Blogs

Recently Viewed Blogs

Beaulampkin