François G. Dorais

Mathematical Philosophy
Set Theory

Back to Cantor?

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.

Leinster (2014) recently wrote a nice account of one of these alternatives, Lawvere’s Elementary Theory of the Category of Sets (ETCS) (Lawvere 1964; Lawvere 2005). 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 (Cantor 1895; Cantor 1897) 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$ .¹

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$ ”.²

Cantor’s pairs $(m,n)$ have no implied structure other than the two coordinates³ 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 (Zermelo 1908). 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.

References

G. Cantor, 1895: Beiträge zur Begründung der transfiniten Mengenlehre (Erster Artikel), Math. Ann. 46, no. 4, 481–512.
- zbl: 26.0081.01
- doi: 10.1007/BF02124929
G. Cantor, 1897: Beiträge zur Begründung der transfiniten Mengenlehre (Zweiter Artikel), Math. Ann. 49, no. 2, 207–246.
- mr: 1510964
- zbl: 28.0061.08
- doi: 10.1007/BF01444205
F. W. Lawvere, 2005: An elementary theory of the category of sets (long version) with commentary, Repr. Theory Appl. Categ. No. 11, 1–35.
- mr: 2177727
- www.tac.mta.ca/tac/reprints/articles/11/tr11abs.html
F. W. Lawvere, 1964: An elementary theory of the category of sets, Proc. Nat. Acad. Sci. U.S.A. 52, no. 6, 1506–1511.
- mr: 0172807
- zbl: 0141.00603
- doi: 10.1073/pnas.52.6.1506
T. Leinster, 2014: Rethinking set theory, Amer. Math. Monthly 121, no. 5, 403–415.
- mr: 3193723
- zbl: 1345.03100
- arxiv: 1212.6543
- doi: 10.4169/amer.math.monthly.121.05.403
E. Zermelo, 1908: Untersuchungen über die Grundlagen der Mengenlehre I, Math. Ann. 66, no. 2, 261–281.
- zbl: 39.0097.03
- doi: 10.1007/BF01449999

Cantor (1895), pp. 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.

↩
Cantor (1895), 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$ ’.

↩
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) = \set{\set{m},\set{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 (Zermelo 1908). ↩

Originally posted on December 28, 2012, by François G. Dorais. To the extent possible under law, François G. Dorais has waived all copyright and neigboring rights to this work.

Comments

François G. Dorais replied to on December 29, 2012, at 02:29

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!
François G. Dorais wrote on December 29, 2012, at 21:13

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.
Todd Trimble wrote on December 29, 2012, at 21:32

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).
François G. Dorais replied to Todd Trimble on December 30, 2012, at 00:12

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.
François G. Dorais replied to Todd Trimble on December 30, 2012, at 00:21

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.
François G. Dorais replied to on December 30, 2012, at 00:58

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.
Todd Trimble replied to François G. Dorais on December 30, 2012, at 02:03

“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.
François G. Dorais replied to Todd Trimble on December 30, 2012, at 04:07

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!
Todd Trimble wrote on December 30, 2012, at 17:22

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.
Todd Trimble replied to on December 30, 2012, at 17:57

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.
François G. Dorais replied to Todd Trimble on December 30, 2012, at 19:15

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 $\set{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.
Todd Trimble replied to on December 31, 2012, at 14:23

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.
François G. Dorais replied to on December 31, 2012, at 18:36

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

What do you mean by “autology”?
François G. Dorais wrote on January 1, 2013, at 09:23

Edit: I updated the reference for Tom’s paper to point to the arχiv.
François G. Dorais replied to on January 2, 2013, at 18:45

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?
François G. Dorais replied to on January 2, 2013, at 18:51

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.
François G. Dorais replied to on January 2, 2013, at 19:21

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.
François G. Dorais replied to on January 2, 2013, at 19:37

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.
Mike Pawliuk wrote on January 2, 2013, at 20:50

Great write-up! I also enjoyed reading the comments of the enem– I mean … category theorists.
Todd Trimble replied to Mike Pawliuk on January 3, 2013, at 00:16

@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.
Mike Pawliuk replied to Todd Trimble on January 3, 2013, at 02:24

No offense meant. I really did enjoy reading the replies/viewpoints of you and Mike Shulman and Jesse (a fellow U of T student).
François G. Dorais replied to on January 3, 2013, at 15:05

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.
François G. Dorais replied to on January 3, 2013, at 19:25

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! :-)
François G. Dorais replied to on January 3, 2013, at 19:35

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.
François G. Dorais replied to on January 3, 2013, at 21:58

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!
François G. Dorais replied to on January 4, 2013, at 00:09

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…
François G. Dorais wrote on January 4, 2013, at 01:18

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!
David Speyer replied to on January 4, 2013, at 14:38

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?
François G. Dorais replied to David Speyer on January 4, 2013, at 17:15

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.
François G. Dorais replied to François G. Dorais on January 4, 2013, at 17:39

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.
Andreas Blass wrote on January 8, 2013, at 16:42

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.
François G. Dorais replied to Andreas Blass on January 8, 2013, at 17:36

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.)
Mark Gomer wrote on January 27, 2013, at 21:32

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

François G. Dorais

Research in Logic and Foundations of Mathematics

home papers posts news about boolesrings.org

Back to Cantor?

References

Comments