Re: naive questions about sets

Re: naive questions about sets

[Meredith Gregory]

Toby,

Thanks for your note. A longer reply is forthcoming, but in regards to
notation, in CS-y conventions it is now standard to separate out the "free"
syntax from the relations. So, you're right, of course, that the * denotes a
list. (It originates from the Kleene operator.) The standard treatment is to
whack this down by what is called a structural equivalence relation. In this
case, you have something like

n1,n2 = n2,n1
n1,n1 = n1

for the structural relations. This is roughly equivalent to specifying
models as algebras, i.e. a free monad plus a a structure map. i find the
ghettoization of the CS notations -- which are extremely compact and well
aligned with category theoretic sensibilities -- to be a source of unending
frustration in communications with the larger mathematical communities. i
really need to write a tutorial.

Best wishes,

--greg

On Fri, Mar 27, 2009 at 5:35 PM, Toby Bartels <
toby+categories@ugcs.caltech.edu <toby%2Bcategories@ugcs.caltech.edu>>wrote:

> Meredith Gregory wrote in part:
>
> >My
> >daughter and i decided that what went into the physical containers were
> >little promisory notes that could be redeemed for actual things. In this
> >version of the construction you only get flat structures, a set never
> >contains a set. That left the problem of the language in which the
> promisory
> >notes were written. Why not use the language of containers?
> >   - Container ::= {c| Note* |c}             // BlackSet ::= {b| RedSet*
> |b}
> >   - Note ::= {n| Container* |n}             // RedSet ::= {r| BlackSet*
> |r}
>
> Not to denigrate your interesting variation,
> but you get a result more like traditional set theory
> if you say that each container contains a *single* note
> which itself has a list of containers written on it:
>   - Container ::= {c| Note |c}
>   - Note ::= {n| Container* |n}
> (You could also have a list of notes, each of which has one container.)
>
> Of course, this is functionally equivalent to
>   - Container ::= {c| Container* |c}
> This is the usual model of what pure sets are like,
> but (as you and your daughter noted) this give an unphysical metaphor.
> However, you could just as easily do things like this:
>   - Note ::= {n| Note* |n}
> Since {n|...|n} contains things by writing down names for them,
> rather than having them physically present as {c|...|c} implies,
> there is no physical impossibility here.
>
> Incidentally, the notation X* suggests to me a list,
> where order and repetition matter and only finitely many terms can appear.
> Of course, sets are not like this, as you know.
> So instead of X* I would write P(X), using "P" for "power".
>
> This matches how category theorists model pure sets
> (the sets that appear in ZF-style set theory).
> A _universe of pure sets_ consists of a set U
> and a function from U to the power set P(U) of U,
> or if you prefer a binary relation E (for 'epsilon') on U,
> satisfying a few axioms (extensionality and well-foundedness,
> although it's also interesting to consider ill-founded sets).
> You get paradoxes like Russell's if you add the axiom
> that the function U -> P(U) is invertible.
>
> Of course, I said "set" above, but there I just meant
> an object of the category of sets as category theorists think of it.
> That is, simply a collection of atoms that may be equal
> but have no other structure (and in particular are not themselves sets).
> So this shows how to model ZF-style set theory in categorial set theory.
> (I apologise for repetition if you already know all about that.)
>
>
> --Toby
>



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com

Re: naive questions about sets

[Toby Bartels]

Meredith Gregory wrote in part:

>My
>daughter and i decided that what went into the physical containers were
>little promisory notes that could be redeemed for actual things. In this
>version of the construction you only get flat structures, a set never
>contains a set. That left the problem of the language in which the promisory
>notes were written. Why not use the language of containers?
>   - Container ::= {c| Note* |c}             // BlackSet ::= {b| RedSet* |b}
>   - Note ::= {n| Container* |n}             // RedSet ::= {r| BlackSet* |r}

Not to denigrate your interesting variation,
but you get a result more like traditional set theory
if you say that each container contains a *single* note
which itself has a list of containers written on it:
   - Container ::= {c| Note |c}
   - Note ::= {n| Container* |n}
(You could also have a list of notes, each of which has one container.)

Of course, this is functionally equivalent to
   - Container ::= {c| Container* |c}
This is the usual model of what pure sets are like,
but (as you and your daughter noted) this give an unphysical metaphor.
However, you could just as easily do things like this:
   - Note ::= {n| Note* |n}
Since {n|...|n} contains things by writing down names for them,
rather than having them physically present as {c|...|c} implies,
there is no physical impossibility here.

Incidentally, the notation X* suggests to me a list,
where order and repetition matter and only finitely many terms can appear.
Of course, sets are not like this, as you know.
So instead of X* I would write P(X), using "P" for "power".

This matches how category theorists model pure sets
(the sets that appear in ZF-style set theory).
A _universe of pure sets_ consists of a set U
and a function from U to the power set P(U) of U,
or if you prefer a binary relation E (for 'epsilon') on U,
satisfying a few axioms (extensionality and well-foundedness,
although it's also interesting to consider ill-founded sets).
You get paradoxes like Russell's if you add the axiom
that the function U -> P(U) is invertible.

Of course, I said "set" above, but there I just meant
an object of the category of sets as category theorists think of it.
That is, simply a collection of atoms that may be equal
but have no other structure (and in particular are not themselves sets).
So this shows how to model ZF-style set theory in categorial set theory.
(I apologise for repetition if you already know all about that.)


--Toby

naive questions about sets

[Meredith Gregory]

Categorical,

From the deafening silence i take it that there is no treatment of these
sorts of structures in the topos-theoretic or other categorical literature.

The whole area is a very rich vein. On the one hand there is great practical
interest in providing a modular semantics for fresh variables and
alpha-equivalence and a whole cottage industry has grown up around it. (Jamie
Gabbay's homepage <http://www.gabbay.org.uk/> is a good place for links.) On
the other, 'atoms' of the type in Fraenkel-Mostowski set theory do not occur
in an effective nature. An infinite supply of entities with no internal
structure, but which support an equality test, takes up way too much room to
fit inside a computational device. So, finding a consistent way to keep all
the benefits of the FM substitution
methods<http://www.gabbay.org.uk/papers/stusun.pdf>as they apply to
alpha equivalence while staying in an effective theory is
of both practical and theoretical interest.

Further, the generalization provide lots of structure to explore. One avenue
of investigation has to do with what can be contained. i found the
construction when teaching my 12 year old daughter set theory. We were using
the pedagogical device of set as physical container. Unfortunately, the
axiom of extensionality introduces a decidedly non-physical twist to things
(not counting quantum mechanical intuitions about what is physical). The
example we hit first was the von Neumann encoding for 2

[| 2 |] = { [| 0 |], [| 1 |] } = { [| 0 |], { [| 0 |] } }

which puts the same set in two clearly different physical locations. My
daughter and i decided that what went into the physical containers were
little promisory notes that could be redeemed for actual things. In this
version of the construction you only get flat structures, a set never
contains a set. That left the problem of the language in which the promisory
notes were written. Why not use the language of containers?

   - Container ::= {c| Note* |c}             // BlackSet ::= {b| RedSet* |b}
   - Note ::= {n| Container* |n}             // RedSet ::= {r| BlackSet* |r}

This has lots and lots of fun questions regarding how to redeem notes for
containers. It turns out that by carefully controlling the computational
power of how things are redeemed you never get the Russell paradox. This
appears to be related to stratified set theories such as the NF (thanks for
the link Paul!), but the circular set up does not show up in the wikipedia
article.

Another avenue of investigation is the number and kinds of color as there is
nothing that requires only two colors. In the spirit of the notation below,
we can think of a whole collection of different colored set theories
arranged by

Set(i) ::= {i| ( \Sigma_{ j != i } Set(j) )* |i}

This has interest for generic programming community. Find
here<http://paste.pocoo.org/show/109929/>Haskell code that resulted in
a conversation i had with Bruno Oliveira
regarding using generic programming techniques to take advantage of cyclic
symmetry in the different set theories.

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com

naive questions about sets

[Meredith Gregory]

Categorical,

i have a question about a presentation of sets. The motivation for this
question comes from a conversation i had a few years ago with Jamie Gabbay
concerning the use of FM-set theory in semantics for 'freshness'. i was
arguing that a certain use of 'reflection' gave a canonical (and smallest)
set of atoms. Jamie objected that atoms are not allowed to have internal
structure in FM-set theory. My question has to do with my response.

Because my question has to do with a formulation in categorical language,
rather than formulate it in that language, i will formulate it naively. In
my view, heavily influenced by computing as it is, i see the basics of set
theory as providing some operations for constructing and inspecting,
de-structing a data type called set. Very primitively, we have operations
for

   - extensionally constructing sets, '{ ... }' and
   - operations for intensionally constructing sets '{ ... | ... }'
   - operations for inspecting sets 'x in ... '

In this view, nothing prevents me from imagining two different versions of
this data type. One of which i will call the 'black' version and one of
which i will call the 'red' version. Initially, i might imagine these data
types as copies of each other; but, we can only construct and inspect 'black
sets' with 'black' braces and 'black' in predicate; and likewise for the
'red sets'. So, never the twain shall meet.

Now, once we've built such a structure, there's nothing to prevent us from
imaginging that the 'atoms' of a 'black' FM-set theory are none other than
'red sets'. Symmetrically, nothing prevents us from imagining that the
'atoms' of a 'red' FM-set theory are none other than 'black sets'. A
suggestive use of data type specifications might illustrate the idea

   - Ordinary sets
      - Set ::= '{' Set* '}'
      - Red/black sets
      - BlackSet ::= '{b|' (BlackSet + RedAtom)* '|b}'
      - RedSet ::= '{r|' (RedSet + BlackAtom)* '|r}'
      - RedAtom ::= RedSet
      - BlackAtom ::= BlackSet

Now, my question: is there a topos theoretic characterization of the obvious
zoology that results from these musings?

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com