Practical abstract algebra for engineers

Kris Brown


(press s for speaker notes, available online here)

11/1/23

About Me

$$

$$

Natural science

• 2015, Bachelors at Dartmouth:
  • Chemical engineering
• 2016, Visiting scholar at EPFL, Switzerland:
  • synthesis of catalysts to extract fuel from waste biomass
• 2016-2021, PhD at Stanford in Chemical Engineering
  • Computational chemistry renewable energy catalysts

Computer science

• 2019-2020, Google: Software engineering intern
• 2020: Research in proving programs are correct

Math + CS + Natural science

• 2022, UF: Postdoc in computational mathematics of scientific modeling
• 2023, Topos Institute: applied category theory and scientific modeling research

My background was first in wet lab chemistry, and I moved into computational science where it seemed like things would be cleaner. However, I soon developed feeling of chaos and helplessness. It seemed like people didn’t trust the results from other research groups or even their own colleagues.

There was lots of collaboration and exchange at the human level, but this broke down whenever anyone tried to do something meaningful with data they did not themselves generate because there is so much context and assumptions implicitly baked into the data and the scripts which generated it. (Even if you generated it, it takes a lot of attention to detail to not misuse it.)

This led to interest in how we represent knowledge formally, so that a machine can make sure that conceptually you are dotting your i’s and crossing your t’s when interpreting some code or data. This involved mathematics and computer science which I started learning in parallel. I now work full time as a researcher the Topos Institute where my job is to develop math and software that helps scientists and engineers communicate their models to each other. Our output right now is in the Julia programming language.

Two kinds of scientific modeling problems

In the course so far, you’ve learned to:

• mathematically model scientific problems
• solve them by hand
• programming analytic and numerical soln’s

Physical system: chemical reaction network

\[ 2 H_2O \rightarrow 2 H_2 + O_2 \] \[ H_2 \leftrightarrow 2 H \]

Mathematical model: ODEs

\[\frac{d[H_2O]}{dt} = -k_1 \cdot [H_2O]^2 + ...\]

\[\frac{d[H_2]}{dt} = 2 k_1 \cdot [H_2O]^2 - k_{2f} [H_2] + ...\]

Computational implementation: Python

from scipy.integrate import solve_ivp 

def python_code_to_solve_ODE(time):
  def yprime(t, species):
    cH2O, cH2, cO2, cH = species
    k1, k2f, k2r = [3e-7, 4e-9, 2e-5]
    f1 = k1 * cH20**2
    f2 = k2f * cH2
    r2 = k2r * cH**2
    return [-2*f1, 2*f1-f2, f1, 2*f2-2*r2]

  solve_ivp(yprime, [0, time], [.1,.4,.3,.5])

On the left, we have our real world situation, which is a chemical reaction network. We start by mathematically modeling it as an ODE. We use math to find analytic solutions or at least understand the format we need in order to use a numerical algorithm like Euler’s method. We then write code which corresponds to our mathematical analysis and plots the solution.

On the right, we have our real world situation, a bar between a hot and cold temperature source. We represent this as a PDE. And so on.

Motivating example: a complex system

def two_reactor(time):
  V1, V2 = 20.0, 30.0 # L
  in_concs = [996, 0.4, 0.05, 0.05] # g/L
  def yprime(t, concs):
    H2O2_1, H2O_1, H_1, ... = concs
    ... # math based on reaction network
  
  solve_ivp(yprime, [0, time], [.1,.4,.3,.5])

Something you might be tasked with as a homework problem is a system with two well-mixed tanks with mass flow in and out of them as well as chemical reactions going on inside. Given some data about the tanks and the initial concentration of the input flow, you might be asked to numerically solve for the concentrations vs time for the two output pipes. Taking the lessons of the course, you’d start writing up some code like this.

Lecture 2 motivating example: system composition

def four_reactor(time):
  V1, V2, V3, V4 = 20.0, 30.0, 20.0, 30.0 # L
  in_concs = [996, 0.4, 0.05, 0.05] # g/L

  def yprime(t, concs):
    # 4 species in four tanks: 1_1, 1_2, 2_1, 2_2
    H2O2_1_1, H2O_1_1, H_1_1, H2O2_1_1, ...
    H2O2_2_2, H2O_2_2, H_2_2, H2O2_2_2 = concs
    # NEW MATH TO BE WORKED OUT  
    # FROM SCRATCH
  
  solve_ivp(yprime, [0, time], [.1,.4,.3,.5])

 
