FOM: questions + "the static nature of sets"

[Carsten Butz]

In this posting I will take up the challenge of Harvey Friedman and
discuss a little of what category theory is the foundation of. 
I regret that it took so much time for such a posting, but there are
many reasons for this. Before getting into details, let me emphasize
what this posting is _not_about:

  the current discussion of whether or whether not topos theory
  provides a foundation of mathematics, and the simplicity of various
  axiomatizations of foundations.

This posting is organized in 3 different parts: Part one contains a
small comment to a posting by Simpson. Part two
explains to you what category theory should capture (as opposed to or
in addition to sets), and part three contains some questions I have.

An apologize in the beginning: I wrote this posting before I answered
some questions by Stephen Simpson, so at various parts it duplicates a
little the statements I made. Sorry for that.

Comments on earlier postings:
=============================
Let me correct a minor misunderstanding between Stephen Simpson and
me: I do care very much abound the foundational issues of people like
Brouwer etc, and I am interested in their philosophical ideas. What I
do not care (too much) about is that topos theory was invented first
as a tool-box in algebraic geometry, and that it became only later
clear that there are foundational issues around: The coincidence that
Grothendieck toposes share all the good properties of elementary
toposes, and elementary toposes are models of bounded intuitionistic
set-theory. 

Category theory as foundations of functions.
============================================
(the static nature of sets).
 
The axioms for sets (this may be ZF, but even much much weaker
systems)
intend to capture the most elementary properties
collections can have. Fine. There is certainly some space for
discussions (do collections really have this or that property? can we
really perform this or that "operation" on collections? etc.),
but this is not the point I want to make here. 

What about the axioms Harvey Friedman presented on this list? Can I
personally live with them? Yes I can, even more, I can only encourage
any attempt to get rid of any axiom referring to infinitary
constructions or axioms postulating the existence of objects as in the
axiom of choice. [Do not misinterpret this as a strong nihilistic
position, it is the position of someone who dislikes to take things
for granted, and after all, I use the axiom of choice for classes
sometimes. But I dislike that not all category theorists are well-aware of
the use of the axiom of choice for classes. There was a recent attempt
by Makkai to clarify the use of the axiom of choice and to describe
what category theory looks like without it. It is a good paper, but
does not reflect the use of category theory in daily
life. Unfortunately.]

I should say something more about the categorists point of view with
respect to sets. It is not as bad as it appeared sometimes on this
list. This might be partly because set-theorists seem to think that
a statement as "yes, we can live with sets" is the surrender of
category theory. Believe me, it isn't. 
In what follows I use "we" to speak about category theorists, and
"you" to speak about set-theorists. Although I can only speak for me.
We like "sets" almost as much as you like. After all, topos theory is
very much about "sets". If you do not believe it, you should look at
the way we proof things: we _do_ think of objects in categories as if
they where sets. This is after all one of the, if not THE major
achievements topos theory (in this case) brought to all of categorical
logic. 

To explain this a little let me answer the post by Konvei (Mon, 2 Feb
98 12:15:09, FOM: poll). Nothing what I say (although I cannot resist
in writing in a polemic style) is intended to be against him
personally, it is intended to show you how some people think, and this
includes partially algebraic geometers I guess.
[quote]
1) groups are concrete sets with the group operation, 
there are also isomorphism classes of them, and, if 
you want to include some extra structure (e.g. topology) 
to groups (and isomorphisms) this does not change the picture, 

2) what is said in 1) is commonly known (both among the 
near 300 fom-ers and among the whole mathematical community), 

3) if someone wants (for the sake of simplicity) to call 
isomorphism classes of groups by simply groups he is 
welcome to do so, and in this sense there are just two 
groups of order 4,

4) what is said above is so elementary that any attempt 
to play this into a foundational system is ridiculous. 
[end quote]

Poor guy! How limited is your world. I myself worked in
cohomology theory, and I used sheaves of groups a lot. But I would be
a fool if I would think of them as sheaves of groups, they
_are_ groups. And this is the only way one should think of them!
Many proofs are much more complicated if you use sheaves of groups,
because this structure is much more complicated that just a group
(with underlying support a set), this is why I _do_ think of a sheaf
of groups as _a group with underlying support a collection_. 

