Peter Smith's Blog, page 115

Revisiting an old result of Hintikka’s

The pedagogic habit dies very hard. In recent months I’ve been hanging out quite a bit at math.stackexchange.com, and answering logicky questions when the mood has taken me (which seems to have been quite often …). You can find over 250 (oops!) of my answers here. But a lot of them are really concerned with baby logic and/or clearing up horrible confusions and won’t be of any interest at all to readers of Logic Matters.

However, a few questions on math.stackexchange have raised more interesting issues, and I’m going to start occasionally posting about some of them here. For example, recently someone posed a question which came to this:

Can we do without equality in first order logic, and get something equally expressive using a language with the semantics for quantifiers tweaked so that different variables get assigned different values?

Unbeknownst to the questioner, who conjectured (on the basis of some examples) that the answer is ‘yes’, the proposal here in fact goes back to Wittgenstein’s Tractatus 5.53, where he writes, ‘Identity of the object I express by identity of the sign and not by means of a sign of identity. Difference of the objects by difference of the signs.’ OK: can this proposal, not really developed out by Wittgenstein, be made to work?

The answer is it that it can, as I recalled was shown by Hintikka in 1956 (‘Identity, Variables, and Impredicative Definitions’, Journal of Symbolic Logic). Hintikka distinguishes the usual ‘inclusive’ reading of the variables (i.e. we are allowed to assign the same object to distinct variables) from the ‘exclusive’ reading, and then proves the key theorem (summarized on his p. 235):

 [E]verything expressible in terms of the inclusive quantifiers and identity may also be expressed by means of the weakly exclusive quantifiers without using a special symbol for identity.

So the questioner’s conjecture is right. This result is nice and probably deserves to be better known, but what was new to me — googling around as you then do — is that Hintikka’s result has of late been revisited (in the context of the seemingly never-ending project of interpreting the Tractatus, of course). See for example. Kai F. Wehmeier’s interesting ‘How to Live without Identity – And Why’, Australasian Journal of Philosophy, 2012, downloadable here.

 

The consistency of NF: meeting in Cambridge

Back in October, I posted a slightly mysterious message noting that Thomas Forster was “in the process of assembling funding for a meeting to discuss and broadcast recent developments in NF” here in Cambridge this Easter. Then in November I was able to reveal more, for Randall Holmes had by then announced “I believe that I am in possession of a fairly accurate outline of a proof of the consistency of New Foundations” and it was this which was to be the topic of the Easter gathering. So: how did the meeting go? For various reasons, I wasn’t there, but here’s a report from Thomas Forster:

It went very well.  It didn’t achieve everything I dreamed of, in that I didn’t come away from the meeting understanding the proof — not entirely.  I understand the strategy and I can see why the strategy should work, but I am a long way from understanding the details.

It involves a Ramsey argument like that used by Randall in his ‘tangled types’ paper (which reduces the consistency problem for NF to the task of finding a model of ZFU with some very delicate combinatorial properties).  It then uses an iterated Fraenkel-Mostowski construction to obtain the desired model of ZFU.

My Ph.D. students and I have a weekly meeting in which we press on with “our exagmination round his factification”.  Meanwhile people ask “Do you believe the proof?” and my reply is  “Not yet, but I believe that I will believe it”.  It is a very large proof.  When written out properly it will be 50-60 pages – possibly more — and certainly not 10-15.

Randall is rejigging the presentation in the light of the audience reaction in Cambridge; there is a cunning plan to get one of the theorem-proving communities to embark on a mechanisation  … and the lads and I have a project to write out a version for our own satisfaction.

I expect that by the end of this year I will understand it, and Randall will have sent off a paper to the JSL.

Footnote: Boise State where Randall is has no PhD programme in maths. Students excited by this kind of thing can always come to Cambridge do a Ph.D. on NFiste matters with Thomas!

 

How do you like your proofs? Round 2 [update]

Even if you didn’t do Timothy Gowers’s questionnaire the first time around, you will be fascinated by his explanation of its hidden purpose and will want to do his follow-up poll.

Update: And you will now be fascinated by Gowers’s report on the experiment.

How do you like your proofs? Round 2