apply_twice = . . . # the wiring diagram

four_reactor = compose(apply_twice, 
                       [two_reactor, 
                        two_reactor])

It would be cruel if, 10 minutes before the homework were due, the professor made an edit to the assignment and said that, actually, the system you need to simulate is this one on the right with four reactors. This is a quite realistic situation outside of the classroom though, whether you’re in academic research or in industry.

But you might realize that in some sense this new problem has the structure on the left, where if you substitute a diagram of the right shape (one input, two outputs) into each of these holes, you should obtain another flow diagram. In fact, if we substitute our earlier problem (which itself had the right shape) into both of these holes, we get the result on the right. So rather than completely re-doing the assignment, what we want is a mathematical formalism that allows us to do this. Some pseudo code on the right shows how one can define the wiring diagram on the left by writing a function in Python syntax. We then want some other code to take the wiring diagram and two chemical flow systems to obtain the composite system.

Lecture 1 motivating problem: computing “sameness”

\[ 2 A + B \rightarrow B + C \] \[ A + D \rightarrow B \]

\[ B \rightarrow C \] \[ 2 C \rightarrow A \]

Two students complete the same lab assignment but get different results.

from scipy.integrate import solve_ivp 

def python_code_to_solve_ODE(time):
  def yprime(t, species):
    cA, cB, cC, cD = species
    fab = cA**2+cB
    fac = cA*cD
    fbc = cB
    fcd = cC**2  
    return [-2*fab - fac + fcd, ...]

  solve_ivp(yprime, [0, time], [.1,.1,.1,.1])

from scipy.integrate import solve_ivp 

def my_python_code_to_solve_ode(t):
  def y_prime(_, specs):
    c1, c2, c3, c4 = specs # corresponds to D, C, B, A
    f1 = c3 # corresponds to bc
    f3 = c1*c4 # corresponds to ac
    f2 = c2*c2 # corresponds to cd
    f4 = c3+c4**2 # corresponds to ab
    return [-f3, ...]

  solve_ivp(y_prime, [0, t], [.1, .1, .1, .1])

This is hard to verify, especially if the code is big.

• variable naming, declaration ordering, multiple valid ways of structuring programs

Different Python versions? Windows vs Mac? We first want to check if they were even modeling the same chemical reaction network:

It’s not obvious whether the two scientific models were the same because code is difficult to analyze algorithmically.

It is hard to write code that takes other code as an input. We cannot simply check whether the source code is exactly the same because there are lots of arbitrary choices, such as the order of declarations or choice of variable names.

Keep in mind this is a VERY restricted kind of problem compared to the ones that engineers typically face. The fact that even this is hard means that the real problems are in practice impossible to solve without some sort of better mathematical tools.

Lecture Outline

Goal: define a mathematical object which can represent a chemical reaction network.

1. Sets and functions between them
2. Graphs and maps between them
3. Petri Nets and maps between them

We do this in three steps.

What is a set?

A set is a collection of things.

Membership notation

\(red \in \{red,blue,green\}\)

\(pink \notin \{red,blue,green\}\)

\(false \in \mathbb{B}\)

\(35 \in \mathbb{N}\)

\(6.02 \times 10^{23} \in \mathbb{R}\)

\(2+3i \notin \mathbb{R}\)

Let’s start with the basic idea of a set. We can think of it as a collection of things. These could be familiar things, like colors, they could be things like the truth values (false denoted as \(\bot\) and true denoted as \(\top\)), and various collections of numbers like the (natural numbers, the reals, the rational numbers) can be thought of as sets.

The epsilon symbol means “is a member of”. We write a slash through it to say “is not a member of”. Some examples of true statements are on the right hand side.

What is a function?

A function is a map between sets.

\(\{red \mapsto \top, green \mapsto \top, blue \mapsto \bot\}\)

\(\{\bullet \mapsto \pi\}\)

What is a function?

A function (or a map between sets, written \(f: A \rightarrow B\)) assigns to each element of set \(A\) an element of set \(B\).

We denote the element that \(f\) sends \(a\) to as \(f(a)\). \(A\) the domain and \(B\) the codomain of \(f\).