Let me start a little digression into elementary algebraic geometry. I
will give you some hints why a small portion of algebraic geometry is
really constructive/intuitionistic algebra. Below, I refer to
Hartshorne's book. If you do not want to read this digression, there is
a mark [end digression] below.

Take a ring R in the base topos Sets (for my set-theory friends: Let R
be a ring). We consider the topological space spec(R), the spectrum of
R, and the topos (category) or sheaves over it. We are mainly
interested in two of them, which are sheaves of rings. There is the
constant sheaf Delta(R), which, as an etale bundle over R, is just the
space R\times spec(R) (the set R equipped with the discrete topology)
together with the canonical projection onto spec(R). The other sheaf
is the so-called structure sheaf O_R, which has as total space the set

 { (p,R_p)  | p a prime ideal of R }

equipped with a suitable topology. (See Hartshorne.) 
(Up to now this is absolutely standard.) I have to name another sheaf,
namely a sub-sheaf of the constant sheaf. The total space of this
sheaf has as underlying set the set

  { (p,a) | p a prime ideal and a an element in the complement 
            of p in R                                   }
Two remarks I have to make: First of all I remind you that the
complement of a prime ideal is a multiplicative subset, and secondly,
I tell you that the set just defined is an open subset of the (total
space of the) sheaf Delta(R), so is itself a sheaf. 

This was the data I need. Now, we told you that any topos is a model
of (intuitionistic) set theory, and indeed, someone "living" in this
topos knows that Delta(R) is a ring, O_R is a ring, S is a
multiplicative subset (!) of Delta(R) and in fact, O_R is isomorphic
to the ring obtained from Delta(R) by inverting the elements in S,
i.e., Delta(R) [ S^-1 ] \cong O_R.
The canonical inclusion Delta(R) --> O_R is nothing but the canonical
inclusion of the ring Delta(R) into Delta(R) [ S^-1 ].
[Another remark: the topos is generic with this property, it is the
classifying topos of multiplicative subsets of the ring R; in terms of
forcing: The topos Sh(spec(R)) of sheaves on spec(R) is obtained by a
forcing construction: We wanted to add generically a multiplicative
subset to our ring R. We do this by a forcing construction, and the
"model" of "set-theory" in which a copy of the ring R lives (called
Delta(R)) and which contains a generic multiplicative subset (denoted
S above) is the topos Sh(spec(R)).]

There is an appropriate notion of modules in a topos, I denote the
category of all modules over a ring Mod(-).
  The constant sheaf functor (which is clearly exact, i.e., preserves
finite limits) induces an exact functor
  Delta: Mod(R) --> Mod(Delta(R)).
There is another functor,
  (-)\tensor_{Delta(R)} O_R : Mod(Delta(R)) --> Mod(O_R).
Through the ring homomorphism Delta(R) --> O_R the ring O_R becomes an
Delta(R) module, and we can obviously tensor with it to get the
functor described above. The standard proof that tensoring with the
quotient ring is exact is constructive (see any book on commutative
algebra), so the second functor above is exact as well. Composing both
of them yields an exact functor
~~: Mod(R) --> Mod( O_R ),
which is exactly the functor studied in [Hartshorne, p.110 ff], and we
just proved the first part of proposition 5.2 on that page, the others
parts are as simple. 

  This is how I think of these basic and elementary results in
algebraic geometry. Another is the following: In section II.8
Hartshorne discusses Kaehler-differentials and the module of such. All
the proofs given for sheaves I do not need: I know them to be true
since I only check that the standard proofs in "Sets" (Hartshorne
refers to Matsumara) are constructive. 
[end digression]

Ok, sorry for this long digression, but I hope you saw some points I
wanted to make. 