Even if you didn’t do Timothy Gowers’s questionnaire the first time around, you will be fascinated by his explanation of its hidden purpose and will want to do his follow-up poll.

TYL, #15. A major update to the Guide

The new April version of the Teach Yourself Logic Guide is now available for downloading. This is re-organized and half as long again as the previous version. After the Introduction there is a short new Chapter 1 on Logical Geography saying more about how the field of logic (and hence the Guide) can be carved up. Chapter 2 on The Basics is much as it was. But Chapter 3, Exploring Further, is much expanded and (at least to a first approximation) a complete draft: there are over a dozen new pages here. The chapter of a rather different character reviewing some of the Big Books now comes at the end, as an Appendix, but is otherwise unchanged in this version.

Most of the new sections of Chapter 3 are not only new to the Guide but haven’t appeared in draft form here on the blog either. So comments, corrections and suggestions will be particularly welcome, either below or by email.

Imogen Cooper plays Schubert, again

I have written here before about Imogen Cooper’s Schubert playing, and in particular about the wonderful series of three double-CDs from live concerts, released some three or more years ago. Well, on Wednesday we had the chance to hear her playing an all-Schubert programme at the Wigmore Hall: a stunning evening.

She began with the 16 German Dances D783, played with even more alternating zest and poignant grace than in those live recordings. What was she saying? That even in these miniatures, there is so much humanity? And then the three Klavierstücke, played as well as I have heard them. The Guardian reviewer wrote “the seriousness with which the Drei Klavierstücke D946 were treated created something as substantial and searching as any sonata”: well, yes, but it isn’t somehow optional, a matter of creative license, to treat these late pieces “seriously” — they are substantial and searching, and Imogen Cooper’s was a true response.

After the interval, the six Moments Musicaux D780, again played with perhaps even more emotional contrasts than on the live recording — the fifth Allegro Vivace really attacked, and the sixth Allegretto magically poised and ending with perfect calm (‘over-leisurely’ playing according to the Guardian — no!). Finally, the great G major Sonata D894. I’m not sure if we were too drained from what went before, or whether Imogen Cooper had herself given too much, but this was the one performance that seemed less wonderfully successful than the recorded version — but it was still astonishing, with quite magical episodes. The audience response was rightly rapturous.

One of the great concerts to remember then.  I’ve been listening again to those earlier performances on the live CDs. If you don’t have them, then you are missing some of the greatest Schubert playing of our age, of any age.

How do you like your proofs?

On his blog, Timothy Gowers has asked for comments on some variant proofs, three proofs apiece in response to five basic problems in the elementary theory of functions, continuity etc. (so the proofs will be accessible by anyone reading this who has just a smidgin of first year maths). How do you rate the alternatives for clarity and style, and why? It’s quite fun to think about, so do join in!

Tennenbaum’s Theorem again

I have posted here a significantly revised version of a handout written a couple of years ago on how to prove Tennenbaum’s Theorem.  This new version should I hope be quite a lot clearer in various ways. Enjoy!

IGT2 … and now available as an ebook

IGT2 is now available from here as an ebook (don’t ask me why it should be a trifle more expensive that the UK paperback … publishers’ pricing policies for e-editions generally is a mystery). Anyway, according to info on the site, with the appropriate app, the Abobe ebook works on iPad and Android tablets, Kindle Fire, Windows, Mac and Linux computers, and any other device that will run Adobe Digital Editions.

I’ll be interested to hear from anyone who buys this version about how well the e-version has been done. I assume it should be pretty closely related to the PDF I sent for printing. I originally sent the publishers a version with internal live-links (for cross-references) so I hope those have been preserved.

Anyway, for all you who desperately want to be able to read IGT2 any time, any place, when you have your iPad, MacBook Air, or some lesser device to hand (and why wouldn’t you?), your dearest wish has now been granted …

TYL, #14. Alternative set theories

I’ve been doing quite a bit of work over the last couple of weeks for a major April update of the Teach Yourself Logic Guide (you can download the current March version here). And I’ve got to a subsection where I could do with advice and comments. I’m working on a new section on more advanced readings on set theory. The subsection on ZFC with all the bells and whistles (large cardinals, forcing, and other excitements) writes itself, and there’s a shorter subsection on the Axiom of Choice. But now I’m drafting a subsection on Alternative Set Theories. Here’s what I have so far written:

