January 15, 2023

Total Freedom

Posted by John Baez

Wow! I just learned an objective reason why sets and vector spaces are special!

Of course we all know math relies heavily on set theory and linear algebra. And if you know category theory, you can say various things about why the categories $\mathsf{Set}$ and $\mathsf{Vect}$ are particularly convenient frameworks for calculation. But I’d never known a theorem that picks out these categories, and just a few others.

Briefly: these are categories of algebraic gadgets where all the objects are free!

We could call these ‘totally free’ algebraic gadgets.

By ‘algebraic gadgets’ I mean sets equipped with some $n$-ary operations obeying equational laws. Examples include monoids, groups, rings, modules over a fixed ring, Lie algebras over a fixed field, etc.

There are three famous formalisms for studying algebraic gadgets. They all describe the same kinds of algebraic gadgets, so which you use is largely a matter of convenience:

Given any variety, or Lawvere theory, or finitary monad on the category of sets, we get a category $\mathsf{C}$ of algebraic gadgets together with a functor

$R : \mathsf{C} \to \mathsf{Set}$

sending each gadget of this kind to its underlying set. And this functor will always have a left adjoint

$L : \mathsf{Set} \to \mathsf{C}$

sending any set to the free gadget on that set.

Steven Givant and later Kearnes, Kiss and Szendrei completely classified the varieties for which every object in $\mathsf{C}$ is isomorphic to one of the form $L(S)$ for some set $S$. We could call these the totally free varieties:

• sets
• pointed sets
• modules over some fixed division ring $F$
• affine spaces over some fixed division ring $F$.

That’s all!

A commutative division ring is called a ‘field’, and a module over a field is called a ‘vector space’. The quaternions are a nice example of a noncommutative division ring. Anyone who has studied modules over the quaternions knows that these act a lot like vector spaces, in part because they’re all free.

An affine space over a field is, poetically speaking, just a vector space that has forgotten its origin. If you pick any point in the affine space and call it $0$, you get a vector space. You can’t take linear combinations of points in an affine space, just ‘affine combinations’. These are $n$-ary operations that obey a bunch of equational laws that I’m too lazy to list. But when your affine space comes from a vector space in the way I just described, these affine combinations can be written as linear combinations:

$a_1 v_1 + \cdots + a_n v_n$

where the coefficients sum to one: $a_1 + \cdots + a_n = 1$. So, for example, if you have two points $v_1, v_2$ in an affine space you can get all the points on the line through them by taking affine combinations $av_1 + (1-a)v_2$.

We can also do all this stuff with a division ring replacing a field! In fact, ‘field’ used to mean ‘division ring’, and the noncommutative ones were called ‘skew fields’.

Now, you’ll notice from what I said that a module over a division ring $F$ is just the same as a pointed affine space over $F$ — that is, an affine space over $F$ equipped with a chosen point. Similarly a pointed set is just a set with a chosen point. So we can list the totally free varieties in a more enlightening way:

• sets
• pointed sets
• affine spaces over a division ring
• pointed modules over a division ring.

And this should remind us of the ‘field with one element’. We don’t know what the field with one element is, exactly, but we know that the modules of this mythical beast should be pointed sets. There are lots of reasons for that. Here we see another: it would unify the above classification!

Suppose we could go back in time, redefine ‘field’ to include division rings and also one extra thing: the ‘field with one element’, $F_{\mathrm{un}}$. We wouldn’t even need to know what $F_{\mathrm{un}}$ is, just that that affine spaces over it are sets. Then this would be the complete classification of totally free varieties:

• affine spaces over a field
• vector spaces over a field.

That would be nice.

But of course, it’s sort of trivial that every set is the free set on some set. In this case our category $\mathsf{C}$ of algebraic gadgets is just $\mathsf{Set}$ itself, and $R : \mathsf{Set} \to \mathsf{Set}$ is the identity functor, so $L: \mathsf{Set} \to \mathsf{Set}$ and the monad $T = R L$ are also the identity.