Coming back to my original task, I have to explain you why I think
that set theory is very static: I agreed already that it captures
more or less some properties of collections, but,
what about functions? Are functions captured in such a setup? I would
probably deny this, although this needs some explanation. Of course
you can encode functions by their graph, but this is just an encoding,
maybe good for some purposes (well, not maybe, but really good for
some). But treating a function like this reduces it to a
black box, determined just by its input-output behaviour. But of
course, this captures only part of the function (namely the
input-output behaviour), but not the function itself. As well, this
does not capture the codomain of a function (which is always part of a
function, even in classical analysis texts).

As an example consider the two functions 
  x mapsto 2x  and  x mapsto x + x
(say on the natural numbers, using binary representation). While the
first one just adds a zero on the right, the second one does a number
of computations. Of course some of you might object that this is just
a question of "implementation", but it may be very useful at being
able to distinguish between "implementation" and behaviour.

So arrows as foundations of what?
The answer to this should be quite simple by now: Of operation, of
doing, of action, of function, of ...

You complain that arrow is a concept that relies on something simpler?
like set, collection, universe (that have to serve as domain and
codomain of the arrow)? Sure, you are (partly) right. There is the
concept of domain which comes either earlier or at the same time as
the concept of arrow. But on purpose I avoided both the terms set and
collection for this domain. There is apriori no such fixed structure
on the domains that they have to be collections, or sets. 

If I "axiomatize" the notion of operation, doing, action, etc then I
will arrive at categories in a natural way: There are domains, and
there are operations. An operation comes equipped with two domains:
one on which it operates, and which represents the kind of outcome of
my operation/doing. (This is the formal setup. If forced into first
order predicate logic we have two sorts. Using standard terminology I
would call them objects and arrows, the two assignments from arrows to
objects are called domain and codomain.)

The axioms then are the following:

(1) Two operations can be be performed one after the other, provided
that the codomain of the first is the domain of the second.

(2) For each domain there is an operation "do-nothing".
    These operations are characterized by the fact that by precomposing or
post-composing with the appropriate "do-nothing"-operation we get the
same operation we started with. 

That's it, categories as the foundation of "doing", "operating" etc. I
do not see any sets around (up to now). 

Some remarks are in order:
- You can put this into a first-order logic set-up. If this is not not
as simple as the first axioms you get for sets, this does not mean
that there is something wrong with operations. The two axioms I wrote
above are as simple and natural as you can imagine. It is well known,
even to set-theorists, that sometimes first-order logic is a little
clumsy to formulate things, isn't it?

- In this informal environment, the axiom for products is very simple,
stating that you can do "operations" in parallel. 

- Similar statements hold for the existence of a terminal object and
for function-spaces. I think it is fair to say that we get on a
very natural base the axioms of a cartesian closed category (I mean
here, all finite products including the empty one which is the
terminal object, and function spaces) for almost nothing. 

- We have to work harder for the sub-object classifier, I agree. 

Questions:
==========
I have some questions I would be pleased some people would comment
on. Some are related to the posting above, some are not. I always
tried to be honest on this list, so are my questions, and some of them
affect any claimed foundation by topos theory as well. Some of the
questions are stated provocative, although I do not have my
private answer to them.  

Pointers to the existing literature are highly appreciated.

(1) How can anybody dare to claim that the axioms presented by, e.g.,
Harvey Friedman, or by Colin McLarthy, or sketched by me above, have
anything to do with foundations for real analysis (as an example)?
What any set-theorist (or topos theorist) presents me as "the reals"
has nothing, really nothing to do with the real numbers we use in
analysis. To use Harvey Friedman's words (from a different
discussion): People present only slavish translations of the reals.

(2) What is the status of the axiom of choice? Aren't the many many
"un-believable" consequences evidence enough (even proof enough?) that
the axiom of choice "is" wrong?
[I would like to see serious comments on this question.]