From earlier reading you should have picked up the idea that, although ZFC is the canonical modern set theory, there are other theories on the market. I will mention just four here, which I find interesting:

ZFA Here’s one conception of the set universe. We start with some non-sets (maybe zero of them in the case of our set theory). We collect them into sets (as many different ways as we can). Now we collect what we’ve already formed into sets (as many as we can). Keep on going, as far as we can. On this `bottom-up’ picture, the Axiom of Foundation is compelling (any downward chain linked by set-membership will bottom out, and won’t go round in a circle).

Here’s another conception of the set universe. Take a set. It (as it were) points to its members. And those members point to their members. And so on and so forth. On this `top-down’ picture, the Axiom of Foundation is not so compelling. As we follow the pointers, can’t we come back to where we started?

It is well known that in the development of ZFC the Axiom of Foundation does little work. So what about considering a theory of sets which has an Anti-Foundation Axiom, which allows self-membered sets? The very readable classic here is

Peter Aczel, Non-well-founded sets .(CSLI Lecture Notes 1988).
Luca Incurvati, `The graph conception of set’ Journal of Philosophical Logic (published online Dec 2012), illuminatingly explores the motivation for such set theories.

NF Now for a much more substantial departure from ZF. Standard set theory lacks a universal set because, together with other standard assumptions, the idea that there is a set of all sets leads to contradiction. But by tinkering with those other assumptions, there are coherent theories with universal sets. For very readable presentations concentrating on Quine’s NF (‘New Foundations’), and explaining motivations as well as technical details, see

T. F. Forster, Set Theory with a Universal Set Oxford Logic Guides 31 (Clarendon Press, 2nd edn. 1995).
M. Randall Holmes, Elementary Set Theory with a Universal Set (Cahiers du Centre de Logique No. 10, Louvain, 1998). This can now be freely downloaded from the author’s website.

IST Leibniz and Newton invented infinitesimal calculus in the 1660s: a century and a half later we learnt how to rigorize the calculus without invoking infinitely small quantities. Still, the idea of infinitesimals has a strong intuitive appeal, and in the 1960s, Abraham Robinson created a theory of hyperreal numbers, based on ultrafilters: this yields a rigorous formal treatment of infinitesimal calculus. Later, a simpler and arguably more natural approach, based on so-called Internal Set Theory, was invented by Edward Nelson. As Wikipedia puts it, ”IST is an extension of Zermelo-Fraenkel set theory in that alongside the basic binary membership relation, it introduces a new unary predicate standard which can be applied to elements of the mathematical universe together with some axioms for reasoning with this new predicate.” Starting in this way we can recover features of Robinson’s theory in a simpler framework.

Edward Nelson, ‘Internal set theory: a new approach to nonstandard analysis’ Bulletin of The American Mathematical Society 83 (1977), pp. 1165–1198. Now freely available from projecteuclid.org.
Nader Vakin, Real Analysis through Modern Infinitesimals (CUP, 2011). A monograph developing Nelson’s ideas whose early chapters are quite approachable and may well appeal to some.

ETCS  Famously, Zermelo constructed his theory of sets by gathering together some principles of set-theoretic reasoning that seemed actually to be used by working mathematicians (engaged in e.g. the rigorization of analysis or the development of point set topology), hoping to a theory strong enough for mathematical use while weak enough to avoid paradox. But does he overshoot? Could we manage with less?

Tom Leinster, ‘Rethinking set theory‘,  gives an advertising pitch for the merits of Lawvere’s Elementary Theory of the Category of Sets, and …
E. William Lawvere and Robert Rosebrugh, Sets for Mathematicians (CUP 2003) gives a very accessible presentation which doesn’t require that you have already done any category theory.

But perhaps to fully appreciate what’s going on, you will have to go on to dabble in category (see the next section of the Guide!).

More?  Finally, for a brisk (and somewhat tough) overview of many other alternative set theories, including e.g. Mac Lane set theory, see

M. Randall Holmes, ‘Alternative axiomatic set theories‘, Stanford Encyclopedia of Philosophy.

So what readings at a comparable level should I also have mentioned? What other deviant set theories should I have mentioned? Comments are open …!