Category theory

Lets hack some abstract bullshit

The best way to understand what you are reading is to make the idea your own “aha”. This means following the idea back to its origin (to What Is), and thus rediscovering it for yourself.

Indeed, everything that has been written by humans (except bullshit) is (or at least should be) verbalized observations of the same reality from different angles and distances (points of view).

Proper philosophy first

Why arrows?

Because they imply a direction - an order for a ordered pair.

Why directed? Because of the Causality Principle. Causality (it and only it) establishes a direction and an order.

A single “step”

\[\cdot \rightarrow \cdot\] This is a minimal directed graph - an abstraction. which may correspond to a single step (a single transition) whatsoever.

It may be a single step of a logical deduction (which is called an implication) or it may be a function application (which sounds almost the same), or it may be a single leg of a path.

Is it really a minimal?

A single “dot”

\[\rightarrow\cdot\] What this corresponds to? From where this arrow points towards something?

From an external observe, of course. This is something he directs his attention to

We seen such arrows before (yes, it is a fat one, but it is an arrow!). \[\Gamma \Rightarrow A\] something that is already known (to an observer).

So, this single dot (selected by the mind or by directing observer’s attention to) is a starting point for a single step. It is sometimes called a selector.

We cannot step from nothing. (Which is why False does not imply anything).

A set

One of the ways to define a set is to state explicitly all the elements. The notation for this is \(S = \{a,b,c,...,x\}\), and we define alphabets essentially in this way. And it seems that \(\{0,1\}\) is enough for everything.

What does it mean? It means that an observer has to know and to point out every single element explicitly, with a finger or with a word, just like children do.

\[\rightarrow\cdot\] is a magical thing. Any set is isomorphic to a set of all arrows from you (towards what you know). \[S \cong Hom(You,S)\]

A next step

A next step starts exactly where the previous ends. This is the essence of a composition (of functions, of implications, etc). \[\cdot \rightarrow \cdot \rightarrow \cdot\] That “dot” in the middle is special - it is a codomain of the previous arrow and domain of the next. It has to be the same.

Any 3 dots are between 2 steps

There can be only “this many” directed arrows between any 3 dots. \[\cdot \rightarrow \cdot \rightarrow \cdot\] the individual steps \[\cdot \rightarrow \cdot\] and the result of their composition, provided the laws of composition hold.

This is a minimal algebraic structure.

Nothing more to consider

Just like it is with the successor function (+1), the ability to take a single step \(\cdot \rightarrow \cdot\) is enough.

It is not an arbitrary choice that a λ abstraction is of an arity one (takes exactly one argument) - it is minimal and enough for everything.

Currying

Currying is a technique to take one (and only one) argument to a function at a time by returning a “next step” function for a “next argument” for multi-argument operators, such as \(+\).

It corresponds exactly to the \[\cdot \rightarrow \cdot \rightarrow \cdot\] “individual steps” pattern (at a type-level), and this is not an arbitrary coincidence.

Partial application (supplying a fewer arguments and using the resulting closure) - like (+1) - naturally follows.

Now we “compose” these steps (or lambdas).

Composition

We describe “steps” as mappings \(x \mapsto x^{2}\), lets say, and give them names, like \(f\) and types, like \(f: N^{+} \rightarrow N^{+}\).

Now we compose these mappings (steps) with an operator \(\circ\).

Associativity

Composition should have the associative property \[\forall f, g, h, (h \circ g) \circ f = h \circ (g \circ f)\] which means it is irrelevant in what order we connect the plumbing pipes.

There is a special case, when \(f = g = h\) (the same operation being composed with itself or pipelined to itself).

This means the operation (\(\cdot \rightarrow \cdot\)) is itself associative.

Addition(\(+\)) or string concatenation ++ are such operations - it does not matter in what order we add up or put together.

Identity

There has to be an arrow from any “dot” to itself, which corresponds to an identity function for a set (or an identity element for an operation).

What can be a “dot”

Usually, dots stand for sets or types, but it could be almost any “collection”, “structure” or a whole “class” of these.

What could be an “arrow”

A single function, a morphism (which is more general), a Functor (which is a particular class of morphisms), everything that takes a single step (and has at most one outgoing arrow).

A homomorhphism is a technical term for a structure-preserving transformation (mapping, or a function).

One more generalization

A category is a higher level generalization from (and defined in terms of) the Set Theory.

“collections” are sets (or classes)
“morphisms” are set-theoretic functions (sets of ordered pairs)
“equality” is also set-theoretic (all the same members)

Within Set Theory functions from \(A\) to \(B\) are viewed as a Set of Ordered Pairs, just as a Cartesian Product.

These functions are single “composite arrows” at the type level - \(f: A\rightarrow B\).

So \(f: A \rightarrow B\) is \(\{(a, b)\}\) (a set of all ordered pairs), just like [(a, b)] which is a table, and a valid type in Haskell, by the way.

A function \(f\) has its image in a set \(S\) such that \(B \subset S\)

There are also “individual arrows” which represent each ordered pair. And \(x \rightarrow x^2\) (\(N^{+} \rightarrow N^{+}\))can be viewed as (in a pseudo-code)

