categories: Re: Characterizing FinSet up to equivalence

[Vaughan Pratt <pratt@cs.stanford.edu>]

In response to John Baez and Steve Vickers, let me put my question more
directly.  What categories of "finite" (in any sense of finite you like)
objects can be characterized up to equivalence as the finite objects (again
feel free to define this notion yourself) common to all categories of some
elementary class?

I showed that finite sets and finite Boolean algebras could be so
characterized.  What about finite Abelian groups, or finitely presented
(by generators and relators) Abelian groups, or finite dimensional vector
spaces over some field?  Once an appropriate notion of finiteness is settled
on, these become straightforward yes-no questions.

A related question is, what categories can be characterized up to equivalence
by purely elementary means?  I hope it's clear why I asked what I did and
not this.  (Loewenheim-Skolem and all that.)

Like John Baez, I like free algebras and cofree coalgebras as methods
of characterization.  (Why else would Dusko Pavlovic and I bother to
characterize the continuum as a cofree coalgebra?)  I would immediately
withdraw whatever I said that conveyed the opposite if I knew what it was.
In asking about definability in a given framework (here first order logic
plus cardinality restrictions) I had not intended to imply even endorsement
of that framework, let alone rejection of other frameworks.

In defense of sets, I very much like them as a foundational concept, in
considerable part because one can reach a larger audience by starting from
sets than from sheaves.  I was impressed that anyone would dislike sets so
much as to compare starting from them to standing in wet concrete until it
sets (or were you just making a pun about sets, Steve?).

Sheaves as a starting point is fine for category theorists, who are equipped
to benefit from its greater generality, but they are singularly inappropriate
for most other mathematical audiences, for most of whom experience with
adding up the restaurant bill has made natural numbers much more familiar
than sheaves.  I'm not objecting to crash courses on sheaves here, just
to talks for a general mathematical audience that start out "Ladies and
gentlemen, let S be a sheaf."

Mentioning categories on Steve Simpson's FOM mailing list typically brings
on a diatribe from someone railing against categories.  It would be nice
if one could mention sets on this mailing list without the analogous response.

John Baez makes exactly the right connection between sets and the free
monoid on one generator (Peter Selinger made a related remark to me
privately about the free cocomplete category on one generator satisfying
FinC ~ FinSet).  The categorification of the semiring of natural numbers
yielding the distributive category of sets is natural, simple, beautiful,
and easily understood.

However I disagree that the assumption of finiteness constitutes smuggling
in FinSet.  A tiny part of it, fine, but that's a long way from smuggling in
the whole notion of function.  The notion of linear order with endpoints can
be characterized elementarily up to isomorphism if one restricts attention
to countable linear orders, but how much of the notion of linear order does
countability smuggle in here?

Cardinality restrictions as an axiomatization strategy convey no substantial
structural information, and are one of the mildest possible excursions
outside first order logic when such is unavoidable.  They have a long and
distinguished history in logic.

Vaughan Pratt