Dec 282012
 

Set Theory has a fantastic and legendary history. At the end, it left us with ZFC, which is currently recognized as the foundation of mathematics. This state of affairs is arguably one of the best possible outcomes for the foundational crisis that plagued mathematics in the early 20th century. However, the choice to adopt ZFC was by no means unanimous, dissent has always been present, often with good reason. Whether propelled by inertia or by sheer power, for better or for worse, ZFC is now approaching 100 years of reign as the foundation of mathematics.

The most vocal opposition to ZFC has been from Category Theory (and its relatives). Indeed, the basic tenets of ZFC are very foreign to Category Theory and the various hoops that one has to go through to formalize Category Theory in ZFC quickly turn into major annoyances. The same issues arise elsewhere but Category Theory distinguishes itself from other areas by the fact that it regularly runs into genuine foundational issues, so the frictions that other areas feel become irritations for Category Theory. As expected, this irritation has led to a lot of heated debates and frustrations, but the more important outcome for a logician like me is a variety of interesting alternatives to ZFC.

Tom Leinster recently wrote a nice account [4] of one of these alternatives, Lawvere’s Elementary Theory of the Category of Sets (ETCS) [2,3]. The paper is intended for a general mathematical audience; the goal is to show that foundations that are friendly to Category Theory aren’t necessarily bad and may even be beneficial for everyone. Since discussions of this kind have been known to degenerate quickly, I wasn’t sure whether to participate in the discussion of this paper at the n-Category Café. Tom was visibly intent on keeping the discussion civilized and so I decided to jump in. I’m glad I did since the discussion was very beneficial for me: it forced me to look more closely at ETCS (and other alternative foundations) and to think very carefully about what it takes to be a foundation of mathematics.

The main difference between the two approaches is that ZFC is a material set theory whereas ETCS is a structural set theory. There is a lot to say about the differences, briefly:

  • Material set theory is based on the membership relation, which is extensional. A difference between two sets must be explained by an element of one which is not in the other. Some material set theories allow atoms but in ZFC, everything is a set. Thus the fact that this element is not an element of the other is explained similarly by elements of that element, or elements of elements of the other set, and so on and so forth. The end result is that a large set in ZFC necessarily comes with a lot of extra baggage which is generally irrelevant to its intended use. The advantage of this approach is the elegant simplicity by which complexity is built from nothing using simple tools.
  • Structural set theory is based on external relationships between sets, whose elements are completely anonymous. In ETCS, sets don’t even have elements per se, everything is expressed in terms of functions between sets. Instead, there is a distinguished singleton set $1$ and functions $1 \to A$ are used to point at the elements of $A$. Consequently, sets in ETCS cannot directly be used as data structures in the usual way since we can’t put things in or take things out of a set (without additional bagage). However, since two sets of the same size are essentially indistinguishable, isomorphic structures may as well be equal, which is a definite advantage of this approach.

Note that both setups can be used for all the same basic tasks of everyday mathematics; it’s the amount of baggage associated with each task that varies. There is much gain for a category theorist to work in ETCS and much pain to work in ZFC. Similarly, there is much gain for a set theorist to work in ZFC and much pain to work in ETCS. In general, mathematicians work with sets both materially and structurally depending on context, so both approaches capture some aspects of mathematical thought.

Since ZFC lies at one extreme of the material-structural spectrum, there is a genuine need for alternative foundations to better accommodate the structural view. Thus came ETCS, which is at the other extreme of that spectrum. It’s very fortunate that there is a very nice translation between ETCS+R (ETCS with replacement) and ZFC. Indeed, one would hope that both could cohabitate peacefully and provide mathematicians with sound foundations for the two points of view that they use every day. Though I was raised as a set theorist and I tend to think from the material point of view, I am sympathetic to my category theorist friends and I have been supportive of Tom and others in their effort to provide a sound structural alternative to ZFC.

There are some problems with this sort of compromise where material and structural set theories cohabitate as equal alternative foundations. One of the important roles of a foundational theory is to act as a communication channel between mathematicians: agreement on a few basic concepts is necessary to exchange ideas. It’s true that most communication happens between mathematicians with common ideas, but even category theorists and set theorists need to talk from time to time. I mentioned several consequences of this at the Café and stressed the fundamental importance of the translation between the material and structural perspectives.

After thinking about this more, I realized that this kind of cohabitation model is actually not the best possible way to accommodate both the material and the structural perspective at the foundational level. Indeed, what we end up doing is moving all the annoyances from both sides into the translation between the two. I’m worried that the translation, even if it is very nice, would simply become an irritating barrier between materialists and structuralists and actually harm communication between both. Even worse is that centrists, who like to blend material and structural views, are now stuck with all the annoyances.

Simultaneously with all this, I was looking back to the root of the problem and reread papers from the very beginning of set theory. The primary goal was to understand how the material perspective dominated at the outset and ultimately led to the general adoption of ZFC as the foundation of mathematics. To my surprise, I realized that the structural perspective was actually present at that time, though not as sophisticated and clearly delineated as it is now. Cantor’s original account of cardinal arithmetic [1] was actually very structural as can be seen in his definition of cardinal number:

Every set $M$ has a definite “power,” which we will also call its “cardinal number.”

We will call by the name “power” or “cardinal number” of $M$ the general concept by which, by means of our active faculty of thought, arises from the set $M$ when we make abstraction of the nature of its various elements $m$ and of the order in which they are given.

We denote the result of this double act of abstraction, the cardinal number or power of $M$, by $\overline{\overline{M}}$.

