2015 - Page 7 of 7 - Logic Matters

What is the category Set?

Category theory / 4 Comments / February 5, 2015

We all know that we quickly encounter issues of size when we start category theory. Categories, we are told, are collections of objects and morphisms satisfying certain axioms. But we very soon meet, among our very first examples of categories, categories like Set whose objects are too many for the collection of them to itself be a set. So what kind of ‘collection’ do we have here?

But here’s another issue about that initial example of the category Set which is ignored by many writers of introductory texts.

The issue can be posed, bluntly, like this: when the category Set is mentioned early on in an introductory text what category is that?

Typically no explanation is given at this stage. But of course which category we are dealing with depends on our set theory. For an NF-iste, the category of NFsets has very different properties from what is intended (for a start NFsets is not cartesian closed and later we learn that Set is). But fair enough, in an intro book you aren’t going to mention that in the opening pages! Rather the authors are, surely, intending to point to stuff that their beginning readers can be assumed to know about, and are saying, “Hey, you in fact already know about some categories, for example …” The charitable reading, then, is that authors are relying on their readers to think of Set as comprising the sets they already know and love.

But what sets are those?

Well, for many readers (if they have done any more than had a bit of set-notation waved at them) the sets they know and love are the pure sets of the cumulative hierarchy — pure in that there are no urlements, no memberless entities in the universe of sets other than the empty set. If set theories with urelements are mentioned in passing in an intro set-theory course, it is usually only to be dismissed and forgotten about. So: in the absence of special explicit signals to the contrary, we might well reasonably take the category Set mentioned in the very early pages to be a category of pure sets of the usual hierarchy (or at least the hierarchy up to some inaccessible, or whatever). Just sometimes this is made explicit. Thus, Horst Schubert in his terse but very good and clear Categories (§3.1) writes “One has to be aware that the set theory used here has no “primitive (ur-) elements”; elements of sets, or classes …, are always themselves sets.”

But then what are we to make, a bit later in our introductory books, of e.g. the usual presentation of the Yoneda embedding as $latex \mathcal{Y}\colon \mathscr{C} \to [\mathscr{C}^{op}, \mathbf{Set}]$. Putting it this way, if you look at the details, assumes that hom-collections $latex \mathscr{C}(A, B)$ for $latex A, B \in \mathscr{C}$ actually live in $latex \mathbf{Set}$. And since such a hom-collection is a set of $latex \mathscr{C}$-morphisms, that assumes that the $latex \mathscr{C}$-morphisms — irrespective of what the [small] category $\mathscr{C}$ is — must live in the world of pure sets too. [Sure, we may want the relevant hom-collections to be set-sized in the Yoneda embedding case — but being no bigger than set-sized is one thing, living in the universe of pure sets is something else!]

But do we really want to assume that morphisms are always pure sets?

Might we not be looking to category theory for a story about how different bits of the mathematical universe hang together which need not presuppose some over-arching, all-in, set-theoretic reductionism, and so in particular doesn’t presuppose from day one that all morphisms are pure sets?

Now, as I noted, the foundational sections you often meet early in category theory books worry away about questions of size (sets vs classes etc.). But the present worry is orthogonal to all that, and is in a way more basic. If we want to make no assumption that the denizens of different bits of the mathematical universe are all cut from the same cloth, we won’t want to slip into assuming that sets of these denizens are all pure sets. So in particular, do we really want to assume that a collection of morphisms (hom-set) must actually live in Set, if that’s the category mentioned back almost on p.1 of the book which is naturally read (and sometimes explicitly said to be) a category of pure sets? It may be that Set eventually gets to play a special role in the mathematical universe, with other most other categories being representable inside it: but surely this should be something to be shown later, not an assumption to be built in from the start.

