Sunday, February 19, 2017

Monoids: the root of it all


Let's start talking about category theory. We will start from set theory and in the end try to get away from it. The first thing we need to discuss is magma. Basically you have a binary operation on a set and that's all: \(M \times M\rightarrow M\). One problem with magmas is that there is no associativity. Now not all mathematical operations lacking associativity are inherently primitive. Think of Lie algebras: the operation is not associative. However there you have something else: the Jacobi identity. But a pure magma without any additional structure is a rather inert object. The other problem with magmas is the lack of a unit. Add associativity and a unital element and category theory comes alive. 

To link the discussion to physics, nature obeys the structure of a (commutative) monoid: two physical systems can be composed into a larger physical system:
- composition is the binary operation 
- associativity guarantees our ability to reason about physical systems regardless of how we split a physical system into subsystems: quantum mechanics is valid for both an electron or an atom containing an electron
- the unital element is nothingness: composition with nothing leaves the original physical system intact.

In later posts I will show how quantum mechanics is a logical consequence of the commutative monoid above. In other words, quantum mechanics is inescapable and nature is quantum all the way.

Back on monoids, let's fall back on the usual example: composable functions: the image of a function is the domain of the next function. The link with programming is obvious: the output of one computation is plugged in as the input of another computation. As a side note, because of this functional programming is best explained in the language of category theory. When we talk function composition we usually write: \(f \circ g\)  which means \(f(g(x))\). To jump in abstraction and eliminate the nature of the elements considerations, there is an elementary trick to help navigate complex composition chains: call \(\circ\): AFTER like this: \(f~composed~with~g = f\circ g = f~ AFTER~ g\)

Now let's review the usual properties of injectivity and surjectivity:

Injectivity: for any elements \(x, x^{'}\), a function is injective if \(f(x) = f(x^{'}) ~implies~ x=x^{'}\)
Surjectivity: for any \(y\) in the range, there is an \(x\) in the domain such that \(f(x)=y\)

So how can we abstract this away and eliminate the talk about the elements? The corresponding category theory concepts are monic and epic:

Monic: a morphism is monic if for any \(g, h\) \(f\circ g = f\circ h ~implies~g=h\)
Epic: a morphism is epic if for any \(g, h\) \(g\circ f = h\circ f ~implies~g=h\)

Can you prove that if \(f:X\rightarrow Y\) then \(f\) is injective if and only if it is monic and it surjective if and only if it is epic? The proof can be found in many places but it is instructive to try to prove it yourself without looking it up first as this will help you better understand category theory. 

The last point I want to make today is that in category theory we move away from functions into abstract morphisms. The key point of morphisms is that they preserve mathematical structures. As such they can be used to jump between categories of very different nature. This is how category theory is a unifying structure of mathematics where the same patterns of reasoning can be replicated from logic to computer science, to algebraic topology, to quantum mechanics.

To be continued...

No comments:

Post a Comment