Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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 Set\mathsf{Set} and Vect\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 nn-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 C\mathsf{C} of algebraic gadgets together with a functor

R:CSet 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:SetC 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 C\mathsf{C} is isomorphic to one of the form L(S)L(S) for some set SS. We could call these the totally free varieties:

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

That’s all! (No, not quite.)

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 00, you get a vector space. You can’t take linear combinations of points in an affine space, just ‘affine combinations’. These are nn-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 1v 1++a nv n a_1 v_1 + \cdots + a_n v_n

where the coefficients sum to one: a 1++a n=1a_1 + \cdots + a_n = 1. So, for example, if you have two points v 1,v 2v_1, v_2 in an affine space you can get all the points on the line through them by taking affine combinations av 1+(1a)v 2av_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 FF is just the same as a pointed affine space over FF — that is, an affine space over FF 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 affine spaces 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 unF_{\mathrm{un}}. We wouldn’t even need to know what F unF_{\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 C\mathsf{C} of algebraic gadgets is just Set\mathsf{Set} itself, and R:SetSetR : \mathsf{Set} \to \mathsf{Set} is the identity functor, so L:SetSetL: \mathsf{Set} \to \mathsf{Set} and the monad T=RLT = R L are also the identity.

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

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

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

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

But I’m more interested in other categories X\mathsf{X}. For example, what if X\mathsf{X} itself is Vect\mathsf{Vect}, or the category of algebras of some other finitary monad on Set\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

18 Comments & 0 Trackbacks

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

https://oscarcunningham.com/57/monads-on-monoids/

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.

Posted by: Madeleine Birchfield on January 15, 2023 11:37 PM | Permalink | Reply to this

Re: Total Freedom

What a sad life.

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 ff is equivalent to ff’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.

Posted by: Madeleine Birchfield on January 17, 2023 8:34 PM | Permalink | Reply to this

Re: Total Freedom

There is plenty of confusion amongst an older generation of type theorists of the distinction between a type AA which is pointed, i.e. with an element a:Aa:A, and a type AA which is inhabited, i.e. whose propositional truncation has an element a:|A|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.

Posted by: Madeleine Birchfield on January 17, 2023 8:53 PM | Permalink | Reply to this

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 XX and monads T:XXT: X \to X such that every TT-algebra is free.

A general class of examples: every algebra for an idempotent monad is free. (A monad TT is said to be idempotent if its multiplication map T 2TT^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 YY is a full subcategory of a category XX and the inclusion YXY \hookrightarrow X has a left adjoint, then the resulting monad TT on XX is idempotent. Hence every TT-algebra is free.

For example, AbAb is reflective in GrpGrp, giving the abelianization monad TT on GrpGrp. The algebras for the abelianization monad are the abelian groups, and every abelian group is the free TT-algebra on itself.

That’s all very trivial. Of the four monads on SetSet 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 Top\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

If I recall correctly, another example of idempotent monad is sheafification.

Posted by: Peva Blanchard on November 24, 2024 1:09 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 11, or equivalently, the theory consisting of a single constant cc and a single equation x=cx = c.

The second category is the category of algebras for the monad TT defined by

T(A)={1 if A if A=, 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=yx = 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 𝔽 1\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-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 11 is strictly terminal, in the sense that any map out of 11 is an isomorphism. In particular, whenever AA is a 11-module, the ring homomorphism 1End Ab(A)1 \to End_{Ab}(A) that implements scalar multiplication must be an isomorphism. This forces A={0}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’ XX+1X \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 ABA \hookrightarrow B in 𝒯\mathcal{T}, consider its cokernel, the pushout along the unique map to the terminal object A1A \to 1; let’s call the representing object KK. By construction, 1K1 \to K is a pointed object, and since every morphism from 11 is monic, this is a complemented subobject; call the complement KKK' \hookrightarrow K. Pulling back along the morphism BKB \to K, we obtain a complement of ABA \hookrightarrow B thanks to the fact that toposes are extensive categories.

Conversely, if 𝒯\mathcal{T} is Boolean and 1K1 \to K is a pointed object, then we again have a complement KKK' \hookrightarrow K and KK+1K \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