Since every single element $m$, if we abstract from its nature, becomes a “unit,” the cardinal number $\overline{\overline{M}}$ is a definite set composed of units, and this number has existence in our mind as an intellectual image or projection of the given set $M$.1

Thus, to Cantor, the cardinal number of a set is just its purely structural view, where the elements lose their individual identity. Cantor’s structural views are visible throughout.

Any element $m$ of a set $M$ can be thought to be bound up with any element $n$ of another set $N$ so as to form a new element $(m,n)$; we denote by $(M.N)$ the set of all these pairs $(m,n)$ and call it the “set of pairs of $M$ and $N$”.2

Cantor’s pairs $(m,n)$ have no implied structure other than the two coordinates3 and the product $(M.N)$ is actually only defined up to isomorphism!

It’s still not clear to me exactly how the material view of sets came to dominate. Cantor structural views were criticized by others, such as Zermelo who proposed the first materialist account of Set Theory [5]. Perhaps the prevalence of the materialist view is a direct response to the foundational crisis, where the extra baggage carried by material sets brought additional comfort as each set came with the full history leading to its existence according to the iterative conception of material sets. Speculations aside, the predominance of the material view is becoming increasingly frustrating to many and it is time to think how to accommodate the structural view on an equal footing.

Rather than having multiple alternate foundations with bridges between them, it would be much more satisfactory to have a greater overarching foundation similar to Cantor’s universe that comprises both the material and structural views. This way, ZFC and ETCS can more easily be seen for what they really are: formal reductions of the mathematical universe to a simplified context which are nevertheless strong enough to provide reasonable interpretations for all common mathematical constructs. Whenever they desire, category theorists could then preface their papers with a phrase like: “Without loss of generality, we work in Set, the purely structural part of the universe.” Similarly, set theorists could opt to work in V, the purely material part of the universe. In fact, this is close to current practice where mathematicians freely borrow from one side or the other as they please.

This kind of unified foundation is clearly one of the best possible outcomes for everyone. The problem is that it is not currently an option: there is no proposal for an alternative foundation that attempts to fully accommodate both the structural and the material points of view. I long thought that such a foundation would necessarily have to be too complex and therefore unusable. However, after rereading Cantor and seeing how he happily marries the two points of view in his universe, I now think that there might be a reasonably simple way to do this. I therefore conclude with a call to action, a call for structuralists, materialists and all other mathematicians in between to work together and find a reasonable unified foundation where structural sets and material sets happily live together as equals.

Remarks

  1. [1, p. 481–482] Jeder Menge $M$ kommt eine bestimmte ,Mächtigkeit’ zu, welche wir such ihre ,Cardinalzahl’ nennen.
    ,Mächtigkeit’ oder ,Cardinalzahl’ von $M$ nennen wit den Allgemeinbegriff, welcher mit Hülfe unseres activen Denkvermögens dadurch aus der Menge $M$ hervorgeht, dass von der Beschaffenheit ihrer verschiedenen Elemente $m$ und von der Ordnung ihres Gegebenseins abstrahirt wird.
    Das Resultat dieses zweifachen Abstractionsacts, die Cardinalzahl oder Mächtigkeit von $M$, bezeichnen wit mit $\overline{\overline{M}}$.
    Da aus jedem einzelnen Elemente $m$, wenn man yon seiner Beschaffenheit absieht, eine ,Eins’ wird, so ist die Cardinalzahl $\overline{\overline{M}}$ selbst eine bestimmte aus lauter Einsen zusammengesetzte Menge, die als intellectuelles Abbild oder Projection der gegebenen Menge $M$ in unserm Geiste Existenz hat.
  2. [1, p. 485] Jedes Element $m$ einer Menge $M$ lässt sich mit jedem Elemente $n$ einer andern Menge $N$ zu einem neuen Elemente $(m, n)$ verbinden; für die Menge aller dieser Verbindungen $(m, n)$ setzen wit die Bezeichnung $(M.N)$ fest. Wir nennen sie die ,Verbindungsmenge von $M$ und $N$’.
  3. The encoding of pairs in Set Theory was first done years later by Weiner and eventually simplified by Kuratowski into its now customary form $(m,n) = \{\{m\},\{m,n\}\}$. Even Zermelo didn’t have such an encoding and he was only able to form the product of two disjoint sets in his original formulation of Set Theory [5].