This raises the question of ‘relativising’ the ideas I’ve been talking about, by replacing $\mathsf{Set}$ with some other category $\mathsf{X}$.

Puzzle. Give me as many interesting examples as you can of categories $\mathsf{X}$ and monads $T: \mathsf{X} \to \mathsf{X}$ such that every $T$-algebra is free.

Of course we can always take $T$ to be the identity, but that’s boring.

A very interesting small step would be to stick with $\mathsf{X} = \mathsf{Set}$ but drop the requirement that $T$ be finitary. This lets us talk about algebraic gadgets with infinitary operations. Are there any interesting ones where every $T$-algebra is free?

But I’m more interested in other categories $\mathsf{X}$. For example, what if $\mathsf{X}$ itself is $\mathsf{Vect}$, or the category of algebras of some other finitary monad on $\mathsf{Set}$?

Posted at January 15, 2023 5:59 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3440

Re: Total Freedom

On Mathstodon Oscar Cunningham wrote:

1. If X is a poset then monads are ‘closure operations’ and the algebras are the fixed points which are therefore free.

2. If X is the delooping of a monoid M, then provided one of the following conditions holds we have that any monad on X is given by conjugation by an invertible element of M, and the only algebra is free.

a) M is commutative

b) M is a group

c) M is finite

Posted by: John Baez on January 15, 2023 11:22 PM | Permalink | Reply to this

Re: Total Freedom

That every vector space is free is equivalent to the axiom of choice. So for somebody like me who doesn’t assume the axiom of choice in the foundations there are only two totally free algebraic gadgets - sets and pointed sets.

Re: Total Freedom

Posted by: John Baez on January 16, 2023 1:13 AM | Permalink | Reply to this

Re: Total Freedom

Maybe infinity is to blame. Everything John says should be fine constructively for finite-dimensional vector spaces. Contrapositively, if we consider the Löwenheim–Skolem theorem, then I think that we cannot predict the cardinality of our freely-generated sets when they are infinite.

Posted by: Corbin on January 16, 2023 8:05 AM | Permalink | Reply to this

Re: Total Freedom

AC is a horseshoe-phenomenon though: it is acceptable either because you are very non-constructive or because you are very constructive. In the latter case it becomes a theorem, even! This happens, for instance, in Martin-Lof type theory (MLTT).

Intuitively, in a constructive setting, when you have a family of types and you know they are inhabited it is because you actually have constructed an element for each of the types. Then fashioning this data into a choice function is not hard.

So a constructive-leaning mathematician, I’m inclined to accept AC.

Posted by: Matteo Capucci on January 17, 2023 12:02 PM | Permalink | Reply to this

Re: Total Freedom

A constructive-leaning mathematician who really ought to read chapter 3 of the HoTT book! $\Sigma$ is fundamentally not the same thing as $\exists$: the “axiom of choice” you are talking about doesn’t imply LEM, and it can’t prove epimorphisms in Sets split.

That latter one is because of a more fundamental impediment: you can’t show epimorphisms are surjective when you mistake $\Sigma$ for $\exists$. You can’t define the image of a function, either: The “$\Sigma$-image” of $f$ is equivalent to $f$’s domain.

Posted by: Amélia Liao on January 17, 2023 3:39 PM | Permalink | Reply to this

Re: Total Freedom

AC is a horseshoe-phenomenon though: it is acceptable either because you are very non-constructive or because you are very constructive. In the latter case it becomes a theorem, even! This happens, for instance, in Martin-Lof type theory (MLTT).

I am well aware of Martin-Löf type theory, having worked in that subject for the past two years.

There is a big difference between the axiom of choice, which says that a family of inhabited types (i.e. whose propositional truncation comes with an element) is inhabited, and what is sometimes known as the “type-theoretic axiom of choice”, which says that a family of types with the structure of an element itself has an element. The former is the axiom of choice as traditionally known in set theory, while the latter is true constructively in any type theory with dependent products, and is simply the identity function on a dependent product type.