We can explicitly write a function as a set of pairs \(\{a_1 \mapsto b_n, a_2 \mapsto b_m, ...\}\).

Some examples of functions:

\(\{red \mapsto \top, green \mapsto \top, blue \mapsto \bot\}\)

\(\{\bullet \mapsto \pi\}\)

Other functions:

• capital of: \(U.S.\ States \rightarrow U.S.\ Cities\)
• +1: \(\mathbb{N}\rightarrow \mathbb{N}\)
• Determinant: \(Matrix^\mathbb{R}\rightarrow \mathbb{R}\)
• Derivative: \(Polynomial \rightarrow Polynomial\) \(\{x^2+1\mapsto 2x, ...\}\)

Sets and functions: comprehension check

Which of the following is a function?

A function (\(f: A \rightarrow B\)) assigns to each element of set \(A\) an element of set \(B\).

Identity functions, composition of functions

The identity function for a set \(X\) sends each \(x \in X\) to itself.

The composition of functions \(f: A\rightarrow B\) and \(g: B \rightarrow C\) is a function \(f ; g: A \rightarrow C\) which sends each \(a \in A\) to \(g(f(a))\).

• Given \((+1): \mathbb{N}\rightarrow \mathbb{N}\) and \((+2): \mathbb{N}\rightarrow \mathbb{N}\)
  • \((+1);(+1) = (+2)\) and \((+1);id_\mathbb{N}= (+1)\)
• Given \(not: \mathbb{B}\rightarrow \mathbb{B}\)
  • \(not; not = id_\mathbb{B}\)
• Given \(stateOf: Cities \rightarrow States\) and \(capitolOf: States \rightarrow Cities\)
  • \(capitalOf; stateOf = id_{States}\)
  • \(stateOf; capitalOf \ne id_{Cities}\)

Isomorphisms between sets

An isomorphism between sets \(A\) and \(B\) is a function \(f: A \rightarrow B\) such that there exists an inverse function \(f^{-1}: B \rightarrow A\) such that \(f;f^{-1}\) and \(f^{-1};f\) are identity functions.

Quick way to check if function is an iso

1. Do two elements of the function domain ever get mapped to the same element of the codomain?
2. Is there anything in the codomain that was not mapped to?

If both answers are “no”, then it’s an isomorphism!

Worked examples

[see whiteboard]

Checking whether various things are functions are not, whether or not things are isomorphisms or not.

What is a graph?

What is a graph?

A graph is something which has the following components:

• a set of edges, \(E\)
• a set of vertices \(V\)
• two functions \(E\rightarrow V\) called src and tgt.

To connect to earlier drawings of sets, we could draw a graph like this:

The graph itself looks like this:

We can draw graphs in two ways.

What is a graph?

A graph is something which has the following components:

• a set of edges, \(E\)
• a set of vertices \(V\)
• two functions \(E\rightarrow V\) called src and tgt.

To connect to earlier drawings of sets, we could draw a graph like this:

The graph itself looks like this:

We can draw graphs in two ways.

Worked examples

[see whiteboard]

Modeling various things as graphs,

1. BART stops + BART segments
2. divisibility relation on the naturals
3. family relationships

Graph example: representing chemical reaction networks

Suppose we have the chemical reaction network:

\[ ab: A \rightarrow B \] \[ ac: A \rightarrow C \] \[ bc: B \rightarrow C \]

How might we represent this with a graph?

Graph mappings

What would you have to do in order to solve that problem?

A graph mapping \(f: G_1 \rightarrow G_2\) is a pair of compatible functions:

• \(f_V: V_1 \rightarrow V_2\)
• \(f_E: E_1 \rightarrow E_2\)

Compatible means \(f_E;src_2 = src_1;f_V\) and \(f_E;tgt_2 = tgt_1;f_V\).

E.g.: because the edge bc was sent to the top edge of the triangle, for \(f_V\) to be compatible, it is required that \(B\) be sent to the top left vertex and \(C\) be sent to the top right.

Worked examples

[see whiteboard]

Examples of graphs and maps which may or may not be valid

Graph isomorphisms

A graph isomorphism is a graph mapping where \(f_V\) and \(f_E\) are isomorphisms.

Why does graph isomorphism matter?

Two students complete the same lab assignment but get different results.

from scipy.integrate import solve_ivp 