In Chapter 3 of his fine Basic Category Theory, Tom Leinster makes the right moves here. Back track. Ask again: what are the sets that, before we start into category theory, we know and love and which are pointed to as constituting an exemplar of a category? Not the sets of pure ZFC (which mathematicians other than set theorists could even spell out the axioms which are supposed to tell you what these are?) but rather what we might call the sets of the working mathematician — sets of naturals, perhaps, or sets of reals, or sets of points in a space, or a set of continuous functions, or … And these are sets with ur-elements, elements that are not themselves presumed to be sets. (Or if we ascend to talk of sets of sets of naturals, for example, it remains the case that when we descend again through members of members … everything typically bottoms out with primitive non-sets.)

We assume various operations are permissible on these sets, and we can codify the permissible operations (for the purposes of the non-set-theorist, falling short of ZFC). Now Leinster associates this with Lawvere’s codification of the Elementary Theory of the Category of Sets (ETCS). But of course, Zermelo was in the same game, aiming to codify the principles of set-building that the working mathematician actually needs, aiming to provide enough to do the usual constructions but not enough to threaten paradox, and Zermelo’s original set theory too allowed for ur-elements. But then, if Set is to be a category of sets-with-urelements, built up using the principles working mathematicians actually need (whatever they are) — which indeed makes some of appeals to Set in category theory much more natural — then this really needs to be said (as Leinster does, and others don’t, and some actually deny).

Of course, we could go Schubert’s way and take hom-sets to be pure sets, so that morphisms and the other apparatus of category theory are all pure sets. But seeing category theory in this way as simply in the service of an across-the-board set-theoretic reductionism would surely be an unhappy way of looking at things: category theory seemed to promise more than that!

The Takács, in Cambridge

Music / Leave a Comment / February 4, 2015

Out last night to hear the Takács Quartet at the Peterhouse Theatre here in Cambridge (which seats under 200, has a wonderful acoustic, and must be one of the very best places to hear chamber music in England).

I hugely admire some of the Quartet’s recordings, but this was perhaps a more mixed experience (though I’m judging by their own exalted standards).

The programme began with a performance of Schubert’s Quartettsatz which took a while to settle and catch fire but ended in good form.

After the interval, the Takács played the first of Beethoven’s Rasumovsky quartets: and, compared with their fine recorded performance, this was — if truth be told — slightly disappointing. Quite independently, we both thought that there were balance issues. Edward Dusinberre’s first violin was rather too forward, too prominent, the tone not quite melding with the others (interestingly, I notice that reviewers of some other recent concerts have made similar comments). And the transcendental slow movement was I thought a little underplayed (not exactly rushed, but perhaps not allowed quite enough space). Three-and-a-half stars, not five.

But in between — and this more than made the evening — there was a truly stunning performance of the Debussy Quartet. I don’t know if the Takács are working up to record it in the studio, but they gave their heart and soul to the playing in a way which made for utterly compelling listening. I haven’t heard the Debussy for some years (the CDs recently untouched — which I’ll now have to rectify!), and it must be all of twenty years since we last heard this live, played by the Lindsays. But the performance last night was a revelation, which made an answerable case for the stature of the Debussy as a truly great work, and the Takács here more than showed why, on their day, they are almost without peer.

Those suggested readings for PhD students? A sceptical response

This and that / 6 Comments / January 29, 2015

Earlier this month, at the usually highly admirable The Philosopher’s Stone, Robert Paul Wolff posted a list of “twenty-five books by great philosophers that every grad student should read by the time he or she gets the PhD”. The list was remarkably well received — there were quibbles, of course, about what should be on it, but the principle of the thing seemed well supported.

Well, after a forty year career of sorts in philosophy, as far as I can recall I’ve read two of the listed books (for note, the list stops before Frege, Russell and Wittgenstein!).

Should I feel abashed? Inadequate? Am I letting the side down? Not at all. The suggestion that every philosopher (let alone every PhD student) should work through that list is of course complete tosh.

Or at least, it is if “read” means any more than skimming and skipping, pausing over a few particularly interesting/famous passages, and rounding things out from some decent second-hand outlines.