Re: Total Freedom

There is plenty of confusion amongst an older generation of type theorists of the distinction between a type $A$ which is pointed, i.e. with an element $a:A$, and a type $A$ which is inhabited, i.e. whose propositional truncation has an element $a:\vert A \vert$. This confusion results in them using terminology which already has a specific meaning elsewhere in the mathematics community for something totally different, such as using the term “axiom of choice” for the identity function on dependent product types or for the property of distributivity of dependent product types over dependent sum types; where the actual axiom of choice would put propositional truncations around the dependent sum types or in other suitable locations.

Re: Total Freedom

I’m pretty sure that Matteo is too young to be lumped into “an older generation of type theorists”!

As far as the discussion is concerned, if I’ve understood correctly the “type theoretic axiom of choice” allows us to conclude that ‘for every vector space V there exists a basis of V’ (but it doesn’t provide a witness). If I’m allowed to be non-predicative, I can take the dependent sum over [(linearly independent) subsets of the underlying set of V] of [two-sided inverses of the corresponding map from the free vector space on the subset to V] and conclude that the resulting type is inhabited. So as usual in constructive settings, we’re as close as we can be to every vector space being free, we just might not be able to explicitly “find” the isomorphism without the axiom of choice. This might reveal limitations on my understanding of type theory, but I think a consequence of the above is that for all functional purposes every vector space is free in MLTT, since one cannot prove the non-existence of an isomorphism with a free vector space (there is no construction within the type theory that distinguishes a given vector space from all free ones). That said, I wonder if there is a model of MLTT carrying pathological vector spaces – vector spaces having properties (not captured by the type theory) which distinguish them from free vector spaces.

Posted by: Morgan Rogers on January 24, 2023 12:10 PM | Permalink | Reply to this

Re: Total Freedom

I apologize for how I tend to be fast and loose with these things, and as you and Liao pointed out, there’s more nuance in this. And at no point I meant to imply Birchfield wasn’t familiar with MLTT.

I’m also aware of the modern distinction between propositional types and types, as well as the distinction between pointedness and inhabitation.

Translating the classical axiom of choice with truncation is indeed more faithful to its literal meaning (though this might not be as obvious as you make it seem). If I’m doing mathematics, however, I might choose to not shoot myself in the foot by having explicit points and then forgetting them. So probably I’m arguing for a Bishop-style constructivism in which existential statements are always deemed effective.

In a sense, translating between classical and constructive mathematics is like translating between languages: a literal translation might not always be the best choice!

Posted by: Matteo Capucci on January 25, 2023 2:12 PM | Permalink | Reply to this

Re: Total Freedom

Give me as many interesting examples as you can of categories $X$ and monads $T: X \to X$ such that every $T$-algebra is free.

A general class of examples: every algebra for an idempotent monad is free. (A monad $T$ is said to be idempotent if its multiplication map $T^2 \to T$ is invertible.) This includes Oscar Cunningham’s example of monads on a poset.

Idempotent monads come from reflective subcategories. That is, if $Y$ is a full subcategory of a category $X$ and the inclusion $Y \hookrightarrow X$ has a left adjoint, then the resulting monad $T$ on $X$ is idempotent. Hence every $T$-algebra is free.

For example, $Ab$ is reflective in $Grp$, giving the abelianization monad $T$ on $Grp$. The algebras for the abelianization monad are the abelian groups, and every abelian group is the free $T$-algebra on itself.

That’s all very trivial. Of the four monads on $Set$ that you list in your post, only the identity monad is idempotent. It’s the non-idempotent monads that make this story interesting.

Posted by: Tom Leinster on January 16, 2023 2:18 AM | Permalink | Reply to this

Re: Total Freedom

A funny example of this is the monad on $\mathbf{Top}$ that sends each space to the indiscrete topology on the same points. Its algebras are sets, so we’ve ended up back where we started!

