FOM: concepts, sets

Vaughan R. Pratt pratt at cs.Stanford.EDU
Thu Oct 23 02:57:23 EDT 1997


(I should further clear the air by saying that the seamless Grand
Unified Category setup I mentioned in my previous message is orthogonal
to my seamier sets-as-ordinals stuff.  The former isn't terribly
dependent on which set theory one works in.)

> From: Neil Tennant <neilt at hums62.cohums.ohio-state.edu>
> On a different point, in reply to Vaughan Pratt's email in which he says
> that he thinks all sets are ordinals: What?! What about, for example,
> {2} or {3,7}? Can one no longer have such sets?

This depends on what you want to do with them.  If you want them as the
respective carriers of the trivial group and the group Z_2, then the
answer is, no, you can't have them.

But if you want to perform Boolean operations on them such as
intersection, union, or complement, then you can have them.  However
such sets can't just wander round naked the way they do in ZF.  The
Separation Axiom is modified to say that the intersection of a class
(qua predicate) and a set X is not just any old set but a subset of X.
Once formed in that way, that intersection remains a subset of X, i.e.
it is a typed set.  One may take the union of any set of subsets of X,
what one can't do is take the union of a subset of X and a subset of
Y.  In this setup complement is just as well defined as union and
intersection.

The full structure of such a subset is given by the following
composite.

		    t        c
		Y -----> X -----> 2

Here Y, X, and 2 are ordinals, t is a monotone injection, c (the
characteristic function of the subset) is an arbitrary function to
2={0,1}, and im(t) = c^{-1}(1).  This last condition says that for
every x in X, x is in the image of t iff c(x) = 1, and ensures that c
uniquely determines Y and t.  (This is roughly speaking the condition
that makes a cartesian closed category a topos, customarily expressed
as a pullback.)  Y is a kind of carrier of the subset (so at least in
this sense {2} *can* exist as a naked set, namely the ordinal 1), but
requires the translation function t to assign the intended
interpretation to its elements.

Since c determines Y and t, why bother with them at all?  Well, it's
nice to have a carrier so you can treat a subset as a first class set.
Since they *are* uniquely determined, there is no harm in taking them
to be an integral part of the notion of subset, it doesn't add any
information not already present in c.

Although the order type of a carrier of a subset is an accident of the
details of its construction, usually not useful for or relevant to the
constructed subset, it may nevertheless be illustrative to examine the
respective carriers of the integers, rationals, and reals under their
usual constructions.  That of the integers is \omega.2, with the
nonpositive integers coded as the finite ordinals (ordinal n codes
integer -n) and the positives as the ordinals in [\omega,\omega.2)
(ordinal \omega+n codes integer 1+n).  A minor variant of the
construction replaces "nonpositive" by "nonnegative".

I'd have to compute for a bit to figure out what carriers arise with
the usual definitions of the rationals and the reals (as Dedekind
cuts).  In the case of the rationals, Y and t are unambiguous.  For the
reals an element of randomness enters into the picture due to the
well-ordering of infinite products being left unspecified by the
framework.  For finite products, more generally for "successor
products", meaning products of i+1 sets where i is any ordinal, the
order is specified as lexicographic.

Vaughan



More information about the FOM mailing list