Date: Tue, 10 Nov 1998 18:53:15 +0100 (MET)
From: Perez Garcia Lucia
Subject: categories: Gödel and category theory
I am interested in the foundations of mathematics -more concretely,
in the claim that category theory can serve as a superior substitute
for set theory in the foundational landscape. In this context, I would
like to point out a footnote which appears in 'What is Cantor's
Continuum Problem?', written by Kurt G?del in 1947, revised and expanded
in 1964, and finally published in Benacerraf P. and Putnam H. (eds.) 1983:
Philosophy of Mathematics. Selected Readings, Cambridge University Press,
pp. 470-485. It reads as follows:
It must be admitted that the spirit of the modern abstract disciplines
of mathematics, in particular of the theory of categories, transcends
this concept of set*, as becomes apparent, e.g., by the self-applicability
of categories (see MacLane, 1961**). It does not seem however, that
anything is lost from the mathematical content of the theory if categories
of different levels are distinguished. If there exist mathematically
interesting proofs that would not go through under this interpretation,
then the paradoxes of set theory would become a serious problem for
mathematics.
*(the concept of set G?del was referring to is the iterative
one).
**(MacLane, S. 1961. "Locally Small Categories and the
Foundations of Set Theory". In Infinitistic Methods,
Proceedings of the Symposium on Foundations of Mathematics
(Warsaw, 1959). London and N.Y., Pergamon Press).
I need some help to grasp the following questions:
- In what sense the self-applicability of categories transcends the concept
of set?. (It is obvious that categories transcend the concept of well-
founded set but, what's the matter with non-well-founded sets?.
- In what sense do you think G?del proposed distinguishing different levels
of categories?. Would it be possible that G?del was thinking of something
like type theory?.
- Do you agree with G?del's intuition that nothing would be lost with such
a distinction?.
- Finally, in the last lines of the note G?del seems to suggest a research
programme for category theory as an alternative foundation of mathematics.
To what extent has it been carried out?.
Thanks for your help.
Regards,
Luc?a P?rez
Dpt.L?gica y Filosof?a de la Ciencia
University of Valencia -Spain-
--
***********************************************
lperez
***********************************************
Date: Wed, 11 Nov 1998 10:03:10 -0500 (EST)
From: Michael Barr
Subject: categories: Re: Gödel and category theory
I should really let people with more interest in foundations field this
question, but fools rush in ...
On Tue, 10 Nov 1998, Perez Garcia Lucia wrote:
>
> I am interested in the foundations of mathematics -more concretely,
> in the claim that category theory can serve as a superior substitute
> for set theory in the foundational landscape. In this context, I would
> like to point out a footnote which appears in 'What is Cantor's
> Continuum Problem?', written by Kurt G?del in 1947, revised and expanded
> in 1964, and finally published in Benacerraf P. and Putnam H. (eds.) 1983:
> Philosophy of Mathematics. Selected Readings, Cambridge University Press,
> pp. 470-485. It reads as follows:
>
> It must be admitted that the spirit of the modern abstract disciplines
> of mathematics, in particular of the theory of categories, transcends
> this concept of set*, as becomes apparent, e.g., by the self-applicability
> of categories (see MacLane, 1961**). It does not seem however, that
> anything is lost from the mathematical content of the theory if categories
> of different levels are distinguished. If there exist mathematically
> interesting proofs that would not go through under this interpretation,
> then the paradoxes of set theory would become a serious problem for
> mathematics.
> *(the concept of set G?del was referring to is the iterative
> one).
> **(MacLane, S. 1961. "Locally Small Categories and the
> Foundations of Set Theory". In Infinitistic Methods,
> Proceedings of the Symposium on Foundations of Mathematics
> (Warsaw, 1959). London and N.Y., Pergamon Press).
>
> I need some help to grasp the following questions:
>
> - In what sense the self-applicability of categories transcends the concept
> of set?. (It is obvious that categories transcend the concept of well-
> founded set but, what's the matter with non-well-founded sets?.
>
I will pass on this one. As far as I know, using category theory as
foundations gives an equally powerful, but not more powerful, foundation.
But I would say the same about non-well-founded set theory. Basically, it
is a matter of convenience and, perhaps, coherence.
> - In what sense do you think G?del proposed distinguishing different levels
> of categories?. Would it be possible that G?del was thinking of something
> like type theory?.
>
I would assume that is what he meant.
> - Do you agree with G?del's intuition that nothing would be lost with such
> a distinction?.
>
In a word: no.
> - Finally, in the last lines of the note G?del seems to suggest a research
> programme for category theory as an alternative foundation of mathematics.
> To what extent has it been carried out?.
>
Quite a bit; it is called elementary topos theory. I want to add
something here. I have taught a course in set theory (twice, actually).
I didn't much enjoy it, so perhaps I am prejudiced. But I have a specific
complaint. In all the fields of mathematics that I have worked with (all
the axiomatic fields, I should say), structures are defined and then
functions that preserve those structures. The structure of a set is that
of an epsilon tree, but this structure is ignored when it comes to
defining functions. A good thing too, since the only functions that
preserve that structure are inclusions of subsets. And the only
endomorphism of a set is the identity. Believing that theory should
follow practice, I am unhappy with the standard foundations that build
this elaborate structure only to ignore it. When categories are used as
foundations, then the undefined terms are object, arrow, domain, codomain,
identity, and the relation (partial function) of composition. They are
all used regularly in category theory; they are not just there to give a
formal foundation. And functors are exactly what preserve these things.
>
> Thanks for your help.
>
> Regards,
>
> Luc?a P?rez
> Dpt.L?gica y Filosof?a de la Ciencia
> University of Valencia -Spain-
>
> --
> ***********************************************
> lperez
> ***********************************************
>
>
Date: Wed, 11 Nov 1998 16:41:48 -0500 (EST)
From: cxm7@po.cwru.edu (Colin McLarty)
Subject: categories: Re: Gödel and category theory
Perez Garcia Lucia wrote, among other things:
>- In what sense the self-applicability of categories transcends the concept
> of set?. (It is obvious that categories transcend the concept of well-
> founded set but, what's the matter with non-well-founded sets?.
Well-founding is an irrelevant detail. Take any non-wellfounded set
theory which includes the axiom of choice, such as Aczel's AFA. Then every
set is isomorphic to an ordinal, that is to a well-founded set. Since
categorical methods are all isomorphism invariant, any categorical structure
available in this set theory is also available in well-founded sets. I have
discussed this in an article "Anti-foundation and self-reference" Journal of
Philosophical Logic 22 (1993) 19-28. There is no real chance that abandoning
the axiom of choice will help either--say by adopting AFA without Axiom of
Choice.
Rather, the apparent issue is existence of a universal set--a set of
all sets, so that you make a category of all categories. If you want to use
membership based set theory this will require non-wellfounding, but again
the details of membership and wellfounding are irrelevant.
Anyway, the problem here is that functions are hard to work with in
set theory with a universal set. I have shown that in any such set theory
meeting a few weak conditions there is a category of all categories, and it
is not cartesian closed. The result is clear from the more particular case
"Failure of cartesian closedness in NF" Journal of Symbolic Logic57 (1992)
555-56. Working with such a poor 'category of all categories' is much more
difficult than just doing without.
I think a more promising approach is to use Benabou's theory of
fibrations and definability as in Benabou J. (1985). "Fibered categories and
the foundations of naive category theory". Journal of Symbolic Logic 50,
10-37. I have discussed this briefly in "Category theory: Applications to
the foundations of mathematics" Routledge Encyclopedia of Philosophy (1998);
and in "Axiomatizing a category of categories" Journal of Symbolic Logic56
(1991) 1243-60.
I see no good arguments that there SHOULD be a genuine "category of
all categories" in any strong sense. But it seems an interesting question.
>- In what sense do you think G?del proposed distinguishing different levels
> of categories?. Would it be possible that G?del was thinking of something
> like type theory?.
More likely he was thinking of Eilenberg and Mac Lane's use of
Goedel-Bernay's set theory as a foundation in "The general theory of natural
equivalences", so there are set categories and class categories.
To study Goedel's claim here, you should look at any of Mac Lane's
papers on foundations that Goedel might have seen by this time. Maybe the
foundational parts of "The general theory of natural equivalences" are all
he could have seen, I don't know. Then it would be good to know what people
around Princeton were saying about category theory at this time--and that
might be very hard to find out.
Colin
Date: Thu, 12 Nov 1998 00:33:47 +0100
From: aurelio carboni
Subject: categories: Godel
AS for the Perez calling for references, I found quite surprising
that nobody quoted Lawvere's work on the subject. Carboni.
Date: Mon, 16 Nov 1998 15:07:52 -0500 (EST)
From: F W Lawvere
Subject: categories: re: Sets
Conceptualizing and axiomatizing
Mike Barr's experience with teaching membership-based set theory is
shared by many mathematicians, and quite a few share his conclusions. One
conclusion is that clarification is needed on even more basic questions
than just the large/small issue (which concerned Goedel, Mac Lane, and
Perez), in order to arrive at conceptions and axiomatizations compatible
with the practice of mathematics. For example, I was aiming at such a
clarification in pp. 118-128 of my 1976 paper in honor of Professor
Eilenberg's 60th birthday, where I advocated some rational connection
between conceptualizing and axiomatizing.
The complete lack of such a connection in a recent article in the
journal "Mathematical Structures in Computer Science" could have been
avoided by the editors, if not by the authors. In a section labeled
"Basic Set Theory" (p.510) they quote from my above paper a description of
the notion of abstract set:
1. ...each element of X has no structure whatsoever.
2. X itself has no internal structure except for equality
and inequality of pairs of elements....
immediately followed by their absurd conclusion:
"axiomatically this corresponds to taking the membership relation epsilon
as the only primitive notion of set theory and to postulating .." some
axioms typical to Zermelo-style membership-based theory!
Of course those axioms are NOT compatible with the conception
quoted: they violate (1) because according to the Zermelo primitives and
axioms, an element usually has elements, which would be structure; and
they violate (2) since according to those primitives and axioms, a pair of
elements of X may stand itself in the membership relation, which would be
an internal structure other than equality. The authors neglected to quote
the third clause which (as in the example that Mike mentions) their axioms
also violate.
The notion of abstract set (Kardinalen in Cantor's sense) is basic
among the many other notions of cohesive and/or variable sets (Mengen) to
the extent that we can model the Mengen via diagrams of maps between
abstract sets. Abstract sets may be "abstracted from" less abstract sets,
as Cantor did, or used, as most modern mathematics in practice does, as
all-purpose memory cells or parameterizers or nodes in such diagrams. In
addition to the papers by Colin McLarty mentioned in his message of
November 11, 1998, the following papers should help to clarify this notion
and its role in mathematics.
J. Isbell Adequate sub-categories
Illinois J. Math. vol. 4, pp 541-552, 1960
F. W. Lawvere An elementary theory of the category of sets
Proc. Nat. Acad. Sc. USA, vol. 52, 1964,
pp 1506-1511
F. W. Lawvere Variable quantities and variable structures in
topoi, (see especially pp 118-128)
in Algebra, Topology, and Category Theory,
ed. Heller & Tierney, Academic Press, 1976
F. W. Lawvere Cohesive toposes and Cantor's lauter Einsen
(concerning Cantor's neglected Kardinalen)
Philosophia Matematica, vol. 2, 1994, pp 5 - 15
W. Mitchell Boolean topoi and the theory of sets
(the membership-free content of Goedels
constructible sets still needs to be clarified
further)
Journal of Pure and Applied Algebra,
vol. 2, 1972, pp 261-274
********************************************************************
F. William Lawvere Mathematics Dept. SUNY
wlawvere@acsu.buffalo.edu 106 Diefendorf Hall
716-829-2144 ext. 117 Buffalo, N.Y. 14214, USA
*********************************************************************