FOM: Re: Structures prior to homomorphisms

Vaughan R. Pratt pratt at cs.Stanford.EDU
Tue Nov 25 03:59:58 EST 1997

Sol Feferman:
>The relation of categories to functors is just a special case of the
>general relationship of algebraic structures to homomorphisms.  You can't
>define the latter without specifying the former (at least, not

Colin McLarty:
>If you mean it is impossible to give *logically rigorous*
>definitions of the latter before the former, then I'd like to see
>some particulars

In one sense Sol is right: if you throw away the objects leaving only
the morphisms presented abstractly, you can't recover the objects
because they contain information that has been irretrievably lost, in
particular the carrier.

But if you weaken the requirement to recovering the objects only up to
isomorphism, and add some structural requirements that can be justified
on the grounds that they obtain when your category of vector spaces
arises in one of various uniform ways, then for this case, and for many
other such cases, Colin is right.

Colin's axioms L1-L4 depend on several key properties of linear
transformations, e.g. Hom(G,V) is isomorphic to V where G is the
generator, Hom(G,G) with composition interpreted as multiplication is
the ring R, composition with elements of Hom(G,G) is scalar
multiplication, etc.

But while very interesting in their own right, an adequate account of
these properties and how they lead to Colin's claim might try the
patience of the reader who merely wants to grasp the general principle
without drowning in details.

Fortunately there is a much simpler case that many will be familiar
with that illustrates the general principle very nicely.  This is the
case of inclusions between the sets of a "ring" of sets, Birkhoff's
name for a set of sets closed under binary union and intersection.

Such a ring of course forms a poset under inclusion.  But to make the
connection with algebras and their homomorphisms more apparent, we can
view the inclusions as *rigid* functions, those satisfying f(x)=x.  In
this light, any set of sets can be viewed as a concrete category whose
homomorphisms are the rigid functions between them.  To maintain focus
on the main point, that objects can be recovered from morphisms, I'll
use "category of rigid functions" and "poset" interchangeably in the

One can then ask two questions.

(a) Is there an independent characterization of those abstract
categories arising as the category of inclusions in a ring of sets?

(b) Given a ring of sets, can the sets and inclusions between them be
recovered up to isomorphism from its associated abstract

The answer to (a) is yes: these are all and only the distributive

The answer to (b) is in general no.   Consider those sets of the form
{x < y | x is rational} vs. {x < y | x is real} where y is real.  The
former set is Dedekind's representation of y, the latter its completion
in the reals.  Ordered by inclusion, both rings of sets code the reals
under their standard order and hence are order isomorphic.  This makes
it clear that any fixed method of representing abstract posets cannot
recover even the cardinalities of the sets giving rise to them, let
alone the specific inclusions.

But with additional conditions the answer to (b) becomes yes.  One
simple condition is that the ring be finite, contain the empty set, and
be separable in the sense that for every pair of elements some member
of the ring contains exactly one member of that pair.  In this case the
ring can be recovered up to isomorphism from its abstraction as a

For infinite rings, a sufficient condition for recoverability up to
isomorphism is that the ring arise as the order ideals of a poset.  In
this case one first recovers from the abstract distributive lattice L
of this ring an isomorphic copy of the original poset.  The elements of
this poset are taken to be those elements x of L that are not the sup
of the elements strictly below x, ordered as in L.  (A little
reflection reveals how this must work.)  It is then immediate that the
order ideals of this poset are isomorphic copies of those of the
original ring.

Similar scenarios are played out for many other classes of categories
and their morphisms, quite independently of whether they happen to be
posets.  For modules, the respective counterparts of (i) ring of sets,
(ii) distributive lattice, and (iii) representation of the latter as
the former, are: (i) concrete category of R-modules, (ii) module
category, and (iii) representation of the latter as the former.

The axiomatization of module categories with generator R may thus be
seen as a theory of categories of R-modules, in the same sense that we
may view the axiomatization of distributive lattices as a theory of
rings of sets.

By further axiomatizing R to be a field we obtain in this sense a
theory of categories of vector spaces.  This theory is axiomatized
purely in terms of morphisms, the objects are mere vertices serving to
anchor the morphisms, just as the elements of a distributive lattice
make no mention of any representing set, nor those of a group any
representing permutation.

Vaughan Pratt

More information about the FOM mailing list