def python_code_to_solve_ODE(time):
  def yprime(t, species):
    cA, cB, cC, cD = species
    fab = cA
    fac = cA
    fbc = cB
    fcd = cC  
    return [-fab - fbc, fab - fbc, fac + fbc - fcd, fcd]

  solve_ivp(yprime, [0, time], [.1,.1,.1,.1])

from scipy.integrate import solve_ivp 

def my_python_code_to_solve_ode(t):
  def y_prime(tim, specs):
    c1, c2, c3, c4 = specs # corresponds to D, C, B, A
    f1 = c3 # corresponds to bc
    f3 = c4 # corresponds to ac
    f2 = c2 # corresponds to cd
    f4 = c4 # corresponds to ab
    return [f2, f3 + f1 - f2, f4 - f1, -f4 - f2]

  solve_ivp(y_prime, [0, t], [.1, .1, .1, .1])

This is hard to verify, especially if the code is big.

• variable naming, declaration ordering, multiple valid ways of structuring programs

Solution

If the two students had first defined their models as graphs, then they could answer their question by computing whether or not their graphs are isomorphic.

Different Python versions? Windows vs Mac? We first want to check if they were even modeling the same chemical reaction network:

It’s not obvious whether the two scientific models were the same because code is difficult to analyze algorithmically.

It is hard to write code that takes other code as an input. We cannot simply check whether the source code is exactly the same because there are lots of arbitrary choices, such as the order of declarations or choice of variable names.

WORK THE EXAMPLES IN CODE OUT ON THE BOARD.

What is a Petri net?

Problem with graphs

Chemical reactions contain multiple inputs and outputs.

\[\square: A\rightarrow 2B\]

\[\blacksquare: C+D\rightarrow A\]

What is a Petri net?

Problem with graphs

Chemical reactions contain multiple inputs and outputs.

A Petri net consists of:

• Four sets: Species, Transitions Inputs, and Outputs
• Four functions: \(is: I\rightarrow S\), \(it: I \rightarrow T\), \(os: O\rightarrow S\), \(ot: O \rightarrow T\).

What is a Petri net?

A Petri net consists of:

• Four sets: Species, Transitions Inputs, and Outputs
• Four functions: \(is: I\rightarrow S\), \(it: I \rightarrow T\), \(os: O\rightarrow S\), \(ot: O \rightarrow T\).

E.g. the reaction network: \(\square: A\rightarrow 2B\) and \(\blacksquare: C+D\rightarrow A\).

The Petri net is drawn like this:

I.e. each input has a designated species and transition, and its existence is the assertion that this species in an input to this transition. (Likewise for outputs).

Once again we can draw these in two ways.

Worked examples

[see whiteboard]

Petri nets: Example

Suppose we have the chemical reaction network:

\[ A + B \rightarrow B + C\] \[ A \rightarrow C \]

How might we represent this with a Petri net?

Reminder from last slide:

\(\square: A\rightarrow 2B\)

\(\blacksquare: C+D\rightarrow A\).

Petri nets: maps and isomorphisms

A map of Petri nets \(f: P_1 \rightarrow P_2\) consists of four compatible functions, \(f_S: S_1 \rightarrow S_2,\ f_T: T_1 \rightarrow T_2,\ f_I: I_1 \rightarrow I_2,\ f_O: O_1 \rightarrow O_2\).

• Compatibility: 1.) \(f_I;it_2= it_1;f_T\), 2.) \(f_O;ot_2= ot_1;f_T\), 3.) \(f_I;is_2= is_1;f_S\), 4.) \(f_O;os_2= os_1;f_S\)

A Petri net isomorphism is a Petri net map where all four functions are iso.

Petri nets: maps and isomorphisms

Lecture 1 motivating problem: computing “sameness”

\[ 2 A + B \rightarrow B + C \] \[ A + D \rightarrow B \]

\[ B \rightarrow C \] \[ 2 C \rightarrow A \]

Two students complete the same lab assignment but get different results.

from scipy.integrate import solve_ivp 

def python_code_to_solve_ODE(time):
  def yprime(t, species):
    cA, cB, cC, cD = species
    fab = cA**2+cB
    fac = cA*cD
    fbc = cB
    fcd = cC**2  
    return [-2*fab - fac + fcd, ...]

  solve_ivp(yprime, [0, time], [.1,.1,.1,.1])

