From Category Theory for Programmers - Series 1

Lecture 3

• Redefine descriptions about sets in terms of morphisms, and then ask, how does this generalize to categories?
• Can you have a category with no objects?
• Well, if there are no objects, there are no arrows.
• With no arrows, requirements for identity are technically met
• Requirements for composition are technically met
• So it's a valid category
• Not very interesting by itself, but important concept, similar to zero, null set
• In the category of categories, it will be an initial object
• Category with one object
• Has to have at least one arrow (the identity)
• Not much you can do with this category either by itself, but it's still useful
• "A terminal object" in the category of categories
• Can look at categories with more objects
• Helpful to draw a graph, but not every graph is a category
• Identity arrows are required
• Composition arrows are required
• Can be made into a category by adding arrows
• Just keep adding arrows until requirements are met
• Called "free" category -- adding arrows without restriction
• Orders: a category where arrows are relations, not functions
• A useful relation is "⩽" (less than or equal)
• a → b
• a less than or equal to b
• or a comes before b
• Useful for sorting
• A pre-order is something that satisfies the minimum of conditions (for sorting); here, ⩽ is a pre-order
• Kind of binary condition, either there is an arrow between two objects or there is not
• Always have zero or one arrow between objects
• Which is different from total order, which can have arrows both directions
• Composable
• Associative
• Reflexive -- every object is ⩽ itself
• This is called a thin category
• Every thin category corresponds to a pre-order
• And every pre-order corresponds to a thin category
• The set of arrows between any two objects has a name, called a "hom-set"
• Hom-set in a category 𝑪 between two objects a and b is written 𝑪(a,b)
• A thin category is one in which every hom-set is an empty set or contains one element
• Partial order is same as directed a-cyclic graph
• Some objects are not comparable
• Total order contains arrows between any two objects (you can compare any two objects)
• In thin category, every arrow is a monomorphism and an epimorphism
• Technically, because there aren't multiple arrows to check
• Not necessarily invertible
• A thick category would be one where hom-sets contain more than one element (multiple arrows)
• Back to one object category
• Can have more arrows than just the id
• All arrows are composable (all through the only object)
• This is called a monoid (mono=single)
• Any category with single object is a monoid
• What does a monoid look like in set theory
• Natural numbers with multiplication form a monoid
• Is associative
• (a ⨯ b) ⨯ c = (a ⨯ b) ⨯ c
• Has an identity element ("unit" in category)
• ∃ e ∀ a . e ⨯ a = a ⨯ e = a
• Natural numbers with addition form a monoid
• String concatenation
• not symmetric, still a monoid
• Back to categories, consider the single object category
• Call it category 𝑴, with single object m
• There's only one hom-set: 𝑴(m,m)
• The hom-set defines a set
• This is the same as the example above
• m is the set of natural numbers and an arrow is a multiplication
• Has the identity (times 1)
• Composable function corresponds to strongly typed system
• A monoid means any two functions are composable
• Weak typing is "inside" strong typing

(part 2)

• Lets define a relation, inclusion
• Being a subset of another set is a relation
• Does it have identity?
• Every set is a subset of itself
• Is it composable?
• It seems composable: a ⊆ b ⊆ c ⇒ a ⊆ c
• Associative
• So this is a pre-order
• Also a partial order because there are no loops
• But it's not a total order
• This is a category (side note: shows up in topology)

(programming example with c++)

• Function with embellishments
• It's called Kleisli category
• Arrow is a "monad"
• Monad is a way of composing special types of functions

• The arrows in a single object category are not necessarily functions.
• For instance, natural numbers with addition
• Composition is the addition part
• But each arrow is simply a natural number
• 2 ∘ 3 gives 5
• The restriction of "identity" and "associative" is specific to sets in category theory
• Actual definition of a monoid is a bit more generic
• https://math.stackexchange.com/questions/2110359/a-monoid-is-m-or-m-%CE%BC-%CE%B7?rq=1
• https://en.wikipedia.org/wiki/Monoid_(category_theory)

Translated the c++ example to c#

public class PairResult<T>
{
    public T Value { get; set; }
    public string Note { get; set; }
}

public PairResult<int> Increment(int x)
{
    return new PairResult<int>() { Value = x + 1, Note = "Increment;" };
}

public PairResult<int> Add3(int x)
{
    return new PairResult<int>() { Value = x + 3, Note = "Add3;" };
}

public Func<int, PairResult<int>> Compose(Func<int, PairResult<int>> first, Func<int, PairResult<int>> second)
{
    Func<int, PairResult<int>> composed = x => { 
    
        var pair1 = first(x);
        var pair2 = second(pair1.Value);
        
        return new PairResult<int>() { Value = pair2.Value, Note = pair1.Note + pair2.Note };
    };
    
    return composed;
}

// C# interactive :

> var inc2 = Compose(Increment, Increment);
> inc2(1)
Submission#0.PairResult<int> { Note="Increment;Increment;", Value=3 }

> var c = Compose(Increment, Add3);
> c(1)
Submission#0.PairResult<int> { Note="Increment;Add3;", Value=5 }

> var d = Compose(inc2, c);
> d(1)
Submission#0.PairResult<int> { Note="Increment;Increment;Increment;Add3;", Value=7 }