Base definitions

Definitions

The chapter provides you with base definitions that will be widely used in the book later. We will give definitions for Object, Morphism, Category and also provide you with several important examples, such as the Set category.

Object

Morphism

Morphism is a kind of relation between 2 Objects.

The important remark about morphisms is below.

Morphisms have several properties. ¹

Note that Identity morphism is unique, see Identity is unique below.

A diagram in a category \(\mathbf{C}\) is a collection of vertices and directed edges where the vertices correspond to the objects of \(\mathbf{C}\) and edges consistently correspond to the morphisms (see Diagram).

Consistently means that for an edge named as \(f\) has endpoints labeled \(a\) and \(b\), where \(f\) is a morphism of \(\mathbf{C}\), \(a\) is Domain of \(f\) and \(b\) is Codomain of \(f\).

The trivial example of Commutative diagram is Composition for \(f_{ab} = f_{cb} \circ f_{ac}\):

If \(\forall g_1, g_2\) the equation \[f \circ g_1 = f \circ g_2\] leads to \[g_1 = g_2\] then \(f\) is called monomorphism (see Monomorphism). The monomorphism between \(a\) and \(b\) is denoted as \(f: a \hookrightarrow b\) (see also Injection or “one-to-one” functions).

If \(\forall g_1, g_2\) the equation (see Epimorphism) \[g_1 \circ f = g_2 \circ f\] leads to \[g_1 = g_2\] then \(f\) is called epimorphism (see also Surjection or “onto” functions).

Category

The Category can be considered as a way to represent a structured data. Objects are the data and Morphisms form the structure that connects the data.

There are several examples of categories below that will also be actively used later in the book:

• \(\mathbf{Set}\) category example: see Set

• Programming languages (Haskell, C++, Scala) examples: see Programming languages examples

• Quantum mechanics example: see Quantum mechanics examples

\(\mathbf{Set}\) category example

The category of sets is the most important example because it connects our usual knowledge about sets with the category theory.

Example of binary relation is shown on Binary relation. There is a relation \(R\) between 2 sets \(A\) and \(B\). The relation maps \(a_1\) into two different values \(b_1\) and \(b_2\).

An example of a surjective function is shown in Surjection. Note that the function in the figure is not an Injection. You can find an example of a function that is Surjection as well as Injection (aka Bijection) in Set.

Surjection and Epimorphism are related each other. Consider a non-surjective function \(f: X \rightarrow Y\) and let \(Y' \subset Y\) be the image of \(f\) (see Surjection vs Epimorphism). One can conclude that \(f\) is not an Epimorphism. Let \(Z = \{0, 1\}\). We can define two functions \(g_1, g_2 : Y \to Z\) such that \(g_1(y) = g_2(y)\) for all \(y \in Y'\) but \(g_1 \ne g_2\) on at least one element of \(Y \setminus Y'\). As soon as \(f(x) \in Y'\) for all \(x \in X\), we always have \(g_1(f(x)) = g_2(f(x))\). I.e. \[g_1 \circ f = g_2 \circ f,\] but \(g_1 \ne g_2\). Thus every Epimorphism in \(\mathbf{Set}\) has to be a Surjection. Conversely, every Surjection is an Epimorphism in the \(\mathbf{Set}\) category. The full proof can be found at (ProofWiki 2018b).

An example of an injective function is shown in Injection. Note that the function in the figure is not a Surjection. You can find an example of a function that is Surjection as well as Injection (aka Bijection) in Set.

There is a question what is the categorical analog of a single Set. Main characteristic of a category is a structure but the Set by definition does not have a structure. Which category does not have any structure? The answer is the Discrete category.

Programming languages examples

Functions are the most important constructions in programming languages. They convert elements ² of one type into elements of another one.

Categorical view to programming languages assumes types as Objects and functions as Morphisms. The critical requirements for such consideration is that the functions have to be Pure functions (without side effects). This requirement mainly is satisfied by functional languages such as Haskell and Scala.

From other side the functional languages use lazy evaluation to improve their performance. The laziness can also make category theory axiom invalid (see Haskell lazy evaluation below).

    seq undefined True

    seq (id.undefined) True
    seq (undefined.id) True

    id . undefined /= undefined
    undefined . id /= undefined,

    seq :: a -> b -> b