Now, I’m all for students having, say, a fifty lecture course giving the headline news about Wolff’s listed books. Or perhaps better, there is the do-it-yourself equivalent of reading the relevant twenty-five Stanford Encyclopedia articles, one a fortnight for a year, interspersed with chasing up a few choice passages for instruction and pleasure. That could be both fun and educational. But much more, for non-historians, is likely to be not only beyond the call of duty but of no particular use — except for at most two or three books (which books those are will depend of course on your interests).

To be sure, a modern ethicist would probably do well to read carefully a fair amount of the Nicomachean Ethics (say). And a modern metaphysician might get something out of struggling with some of Aristotle’s Metaphysics — or then again might not (I know a world-class metaphysician or three who seem to have managed very well without). But two or three books isn’t twenty five.

I’ve always been struck by these words of the great Cambridge classicist, Francis Cornford, in the preface from his book on Thucydides:

In every age the common interpretation of the world of things is controlled by some scheme of unchallenged and unsuspected presupposition; and the mind of any individual, however little he may think himself to be in sympathy with his contemporaries, is not an insulated compartment, but more like a pool in one continuous medium — the circumambient atmosphere of his place and time. This element of thought is always, of course, most difficult to detect and analyse, just because it is a constant factor which underlies all the differential characters of many minds.

That is one central reason why it can be so revealing to engage closely with one of the Great Dead Philosophers. By working our way into some measure of real understanding of what is going on in their texts, by finding what they take for granted, and the unspoken presumptions which shape the seeming-oddities of their position, our own unspoken presumptions can be thrown into relief and indeed challenged. It widens our sense of the range of possible approaches and positions. However, and this is the important point, to get to the stage where you can work far enough into a distant intellectual framework in this way takes considerable amounts of time and effort (and takes skills and aptitudes that many philosophers don’t have). If you have the time and the aptitude, then yes, seriously engage with a favourite work from the more distant past. But this is certainly not something you can do for twenty-five books by long-dead authors while getting on with your the day-job of writing a PhD on some contemporary topic.

So I agree: even for non-historians, if you find your interests meshing enough with those of some particular long-dead author, there can be pleasure and instruction to be had from trying to tackle some of the author’s work at first-hand in a moderately serious way. But as for the rest of the Great Dead Philosophers, the sensible course for the PhD student (the course which you might actually profit from in some small ways) is to stand on the shoulders of the serious scholars, take in the SEP articles or whatever which will tell you just a little about voyages to those alternative intellectual landscapes, and dip just here and there into (translations of) the original texts. But don’t even begin to try to really read those twenty five books while you are a student. And good luck to you if you ever find the time later.

Spam, spam, spam, spam ….

This and that / Leave a Comment / January 27, 2015

There are only two options for any blog. Allow no comments at all; or have a spam-filter. No way can you moderate by hand all the comments that arrive. For example, in the last six months — reports the plug-in at LogicMatters — there have been 72,664 spam postings in the comments here filtered out by Askismet so that I never even see them, never have to deal with them.

Askismet does a quite brilliant job, then. I’m certainly not going to turn it off! But apparently it can err on the side of sternness. If you try to make a sensible comment here which never gets approved, then it may not be me being unfriendly! If your words of wisdom seem unappreciated, you can always try re-sending them as an email.

Be smart by being systematic?

This and that / 6 Comments / January 25, 2015

I’ve just got this notice of tomorrow’s Trinity Maths Society meeting (details of when/where at that link, if you are in Cambridge). Sounds as if it should be fascinating …

Prof Tim Gowers FRS (DPMMS):
“Can interesting mathematics problems be solved systematically?”
Solving a mathematics problem that is not a routine exercise can often feel more like an art than a science. Different people attack problems in different ways, and ideas can appear to spring into one’s mind from nowhere.
I shall argue that solving problems is a much more systematic
process than it appears, and shall also try to explain why, if that is the case, it has the features that make us think that it isn’t. For the bulk of the talk, I shall attempt, with help from the audience, to solve an Olympiad-style problem that I have not seen before, and to do so systematically rather than by waiting for a clever idea to appear out of the blue. The attempt is not guaranteed to succeed, but I hope that it will be informative whether or not it does.

