Monday, September 24, 2007

As I was saying, of making many books there is indeed no end!

This time a logic recommendation. I got in the post today a copy of the recently published paperback version of José Ferreirós, Labyrinth of Thought: A History of Set Theory and its Role in Modern Mathematics. History of mathematics is not at all my thing, but I got it as it seems very well regarded, and I wanted to have more sense of how we got to where we are with set theory. Having dipped into it over a couple of leisurely coffees in a cafe this afternoon, it seems very approachably written and intriguing. It is still jolly expensive; but at least make sure that your library has a copy.

Of making many books there is no end ...

... and much study is a weariness of the flesh. Still, some study is a lot less wearisome, and some books a heck of a lot more fun, than the alternatives. So let me recommend Kate Belsey's Why Shakespeare? as a good read, and really illuminating. I think she's wrong about Bridget Jones's big knickers, but then disagreeing is fun and illuminating too. However, you'll have to see how Bridget gets into the story for yourself.

Tuesday, September 18, 2007

Atheists, quaffing wine

I mentioned two edited collections of articles in recent posts, Louise M. Antony's Philosophers without Gods and Barry Smith's Questions of Taste. Having now read them both, let me just very warmly recommend the first, but suggest that you might perhaps buy a moderately decent bottle of Rosso di Montalcino instead of forking out for the second ... (in part because you'll find a summary of some of the papers for free here).

The atheism volume is a serious affair, put together -- it seems to me -- with considerable tact and finesse, the papers (nearly all worth reading) arranged to draw in but then get under the guard of the sort of intelligent religious reader who might simply put up the shutters against (say) Dawkins's more direct attack. Let's hope that there is a cheap paperback in every student bookshop soon.

As to 'the philosophy of wine', there is indeed a nice piece by Barry himself but also some mildly daft provocations (Roger Scruton). Let me add a provocation of my own. A certain kind of English obsession with a somehow absolute category of "fine wine" seems to me an odd distortion -- a thought prompted more than once in the past at college feasts, where indeed wonderful Bordeaux was served with frankly awful bland food, so the wine had to stand by itself and provide all the interest, making complexity a great virtue, while the food was little more than mere padding. I suspect an Italian, say, would find that imbalance, making the wine stand on its own, most peculiar -- and think of excellence in wine as something much more relative to an occasion and a kind of meal and even the company.

Remembrance of photos past, #2


Monica Vitti
Putting a tracker here has certainly been very good for deflating any fantasies about the number of people who might read this blog or about why they arrive here. You dream that are oodles of logic enthusiasts out in the world. But ah no, people arrive having googled for "Tesco discrimination", "cheap universities", "donkey philosophy", "JK Rowling eat your heart out" ... and now "photos of Monica Vitti". Heaven knows what you all make of it!

But so as not to disappoint at least the last contingent of surfers, here is Vitti again, with Alain Delon in L'Eclisse. An earlier time-slice of me used to think they were the epitome of cool; and in fact, I rather think I still do ...

Friday, September 14, 2007

ACA0, #3: Finite axiomatizability

Aatu (in his comment on a previous post) raises two issues, one about the finite axiomatiability of ACA0, and one about the relation between ACA0 and ACA. I think there are some conceptually slightly puzzling issues about the second issue, and I'll come back to that when I feel I've got them straighter. As to finite axiomatiability, here's one line of proof (essentially, Simpson's, I hope!).

ACA0 is equivalent to the theory we could dub ΣCA, which is what you get by restricting the comprehension principle to Σ1 wffs (with second-order parameters), by an induction proof relying on the easy observation that Σn comprehension implies Σ(n+1) comprehension. So it is enough to show that ΣCA is finitely axiomatizable.

Now recall that the extension of a Σ1 wff φ(x) (without second-order parameters, for the moment) has as its extension a recursively enumerable set that can be enumerated by some Turing machine or other (the e-th machine in a certain enumeration). And recall too the possibility of universal Turing machines: there is, in a particular, a universal machine which takes as input the index e and enumerates the set enumerated by the e-th machine. That means that there is a 'universal' Σ1 wff U(w, x) such that for any Σ1 wff φ(x) there is some e such that it is provable in first-order arithmetic that φ(x) ↔ U(e, x), where 'e' is the numeral for e.

We can now generalize that line of thought, to the case where φ(x) has second-order parameters, and show similarly that there is a ‘universal’ Σ1 wff U(w, x, Y) such that for any Σ1 wff φ(x, Y) there is some e such that it is provable in first-order arithmetic that φ(x, Y) ↔ U(e, x, Y). So a comprehension schema that allows all instances for Σ1 wffs φ(x, X) can be replaced by a single comprehension axiom

∀w∃X∀x(x ∈ X ↔ U(w, x, Y)).

Adding a few bells and whistles, it quickly follows that ΣCA can be finitely axiomatized.