{ (1, 1),
  (2, 4),
  (3, 9),
...
}

The ordering of pairs (not within a single pair) is immaterial.

So, ordered pairs were generalized as “arrows” (which are convenient for directed graphs) and values as mere “dots” (which they call “objects”).

Thus we have something even more abstract, like

 * -> *
 * -> *
 * -> *
 ...

and particular strucures (directed graphs) they form when being composed.

Not only we generalize structure, we also generalize associative composition of “arrows”.

Structure

So, structurally, there are a “collection” (a set) of “objects” (“dots”) together with a “collection” (a set) of “arrows” (“morphisms”). \[(O, A,...)\] While a set is just a “collection”, a category is a pair of “collections”. Actually it is a triple.

Structurally, there must be at least one “object” and at least one “arrow” (to itself) in a category. And a trivial composition with itself.

One of the most important notions is to show that some structure of “dots” and “arrows” is all that is there.

This has philosophical correlation to the fact, that there is no such thing as randomness, only “possible paths” and “forks” (which, in turn, corresponds to sum-types and pattern-matching on them).

Nesting

Just like sets, these abstract entities could be nested, given that they have the same structure of composed arrows.

All the individual arrows

Lets say we have augmented a set of values with an explicit set of all “arrows”, which means adding more structure.

Not just one arrow, as in \(A \rightarrow B\), but all the individual arrows, which form different patterns (structures, or directed graphs).

Usually a collection of all arrows (within a category) is denoted as \(C(A,B)\).

All the “individual arrows” have the same domain \(A\) and codomain \(B\).

Sadly, not all functions (morphisms) are one-to-one, so different patterns emerge.

Composition

The composition operator \(\circ\) for total functions is defined as \(\forall f: A\rightarrow B, g: B\rightarrow C, c = g(f(a))| a\in A,c\in C\)

Associativity of composition (of functions or “morphisms”) \(\forall f: A \rightarrow B, g: B \rightarrow C, h: C \rightarrow D\) \[ h \circ (g \circ f) = (h \circ g) \circ f\] The resulting function (morphism) will be \(A \rightarrow D\).

This means, that it is irrelevant which two you “chain” first, just as if one is wielding pieces of a pipe together into a single one.

A chain reaction is a direct manifestation of Causality.

Yes, this is a pipeline of functions (or morphisms). It is typed (a domain and a range must be consistent), so it is not the case that anything can be composed to anything else (as in naive systems).

Obviously, not every implication can be composed with every other.

There is nothing magical about associative property of a composition of arrows.

And if \(A = B = C = D\) and \(f = g = h\) we have a Monoid (just a single arrow and a closure).

So, to form a category all the arrows must be composable (properly chain-able).

Identity

For every “object” (a “dot”) an “identity morphism” (an arrow to itself) is required.

An arrow is a mapping - a particular function with its domain and range. \[\forall f:A \rightarrow B\] \[f \circ id_{A} = f\] \[id_{B} \circ f = f\] For a single “dot” and for Monoids \(A=B\), of course.

Identities are important for “at the ends” of a sequence.

Just as with identity values (for an associative operation) these identity functions (identity arrows) are used in composition - at “both ends” of a chain of composed functions.

Structural patterns

It is not enough to specify (list) every single individual arrow, we have to realize which pattern they form when being composed.

Some patterns are common, and we give them a name.

Each particular structural pattern is its own kind or a structual type.

So, a set of dots, a set of arrows and a pattern (directed graph) the arrows from.

Homomorphisms

Some mappings of structured objects (values) are structure-preserving, some are not.

Obviously, different kind of mappings belong to distinct categories, and here you have categories all the way down.

Monoids

\[(S,\cdot,e)\] \[\forall x,y,z \in S, (x\cdot y)\cdot z = x\cdot (y\cdot z)\] \[\forall x \in S, e\cdot x = x = x\cdot e\] Monoid homomorphism \[f:(S,\cdot,e) \rightarrow (S',\cdot',e')\mid f(e)=e', \forall x,y\in S,f(x\cdot y)= f(x)\cdot' f(y)\] Composition of two homomorphisms yields a homororphism.

So it is a category with only one object: \(Ob_{C} = \{S\}\) and \(Hom_{C} = \{id, \cdot\}\)

By the way, the identity function is a partially applied \(e\) (e.), for example (+0) or (*1) or (++ "")

Isomorphism

\(f: A\rightarrow B\) is an isomorphism \(\iff\) \[\]\[\exists g: B\rightarrow A \mid g\circ f = id_{A} \land f\circ g = id_{B} \]

Complications

\[\forall A,B \in Ob_{C},\exists Hom_{C}(A,B)\] \[Ob_{C}=\{A,B\}, Hom_{C}(A,A)=id_{A}, Hom_{C}(B,B)=id_{B}, Hom_{C}(A,B)=\emptyset, Hom_{C}(B,A)=\emptyset\] No arrows between \(A\) and \(B\), which means they are unrelated. Identities must always be there.