Strictly speaking neither Haskell (pure functional language) nor C++ can be considered as a category in general. For the first approximation a functional language (Haskell, Scala) can be considered as a category if we avoid to use functions with side effects (mainly for Scala) and use strict, not lazy, evaluations (for both Haskell and Scala). Lets take the fact into consideration and define categories for 3 languages

In any case we can construct a simple toy category that can be easy implemented in any language. Particularly we shall look into category with 3 Objects that are types: Int, Bool, String. There are also several Morphisms (functions) between them (see Programming languages examples).

\(\mathbf{Hask}\) toy category

    isEven :: Int -> Bool
    isEven x = x `mod` 2 == 0

    id :: a -> a
    id x = x

    stringLength :: String -> Int
    stringLength x = length x

    isStringLengthEven :: String -> Bool
    isStringLengthEven = isEven . stringLength

\(\mathbf{Scala}\) toy category

    object Category {
      def id[A]: A => A = a => a
      def compose[A, B, C](g: B => C, f: A => B): 
          A => C = g compose f 
      
      val isEven = (i: Int) => i % 2  == 0
      val stringLength = (s: String) => s.length
      val isStringLengthEven = (s: String) => 
          compose(isEven, stringLength)(s)
    }

    
    class CategorySpec extends Properties("Category") {
      import Category._
      import Prop.forAll
      
      property("composition") = forAll { (s: String) =>
        isStringLengthEven(s)  == isEven(stringLength(s))
      }
      
      property("right id") = forAll { (i: Int) =>
        isEven(i)  == compose(isEven, id[Int])(i)
      }
      
      property("left id") = forAll { (i: Int) =>
        isEven(i)  == compose(id[Boolean], isEven)(i)
      }
    }

\(\mathbf{C\texttt{++}}\) toy category

    auto isEven = [](int x) { 
      return x % 2 == 0; 
    };

    auto stringLength = [](std::string s) { 
      return static_cast<int>(s.size()); 
    };

    // h = g . f
    template <typename A, typename B> 
    auto compose(A g, B f) {
      auto h = [f, g](auto a) {
        auto b = f(a);
        auto c = g(b);
        return c;
      };
      return h;
    };

    auto id = [](auto x) { return x; };

    auto isStringLengthEven = compose<>(isEven, stringLength);

    auto isStringLengthEvenL = compose<>(id, isStringLengthEven);

    auto isStringLengthEvenR = compose<>(isStringLengthEven, id);  

Quantum mechanics examples

The most critical property of quantum system is the superposition principle. The Set category cannot be used for it because it does not satisfy the principle but a simple modification of the \(\mathbf{Set}\) category does.

In quantum mechanics we use Hilbert spaces that are Vector spaces under Field of complex numbers \(\mathbb{C}\).

The transformation between 2 Hilbert spaces that preserves the structure is called linear map or linear transformations.

If we want to combine 2 Hilbert spaces into one we use a notion of direct sum.

For our example we consider a 2 level atom with states \(\ket{a}\) - excited and \(\ket{b}\) - ground. As soon as we consider a 2-level system we are in the 2 dimensional Hilbert space. The category in the example will be called as \(\mathbf{Rabi}\). It has only one Object: \[\mathrm{ob}(\mathbf{Rabi}) = \{\mathcal{H}_2\}.\]

The atom interacts with light beam of frequency \(\omega = \omega_{ab}\). The state of the system is described by the following equation (Мурашко И. В. 2018): \[\ket{\psi} = \cos{\frac{\omega_R t}{2}} \ket{a} - i \sin{\frac{\omega_R t}{2}} \ket{b}, \nonumber\] where \(\omega_R\) - Rabi frequency (Мурашко И. В. 2018).

The interaction time \(t\) is fixed and corresponds to \(\omega_R t = \pi\) i.e. the interaction can be described a linear operator \(\hat{L}\).