Tuesday, September 11, 2007

Remembrance of photos past, #1


Monica Vitti
Idling through the net -- as one does -- I just chanced on this photo of Monica Vitti. A blast from the past indeed, as I had a copy of that very shot on my wall as a student for a couple of years.

I fairly recently saw L'Avventura again after a gap of many, many years. I'm not sure why, but I wasn't really expecting the film to stand up after four decades, and predicted that it would seem too mannered and pretentious. But I was bowled over anew: bleak but stunning still. And Monica Vitti so beautiful and touching ...

While I couldn't possibly condone downloading it, I notice that -- in the absence of a DVD for the UK -- a torrent of L'Avventura is indexed at mininova.org. [Revised: The photo now links to a somewhat larger version. For a few more photos, search this blog for "Monica Vitti"! ]

Monday, September 10, 2007

Bourbaki and friends

I'm a great fan of Guardian Review on Saturdays, which has usually decent and sometimes terrific book reviews (and is a lot more fun than the TLS). But they did get it badly wrong this week, recommending the awful The Artist and the Mathematician by Amir Aczel, which is a badly written pot-boiler about the Bourbaki group. Which is a great pity when there is a very good and readable book which is actually pretty illuminating, Maurice Mashaal's Bourbaki: A Secret Society of Mathematicians.

ACA0, #2: Are the coding tricks horribly artificial?

Even before we do the fancy stuff to define the 'reals' in ACA0, we twice over have to use pair-codings (i.e. use natural numbers as codes for pairs of naturals) to construct first the integers and then a rational field. Is that bad news? Does that make even those initial constructions unacceptably artificial?

Well, on reflection, it is not easy to see how anyone who is happy with more standard set-theoretic constructions of number systems can really press this complaint. For they are equally committed to essentially parallel artificial coding tricks.

Recall, for a start, the way ordered pairs are usually handled in a set theoretic framework. Sets with the same members are identical -- that is arguably analytic of the very notion of a set. But two ordered pairs with the same members in the opposite order are not identical, so ordered pairs aren't sets, and that is analytic of the very notion of an ordered pair. So it is plain that we shouldn't, strictly speaking, identify an ordered pair with its Kuratowski reduction, for that set is never ordered and indeed is often not a pair either. But -- of course! -- the Kuratowski reduction has the property of real ordered pairs that that matters. So we've all learnt to use Kuratowski unordered sets as proxies for ordered sets. And this trick works so smoothly that we soon fall into the habit of saying that ordered pairs are sets of sets, keeping more cautious talk of proxies (or representations, or codes) for when we are on our Sunday best behaviour.