Posted by: Oscar Cunningham on January 16, 2023 5:53 AM | Permalink | Reply to this

Re: Total Freedom

The word “nontrivial” has to be uttered somewhere, otherwise your list of four has two missing:

• sets with exactly one element
• sets with at most one element.

The first category is the category of algebras for the monad with constant value $1$, or equivalently, the theory consisting of a single constant $c$ and a single equation $x = c$.

The second category is the category of algebras for the monad $T$ defined by

$T(A) = \begin{cases} 1 &\text{if } A \neq \varnothing \\ \varnothing &\text{if } A = \varnothing, \end{cases}$

or equivalently, the theory consisting of no operations and a single equation $x = y$.

Interestingly, the first is the pointed version of the second. So even adding these trivial examples to the list, everything falls into unpointed/pointed pairs.

Kearnes, Kiss and Szendrei do say “nontrivial” somewhere in their paper.

Posted by: Tom Leinster on January 16, 2023 2:24 AM | Permalink | Reply to this

Re: Total Freedom

Wow, thanks! I didn’t notice that, since I only skimmed their paper trying to see how division rings got into the game. (It led to references to earlier work written in the tradition of universal algebra, which makes me feel the finitary monad / Lawvere theory crowd has some catching up to do, or at least I do!)

So what are these things? Vector spaces and affine spaces over the field with no elements?

Posted by: John Baez on January 16, 2023 4:53 PM | Permalink | Reply to this

Re: Total Freedom

There was an idea cited here that

sets are the modules of the “field without elements”

and pointed sets are $\mathbb{F}_1$-modules.

Posted by: David Corfield on January 17, 2023 7:04 PM | Permalink | Reply to this

Re: Total Freedom

So what are these things? Vector spaces and affine spaces over the field with no elements?

I wondered the same. For some reason, the possibility of the field with $-1$ element also flashed across my mind. It was probably just a misfiring synapse.

Here’s something precise. Let “ring” mean “ring with identity”. Then the one-element ring $1$ is strictly terminal, in the sense that any map out of $1$ is an isomorphism. In particular, whenever $A$ is a $1$-module, the ring homomorphism $1 \to End_{Ab}(A)$ that implements scalar multiplication must be an isomorphism. This forces $A = \{0\}$.

Conclusion: the one and only module over the ring with one element is the one-element module.

That feels kind of relevant, but I’m not sure how.

Posted by: Tom Leinster on January 17, 2023 12:05 AM | Permalink | Reply to this

Re: Total Freedom

Reversing the puzzle, one could ask whether the monads from the list you gave always have free algebras when they make sense. In particular, any topos has all of the structure needed to talk about division rings and their modules, not to mention pointed objects; is it true that these are all free in this setting? I’ll answer one of those questions.

Proposition: Let $\mathcal{T}$ be a topos. The ‘pointed object monad’ $X \mapsto X+1$ has all algebras free if and only if $\mathcal{T}$ is Boolean (every subobject is complemented).

Proof: In the forward direction, given a subobject $A \hookrightarrow B$ in $\mathcal{T}$, consider its cokernel, the pushout along the unique map to the terminal object $A \to 1$; let’s call the representing object $K$. By construction, $1 \to K$ is a pointed object, and since every morphism from $1$ is monic, this is a complemented subobject; call the complement $K' \hookrightarrow K$. Pulling back along the morphism $B \to K$, we obtain a complement of $A \hookrightarrow B$ thanks to the fact that toposes are extensive categories.

Conversely, if $\mathcal{T}$ is Boolean and $1 \to K$ is a pointed object, then we again have a complement $K' \hookrightarrow K$ and $K \cong K' + 1$ is free. $\square$

Looking back at Madeleine Birchfield’s comment earlier, a constructivist can’t even take for granted that pointed sets are free if they reject the law of excluded middle!

Posted by: Morgan Rogers on January 24, 2023 12:37 PM | Permalink | Reply to this

Post a New Comment