References

  1. G. Cantor, Beiträge zur Begründung der transfiniten Mengenlehre, Mathematische Annalen 46 (1895), 481–512. [doi:10.1007/BF02124929]
  2. F. W. Lawvere, An elementary theory of the category of sets, Proceedings of the National Academy of Science of the U.S.A 52 (1964), 1506–1511. [link]
  3. F. W. Lawvere, An elementary theory of the category of sets (long version) with commentary, Reprints in Theory and Applications of Categories 11 (2005), 1–35. [link]
  4. T. Leinster, Rethinking set theory. [arχiv:1212.6543]
  5. E. Zermelo, Untersuchungen über die Grundlagen der Mengenlehre I, Mathematische Annalen 65 (1908), 261–281. [doi:10.1007/BF01449999]

  55 Responses to “Back to Cantor?”

  1. Is MST vs SST analogous to quantitative vs qualitative, or geometry vs topology? There are metric spaces, topological spaces and metrizable spaces. So what about material sets (or labelled sets), structural sets (or unlabelled sets) and materializable sets (or labelable sets). An atom is the same as a singleton lablelled set. Questions of membership and inclusion require labellings. What is a labelling? Is a labelling just a function from something to something? When does it make sense to talk about the automorphisms of a group if the elements aren’t labelled and relabelled? In “Combinatorial Species and Tree-like Structures” can the definition of species be extended to infinite sets. Would infinite species have anything to do with unifying structural and material viewpoints.

    • I don’t think quantitative vs qualitative or geometry vs topology are fair comparisons, but there are some similarities. One of the main aspects which is different is that these are foundational views, so there is no a priori. We can’t really think of labels and such, where would they come from?

      I like the analogy with combinatorial species. As formulated by Joyal, these are essentially structural, but they represent very real objects and they wouldn’t be nearly as interesting if they did not correspond to real objects. However, this is misleading since even those real objects are not as material as the sets in material set theory. It’s easy to formulate basic structures structurally. That’s where structural set theory is most useful: the materialization of our thoughts is a much closer rendition of our actual thoughts. When we think of a tree, it doesn’t matter what the root or branches are actually made of, all that matters is how the root and branches behave with their immediate environment. That’s the nature of structural sets!

  2. Harvey Friedman made some interesting remarks on FOM regarding the possibility of incorporating the structural and material views of sets in the foundations. Though he admits that this is possible and perhaps desirable, he claims that material set theory is the simplest foundationally complete system and he concludes that such efforts are not worthwhile. I don’t fully disagree Friedman’s claim but I do disagree with his conclusion. I think that there is a possibility for a sufficiently simple integration of material and structural perspective. I think that through the exploitation of the advantages of the material and structural views, we can achieve a foundation where the axioms are simpler and more natural at the expense of making the language a little more complex.

  3. Thanks François — I do appreciate the spirit in which this is written. However, I have two gripes or nitpicks. One: I don’t like this absolute ‘the’ in “currently recognized as *the* foundation of mathematics”. Because, after all, there is more than one recognized way of founding mathematics, as we have been discussing. If you want to say, “currently recognized as the predominant foundation of mathematics”, then I would have no problem with that, but the absoluteness and added emphasis of your ‘the’ irritates me (sorry). Two: where CT typically bumps up against foundational issues is where we would like to manipulate large categories as perfectly legitimate mathematical objects, and there is certainly ongoing debate about the best way to deal with such things. But ETCS is not an outcome of this type of issue, AFAICT.

    If I may presume to speak for Lawvere (who invented ETCS), a particular friction here is more that logicians and set theorists commandeer the word “foundations” to mean a concretized membership-based set theory on top of Fregean logic (what Lawvere calls “speculative foundations”, for reasons that are obscure to me), and reject the categorists’ proposals, according to Kreisel’s argument that they are about *organization* of mathematics and not about foundations *per se*. Lawvere’s counter-argument is that this is an excessively narrow conception of foundations. Lawvere and Rosebrugh put it strongly: “A foundation makes explicit the essential features, ingredients, and operations of a science as well as its origins and general laws of development. The purpose of making these explicit is to provide a guide to the learning, use, and further development of the science. A “pure” foundation that forgets this purpose and pursues a speculative “foundations for its own sake is clearly a nonfoundation.”

    Well, I’m sure those words sound aggressive; I reiterate that they belong to Lawvere and Rosebrugh. But an example of what Lawvere is referring to might be the categorical analysis of logic or logics (as interlocking systems of adjoints), e.g., finite limit logic, regular logic, coherent logic, etc. as a bona fide foundational topic. Another example might be that the actual uses made of sets by those who wish to develop number theory, elementary analysis, topology, etc. has little to do with set-theoretic encodings; those involved in developing such topics have greater need of e.g. the universal nature of products and quotients to guide them to the correct notion of product topology, quotient topology, and so on. Lawvere wishes to consider those needs as belonging to “foundations of mathematics” according to his sense of what those words should mean.

    I don’t wish to derail the discussion — I’m just trying to articulate what I think Lawvere’s motivations were for ETCS, categorical logic, etc. with respect to foundations, which as I see it have little to do with the perennial questions of classes vs. sets (which seem not to exercise him very much).

    • I emphasized ‘the’ to be provocative and to emphasize the fact that there is something fundamentally wrong with this state of affairs. As I said at the Café, this post is intended to reach out to set theorists, who are not necessarily as aware of the problem the ZFC hegemony is causing.  It’s probably best if you, and others who are already familiar with the issues, simply ignore that hook and let others bite.

      That said, I disagree with your correction. ZFC is not the predominant foundation, it is (essentially) the only accepted foundation. I guess it’s not that clear that I am talking about the collective mind rather than the individual mind. The issue is again the communication problem that I keep emphasizing as a key issue. The current state of affairs is that if a mathematician does some work using alternate foundations, then they must also provide a translation into ZFC or else their work will not be integrated into mainstream mathematics. Otherwise, it will forever be cited with a caveat that the result was proven in this or that alternate system which may or may not be fully compatible with ZFC. As an extreme example, any analysts that use Brouwer’s theorem that every (total) function $[0,1]\to \mathbb{R}$ is uniformly continuous in a paper will see their work rejected, but it is fine if they say “within the context of intuitionistic analysis” somewhere (and handle the consequences thereof). There are some exceptions to this, especially where the translation into ZFC is well-known.

      As for the second gripe, I think this was poorly phrased on my part. I didn’t mean to imply that all of the things I mentioned are so closely entangled. The part about bumping into foundational issues was a tentative explanation why category theorists care about foundations so much about this while analysts and algebraists don’t care much even though they experience the same basic annoyances. (The other tentative explanation is that leading category theorists just happen to care a lot, which is much more tenuous.) Anyway, I might add another footnote or make a minor edit to clarify this since your reading of what I wrote is completely fair though not as I intended.

      Now that the two gripes have been clarified, I find the rest of your comment very interesting and I would like to add a few comments. While I’m doing this, I will air out one of my own gripes. Please don’t take it too seriously, I just want to vent some accumulated irritations. My gripe is with your use of “logicians and set theorists” and similar uses at the Café. I personally identify with both clans and yet I plea innocence for all the crimes that you and others have claimed here and elsewhere. In fact, I know that most logicians and set theorists are also innocent of those crimes, most of those that are guilty of some of these crimes have only committed only a few, and finally that those who are guilty on all counts are usually not logicians nor set theorists!Having aired out my gripe, let’s get back to serious business. Lawvere and Rosebrugh got it right, but you and others are apparently confused about the difference between the object (foundations of mathematics) and the analysis of the object (a part of logic and set theory). As Lawvere and Rosebruch said, the foundation of mathematics is something that everybody should be able to use and understand; it should serve as a basis for communication among mathematicians by clarifying basic concepts and understandings. As I emphasized in the penultimate paragraph, ZFC should really be understood as a formal reduction of the mathematical universe we all work in. The reason for this is that ZFC is much easier to analyze because of its simplicity. This analysis is what much of logic and most of set theory is all about. (However, the main focus of Set Theory is very specialized and most set theorists don’t care at all about foundations in the aspect being discussed here. When they do, they usually self-identify as logicians for that purpose.) In my opinion, the claim that ZFC is the foundation of mathematics is misplaced prescriptivism à la Bourbaki (who I would have loved not to mention here, but are nevertheless the main neither-logicians-nor-set-theorists who are guilty of all accusations I’ve seen here and at the Café). Bottom line: Yes! ZFC is a “speculative foundation” in the sense that it is “foundations for its own sake” as Lawvere and Rosebrugh put it. (I’m also not sure about the choice of word “speculative” but if I understood right, then I completely agree.) I would even add that this is one of the main points of ZFC!

      This whole topic is very confused and very confusing. I think the main culprit for the confusion is the foundational crisis of the early 20th century. The word “crisis” is important here. As with any crisis, the consequences were fear and panic and the responses were drastic. After a century, the crisis is gone and the fear and panic have (mostly) dissipated, but we still live with the responses. That’s where I think the problem really is: have yet to move on. During this century, we have figured out most of the relevant parts of what can and cannot be reduced to a reasonably sound basis. We’ve also figured out a few auxiliary things such as the fact that we cannot reasonably hope  for a provably sound basis and we have matured to accept that fact. It’s the right time to undo the drastic part of the response to the crisis and expand to a more tolerant foundation that allows for most things that we know can be reduced to a reasonably sound basis, such as ZFC, ETCS, and others that have either been put to the test (such as ZFC) or reduced (such as ETCS). We are all vey hopeful that the main dangling thread, NF, will be verified to be sound in the near future.

      Finally, let me mention that I do feel some of your pain. As a logician deeply interested in foundations, I am interested in a lot of approaches in the analysis of foundations. One of the approaches I have been fond of has been the wonderful progression from regular logic, coherent logic, to geometric logic and beyond that is best understood through Category Theory. I’ve used these in all sorts of ways to tackle the issues I am concerned about. It has been very difficult to sell this approach to my colleagues, while most are open and intrigued there are some who resist with force, presumably as a result of past heated discussions. I’m still hopeful that I will be able to break through eventually, but for the time being these efforts have been in vain and some have actually been harmful. I am pushing for equality because I firmly believe that all these approaches have their own merits and they each allow us to understand parts of this unfathomably complex mathematical world we live in.

      •  “My gripe is with your use of “logicians and set theorists” and similar
        uses at the Café. I personally identify with both clans and yet I plea
        innocence for all the crimes that you and others have claimed here and
        elsewhere.”  — Sorry!  Where I wrote “logicians and set theorists in my comment”, I only meant *some* logicians and set theorists; certainly not all!  (I particularly was thinking of some in the FOM battles of long ago, whom I viewed as upholding a Kreiselian line.)  Other than that, I don’t think I was accusing people such as you of any “crimes” (and I certainly hold set theorists and logicians as a group in very high regard, to the point of awe actually).  Anyway, sorry for not being clear there.

        “As Lawvere and Rosebruch said, the foundation of mathematics is
        something that everybody should be able to use and understand; it should
        serve as a basis for communication among mathematicians by clarifying
        basic concepts and understandings.” I certainly agree wholeheartedly with you (and them) there. If you think I’m confused, maybe it’s because I expressed myself poorly?  I certainly find, for example, the analysis of logical quantification in terms of adjoints a “clarification of basic concepts and understandings”.

        Finally, thanks for clarifying with regard to my first gripe. To me, the fact that ZFC and ETCS+R are equally strong as foundations is in my mind a commonplace, so it hadn’t registered (as it probably should have) that your observation was more sociological than mathematical. This is really important to keep in mind.

      • I only meant *some* logicians and set theorists
        I know you did, and I keep reminding myself of that whenever I see that phrase.  I’m glad you confirmed though since it’s much better to hear that from you than from myself!

      • I’m glad Todd brought up his second gripe, because I was about to say something along the same lines.  Actually, I think that many category theorists don’t care all that much about foundations.  A relative few care about the size issues that Todd mentioned; another relative few care about the material/structural divide.  The two groups of few may have significant overlap, but the issues invoved are largely distinct (although the latter can help to clarify the former).

        I would have phrased the origin of structural set theory and its connection with category theory more like this.  Category theory requires a broad perspective on mathematics, which makes more obvious the mismatch between the way ZFC treats sets and the way that the working mathematician uses sets (since we see working mathematicians of many different stripes at work, and train ourselves to notice the commonalities).  And category theorists are by nature uncomfortable with kludgy solutions, since most important facts in our subject are true for beautiful and simple reasons.  These twin characteristics probably make category theorists more likely to notice the issues with ZFC, and more likely to be bothered enough by them to try to do something about it.

      •  I understand that in two instances where category theorists have voiced discomfort or dislike of ZFC (Lawvere and Barr), that dislike really came to the fore as the result of dealing with it in the classroom, and not in research.

        If I try to introspect, I feel as if my preference for categorical approaches to logic and set theory might be partly a reflection of the type of mathematician I am generally. When I work categorically, I feel as if I’m doing pure algebra; when I attempt to read set theory as expounded by set theorists, it feels much more like combinatorics. I suspect most category theorists have this algebraizing tendency.

      • To be brutally honest, when I see set theorists do something that depends on the material structure of $\in$, like the fact Francois mentioned below that von Neumann’s ordinals can be defined in a special way that makes them “logically simpler” than arbitrary well-orderings, my immediate reaction is “that’s not mathematics”.  I know that this is wrong; set theory is clearly mathematics, and beautiful mathematics at that.  But all other kinds of mathematics that I know of are the study of structured (structural) sets, and a von Neumann ordinal has exactly the same structure as any other well-ordering: how can it be any different?

        This leads me to feel that there must be a way to reformulate set theory — meaning the set theory that set theorists do — in a structural way.  I don’t think this is an unreasonable expectation.  It’s not that different from what we do elsewhere in mathematics: whenever we see a pattern which fits many examples but there is an “odd one out”, often we are able to reformulate the odd one, or generalize the pattern, so that it is included.  Perhaps it’s a very category-theorist way of thinking to apply “many examples of a pattern” to “many fields of mathematics”, but in a sense I think the reasonableness of doing that is one of the most important insights of category theory (which is confirmed by many *other* examples of its applicability, so if this example is the odd one out, then…).

        This isn’t to say that such a reformulation would necessarily be useful to set theorists.  But I think there’s a good chance it might be — lots of other kinds of mathematics have benefitted from using category theory, once reformulated slightly in order to take advantage of it.  I think it’s a promising sign that set-theoretic forcing is so closely related to sheaf toposes.

      • I still don’t understand why you think set theorists think differently than other mathematicians. There is no brain swap that happens when I switch from doing set theory to doing anything else. I have no problems thinking structurally in either case.

        Categories don’t show up very much in some places because because the categories relevant are just too simple. For example, transitive sets are a skeleton for the category of extensional wellfounded relations and there is at most one transitive embedding between two transitive sets. It’s also pretty clear which limits exist and which don’t and there is nothing very involved in computing what those are. There isn’t much to gain in using more sophisticated tools.

        Large parts of set theory are completely structural. To a set theorist, a real is any point in a complete separable metric space (actually, a Polish space since the metric is not directly relevant). Descriptive set theory is the study of definability in such contexts. Again, categories don’t pop up much because all uncountable such spaces are Borel isomorphic. There are also topics in set theory that are completely structural and where categories play a key role, such as cardinal characteristics of the continuum and Borel equivalence relations. Forcing and symmetric models also have well understood category theoretic aspects.

        How is this so different from everything else in mathematics?

      • I agree that *large* parts of set theory are completely structural, but aren’t there also parts which aren’t?  You said yourself that well-foundedness is harder to talk about structurally, because you don’t have the $\Sigma_1$-formulation using von Neumann ordinals and the axiom of foundation.  This is the sort of thing that I don’t see anywhere else in mathematics.

      • I still don’t see it. The reason why it’s important to have that is that wellfoundedness is then absolute: it transfers between transitive models. That’s a structural idea, right? The point is to choose the theory that makes important things fit well. Since wellfoundedness is a key idea in set theory, it should fit well.

        To me this is a lot like choosing the right morphisms for the category of Banach spaces. If I think that isomorphic spaces should have the same norm, I’ll choose contraction maps; if I think that they should just have equivalent norms, I’ll choose continuous maps. Both are fine, it’s just a question of choosing the right one for the task.

      • The notion of “transitive model” doesn’t seem very structural to me.  How would you define it in a structural set theory?

      • It only makes sense when considering transitive substructures of a fixed wellfounded extensional structure. That is missing in ETCS so it doesn’t make sense to use transitive models.

        Note that you don’t need this skeleton. In ZFC, wellfoundedness is still absolute between wellfounded extensional models of (a small fragment of) ZFC, regardless of whether they are transitive models or not. Wellfoundedness is not absolute between standard models of ETCS and there does not appear to be an easy way to fix that.

      • Exactly.  This is where set theory seems to me to be non-structural and differ from the rest of mathematics.

    • Just to make things clear. I think both your comment and my response can be read as “passive agressive.” Whoever reaches that conclusion should read again since that is not my intent nor is it Todd’s intent (I believe). We’re both extremely reasonable people who happen to be talking about a touchy subject using a language and medium that is unfortunately not a perfect reflection of our thoughts.

  4. Thanks for the post, François.  Very interesting! 

    After I saw your post, I spent a while thinking about the various points of contact between category theory and set theory. I came up with three:

    1. Categorically-flavoured set theories such as ETCS.

    2. The need to put “large” categories (such as the category of groups or of topological spaces) on a rigorous footing.

    3. More philosophically: general thoughts about foundations of mathematics.

    While I was thinking about all this, Todd came along and said some of what I was going to say; but I’ll go ahead anyway.

    The most important thing is that these three points of contact are really distinct.  In particular, as you know, one can state ETCS without needing to be able to handle large categories (or even mentioning the word “category”).   So 1 and 2 are very different.  Personally, I’ve thought quite hard about 1 but don’t know much about 2.

    I think it’s 3 that ultimately causes the friction in discussions.  Category theorists (myself included) are apt to make grand claims about how their subject exhibits and illuminates the relationships between whole fields of mathematics.  Set theory is often referred to as “the foundation of mathematics”, which also sounds pretty grand.  If one is not careful, these sound like competing claims.  And often people aren’t careful, leading to confusion and frustration. 

    As Todd described, there’s been a tussle — a not very productive one, in my opinion — over the meaning of the word “foundations”.  Part of the reason why I avoided the word in my paper is that I didn’t want to get involved in that tussle, nor did I want to make the claim that a foundation for set theory was a foundation for all mathematics (whatever either phrase means).  I really don’t know what I think about these questions, and I thought it best to let the reader have their own opinion about what constitutes a foundation.

    • I wholeheartedly agree with you, Tom. I’ve clarified some fringe issues in my response to Todd, and I do mean fringe issues. It’s time for us to put all those small disputes aside and work together toward a better good.

  5. One of the things that is very appealing about material set theories and ZFC in particular is that its apparent semantics have a very intuitive feel, once you do get around the initial weirdness of there being “nothing but sets” (which is, of course, hyperbole; ∈ is not a set!) it doesn’t feel too difficult to construe any generalized list of sets as a name for a new set, so long as the list isn’t too long.  The structural theories, on the other hand, tend to leave more room at the bottom for either flexibility or mystification as to what the sets are, focusing instead on what sets are for and how most directly to describe every possible thing you could do with sets, as economically as possible; in categorical language, a theory of a category of sets is an attempt to say what is necessary to internalize some reasonably large fragment of ordinary mathematics, engendering as few surprises as possible.

    Of course, this attractiveness in ZFC is the same thing that tempts one to claim all the paradoxical things that had first to be excluded by restricting the comprehension scheme.

    •  

      The structural theories, on the other hand, tend to leave more room at
      the bottom for either flexibility or mystification as to what the sets
      are, focusing instead on what sets are for and how most directly to
      describe every possible thing you could do with sets

      That’s sort of how I view things too, but I would like to say something about the “mystification”. If I understand Lawvere’s POV, we know basically what we mean by “sets” — they are collections, just as you usually think of them. It’s just that for him, it is *mathematically irrelevant* to ask what the elements “are” or what is their “substance”. What is relevant to ask is: are these two elements (in a given set S, serving as a temporary universe of discourse) equal or not? Or: does this element x of S belong to that subset A of S?  Only those types of questions are *mathematically* relevant.

      As for the ETCS axioms, I think Lawvere views them simply as *observed facts* about sets and functions (ZF sets and ZF functions if you like, or if you insist on a fixed background) as they are actually used by mathematicians in mathematically relevant ways. Certain of these facts serve to concentrate the essence of mathematical practice (or at least “most” of mathematical practice) in a small collection of axioms. Which is close to what you were saying.

  6. Hi, François. While I’m trying to understand better what you might have in mind regarding a unified foundation, I’ll ask a question which I hope is not too unproductive: could you describe in more detail this “much pain to work in ETCS” for a set theorist?  (If I had to guess, it might be like the slight terror one feels reading, “some assembly required”, for example the construction of disjoint unions starting from scratch. But I’d rather hear your own impressions.)

    Incidentally, are you familiar with Algebraic Set Theory?  It’s something like a category theorist’s account of ZF, from the point of view that the recursive structure of the cumulative hierarchy can be described in terms of an initial algebra of some sort. Roughly, it starts with a category (a pretopos), whose objects are thought of as “classes”, and this category is equipped with a notion of smallness. Then, the cumulative hierarchy, when it exists, is defined to be initial among partially ordered classes (V, V.  Remarkably, if one defines “membership” by x in y  iff  s(x) <= y, then for the initial object V, the structure (V, in) can be shown to satisfy the axioms of intuitionist ZF.  More generally, if A is any class, the free "small-sup lattice equipped with an endofunction s" generated from A is a model of ZF + atoms A, and is an appropriate notion of "the cumulative hierarchy" generated from atoms A.

    It's quite likely you know about this, in which case this thumbnail sketch is for other potentially interested set theorists. But I wondered how it might fit in with a unified foundation that you envisage.

    • The most painful part for a set theorist is that ETCS has a very weak grasp of wellfoundedness. Wellfoundedness is one of the central pillars of Set Theory and I personally think it is the most important concept in Set Theory. Because of the Axiom of Foundation and the ordinal spine of the cumulative hierarchy, ZFC has both the usual $\Pi_1$ formulation of wellfoundedness and a $\Sigma_1$ formulation (via rank functions). This means that wellfoundedness is absolute for transitive models of ZFC, which is key to a very large part of Set Theory. ETCS only has the usual $\Pi_1$ formulation and consequently wellfoundedness does not transfer as well between models. The bottom line here is that the highly refined analysis of ZFC that set theorists have done has no natural analogue in ETCS. For a concrete example, a measurable cardinal makes perfect sense in ETCS since the idea of $\{0,1\}$-valued measure translates directly; ETCS starts having a rough time with normal measures and ETCS has very little understanding of the elementary embedding $j:V \to M$ resulting from the measure in ZFC (other than through the translation).

      A broader problem is that ETCS cannot directly use sets as data structures (the kind of sets where you can put stuff in and take stuff out) which is a really common use of sets. This can be done but ETCS needs a lot of annoying baggage to simulate this kind of data structure. This is a minor annoyance but it’s hard to tolerate it knowing that a slightly more material view would allow one to use sets this way with no baggage at all. (This kind of annoyance is very similar to the kind of annoyance that material sets have when thinking structurally.) Since sets are so simple, versatile, and powerful when viewed as data structures in this way, this is a worthwhile thing to do.

      Yes, I am aware of ZF algebras but I hadn’t thought of using them for this purpose. I am still thinking about what kind of system would be best for this. Right now, I’m testing out some hybrid systems with both membership and functions as primitives on an equal footing. The idea is to incorporate ZFC and ETCS as faithfully as possible and allow them to mix. So far, this is pretty interesting. It’s fun to try to exploit the strengths of one to compensate for the weaknesses of the other. In any case, this are very preliminary thoughts. I’m open to suggestions and I will write another post when I get somewhere interesting.

      • I’m surprised by what you say about well-foundedness.  I agree that much of what set theorists do is difficult to express in ETCS, but I would have attributed it to the non-rigidity of the models rather than to a weak grasp of well-foundedness.  Can you say more precisely what the $\Sigma_1$ formulation of well-foundedness is, and why you can’t express it in ETCS?  Would autology help?

      • The $\Sigma_1$ formulation is “has an (ordinal-valued) rank function.”

        What do you mean by “autology”?

      • Ah, and the thing which makes that $\Sigma_1$ and therefore useful is that the von Neumann notion of “ordinal” is $\Delta_0$.  Got it.

        Autology is an enhanced axiom for categorical set theory described in http://arxiv.org/abs/1004.3802, which helps when dealing with unbounded quantifiers.  Over ETCS it is equivalent to replacement.  But now that I see the real issue, I don’t think it’s relevant.

      • Reflecting on your two recent comments, Mike: Perhaps, then, it isn’t von Neumann ordinals that are “wrong”, but this filtration of the arithmetic hierarchy.

      • This is the Lévy hierarchy, not the arithmetic one. In any case, this is not a syntactic issue: the point is that $\Sigma_1$ statements are upward absolute for transitive sets, $\Pi_1$ statements are downward absolute for transitive sets, so $\Delta_1$ statements are absolute for transitive sets.

      • In this context, I mostly think of ETCS in the generic sense to mean ETCS+R+whatever (and ZFC for ZFC+whatever). The idea being that if something can be fixed by adding a few extra axioms, then it’s not a critical problem.

      • Fair enough.  Although I think for some phrasings of replacement for ETCS it is less clear how to use them to do analogous things to ZFC’s replacement; the “uniqueness up to isomorphism” can be tricky to deal with.

      •  Very dumb question here: The Axiom of Foundation is $\Pi_1$. Since the von Neumann definition only works because of Foundation, why doesn’t using a $\Pi_1$ axiom cause the same problems?

      • An axiom is a true sentence, so preservation is a non-issue (between models of that axiom, of course). Preservation is more interesting for formulas with free variables, such as “$R$ is a wellfounded relation on $X$,” in which case a morphism preserves it if it maps objects that satisfy the formula in one structure to objects that satisfy the formula in the other structure.

      • If I understand the first problem you mention correctly, I would tend to descibe it not as ETCS having a weak grasp of well-foundedness (the structural theory of well-foundedness works just fine in ETCS), but rather that notions like “transitive model” are hard to make sense of structurally.

      • Is the problem that skeletons are “evil”? The reason transitive models are so important is that they are a skeleton for the category of wellfounded extensional structures. Moreover, it’s a very convenient skeleton since the limits and colimits that exist are trivial to compute.

      • No, there’s no problem with skeletons in general, I think it’s the definition of this particular skeleton.  If you can give a definition of “transitive model” that makes sense structurally, I think that’ll be a big step forward.  I think its non-structurality is betrayed by what you say about its limits and colimits being trivial to compute, because structurally, any skeleton is just as good as any other.

      • So it’s the fact that this is a convenient and canonical skeleton that is the issue? It sounds like you’re telling me that my life should be more complicated. Maybe you’re just jealous! :-)

      • There’s nothing wrong with convenient and canonical skeletons (at least when you do category theory within a set-theoretic framework).  But I thought from your remarks that transitive models were *more* than just a convenient and canonical skeleton.  Anything structural that is true about one skeleton is true about any other, even if it’s easier to prove for one skeleton than it is for another (or for the whole category).  Indeed, anything structural that is true about one skeleton is true about the whole category.  Thus, anything structural that is true about transitive models is also true about the category of all wellfounded extensional structures, and that is something which makes perfect sense in ETCS.  But it sounded like you were saying that transitive models let you do things that *can’t* be done in ETCS.

        At a guess, maybe what’s going on is that wellfoundedness is still absolute in ETCS in the category of wellfounded extensional structures, but that ETCS *itself* is not a wellfounded extensional structure?  In other words, set theorists have developed lots of machinery that studies wellfounded extensional structures, and all that theory is equally true (if somewhat more awkward to express) in ETCS, but it cannot be applied *to* ETCS itself.

      • The problem is with extensions of models. You can expand a model of ETCS with new sets and morphisms (even while preserving nnos) in such a way that there is some wellfounded relation in the original model which is not wellfounded in the extension. There is no way to prevent that other than just requiring that the extension preserves wellorderings.

        ETCS is not the only theory with this problem. Second order arithmetic has this problem too. There, three different categories with the same objects coexist: simple embeddings, $\omega$-embeddings that preserve the natural numbers, and $\beta$-embeddings that preserve the natural numbers and $\Pi^1_1$ statements (equivalently, wellfoundedness). It is possible to study wellfoundedness in ETCS, it’s just more awkward since it similarly requires distinguishing simple embeddings from those that preserve $\Pi_1$ statements. For ZFC, the distinction between simple embeddings and transitive embeddings is very simple, natural, and elegant!

      • It sounds to me as though you’re saying that ETCS is just more expressive than ZFC, since it can talk about more different kinds of embeddings.  A more general framework is always a bit more awkward when you aren’t interested in the generality it permits, like having to add the adjective “commutative” everywhere in front of “ring” if the only rings you care about are commutative.  Is that accurate?

      • No. If you drop “transitive” then you get all the same morphisms that ETCS does, so there is no loss when moving between ZFC and ETCS. What I’m saying is that if you are interested in wellfoundedness then ZFC is the right tool. The analysis of wellfoundedness is a central part (if not the central part) of set theory, so ZFC is much, much better to work in than ETCS. (For example, compare checking “$f$ preserves wellorderings” with checking “$f$ maps elements of $x$ onto the elements of $f(x)$.”)

        A closer analogy with ring theory is that asking a set theorist to work in ETCS instead of ZFC is a lot like asking a ring theorist to work with addition as a ternary relation $A(x,y,z)$ instead of as a function $x + y = z$. It’s simply not the right language, though you could do all the same things in principle. And, yes, the ternary relation is “more expressive” since it’s much easier to think of addition as being partial and/or multivalued if it is just a ternary relation…

      • Can you clarify explicitly whether you’re saying that using ETCS for set theory would merely be more awkward when you formalize things, or actually more difficult mathematically?  Sometimes it seems to me like you’re saying one and sometimes the other.

      • Both. ETCS is more awkward because the tools available to handle wellfoundedness are clumsy: there is no canonical skeleton like transitive sets and computing limits and colimits requires work. Working in ETCS also more difficult because there is no simple check to make sure that wellfoundedness is preserved. Even going through the interpretation of pure sets doesn’t help since there is no simple characterization of pure sets in ETCS.

      • Thanks; now I understand better.  I don’t think we’re really disagreeing about anything, except maybe words (e.g. I feel like possibly you mean something a bit different than I do by “well-foundedness”).  What you say confirms the general feelings I’ve gotten from reading set theory.  It’s an interesting challenge to try to marry the ideas of modern set theory with the structural perspective coming from category theory and “algebraic/topological” mathematics, and I’m glad there are other people thinking about it and approaching it from other perspectives.

      •  In other words, is ETCS just as good as ZFC for studying models of ZFC?

  7. Edit: I updated the reference for Tom’s paper to point to the arχiv.

  8. Great write-up! I also enjoyed reading the comments of the enem– I mean … category theorists.

    • @Mike Pawliuk: please don’t refer to the category theorists as “enemies” — even as a joke.  I think we are all here to try to understand.

      •  No offense meant. I really did enjoy reading the replies/viewpoints of you and Mike Shulman and Jesse (a fellow U of T student).

  9. The discussion in the comments here between Mike Shulman, Todd Trimble and I are very interesting. I just posted an answer on MathOverflow summarizing my point of view in this discussion. Thank you very much Mike and Todd for the very engaging, stimulating, and entertaining discussion!

  10. [...] Francois Dorais’ reply to the n-Category post, “Back to Cantor?”. [...]

  11. A minor comment about “ZFC is now approaching 100 years of reign as the foundation of mathematics”: Is there a clear indication of when the reign actually began?  Gödel’s paper proving the incompleteness theorems refers, in its title, to Principia Mathematica, suggesting that this was still the dominant foundation at that time.  Just a few years later, Gödel used NBG as the framework for his consistency proof of AC and GCH, but that choice may have been heavily influenced by the nature of the proof.  Since NBG is conservative over ZF, one might regard this as an indication that ZF was beginning its reign (or at least preparing for a coup d’état), but I’m not sure conservativity is a strong enough connection to support such a claim.  So when did ZF “really” start to reign?

    A slightly related point: In early work of Erdös on the partition calculus, there are notational distinctions between a cardinal number, the initial ordinal of that cardinality, and the set of ordinals below that initial ordinal.  For today’s set theorist, this looks like a horrible, unnecessary proliferation of notation, wasting the reader’s mental energy on keeping track of the notation, when the energy is really needed for the mathematical content.  But from a structural point of view, these notational distinctions make perfect sense; the three concepts really are different. The materialist has just taken advantage of the nice well-founded structure of the ZFC world to identify all three concepts, and we’ve become so accustomed to the identification that its absence strikes us as very unpleasant.

    • Thanks for the comments, Andreas. I’m not sure exactly when ZFC was “crowned” but it has to be after key papers by von Neumann and Skolem in the late 1920s when the current formulation took form and before 1940 when Gödel published the details of his construction of L. (Technically, Gödel used NBG but that is morally the same as ZFC.)

    • I agree that the three concepts are really different for a structuralist — they are different for me, even though I’m not exactly a structuralist any more.  However, that doesn’t prevent a structuralist from systematically using implicit coercions (which mathematicians traditionally call “abuses of notation”) to avoid introducing separate notations for the three concepts.  This sort of thing is common among materialists too: a group is a different concept from its underlying set, but we have no problem using the same name for both.

  12. Type theory gives you the best of both worlds, and unlike ZFC or ECTS it doesn’t presuppose first-order logic!

    http://golem.ph.utexas.edu/category/2013/01/from_set_theory_to_type_theory.html

 Leave a Reply

(required)

(required)


− four = 3

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>