A folk theorem on algebras

Status: Draft
Confidence: Likely

Math in this page not rendering? See the fix

Mathematicians concern themselves with a remarkably small number of algebraic structures (or theories if you’re a model theorist), a couple dozen in all. Why is this?

If we look at groups or vector spaces or lattices, they all have the form of a set of elements with binary or trinary relations among them. A relation here is a list of tuples of sets of elements. A group, viewed this way, is a set with two relations. One is a binary relation that relates each element to its inverse. The other is a trinary relation that associates two elements with their product. The Klein four group (with elements $e$, $a$, $b$, and $c$) has the relations

and

where we have one row for each entry of the group multiplication table.

We could also have much smaller relations. Imagine the same set with a single relation

and no more. How is this different from the relations for the group above? The group’s relations are maximal in a sense. Every pair of elements is represented in the first two slots of the multiplication relation. Every element is represented in the first slot of the inverse relation. The relations are transitive. These relations are very structured.

The single, small relation in our second example might be useful for describing a particular situation, but there isn’t much interest in it. It’s not going to connect to many other things, nor is there anything that’s going to emerge from studying it that isn’t evident in the first minute or so. It’s a poor substrate for a physicist or chemist trying to construct general theories, and isn’t going to yield much to a mathematician’s interest.

So the algebras that mathematicians use, either because they have arisen in the sciences and needed examination or from following threads of existing mathematics, are those that are maximally structured. There’s probably some way of making this precise by defining some kind of measure of deviation from maximal structuring of the relations and then looking at structures with zero deviation. That viewpoint, though, suggests an analogy.

In linear algebra, say you choose a matrix at random? (Assume here uniformly distributed components of the matrix.) What is the probability that a matrix will not be invertible?

For a matrix to not be invertible, its determinant must be 0, that is for a matrix $A$, $\textrm{det}(A) = 0$. That is a polynomial in the components of $A$, so it defines a $n-1$ dimensional subspace in the $n$ dimensional space of matrices. The volume of that space is 0, just like the volume of a plane in a 3D space is zero. The probability of choosing a matrix in a subspace is proportional to the volume of the subspace, so the probability of choosing a non-invertible matrix at random is zero.

Likewise, our maximally structured algebras form a lower dimensional subspace in the space of possible algebras. Mathematicians trace out the spidery path of this subspace and the few dozen or so objects of interest.

I have observed that the objects of interest fall on one of three paths out from a center point. The center point is a set with no relations on it (not very interesting, but the trivial case). From there we have:

Number-like structures

Magmas, monoids, semigroups, groups, rings, fields, with digressions through tropical rings on one side and vector spaces and modules on another. These were first identified to talk about numbers and things that are more or less like numbers.

Subset-like structures

Preorders, partial orders, semilattices, lattices, directed acyclic graphs, chain complete partial orders, and all the other variations on containment and graphs. These were initially inspired by the structure of subsets of a set and problems like the bridges of Königsberg.

Program-like structures

Monoids again, but then diverging through functors, natural transformations, applicative functors, monads, and arrows. These were derived from similarities among mappings between spaces (natural transformations) and fragments of imperative programs (monads).

So what about all the other, not so regular ones? Mathematicians don’t care about them much, but it turns out that software engineers do. When you are designing software, you don’t need a general structure. You need guard rails around your thinking to help handle the complexity of writing programs.

For example, if you have three functions f : Integer -> String, g : String -> [String] and h: [String] -> Float, there is only one way that these can be composed. The types forbid anything else. At a larger level, only permitting requests to a web server to communicate by how they read from and write to a database, or making views in a GUI only be functions of the model and not of each other is strictly limiting the algebra involved, and are necessary to successful programming.

From this point of view, Peter Naur’s “Programming as theory building” is actually talking about theories in the model theoretic sense of formal languages with properties and models that have those properties and so are modelled by the theory, and programmers, to work effectively, need those theories.

« Home