(3) [The following question applies to topos-theory in about 20 years
as well.]
How can set-theorists be so happy with their subject? They were
pressed into some set-up about 80 - 100 years ago, and since then they
haven't made any progress (in presentation), and are even proud of it!
Still the same boring language etc. Any field of mathematics has
changed dramatically over the years, no field is taught the same way
as 80 years ago. Not so set theory. 
[Remark: The only change in set theory was the invention of forcing,
which is taught nowadays. What I mean is the clumsy language, which
wasn't modernized at all over the years.
  Do not respond with something like...because we found once and for
all the true language,... that's too simple.]

(4) How can anybody claim that there is absolute truth out there? I
liked very much the story about the three lions, so I guess there is
truth out there that 1+1+1=3, and may be that 1+1 does not equal 3,
but how can we (all of us, including me) be so sure that any
(mathematical) statement is apriory true or false.
  How does this relate to modern approaches in physics (in particular
quantum physics), which states that we _cannot_ give these simple
answers to elementary (physical) questions?

  [My favourite solution here is the transfer of the following example
to mathematics:  
   Newton mechanics _is_ true (what does this mean??), for many of our
purposes, but it is _wrong_ as well, if you look much more carefully
(small particles, high speed). We should never give up Newton
mechanics, but as well should not deny relativity theory.

In this category theory vs set-theory debate I felt a little like as
if set theorist advocate Newton mechanics, and cannot see why some
people think relativity is good as well, and may be set theorists 
even believe that
we would like to persuade them to use relativity theory to calculate
the time needed to get from home to university. We didn't. 
I  know that this example goes partly in a wrong direction, since 
it suggests that set-theorists are here the only bad-boys 
(but, after all, I am a category theorist).
  ]

(5) Could it be that in this debate set-theory vs category theory we
had many communication-problems? I got the impression, and if this is
the case, we should work harder on our postings. I for myself felt
quite misunderstood with my last-but-one posting. 
  As well, I regret that we haven't discussed so much real
foundational issues, partly because set-theorists do not know category
theory too well (this is the polite version of formulating it), partly
because because we category theorists didn't express our-selves
clearly enough (fellows, people who never thought about topos theory,
functions as foundations etc _must_ think we are crazy if we talk
about "objects in the category of sheaves _are_ sets", we have to be
more careful in explaining our ideas and experience).

(6) Unfortunately, I do not have McLarty's book on topos theory, (and
the library copy is not available) but
remember vaguely that he discusses forms of analysis in a topos. 
He mentioned this as well on this list. Would
anyone from the set-theory-side comment on that? How much they think
this is real analysis? Would they agree that Brouwer or Bishop would
have been able to build a bridge?
(If you are in the same position as I am, can you comment on
vanDalen/Troelstra, Constructivism in Mathematics?)

(7) On the categories mailing list some people regretted recently that
they were ever taught classical set-theory, in particular the
cummulative hierarchy. (Without going into details, they had some good
reasons for complaining.) This goes hand-in-hand with another question
I have: 
  Being like babies we are pretty unbiased towards foundations, but as
soon as we enter Highschool or University, we are indoctrinated with
(sorry, I don't mean it as strong as it sounds), say taught on a
set-based foundation that there is hardly any escape. Any sociologist
can tell you how important the first years are, so it should not be a
miracle that "almost everybody" has a set-based foundation. But if
this is only "indoctrination", what are the consequences for foundations?
(If we would have had 80 years of categorical foundations, I would
still ask a similar question!)

(8) How does my way of thinking of sheaves of groups (and that of many
others) affect foundations? Is this evidence that there is something
wrong with our intuition of sets, or is it evidence that the axioms of
sets are so "incomplete" that they can be applied at various places?

(9) A final question about equality. There are various forms of
equality, like indistinguishable qua properties, or physical equality.
(imagine some pencils on a table that all look the same, and the two
sentences
"This is the pencil I used yesterday."
which can mean "a similar one as" or "the one" (in German language
this is distinguished by "der gleiche wie" and "der selbe wie").
How does this enter into foundations, how can we ever claim to know
equality of the second kind, if we can only detect equality of the
first? (Again, I know that my example only illustrates, it is not the
best.) 

  Best regards,

  Carsten Butz

Carsten Butz
Research Associate
Department of Computer Science, University of Aarhus (Denmark)
Research interests: Categorical logic, topos theory, homological algebra
WWW: http://www.brics.dk/~butz/