from scipy.integrate import solve_ivp 

def my_python_code_to_solve_ode(t):
  def y_prime(_, specs):
    c1, c2, c3, c4 = specs # corresponds to D, C, B, A
    f1 = c3 # corresponds to bc
    f3 = c1*c4 # corresponds to ac
    f2 = c2*c2 # corresponds to cd
    f4 = c3+c4**2 # corresponds to ab
    return [-f3, ...]

  solve_ivp(y_prime, [0, t], [.1, .1, .1, .1])

This is hard to verify, especially if the code is big.

• variable naming, declaration ordering, multiple valid ways of structuring programs

Now we can return to our motivating problem with a solution. Rather than write Python code that simulates a reaction network, the two students should have constructed Petri nets and written a function that simulates a Petri Net. One of the many advantages that comes from this is that it’s straightforward to check whether the two Petri nets are isomorphic.

Lecture 1 Conclusions

• For each of these data structures:
  • maps between them
  • isomorphisms between them

Rxn Net Representation	Advantage
Traditional text-based format	Communication
Code representation	Computation of concentrations over time
Petri nets (drawing)	Visualization
Petri nets (four sets, four functions)	Computation on the network itself

Next lecture:

After this lecture you should be able to go back and forth between the four representations of chemical reaction networks.

You should understand what a set is and how graphs and Petri nets are made up out of sets and functions. You should see how the idea of a function is generalized to a map between graphs and a map between Petri nets, likewise for isomorphisms.

code representation: e.g. when defining yprime for an ODE solver

Algorithmic computation on the network itself: (e.g. checking iso, gluing networks together)

Resources

Applied category theory textbooks

1. Category Theory for the Sciences
2. Seven Sketches in Compositionality

Category theory textbooks

• Emily Rhiel’s Category Theory in Context
• Bill Lawvere’s Conceptual Mathematics

Blogs

1. AlgebraicJulia
2. Math3ma
3. Graphical Linear Algebra
4. Kittenlab

Notes

Practical abstract algebra for engineers: Lecture 2

Lecture 1 Review: sets

A function \(f: A \rightarrow B\) assigns to each element of set \(A\) an element of set \(B\).

An isomorphism between sets \(A\) and \(B\) is a function \(f: A \rightarrow B\) such that there exists an inverse function \(f^{-1}: B \rightarrow A\) such that \(f;f^{-1}\) and \(f^{-1};f\) are identity functions.

We started last time with the idea the sets are collections of things. The basic relationship between two sets is a function, which takes everything in the domain, \(A\), and assigns it an element of the codomain, \(B\).

A special kind of function is an isomorphism which has an inverse. In practice, this means the function doesn’t squash anything together and it hits everything in the codomain. This is only possible when the domain and codomain have the same number of elements.

Lecture 1 Review: graphs

A graph has a set of edges, \(E\), a set of vertices \(V\), and two functions \(E\rightarrow V\) called src and tgt.

The graph on the left is visualized like this:

A graph mapping \(f: G_1 \rightarrow G_2\) is a pair of compatible functions \(f_V: V_1 \rightarrow V_2\) and \(f_E: E_1 \rightarrow E_2\). (Compatible means \(f_E;src_2 = src_1;f_V\) and \(f_E;tgt_2 = tgt_1;f_V\))

[On the board, take the first graph map and work out what is \(E_1, E_2, f_V\) + show compatibility conditions hold — etc.]

We used sets and functions to define graphs, which can be thought of as a pair of sets and a pair of functions from the edge set to the vertex set. It can be a pain to visualize it that way, so we instead draw the edges as beginning at their source vertex and ending at their target vertex.

Just like functions between sets, we can consider mappings between graphs. This is a pair of functions which sends the vertices of the domain graph to the vertices of the codomain graph, and edges of the domain graph to edges of the codomain graph. This compatilibity constraint basically says that you can’t chop up your graph when sending it along a graph mapping: if you send an edge somewhere, then the source and target must be sent to the source and target of that edge in the codomain.

We also have a notion of graph isomorphism which can either be thought of as a graph map with an inverse or a graph map in which the two component functions are inverses.

Lecture 1 Review: Petri nets

A Petri net consists of:

