Re: The Idea of Structure as Data and Conditions

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

On 5/27/2012 11:00 PM, FEJ Linton wrote:
> Virtually no one ever wants to restrict attention to functions that respect
> (preserve or reflect) membership (other than "preserve" between ordinals).

Wouldn't that depend on the context in which membership arises?
Certainly group homomorphisms aren't expected to respect membership of
group elements in groups, but neither are they expected to respect the
composition of group homomorphisms equipping the category Grp.

The latter kind of respect is accorded categories by functors between
them.  By the same token the former kind is accorded elementary models
of set theory by elementary homomorphisms between them, the appropriate
counterpart of functors in that context.  Elementary homomorphisms
preserve elementary structure, which in the case of models of set theory
has membership as a basic part.  ZFC structure is very different (at the
bottom few layers) from the algebraic-in-Grph structure of the category
Set, which has function composition as a basic part.

For those who prefer algebra to logic, Joyal, Moerdijk and Awodey offer
Algebraic Set Theory, AST, as a middle ground here.  This replaces
membership by (set-sized) unions and singleton a |--> {a}.
Homomorphisms then have their usual algebraic meaning, which is arguably
less fiddly than for elementary maps.  Union allows the subset relation
to be defined as X <= Y  iff  X U Y = Y, from which one can then define
membership X e Y as {X} <= Y.  Both relations are preserved by the
homomorphisms of AST.  For a crash course see Awodey's

http://www.andrew.cmu.edu/user/awodey/preprints/astIntroFinal.pdf

ZFC, Set, and AST differ only at the bottom few layers, above which
foundational variations are tied to more fundamental issues involving
Choice vs. Determinacy etc.  One might compare the differences at the
bottom with the wave-particle dichotomy in quantum mechanics or the
event-state and time-information dichotomies in concurrency that I spoke
on at Physics & Computation 1992 and 1994, see

http://boole.stanford.edu/pub/ph94.pdf
and the earlier (1992)
http://boole.stanford.edu/pub/ql.pdf

Or at least that's how it all looks to this outsider.  Happy to be
corrected on details I've got wrong.

Vaughan Pratt


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