Perhaps, in the spirit of the times, someone should try live-blogging as the clock ticks down through the meeting! I’m not sure I’ll be able to get there — but if I can, I’ll try to take notes good enough to report back, as Tim Gowers can be fascinating on this kind of topic.

[Added 27th January] Well, I did go the meeting which was fun but actually not that illuminating. In so far as Tim Gowers had suggestions about how to approach problems “systematically”, they were rather anodyne rules-of-thumb for trying to find easier things to prove which together might give you (or point the way to) what you want. Thus sometimes if you want to prove a target result $latex P$ the aim will be to find propositions $latex A$ and $latex A \Rightarrow P$ which look easier to prove –“easier” relative to your background knowledge, of course. Sometimes a good bet will be to try to prove a special case of the general proposition $latex P$, for the proof of the special case may reveal rather naturally what needs to be done to generalize. Sometimes the thing to do will be to prove a more general proposition $latex P’$ (it may be easier to find a proof of the more general proposition because there are fewer ideas in play, cutting down the routes it seems natural to explore). Sometimes fiddling around with the terms of the problem, unpacking definitions etc., may simplify things by allowing you to hit the problem with what you already know.

All true — and Tim Gowers indicated some examples — but advice along the lines of “try breaking down the proof-goal to simpler-for-you sub-goals” is not exactly a systematic heuristic!

In the second part of talk, the audience were offered a list of Olympiad-style problems which Tim Gowers promised he’d not worked on before. I think these were proposed Olympiad questions rather than actual questions, so I’m not sure what kind of check there would be at this stage on difficulty-level. Anyway, the one chosen to tackle was this:

Find all the functions $latex f$ from non-negative integers to non-negative integers such that $latex f(f(f(n))) = f(n + 1) + 1$.

A not unfamiliar type of such question. So how are we do approach this systematically? And what’s the solution we thereby reach?

First question: are there any solutions at all? (that seems pretty natural to begin with). Try polynomials. It’s obvious that a polynomial with leading term of order $latex n^k$ with $latex k > 1$ can’t work. So try linear functions. And yes, $latex f(n) = n+ 1$ does the trick.

So we’ve got one solution. Are there others?

Well, at the time of writing this, I don’t know! After half-an-hour, Tim Gowers hadn’t found it (and an audience of maybe 400 — with quite a few recent Olympiad participants, I guess — hadn’t been able to help him out). Some not-very-systematic probings left us still floundering.

When the usual closing time for meetings arrived, the TMS President declared that extra time would be played after a ten minute break. But I had to leave the meeting, so I don’t know if the answer was found. I’ll let you know if I ever discover it. But the promised illustration of a successfully systematic approach to tackling such a problem didn’t come off. (So enormous credit to Tim Gowers for putting himself on the line like this!)

[Added later, 27 Jan.] You can find two full solutions at pp. 16-17 here. The headline is that the there are just two functions satisfying the condition, namely $latex f(n) = n + 1$, and

$latex f(n) = n + 1\quad (\mathrm{for\ } n \equiv 0, 2 \mod 4)$
$latex f(n) = n + 5\quad (\mathrm{for\ } n \equiv 1 \mod 4)$
$latex f(n) = n – 3\quad (\mathrm{for\ } n \equiv 3 \mod 4) $

But, the difficult bit, to show these are the only solutions without magic (or a “clever idea out of the blue”) — especially in Olympiad conditions — will surely require that you have up your sleeve a repertoire of known techniques and approaches for this sort of problem, and a practiced sense of what is likely to work. And it is interesting that some ingredients used in the solutions were suggested by students in the TMS audience apparently familiar with this general kind of question.