There are 4 different Morphisms: \[\mathrm{hom}(\mathbf{Rabi}) = \{\mathbf{1}_{\mathcal{H}_2 \to \mathcal{H}_2}, \hat{L}, \hat{L}^2, \hat{L}^3\}.\] The corresponding orbit of the initial state \(\ket{\psi}_0\) is given as follows: \[\begin{aligned} \ket{\psi}_0 = \ket{a}, \nonumber \\ \ket{\psi}_1 = \hat{L} \ket{\psi}_0 = -i \ket{b}, \nonumber \\ \ket{\psi}_2 = \hat{L}^2 \ket{\psi}_0 = - \ket{a}, \nonumber \\ \ket{\psi}_3 = \hat{L}^3 \ket{\psi}_0 = i \ket{b}, \nonumber \end{aligned}\]

Categorical approach

There is an interesting relation between sets and categories. In both we consider objects(sets) and relations between them(morphisms/functions).

In the set theory we can get info about functions by looking inside the objects(sets) aka use “microscope” (Milewski 2018). For instance the definitions for Injection and Surjection are given in the terms of internal objects (sets) structure.

Contrary in the category theory we initially don’t have any info about object internal structure but can get it using the relation between the objects i.e. using Morphisms. In other words we can use “telescope” (Milewski 2018) there. For the instance in the Surjection vs Epimorphism we concluded that Epimorphism is a categorical definition for Surjection. The same conclusion for relation between Injection and Monomorphism was made in Injection vs Monomorphism.

Many constructions can be defined in the 2 different ways: via local (via “microscope”) or global (via “telescope”) approach. This gives us the following definitions.

Categorical approach often uses so called Universal property to define different constructions. There is an informal definition of the property below

Typical examples of the universal property application are Product and Sum definitions. You can find the definitions later in the book (see Product and sum). The Universal property seems to be broadly used in different areas. There are several examples of such Universal property usage (see Physics) and Categorical approach (see Programming languages) below.

Programming languages

There are two basic options possible in programming language. You can use an imperative approach to implement requested functionality or declarative (functional) one. Lets illustrate it on the factorial calculation example.

The factorial can be defined in 2 forms. The first one assumes direct instruction on how to calculate it: \[n! = \prod_{i = 1}^n i,\] another one gives you a formal definition for the function: \[\begin{aligned} n! = n \cdot \left(n-1\right)!, \nonumber \\ 0! = 1 \end{aligned}\]

Straightforward approach to resolve the task is demonstrated by C++ language in implementing (Programming languages):

int f(int n) {
  if (n < 0) {
    throw std::invalid_argument(
      "the argument has to be greater or equal 0");
  }
  int res = 1;
  for (int i = 1; i <= n; ++i) {
    res *= i;
  }
  return res;
}

The solution requires provide all details about the internal structure of the solution i.e. which variables to be used and how to calculate result using them. Thus the approach can be considered as a variation of Non-categorical approach.

Another case assume that the formal definition of the function is provided without any internal details about the implementation. I.e. the (Programming languages) is used. A functional language such as Haskell is a good candidate for the implementation:

-- Factorial
f 0 = 1
f n = n * f (n - 1)

Physics

Many physical concepts (may be every one) can be formulated in 2 ways. The first one uses differential equations (aka local approach). The second one uses integral equations (aka global approach). The first case is similar to the “microscope” usage. The second one is the similar to “telescope” approach.

Optics

Optics is another good example of Universal property in physics. In optics it can be reformulated as follows

Good example of the property is shown in Optics. When the light traverse from point \(A\) to point \(B\) it does not use the shortest path because a big part of the path will be in water where speed of the light (\(v_2\)) is smaller than in air (\(v_1\)): \[v_2 < v_1\] Thus if it follows the Universal property then it should minimize the path in water that leads to well known Snell’s law (Wikipedia contributors 2019b): \[\frac{\sin \theta_2}{\sin \theta_1} = \frac{v_2}{v_1} = \frac{n_1}{n_2}.\]

Classical mechanics

we shall consider a motion of a classical mechanical system there. The system consists of \(n\) particles. Each particle with number \(i \in {1, \dots, n}\) has coordinate \(q_i \in \mathbb{R}^3\) that changes with time. The set \({q_1(t), \dots, q_n(t)}\) defines the trajectory.

