Re: abstraction of notation from sets.

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

Besides Peter Easthope's question on the appropriateness of considering
an object of C as an element of C there is also (in fact more generally
as I'll mention near the end) the question of whether the notion of
"element" is well established in a presheaf category C = Set^{J^op} on
J, made a topos by choice of a final object 1 and a subobject classifier
O, and (by Yoneda) with the further choice of a full embedding of J in
C.  With that arrangement, and with the idea that distinct provenances
for sets give rise to distinct notions of "element," it seems to me that
at least four natural kinds of set arise in a presheaf topos in ordinary
mathematical practice.

First kind.  As a homset from 1.  This notion makes the connection with
set theory that toposes were developed for, with the caveat that it
should be understood in the light of the third and fourth kinds so as
not to overstate its applicability.

Second kind.  As a morphism to O.  This represents a subobject of the
domain of the morphism (the subobject itself being in general a proper
class and therefore not a fit entity for ordinary mathematics).  For
example in the topos Set with natural numbers object N it is natural to
write {2,3,5,7} for the set of 1-digit primes, understood as (the
subobject of N represented by) its characteristic function as a morphism
from N to O.

Third kind.  As a homset to O.  This is the power *set* C(X,O) of
subobjects of the domain X of the homset, which by the cartesian closed
structure of C is in a natural bijection with the power *object* O^X
when considered as a set C(1,O^X) of the first kind.

Fourth kind.  As a homset from the image Y(j) under the embedding Y: J
--> C of some object j of J.  For example if J has objects V and E
making each object of the topos a graph G then we think of G as formed
from two sets, and refer to the morphisms to G from Y(V) and Y(E) as
respectively the vertices and edges of G.  In this example the set of
vertices of G also happens to be a set of the first kind, but not the
set of edges, pointing up the need I mentioned earlier not to overstate
the significance of sets of the first kind while also addressing Peter's
original question in a roundabout way in terms of the underlying graph
of a category.  A morphism of a presheaf category is properly understood
as an ob(J)-indexed family of functions mapping sets of the fourth kind
to their counterparts in the codomain of the morphism.  Among these the
monics as families of injections furnish the notion of subobject in a
presheaf topos with its intuitive meaning complementary to that of the
second kind of set, the remark about proper classes notwithstanding.

Of course any homset of a topos is a set, but it seems to me that the
above four kinds deserve special recognition as sets commonly
encountered in mathematical practice having readily distinguishable
provenances.

Vaughan Pratt


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]