Being smart, being judged smart

This and that / 3 Comments / January 25, 2015

There’s recently been a lot of fuss (including on some philosophy blogs) about a short paper by Sarah-Jane Leslie et al., that purports to show that “women are under-represented in fields whose practitioners believe that raw, innate talent is the main requirement for success because women are stereotyped as not possessing that talent.” NB the ‘because’.

The methodology looked more than a bit dodgy to me when I glanced at the paper, for the discussion seems rather short on comparisons against alternative causal hypotheses. So you’d have thought that philosophers would have been more circumspect, rather than rushing immediately to conclude e.g. “Maybe now we can all finally stop talking about who’s smart”. Really? But what do I know, old fogey that I am?

Well, actually a little more than I did know, having now read this seemingly excellent sceptical statistical analysis of the Leslie paper, which strikes me as rather — what’s the word I’m searching for? — … “smart”, perhaps. [Added: there is now an extensive comments thread on that analysis, which raises some interesting issues. But one thing is clear; rushing to conclude that the Leslie paper nails it, or shows that we should ‘finally stop talking’ about this or that, is more than a little premature.]

What’s so great about sets?

Logic, Phil. of maths / 5 Comments / January 23, 2015

Here’s something I wrote a while back to answer a question on math.stackexchange about why sets and set theory should (or shouldn’t) be thought to have a special place in maths. Following a link on a related matter I found myself directed back to this piece of my own: I think I still quite like it. So here it is again …

There is a long, fascinating, and often-told story about the nineteenth century project for the rigorization of analysis, and about the re-construction of classical mathematics in terms of natural numbers and sets of natural numbers and sets-of-sets of natural numbers, etc. etc. And if we are feeling particularly austere we can even re-construct the naturals in a pure set theory which lacks urelements, so everything gets implemented in pure set theory. There are lots of good recountings of the story — here’s a short one with lots of pointers to more: http://plato.stanford.edu/entries/settheory-early/

I mention the history because it explains why set theory has long been thought to have a special “foundational” place in the architecture of mathematics. But does it really? Can category theory (for example) provide an alternative foundation? And anyway, now we’ve got over our wobbles from about a hundred-and-twenty years ago, when some thought classical mathematics was threatened by paradoxes of the infinite, does mathematics in any sense need universal “foundations”?

Big questions indeed, and the general question about some supposed need for “foundations” is not wanted I wanted to comment on here. But here’s one line of thought that I’ve encountered from mathematicians, not so often mentioned by philosophers, which perhaps underlies some of the continuing nods to the special place of set theory.

Suppose working on Banach spaces, or algebraic topology, or whatever, I conjecture all widgets are wombats. And then the bright young grad students try to prove or disprove Smith’s Conjecture.

Next week, Jane turns up to class claiming to have refuted the conjecture by finding a structure in which there is a widget which isn’t a wombat.

Well, what are the rules of the game here? What kit is Jane allowed to use in her structure building? To give her a best shot at refuting the conjecture, she perhaps ideally wants some kind of all-purpose kit that only minimally constrains what she can build. She wants the mathematical equivalent of a Lego kit where you can pretty much attach anything onto anything, rather than the equivalent of a building kit you can only make toy houses from, or one you can only make toy cars from. (Perhaps Smith’s Conjecture still works fine for, so to speak, houses and cars.)

What the standard sets of the iterative hierarchy seems to provide is just such an all-purpose mathematical Lego kit. We start with some things (or if you like, with nothing at all), and then we are allowed to put them together however you like into new things, and then we are allowed to put what we’ve got together however we like ad libitum, and to keep on going as long as we like. Precisely because the rules for building new sets allow maximising at every step (the idea is at each level we are allowed every possible new combo, and there is no limit to the levels), we really do get an all-purpose structure-building kit. And having such a mathematical Lego kit is just what Jane ideally needs if she is to have untrammelled free rein in coming up with her widget which isn’t a wombat.