• Four sets: Species, Transitions Inputs, and Outputs
• Four functions: \(is: I\rightarrow S\), \(it: I \rightarrow T\), \(os: O\rightarrow S\), \(ot: O \rightarrow T\).

A map of Petri nets \(f: P_1 \rightarrow P_2\) consists of four compatible functions for \(S\), \(T\), \(I\), and \(O\).

Petri nets were a variant of graphs which allowed us to talk about edges which have multiple inputs and multiple outputs. We represent these edges (which we call transitions) as squares. It turns out this is just the right thing we need to represent chemical reaction networks, where the transitions are reactions.

Very similar to graphs, we can have maps between these things which are functions for each of the component sets, which likewise have to be compatible (\(f_I;it_1= it_2;f_T\), likewise for \(is, os, ot\)). We also have a natural notion of isomorphism between these things. The main motivation of what we learned last lecture was that we care about whether two chemical reaction networks are equivalent, but in practice this is hard to tell when we represent the network in software. This Petri net representation is however a good representation for answering that question.

We’ll show how this perspective of sets and functions allows us to answer other questions today.

Motivating problem

def rxn_network_1(t):
  def yprime(t, species):
    cH2O, cH, cOH = species
    k1, k2 = [0.02, 0.01]
    f1 = k1 * cH20
    f2 = k2 * cH * cOH
    return [-f1,f1-f2,f1-f2]

  solve_ivp(yprime, [0, t], 
            [.1,.4,.3])

def rxn_network_2(t):
  def yprime(t, sp):
    cH2O2, cH2, cWater = sp
    k1, k2 = [0.01, 0.3]
    f1 = k1 * cH2O2 * cH2
    f2 = k2 * cWater
    return [-f2,-f2,2*f2-f1]

  solve_ivp(yprime, [0, t], 
            [.5,.5,.1])

def combined_rxn_network(t): # tedious to construct
  def yprime(t, species):
    cH2O, cOH, cH, cH2O2, cH2 = species
    k1, k2, k3 = [0.02, 0.01, 0.3]
    f1 = k1 * cH20
    f2 = k2 * cH * cOH
    f3 = k3 * cH2O2 * cH2
    return [f3-f1, f1-f2, f1-f2, -f3, -f3]

  solve_ivp(yprime, [0, t], [.1,.4,.3])

# Preferred alternative 
overlap = Overlap(rxn_network1, rxn_network2, ...)
combined_rxn_network = glue(overlap)

Motivating problem

Gluing together graphs

Gluing together Petri nets

Gluing together dynamical systems

Reinvent the wheel each time? Or general solution possible?

Generalizability

Beyond being precise, we want to be generalizable.

Ideally there is just one definition that works for:

• sets
• graphs
• Petri nets
• matrices
• electrical circuits
• heat flow problems
• etc.

We will do this with the technique of universal properties.

For any specific context, we can work out (or guess with some confidence) what the ‘right’ notion of these phrases mean. But a general solution requires

Two intuitions we will make precise today

Part 1. The notion of being empty

Part 2. Placing things side-by-side

Abstract characterization of empty and placing things side-by-side that works in all sorts of contexts.

Part 1: Emptiness for sets

For any set \(X\), there exists exactly one function \(\{\} \rightarrow X\).

• This is a function because it assigns a value of \(X\) for every element of \(\{\}\).

• This function is unique for each \(X\) because there are no other ways to make this function.

• \(\{\}\) is an initial object because this is true for any set \(X\).

A set with even a single element doesn’t have this property:

It’s important that we are NOT interested in defining the empty set as the set with no elements, because that definition would not generalize to other contexts.

Emptiness for graphs

What is special about defining ‘emptiness’ via the diagram \(0 \rightarrow X\) is that it can be interpreted in many contexts, not just sets and functions.

Initial object for graphs

Is there a graph which plays the role of “initial object” in the context of graphs and graph mappings?

Initial object for Petri nets

When \(E\) and \(V\) are empty, the resulting graph is an initial object.

When \(S\), \(T\), \(I\), and \(O\) are empty, the resulting Petri net is an initial object.

Emptiness in general characterized by initial object

Universal property of being an initial object:

We can think of other contexts than the ones discussed so far:

• Consider natural numbers, \(\mathbb{N}= \{0, 1, 2, ...\}\), and an arrow \(n \rightarrow m\) whenever \(n \leq m\).
• Consider natural numbers, \(\mathbb{N}\), and an arrow \(n \rightarrow m\) whenever \(m\) is divisible by \(n\).

Not every context has an initial object

Consider the integers, \(\mathbb{Z}\), (…-2, -1, 0, 1, 2, …) and an arrow \(n \rightarrow m\) whenever \(n \leq m\).

Worked examples

[See whiteboard]

Part 2: Placing sets side-by-side

What does it mean to place two sets side-by-side?

The disjoint union of two sets \(A\) and \(B\), written \(A + B\) is a set which contains the elements of both \(A\) and \(B\) along with a label to distinguish whether the element came from \(A\) or from \(B\).

Sets are not allowed to have duplicates, so the label prevents collisions between the overlapping items of \(A\) and \(B\).

Property of disjoint union

Fun fact

We can encode any pair of functions \(A \rightarrow X\) and \(B \rightarrow X\), as a function \(A+B\rightarrow X\).

Let’s do a similar trick. Rather than thinking of this as just a fun fact of the disjoint union, what if we considered it to be essential to the idea of placing things side by side? Let’s test that intuition in some other contexts.

Worked examples

[See whiteboard]

Coproduct as universal property

Disjoint union only makes sense for sets. We want to describe it purely in terms of abstract points and arrows in order to generalize to other contexts.

Can you prove that 1+1 is not equal to 1?

Coproduct for graphs

This is sufficient to define putting graphs side-by-side.

Coproduct for Petri nets and beyond

These universal properties can surprise you by showing how lots of things you thought were completely unrelated actually share the same structure.

Fun facts

• In the context of natural numbers with \(n \leq m\), coproduct is maximum.
• In the context of natural numbers with arrows \(n \rightarrow m\) whenver \(n\) is divisible by \(m\), coproduct is greatest common denominator.
• In the context of linear algebra, the coproduct gives us block matrices \(\begin{pmatrix}A & 0 \\ 0 & B \end{pmatrix}\)

Worked examples

[See whiteboard]

(BONUS MATERIAL) Pushouts: a notion of gluing

Universal property of a pushout:

Two simple definitions yield all of the specifics of these lectures as special cases:

Lecture 1&2 Conclusions

• For each of these data structures:
  • maps between them
  • isomorphisms between them

It’s easy to write code which manipulates sets/graphs/Petri nets.

It’s hard to write code which manipulates other pieces of code.

Universal properties allow us to make very general definitions (and write flexible code) which work in many contexts.

• sameness (generalizing the notion of isomorphism)
• emptiness (generalizing the empty set)
• side-by-side placement (generalizing the disjoint union)

The field of category theory strives to do this with all concepts we care about, including gluing, multiplication, optimization, substitution, and recursion.

To not be scary, I’ve been talking about abstract “contexts” of points and maps, but that is precisely what a category is!

Resources

Applied category theory textbooks

1. Category Theory for the Sciences
2. Seven Sketches in Compositionality

Category theory textbooks

• Emily Rhiel’s Category Theory in Context
• Bill Lawvere’s Conceptual Mathematics

Blogs

1. AlgebraicJulia
2. Math3ma
3. Graphical Linear Algebra
4. Kittenlab

Notes

(BONUS MATERIAL) Coproduct for graphs

The coproduct of graphs \(G_1 + G_2\) can also be described as the following graph:

• \(E = E_1 + E_2\)
• \(V = V_1 + V_2\)
• \(src\) and \(tgt\) functions \(E_1+E_2 \rightarrow V_1+V_2\) (derived from the original graphs)

How to say more precisely what functions \(src\) and \(tgt\) are?

(BONUS MATERIAL) Coproduct for graphs

The coproduct of graphs \(G_1 + G_2\) can also be described as the following graph:

• \(E = E_1 + E_2\)
• \(V = V_1 + V_2\)
• \(src\) and \(tgt\) functions \(E_1+E_2 \rightarrow V_1+V_2\) (derived from the original graphs)

How to say more precisely what functions \(src\) and \(tgt\) are?

We don’t have an arbitrary choice what to make src and tgt for the coproduct graph. We can show that src (and likewise for tgt) comes from the universal property of the disjoint union of the edge sets. The result is a src/tgt function which matches our intuitions of side-by-side placement.