Likewise, we standardly learn to say that rationals, for example, are equivalence classes of ordered pairs of equivalence classes of ordered pairs of natural numbers, keeping proxy talk for Sundays. But it is no more and no less true that rationals are sets of sets of sets of sets of sets of sets of numbers than that they are numbers coding for pairs of pair-codes. Either both claims should be rejected; or both claims should be endorsed, each relative to its proprietary modeling scheme for representing the rationals (and then we will no doubt be tempted to go structuralist about 'the rationals themselves' -- it's in some sense what is shared by the various schemes that matters). What wouldn't seem defensible is any suggestion that the standard set-theoretic coding of the rationals gets it fundamentally right (whatever 'it' precisely might be) while the arithmetic coding available in Peano Arithmetic and hence ACA0 gets it wrong.

'Still,' it might be protested, 'surely the familiar set-based construction is compelling in a way that using number-codes isn't. Surely, for example, rationals are ratios of pairs of numbers, and it is much more natural to have the relevant pairs of numbers there, in some sense in the construction, rather than just being pointed to by some essentially arbitrary coding device.'

However, this line of thought is definitely resistable. For a start, thinking of elements as being present in the sets of which they are members is highly misleading. Some might be tempted, perhaps, to think of the numbers 1, 2 as being 'in' the set {1,2} in something like the sense in which the numerals '1', '2' do indeed feature in the name of the set '{1,2}' -- as if, metaphysically, all we have to do is remove from around the members the lasso which pulls them into a set, to be left with the naked members themselves. But that is a quite hopeless picture, confusing parthood with set-membership. Much better to think of sets in more category-theoretical terms, as being entities that come equipped with a bunch of special 'arrows' out, with the arrows mapping the set to its several members. And what makes the entities in question just sets is that this is all there is to be said about them -- they are abstract entities whose only feature is to have those 'arrows' out, their only role is to thereby enable us to treat many objects together as one.

Looked at that way, the difference between a set-theoretic construction and a coding-by-numbers construction comes down to this. In the first case, we are introducing new entities whose sole role is to enable us to point to two or more numbers taken together; while in the second case, we are making use of what we already have, i.e. numbers, to enable us to point to pairs of numbers taken together. But now remember again that, in the standard set-theoretic construction of ordered pairs, we do put a considerable premium on using what we have around already, namely unordered sets, rather than introducing ordered pairs as new primitives governed by their own laws (as Russell and Whitehead did). Analogously, when constructing the integers and rationals, why shouldn't we put a premium on using what we already have around while we can, and so use numbers to point to pairs of numbers rather than introduce new entities to do the job?

There more to be said about set-theoretic constructions. But at least initially, we can insist that, while the set-construction of the integers and the rationals may win over the number-code construction in ACA0 on grounds of sheer familiarity, there is no very obvious sense in which it is intrinsically preferable.

Tuesday, September 04, 2007

Another book, another blog

I need some light relief from both logic and atheism. So I've just ordered Barry Smith's recent edited book Questions of Taste: The Philosophy of Wine, which promises to be both illuminating and fun. You can hear Barry talking on the topic here.

I've also just discovered that Tim Crane, another contributor to that book, has been been blogging for a while here (and very classy it looks too ...). I'm not sure I'll entirely thank him for pointing to the Arts & Letters Daily page which I'd not discovered before -- a page of links to a host of worryingly distracting stuff!

Saturday, September 01, 2007

ACA0, #1: What are those parameters doing?

ACA0 is the two-sorted arithmetic you get when you restrict the φ(x) we can substitute into the Comprehension Scheme to those which lack bound set variables. Note, however, that banning bound set variables in φ(x) still allows free set variables/parameters to occur. But why should we want to allow them? Unless I’ve missed a discussion, this obvious question seems usually to be passed over without very much comment. So let me try to plug the gap. (Not that it’s hard!)

Certainly, allowing free variables/parameters in the wffs φ(x) substituted into the Comprehension Scheme makes things technically sweet. But, as I've insisted here before, formal attractiveness is one thing, a decent conceptual motivation is something else. So -- given a choice between either avoiding impredicativity by banning bound set variables in φ(x) or going the extra step and banning all set variables, bound or free -- what principled reason is there for choosing between the resulting theories?

Well, let T be the theory which you get by banning all set variables from instances of φ(x); in other words, T requires instances of φ(x) to be open wffs of the language L1 of first-order arithmetic. Now, endorsing theory T requires us to hold that the open sentences of the L1 do indeed express cogent conditions which determine sets as their extensions -- 'arithmetical' sets, as we'll call them (otherwise, of course, we shouldn't be endorsing even the restricted comprehension principle saying that there are such sets). Then, if X is such an arithmetical set, there is -- according to us -- a fact of the matter whether n X. So an open sentence of the language of first-order arithmetic augmented with a way of expressing that some number is in X also expresses a fully determinate condition. But then what reason can we possibly have for supposing that conditions expressed in the language of first-order arithmetic do determine sets as their extensions, while equally determinate conditions expressed in the augmented language which allows parameters acting as temporary names for arithmetic sets don’t have extensions? After all, if we arithmetically define a condition in terms of membership of some arithmetic set, then it will be equivalent to some purely arithmetical condition – so of course it has an extension!

Hence, if we are going to seriously countenance arithmetical sets at all and start quantifying over them, as in theory T, it seems we should also countenance sets arithmetically defined in terms of particular arithmetical sets. Which formally comes to allowing free set-variables/parameters in our comprehension principle after all, giving us ACA0.

‘Hold on! You just said that if we accept arithmetical sets, we should equally accept sets defined with parameters acting as temporary names for arithmetic sets. Fair enough. But the specification of ACA0 allows the wffs substituted into the comprehension schema to have parameters – free set-variables – without restriction. So doesn’t that overshoot?’ No. It is in fact not hard to show that the smallest model of ACA0 where the domain of the first sort of quantifier is the natural numbers has just the arithmetical sets as the domain of the second sort of quantifier (see Simpson, SOSAS, p. 317, Corollary VIII.1.11). So accepting ACA0 indeed commits us to no more than the arithmetical sets that we are committed to by T, just as we wanted.

As I said, this point about ACA0’s allowing set parameters in the comprehension principle usually seems to be passed over without real comment. Tim Storer, however, has reminded me that there is a relevant discussion by Azriel Levy, writing about the relation of VNB to ZF (see Fraenkel/Bar-Hillel/Levy, Foundations of Set Theory, 1973, ch. 3, §7, slightly reworked in Levy 1976). For the relation between ZF and VNB – also known as NBG – is in the key respect close to that between first-order PA and ACA0. In each case a single-sorted first-order theory is extended by adding a second sort of variable, running over sets/classes, whose use is governed by a predicative comprehension principle where substitutions for φ(x) lack quantifiers of the second sort. Levy’s central argument for allowing class parameters when substituting into Comp in the case of VNB turns out to be parallel to the argument above for allowing set parameters into φ(x) in the case of ACA0.

Or at least, I think that’s how things go ...