Or so the story goes, in outline …

Reasons to be cheerful

Music, Pavel Haas Qt / Leave a Comment / January 5, 2015

New CDs are announced from some musicians whom I admire immensely. For a start, later this month, David Fray is releasing a disk of Schubert’s great G major piano sonata, the four-hand Fantasia D940 and “Lebenssturme” D947 (with Jacques Rouvier). As I’ve said here before, I think Fray’s previous disk of the Moments Musicaux and Impromptus Op.90 is simply mesmerising, so I can’t wait to hear more Schubert from him.

Next, Alina Ibragimova recorded the Bach Violin Concertos with Jonathan Cohen and his Arcangelo ensemble back in August, and the disk will come out this year. Ibragimova’s earlier disks of the Bach sonatas and partitas are just wonderful (as one review put it, “Her playing proclaims authority… In slow movements, [her] understated poise asserts an intensity all her own. The famous D minor Chaconne here becomes an absorbing saga unto itself.”). This new disk too should surely be equally compelling.

Rachel Podger has been playing Vivaldi’s L’Estro Armonico with her Brecon Baroque ensemble in concerts over the last year or so. Hearing them perform a selection of these concerti in King’s College Chapel was one of our concert highlights of 2014. As I said here, “they played with verve and enjoyment, playfulness and charm, and a lot of light and shade. Technically brilliant too. The performances made the case wonderfully well for Rachel Podger’s description of these works, in her lovely talk to the audience after the first concerto, as intriguingly complex and rule-bending.” A recording is due out this year.

And, then there’s the Pavel Haas Quartet — who were from the beginning a really fine quartet, but who have undergone that alchemical transformation into a truly great quartet. They have now recorded the Smetena Quartets. Anyone who has heard the PHQ’s live performances of these quartets will know that the disk is destined to be an instant classic.

(My review of their Schubert recording from the previous year was still the most-viewed blog-post here during 2014. It would be really rather good to think that I’ve encouraged some readers to listen to the PHQ.)

Category Theory 2015

Category theory / 4 Comments / January 4, 2015

My main logical resolution for 2015 is to get to know quite a bit more category theory. Well, it’s fun, I find it aesthetically very appealing, there are some super-smart category theory people here in Cambridge — and there seem to be enough lurking conceptual issues to engage the philosophical bits of my brain, though I want to know (a lot) more category theory before sounding off about them.

I’ve therefore now started a new section of Logic Matters on categories where I’ll be posting various stuff — starting with my slowly-expanding Notes on Category Theory, and eventually some book notes, links to on-line resources on Category Theory, and so on. Enjoy!

(Other New Year’s resolutions? One is to stop wasting time and endangering my blood pressure reading the comments on various Well Known Philosophy Blogs, comments which seem too often to be getting increasingly bonkers, unpleasant and — let’s hope — unrepresentative. Feeling better already …)

Teach Yourself Logic 2015

Study Guide / 3 Comments / January 1, 2015

Back to logic after the festivities. Easing myself in very gently, here’s

A new version of the Teach Yourself Logic Guide.

This is largely a ‘maintenance’ release of the study guide to the literature for upper undergrads/grads wanting to teach themselves some mathematical logic (or to supplement their courses). But it is slightly re-organized, has a couple of added recommendations from 2014 publications, and is actually a few pages shorter.

Last year, the Very Short Teach Yourself Logic Guide single webpage was visited 150K times (with a big spike in visitors due to an honourable mention on Reddit — I suspect most of those visitors, however, were looking for something much more elementary). But even versions of the full TYL Guide were downloaded over 5K times. Since you have to click a link in an explanatory blog-post (like this one) or go to the TYL webpage to get the full version, I guess that most of these downloads are purposeful, indicating that there is indeed a real need for something like the Guide. So although it isn’t my top priority, I’ll keep updating it when the spirit moves me, or when I get some good suggestions/helpful comments. Many thanks to everyone who has provided input over the last few years.