Equations of classical mechanics, that define the trajectory, can be written in different forms. we shall consider Lagrangian form and least action form there. The key point for both is Lagrangian that can be written ⁴ as \[L = T - U,\] where \(T\) is kinetic energy and \(U\) is the potential energy. The Lagrangian is the function of particles positions \(\{q_i\}\), velocities \(\{\dot{q}_i\}\) and time \(t\). For the case of \(n\) particles we can get the following form of Lagrangian: \[L = L\left(q_1, \dots, q_n, \dot{q}_1, \dots, \dot{q}_n, t\right).\] The motion equation can be written in the following form: \[\frac{d}{dt}\left( \frac{\partial L}{\partial \dot{q}_i} \right) = \frac{\partial L}{\partial q_i}\]

The (Classical mechanics) is an example of local approach when the knowledge about local properties (this knowledge leads to the differential equation) gives us the motion equation i.e. the equation has been got using a “microscope” there.

Another way to investigate the motion is the principle of least action. In the principle we consider all possible trajectories of our system between time points \(t_1\) and \(t_2\). For each trajectory \({\bf q}(t) = {q_1(t), \dots, q_n(t)}, t \in [t_1, t_2]\) we can define the following integral \[S\left({\bf q}, t_1, t_2\right) = \int_{t_1}^{t_2}L\left({\bf q}(t), \dot{\bf q}(t), t\right) dt,\] that is called as Action. The principle of least action states that the trajectory taken by the system between times \(t_1\) and \(t_2\) is the one for which the action is stationary (no change) to first order (Wikipedia contributors 2019a) i.e. \[\delta S = 0.\] We can rewrite the principle as follows \[\begin{aligned} \delta S = \int_{t_1}^{t_2} \delta L\left({\bf q}(t), \dot{\bf q}(t), t\right) dt = \nonumber \\ = \int_{t_1}^{t_2} \left[L\left({\bf q} + \delta {\bf q} , \dot{\bf q} + \delta \dot{\bf q}, t\right) - L\left({\bf q}, \dot{\bf q}, t\right)\right] dt = \nonumber \\ = \int_{t_1}^{t_2} \left[\frac{\partial L}{\partial {\bf q}} \delta {\bf q} + \frac{\partial L}{\partial \dot{\bf q}} \delta \dot{\bf q}\right] dt = \int_{t_1}^{t_2} \frac{\partial L}{\partial {\bf q}} \delta {\bf q} dt + \nonumber \\ + \left. \frac{\partial L}{\partial \dot{\bf q}} \delta {\bf q} \right|_{t_1}^{t_2} - \int_{t_1}^{t_2} \frac{d}{d t} \left( \frac{\partial L}{\partial \dot{\bf q}} \delta {\bf q}\right) dt = \nonumber \\ = \int_{t_1}^{t_2} \left[ \frac{\partial L}{\partial {\bf q}} - \frac{d}{d t} \left( \frac{\partial L}{\partial \dot{\bf q}} \right) \right] \delta {\bf q} dt = 0, \nonumber \end{aligned}\] that leads to (Classical mechanics). Therefore the same motion equation can be used using global approach (via integral over all possible trajectories) or in other words the “telescope” was used there.

Quantum mechanics

Very interesting example of Categorical approach is provided us by quantum mechanics via path integrals (Feynman, Hibbs, and Styer 2010). The question that is asked is the following. If we have 2 points \(a\) and \(b\), what’s probability \(P(a, b)\) that a particle moves from \(a\) to \(b\)? The probability is defined as follows (Feynman, Hibbs, and Styer 2010): \[P(a,b) = \left|K(a,b)\right|^2,\] where \(K(a,b)\) is a special function defined by all possible paths from \(a\) to \(b\) as follows \[K(a,b) = \frac{1}{Z} \int_{\bf q} e^{\frac{i}{\hbar}S({\bf q})} \mathcal{D}{\bf q},\] where \({\bf q}\) is a trajectory from \(a\) to \(b\) (see Quantum mechanics), and \(S\) is the action defined by (Classical mechanics). For a path \(x\) such that \(\delta S({\bf q}) > \hbar\) we shall have that a trajectory \({\bf q} + \delta {\bf q}\) that is similar to \({\bf q}\) but gives a completely different action and as result such trajectories will cancel each other.

From other hand the path \({\bf q}_0\) such that \(\delta S({\bf q}_0) = 0\) will have all other similar trajectories \({\bf q}_0 + \delta {\bf q}\) will increase each other and as result the \({\bf q}_0\) will define the real trajectory for the particle. This is in direct connection with the classical least action principle (Wikipedia contributors 2019a).