FOM: NYC logic conference and panel discussion

Vaughan Pratt pratt at CS.Stanford.EDU
Thu Dec 9 16:25:46 EST 1999

>Matt Frank
>I don't think that this is in the book by Lawvere and Schanuel--after all,
>Part I of that book is titled "The Category of Sets".  On the other hand,
>a lot of the book discusses the category of directed graphs instead.  In
>particular, it discusses truth-value objects in this context, and I found
>that useful (the first example of these things that I really liked)
>largely because it was so different from the usual set theory.  

Toposes enter explicitly near the end, where it is pointed out that
the book has been concentrating on toposes throughout, in particular
the categories of sets, irreflexive graphs, reflexive graphs, and
dynamical systems.

The authors define a topos as a category C having finite sums and
products, function spaces ("map objects") Y^X or X->Y, and a truth
value object (\Omega) containing the truth value "true" (the map
true:1->\Omega), and also satisfying the interesting condition that for
every object X of C, the "slice" category C/X has products.

The objects of C/X are the morphisms to X in C, and a morphism of C/X from
g:Y->X to g':Z->X is a morphism f:Y->Z such that g'f=g.  The subcategory
of C/X of primary interest, called P(X) for the "parts" (subobjects) of X,
has for its objects monics (in C) to X.  P(X) is shown to be equivalent
to a poset, namely the poset of predicates on X.

Although the book does not take this development further, the
experienced reader will immediately infer that P(X) has all infs,
i.e. that conjunction is defined on predicates including infinitary
and empty conjunction.  This makes P(X) a complete semilattice, hence
a complete lattice, hence a Heyting algebra.  In the category of Sets
with \Omega = {0,1} the predicates are Boolean, but in general they are
only intuitionistic, or "non-Boolean" as the book puts it.

The book is directed to a considerably younger set of readers than usual
for introductions to category theory.  (The closest the book comes to
mentioning Heyting algebras is to point out that not not not P = not P
in any topos.)  That this is possible without compromising on precision
of definition lends support to the thesis that category theory is an
elementary subject.

>From there one may if so motivated draw the further inference that
category theory is a viable candidate for a component of the foundations
of mathematics along with arithmetic, set theory, Boolean logic, and
other notions sufficiently elementary as to be accessible to at least
those high school students who are not overly anxious about mathematics.

Vaughan Pratt

More information about the FOM mailing list